Least computationally expensive way to implement chess AI?

[Richard Masters]

Least computationally expensive way to implement chess AI?

I'm thinking about using using a mixture of genetic algorithms and neural networks, but a simple framework does not come to mind. I'd also like to attempt the same in creating a powerful computer assisted translation application that learns translation into foreign languages.

I'm not really looking for specific implementations, but perhaps other tools besides GA and NN that have similar or adaptable applications.

Any thoughts?

 

[rcronk]

From the title of your thread, you're asking for the least computationally expensive way to implement a chess AI. You may want to look into ChessGenius, which has been optimized to be a very strong chess engine that can run (and be strong) on wimpy mobile phone CPU's. I think it uses more traditional chess algorithms than what you're thinking about. Those are proven algorithms that have been optimized in many ways over the years.

Learning to translate languages via neural networks is interesting, but still seems difficult. You could language versions of multiple documents into it, but it would still need A LOT of input to produce good output since language translation has to be idiomatic rather than literal - which means that you have cultural differences between languages that must be translated and could be translated many ways based on which cultural version of Spanish, for example, you're using, etc. The neural network would have to learn these cultural idioms above and beyond the text being input.

What are you real requirements? Are you really just looking for practical neural network applications? Why?

Perhaps to get more feedback you could describe more specifically why you are looking for "least computationally expensive" means combined with neural networks, etc. I'm not sure a neural network would be computationally inexpensive in these examples.

 

[nimzov]

In chess, neural-networks can be used for very low-level tasks. like optimizing the parameters of the evaluation function used by the chess program. Subsequently a fine-tuning of this first optimization could be refined using a genetic algorithm. But these tasks accomplished by NN and GA are very far from "learning" anything related to chess.

I doubt very much that a NN could "learn" any general principle of the game given as many examples (games or positions) as we like.

Here is a toy problem that in my opinion cannot even be solved by NN at this time:

Contruct a NN that can determine by classification if a chess positions is a mate or not.

Class 1) In the position Black is checkmate.
Class 2) In the position Black is not checkmate.

Give as many example as you wish to the neural network and it doubt it could learn such a simple task.

And this is very far-off from learning the rules or strategy of the game.

nimzo

 

[Richard Masters]

From the title of your thread, you're asking for the least computationally expensive way to implement a chess AI. You may want to look into ChessGenius, which has been optimized to be a very strong chess engine that can run (and be strong) on wimpy mobile phone CPU's. I think it uses more traditional chess algorithms than what you're thinking about. Those are proven algorithms that have been optimized in many ways over the years.

Learning to translate languages via neural networks is interesting, but still seems difficult. You could language versions of multiple documents into it, but it would still need A LOT of input to produce good output since language translation has to be idiomatic rather than literal - which means that you have cultural differences between languages that must be translated and could be translated many ways based on which cultural version of Spanish, for example, you're using, etc. The neural network would have to learn these cultural idioms above and beyond the text being input.

What are you real requirements? Are you really just looking for practical neural network applications? Why?

Perhaps to get more feedback you could describe more specifically why you are looking for "least computationally expensive" means combined with neural networks, etc. I'm not sure a neural network would be computationally inexpensive in these examples.

Mostly, I'm looking for new tools to implement Computer Assisted Translation. I could easily create a Translation Memory which would do everything I need. However, since I will be creating a translation memory anyway, why not leverage the application such that it suggests more than just a corresponding database matches? Why not teach it to derive rules from my segment database so that it can suggest novel translations (that is, not currently saved to the segment database).

What I am thinking of implementing is a pure Translation Memory, and then add an optional ability to tag words and segments with parts of speech and subject matter tags. This would allow the application to cross-reference and align words, even with a limited Translation Memory.

By adding one case-based rule per translation (not much work, really) the application could create new suggestions both in on-the-fly translations, and could also suggest new word tags subject to the user's approval, based on refactoring.

Once the application had enough tagged words, it could begin to suggest new case-based rules, again, subject to the user's approval.

These inferences would mostly come from routine translations.

A neural network isn't needed to do any of this. But any method that reduces the translator's work and leverages existing information would be welcome.

Any method that can generalize and extract information from the Translation Memory efficiently, so as to occasionally emerge with novel and correct translations, would be ideal.

Perhaps a good use of ANN is in letting the application learn from my selection of computer-generated suggestions so that it can either make better suggestions, or select appropriate generations on its own without user input.

The chess question is simply somewhat analogous in that some methods may overlap. I suppose the goal in both is to leverage limited information maximally, while maintaining growth (in quality and coverage) with limited user input.

 

[Richard Masters]

In chess, neural-networks can be used for very low-level tasks. like optimizing the parameters of the evaluation function used by the chess program. Subsequently a fine-tuning of this first optimization could be refined using a genetic algorithm. But these tasks accomplished by NN and GA are very far from "learning" anything related to chess.

I doubt very much that a NN could "learn" any general principle of the game given as many examples (games or positions) as we like.

Here is a toy problem that in my opinion cannot even be solved by NN at this time:

Contruct a NN that can determine by classification if a chess positions is a mate or not.

Class 1) In the position Black is checkmate.
Class 2) In the position Black is not checkmate.

Give as many example as you wish to the neural network and it doubt it could learn such a simple task.

And this is very far-off from learning the rules or strategy of the game.

nimzo

No, it would seem too complicated without providing a framework of basic rules. But perhaps with such a framework, and given a way to score the current situation, it might derive simple strategies, given the right scope. I'm only speculating here, but with those simple strategies "locked" or generalized into rules or sequences, it could repeat the process at a higher level of complexity.

I guess my real question is how to programmatically generate rules from examples (limited in number, or otherwise) so as to involve the user as little as possible.

 

[rcronk]

It's true that people don't generally learn chess by looking at random snapshots of chess board setups with a score of how good each setup is. A person explains a set of rules about each piece and then they move to simple strategies and one- or two-move simple combinations, book openings, then larger strategies, end-game scenarios, etc. So I'm unfamiliar with how to teach a NN "rules", which I think is what you're asking.

If the real question deals with language translation - have you ever done human-based language translation before? I've done some and have spoken to a professor whose specialty is translation and it's a pretty deep field. Machine translation is fine to get some bulk stuff done, but it seems that there always has to be a human involved. When I became fluent in a second language, I found out that I wasn't translating english to spanish, for example, I was converting thoughts, feelings, and concepts into either English or Spanish and so the mapping between enlish and spanish wasn't direct. The way humans translate is to convert english into the original thought, feeling, or concept, and then translate it back out into spanish, for example. Just some ramblings that might be useful as you think about this - or maybe not.

 

[nimzov]

An interesting discussion on the subject of chess and AI.

"The History of Computer Chess: An AI Perspective."

Google Video This video is not hosted by the ISF, the ISF can not be held responsible for the suitability or legality of this material. By clicking the link below you agree to view content from an external website.

I AGREE

2h05 (but first 10-15 minutes are a bit boring.)

nimzo

 

[Grimoire]

<pendant>

The least computationally expensive way would be rand(). Not very effective, but certainly wouldn't cost much in the way of CPU cycles!

</pendant>

 

[Richard Masters]

<pendant>

The least computationally expensive way would be rand(). Not very effective, but certainly wouldn't cost much in the way of CPU cycles!

</pendant>

Not bad.

 

[Gord_in_Toronto]

<pendant>

The least computationally expensive way would be rand(). Not very effective, but certainly wouldn't cost much in the way of CPU cycles!

</pendant>

Ha! I can beat that. Hide a man inside the box. Zero cycles.

 

[rcronk]

Ha! I can beat that. Hide a man inside the box. Zero cycles.

Yeah, but people will start asking questions when you periodically shove slices of pizza and pour Mountain Dew through the back of the box. "Uh, it's a new EnergyStar green computer..."

P.S. Thanks for the video above, I have looked into writing my own chess engine and it was reassuring to hear some ideas similar to my own from the "pros" on that video.

 

[jeremyp]

I doubt very much that a NN could "learn" any general principle of the game given as many examples (games or positions) as we like.

Here is a toy problem that in my opinion cannot even be solved by NN at this time:

Contruct a NN that can determine by classification if a chess positions is a mate or not.

Class 1) In the position Black is checkmate.
Class 2) In the position Black is not checkmate.

Give as many example as you wish to the neural network and it doubt it could learn such a simple task.

I know at least one neural network that can solve your toy problem. It's the one inside my skull.

Unfortunately for the OP, neural networks of that order of size are not computationally inexpensive. Neither are genetic algorithms, for that matter.

 

[Jekyll]

In chess, neural-networks can be used for very low-level tasks. like optimizing the parameters of the evaluation function used by the chess program. Subsequently a fine-tuning of this first optimization could be refined using a genetic algorithm. But these tasks accomplished by NN and GA are very far from "learning" anything related to chess.

I doubt very much that a NN could "learn" any general principle of the game given as many examples (games or positions) as we like.

Here is a toy problem that in my opinion cannot even be solved by NN at this time:

Contruct a NN that can determine by classification if a chess positions is a mate or not.

Class 1) In the position Black is checkmate.
Class 2) In the position Black is not checkmate.

Give as many example as you wish to the neural network and it doubt it could learn such a simple task.

And this is very far-off from learning the rules or strategy of the game.

nimzo

The trick to solving this problem is to just choose your feature vector wisely. If you had a feature generator that marked lines of attack, or where your pieces could be moved too a neural net should be able to solve this problem easily.

Despite this, they still suck and I'd also try to use something else.

This might be more up your street.
http://dbacl.sourceforge.net/spam_chess-1.html They're using a text classifier (spam filter) to play chess.