A Genetic Algorithm to Find The Value of Chess Pieces

A Brief History

Almost 30 years ago, @Russ, AKA User 1, and I created Rival Chess.

This collaboration mostly involved us sending floppy disks back and forth across the country through the Royal Mail.



At university, again with @Russ, we rewrote Rival to make use of this thing called Windows.

The main benefit to writing for Windows was that you didn't have to write your own mouse driver, but I wasn't sure it had much other use - it wasn't needed to play network Doom, so what was the point?

There were rumours that Object-Oriented Programming was going to be big, so we used C++ instead of C.



I used the Windows version of Rival as the basis for my final year university project, during which I demonstrated a genetic algorithm that could determine the value of the chess pieces to use when estimating the value of any given chess position.

If you are interested, @Russ's final year project involved something to do with realtime 3D graphics rendering or whatever.

Now, I don't know how many of you are history buffs, but computers were a bit slower back then.

Recently, while surfing around the AWS interface, I noticed that I could rent a computer with 96 processor cores. Just one of those cores is over 2000 times faster than the 8086 I used back in the day. And I can use the other 95 to run games in parallel. The results of this experiment are captured in the following video (this is the first YouTube video I have created, and I've always fancied saying this - please like and subscribe).

Genetic algorithms

Genetic Algorithms can help to find solutions to problems where the size of the problem space is too large to search exhaustively.

You generate a bunch of random solutions (a generation), assess each solution against a fitness function (how many games of chess can it win, for example), and assign a score to each one accordingly.

Once you have a score for each candidate solution, you use this to determine how much influence each member should have on the next generation.

One way to do this is to pick two members of the population at random, but with higher-scoring members being more likely to be picked than lower-scoring members. You then combine the two, picking parts of the solution from each member and combining them into a new candidate solution. Repeat this process until you have a new generation.

You'll also want to add some random mutations to keep things fresh and spicy. Without mutations, you are relying on every part of the correct solution already existing across the population. Mutations are what drive the algorithm to find new directions when looking for a solution.

So, to end this little post, here are the results of my first attempt in 25 years to create a genetic algorithm to determine the value of the pieces in a chess evaluation function.

The settings:

- Population size = 48
- Fitness function = round robin tournament with each side playing all others twice (once as white and once as black). To speed things up, I only sampled 20% of these games, at random.
- Number of generations = 1000
- All other evaluation parameters (king safety, pawn structure, etc...) remain as they are set in Rival 30.0.2.
- Three points for a win, 1 point for a draw.
- Selection for next generation based on points scored.

The code for the algorithm can be found on GitHub.

Rival Links

Rival does not have a monogamous relationship with computing languages. Its promiscuity has seen it flirting with Basic, Pascal, C, C++, Java, and now Kotlin.

It currently exists as a collection of Maven libraries.

Other Rival repository links:

Current Rival JVM Engine code
Rival UCI Interface
Chess Board Model and Move-Generation Library
Rival for DOS source code
Rival for Windows source code


TTFN