4/02/2013

Recently, I have been writing a CPU chess engine. There are several reasons why I am doing this instead of the GPU chess engine. First, I need a reference against which to compare the GPU engine. Second, I can more easily test things with the CPU engine, because it is easier to debug the code and, e.g. set up test matches to tune the evaluation function. Third, I might end up with quite a strong CPU engine, which as such is an achievement.

The CPU chess engine has now fully functional move generator, which produces correct results in all the test cases I could find for perft(). The speed is modest 8-12 million nodes per second (no bulk counting; every leaf node is visited) on single core 3.2 GHz CPU. I might try to optimize this, but it is not the first thing on my priority list.

I also implemented a simple evaluation function. It is based on material, mobility, king safety, and pawn structure. I have not tried to tune the evaluation, because I will replace the evaluation function with a more principled approach. I have a general idea how the evaluation function should work, but I have not had time to work out the details yet. This is the most enjoyable part of the whole project, so I am in no rush.

Then, I have the alpha-beta search (with quienscence search) implemented with the iterative deepening at the root level. The principal variation is stored and it is searched first. The full principal variation search is not yet implemented, because I want to be sure I get the transposition table working properly first. I have tried the null-move and razoring at one ply from the leaf nodes, but currently they are not included.

The transposition tables are implemented by using the Zobrist keys for hashing. They are first calculated for the initial positions and updated in make() and unmake()-functions. This does not add much to the instruction count, so it is fast. I have tested the transposition tables with perft()-function and I get the correct results, but much faster. I use two transposition tables, one with the always-replace-strategy and another with the depth-preferred-strategy. Tests with perft()-function show about 15 % speed up compared to either of the strategies alone. I have not yet combined the hash tables with the alpha-beta search, because I want to be absolutely sure I do it properly. One must be careful with the type of the entries and the mate scores.

Although the development is still far from completed, I already have a chess engine that is able to play decent chess. I have played against it a few times now, and have not been able to beat it yet. It is strange that the engine seems to understand some positional concepts that I have not programmed into the evaluation function yet. I find two possible explanations for this: 1) the observed positional understanding follows from tactical considerations, and/or 2) some commonly used evaluation terms are overlapping, so the missing terms are implicitly included in the existing terms. This is interesting and raises a question: how to implement an evaluation function with (almost) orthogonal terms?

No comments:

Post a Comment