The Distributed Chess Project

Web Hosting by Netfirms | Free Domain Names by Netfirms

THE DISTRIBUTED CHESS PROJECT

Creating Chess-Playing Artificial Neural Networks with Distributed Evolutionary Algorithms

Content and Goals of the Distributed Chess Project

Artificial Neural Nets Play Chess ?
Artificial neural nets derive their name from the fact that they are made up by a number of highly interconnected, rather simple nonlinear information processing elements, the artificial neurons, which are supposed to work in a simplified fashion similarly to their natural counterparts in the brain. In the context of this project, an artificial neural net is just a black box that produces a legal chess move from a given chess position. That is to say, the neural net takes a chess position as input and somehow comes up with a legal move as output. Mathematically speaking, it performs a nonlinear map on an input pattern which represents the input position. In other words, such a black box can play chess by the rules. Nothing is said about the quality of play at this point, though.

The computational algorithm by wich new moves are generated from given positions is determined by the internal structure and a number of numerical parameters. Structure and parameters uniquely specify a neural net. They must be appropriately encoded such that they can be used to build a neural net. Let's call this stuff the 'genetic information' of a neural net. Somebody who knows the genetic information can construct the one and only neural net that is specified by it. At this point it is important to note, that the chess playing neural nets will not use any of the methods and functions that are employed by conventional chess programs like Fritz or Shredder, such as positon evaluations, negamax-algorithms, alpha-beta-search, and so on. The approach taken here can perhaps be described best as 'playing chess by pattern recognition'. According to some results recently published in 'Nature' (Grandmasters remember to win), this is the way grandmasters prefer to play.

Evolving Chess Playing Ability in Neural Nets
Every project participant will in some random fashion generate an initial population consisting of a certain number of individual neural nets, who will then try to solve a number of chess problems with known best continuations. After all problems have been addressed by all individuals, the old population will be used to generate a new population, which will get the next shot at the chess problems. This process will continue for many, many generations.

And this is the trick:
The creation of the new population, i.e. the reproduction of the population, will be performed in such a way that the likelihood of an individual to pass on its genetic information to the next generation is proportional to its performance in finding the correct moves for the given problems.

Disregarding what John Crawford said about making assumptions in 'The Silence of the Lambs', it is assumed here that the chess playing ability of a neural net can be in some form related deterministically to its structure and parameters, and therefore to its genetic information. The exact nature of this relation, if it exists, doesn't matter, though. Proving the assumption by finding suitable structures and parameter sets is what this project is all about.
At some point this process of 'problem solving - reproduction - problem solving - reproduction' is going to be terminated. The best neural nets at this time will be transmitted from the Chess Saver-client to the server for further consideration. Then, data specifying a new initial population will be transferred from the server to the Chess Saver-client and the process will repeat. Hopefully, this procedure will culminate in neural nets which are objectively strong chess players. In this respect, the performance on problems that are not related to the problems used for the training is very important, since it shows whether the net has learned some general underlying pattern and not just a particular common feature contained in the training problems. Therefore, the thing that is really of interest, is how well the best trained neural nets perform on independent sets of test problems.

The described process sort of mimicks the process of evolution by selection and reproduction as it occurs in nature. Unlike evolution in nature, here an explicit fitness function is utilized, however. Nevertheless, only the adaption of an individual to the environment matters. In our case the environment is the chess board and life there is governed by the the rules of chess. Those individuals, who consistently outperform their peers in the game of chess will get better chances than the weaker ones to pass on their genetic information to following generations.

Since the evolutionary algorithm outlined here is extremely time consuming and there are very many free parameters specifying the algorithm and the structure of the neural nets, a distributed computing approach is employed.

The Future
Right now, the Chess Saver distributed computing architecture is purely client-server oriented. For the next versions I plan to implement some peer-to-peer-functionality as well, such that project participants can manually exchange populations of neural nets. Moreover, depending on the results in the field of problem solving, the neural nets will be playing matches and tournaments against each other. Then it can be seen whether something like chess playing ability actually can emerge from nothing. This would be a really neat result in the field of artificial intelligence. Validation of the best emerging neural nets could be achieved by letting them play against conventional chess programs or humans.

Another important side effect of tournament based evolution is the fact that an explicit fitness function will not be needed anymore. This brings the whole process a bit closer to natural evolution.

The goals are ambitious but in my opinion feasible, because something similar has been done already with good success with the simpler game of checkers (Chellapilla, K. and Fogel, D. B.: Evolving an Expert Checkers Playing Program Without Using Human Expertise, IEEE Transactions on Evolutionary Computation, Vol. 5, No. 4, 4. August 2001, pp. 422-428.) You can read the paper at http://www.ai.univie.ac.at/~juffi/lig/lig-bib.html.