chess GA experiments

In February 1996, a couple of programmers in the rec.games.chess.computer newsgroup briefly discussed their informal experiments in optimizing chess evaluation functions using a genetic algorithm.

Learning a high quality evaluator is not easy. If the only fitness information is game results, then you need a lot of games to distinguish similar evaluators. That may be why John Stanback’s evaluator population apparently didn’t fully converge.

From:         John Stanback <jhs@verinet.com>
Organization: Hewlett-Packard Company
Date:         23 Feb 1996 18:40:33 GMT

A couple years ago I tried using a genetic algorithm to optimize the coefficients of the evaluation function components in my chess program Zarkov. I started with a population of 100 "players" each which had a set of coefficients randomly generated within a very wide range. For example, the materialvalue for all pieces was a random number between 100 and 1200. Pawns were fixed at 100.

Games were played between randomly selected players. Players were replaced when they had lost more games they they won and they had lost at least 2 games. The replacement algorithm randomly selected 2 parents, each with an even or winning record. For each of the 30 evaluation function parameters, the child program randomly acquired the value of one of the parents. About 1% of the time this value was randomly changed by a small amount (mutation).

After 2000-3000 games at a time control of 2 seconds per move the piece values had nearly converged to reasonable values; knights and bishops were usually a bit over 300 points, rooks a bit over 500, and queens around 1000 points. Other less important parameters had more or less converged, but not to an "ideal" values. A control program with hand-tuned parameters still won against the best of the programs derived using this algorithm, but only by a margin of 55-60%.

I haven't studied genetic algorithms so I'm sure there are better methods for selection and replacement. This experiment does seem to show that there might be some merit in using genetic algorithms for tuning evaluation function parameters in chess programs.

John Stanback

From:         Dan Thies
Organization: Glorious People's Cyber Factory
Date:         Sat, 24 Feb 1996 09:02:42 -0800

John:

I let an experiment run for about 6 months last year, which used a very similar fitness measure. I evolved neural networks to deliver an evaluation function for chess positions. For the first two months, it ran with fixed material values (lifted straight out of gnuchess - thanks). After that, I let the material values float as well. The networks did improve in strength over time, but after 6 months were still weaker (and slower!) than the hand-coded evaluation function I had been using. My conclusion was that I had better things to do with my CPU. :)

I have yet to try the same experiment *starting* with the hand-coded parameters, but perhaps that would be the way to do it, and hope that after several months there would be some worthwhile change.

Dan