Evolution of the chessmover program

In November of 1992 Lionel Tun asked the following rhetorical question in the talk.origins newsgroup:

Lets say there is a computer program which `knows’ the legal moves of chess – lets call it ChessMover. ChessMover plays very poor chess because its moves are made at random. But it does play very fast. ChessMover is small, compact and extremely efficient. But it plays bad chess because it has not been designed with any chess playing algorithms at all.

Would it be possible to subject ChessMover to random mutations, so that eventually you evolve ChessPlayer, a chess program which plays very well, say at master level?

However the genetic program for life doesn’t work the same way as a conventional Von Neumann machine. Here is how one might go about such a program. The board position at any point and the possible moves are available as data — they correspond to the external environment of a cell. Chess mover has several built-in pieces. These are:

(a) A “program” which is simply a string of bits. This is fixed for a given instance of the program, but is alterable during reproduction (by mutation) or genetic exchange (prokaryotic sex).

(b) A pattern matcher which matches a pattern against the data, i.e. against the board position and against the legal moves. This is analogous to enzymes. Each pattern has a value associated with it which is released if the pattern matches the data.

(c) A transcriber which, given a position on the “program” bit string, produces a pattern, following a fixed mechanical rule (the genetic code).

(d) A responder which, given a value, associates with it a bit position on the string.

(e) A move selector. If a pattern matches a move that move is selected. If, after a time out period passes without a move being selected, a random legal move is selected.

The sequence of events is as follows: Several million instances of the program play each other. All programs that lose are eliminated. Programs that draw [we will need to count reaching a maximun number of moves as a draw] may have sex, i.e. drawing instances exchange sections of their programs at random. Half of these instances die. The surviving instances reproduce, i.e. new copies are produced. The “programs” of the new instances may mutate, i.e. the bit strings of their “programs” can either alter at a specific bit or a substring may be replicated or deleted.

In answer to Lionel’s question — a chess program written along these lines can be expected to reach Master level.