Previous   Next

The Chessiverse: Evolution of Chess Programs

Survival of the fittest

In the Chessiverse computer programs compete for survival, based on how well they play chess. They 'live' in an environment that generates chess positions, which the programs then have to play. Apart from knowing how to generate positions, the environment knows awfully little about chess. If the program that has the move comes up with an invalid move, it loses and his opponent deserves a survival point. If a program delivers a valid move that captures the opponents King, it wins. Otherwise the move is performed, and the opponent has to start thinking about its own move. This continues until one of the programs forfeits the game, through an illegal move, or until a King is captured. After 30 moves without any capture or Pawn move the game is declared a draw.

This goes on for a number of rounds (one 'season'), after which a ranking is made. Only the programs at the top of this ranking survive. All other programs 'die', and are erased. They are replaced by 'offspring' from the survivors: copies from randomly chosen survivors in which a number of instructions are randomly changed ('mutated'), or a random block of code is inserted or deleted. Finally recombinants of two survivors are formed, where a piece of code from oneoverwrites the corresponding piece of code (i.e. at the same address) of the other ('crossing over').

Obviously, programs that do not properly know the rules are at a disadvantage when collecting the survival points. Initially all programs are just random sequences of instructions, and will forfeit the game as soon as it is their turn to move. Programs that know how to make a valid move easily score a point against such programs, they either gat it completely for free (because the other had to move and did not know how), or the do a valid move after which the move goes to the opponent after all. Programs that implement the rules thus outcompete those that don't, so the latter become extinct. This makes life much more difficult for the survivors, though: they now only play against opponents that also know how to generate valid moves. The only way to win when your opponent does not forfeit the game is to capture his King. So the programs are under selective pressure to go for the opponents King.

The nice thing about this simulated evolution is that it is almost completely open ended: there is no known way to perform the task perfectly, it can always be done better. The environment can offer no clues as to how the task should be performed, it only enforces the rules of chess, and knows absolutely nothing about strategy. But the programs do not play against the environment, they play against each other. They will have to develop strategies spontaneously.

This part of the web site is still under construction, more pages will be added later.

The Chessivers project currently has two utilities. One to simulate the evolution, which periodically writes all survivors to a file 'chessi.sav'. By calling it with the argument '-r' it restarts from an existing 'chessi.sav', to resume a run that was somehow interrupted. The second utility is an emulator that reads a program organism from this file, and runs it on randomly generated input positions, meanwhile displaying the machine state and (disassembled) executed instructions, as well as the machine output. Sources of these two utilities (compilabe with gcc under cygwin) can be found here:



Previous   Next