Sunday, October 16, 2011

Building and using a chess opening book

After the release of iCE 0.2 I went to something that was on my list for some time. iCE has no opening theory knowledge so far. It calculates every move from the very start of the game. It wasn't a priority so far because iCE knew the basic chess opening principles and calculated the moves from the theory most of the time anyway.

But it may hurt in games with short time controls and it will now lead to some diversity in the games because otherwise the games iCE plays are very deterministic.

In my first engine mACE I assembled a small book by hand using a chess book I had. After some weeks I had maybe 7000 positions and 9000 moves in a small book. I could have used that book for iCE also - but I wanted to try a different approach.

I created a book building application for iCE. This application can read in information from actual games and calculates a statistic how often a move was played by a player that later did win the game. From this database I was then able to extract positions and moves. Depending on the settings I could create easily books of different size.

At the moment my database contains of 7.4 Mio position-move records. It looks like this

Start Position:

No    Move      Prob    Played
------------------------------
 1    e2e4      46      93.106
 2    d2d4      35      72.529
 3    g1f3       9      18.729
 4    c2c4       9      17.756
 5    g2g3       1       1.343
 6    b2b3       0         585
 7    f2f4       0         471
 8    b1c3       0         416
 9    b2b4       0         229
10    a2a3       0          54
11    h2h3       0          45
12    d2d3       0          44
13    e2e3       0          36
14    c2c3       0          33
15    g2g4       0          15
16    f2f3       0           3
17    a2a4       0           1
18    g1h3       0           1
19    b1a3       0           1

when a book is created the here first 5 moves are copied to the book, moves with a probability of 0% are skipped. So the book for the start position for white contains the following records

No    Move      Prob
--------------------
 1    e2e4      46
 2    d2d4      35
 3    c2c4       9
 4    g1f3       9
 5    g2g3       1

When the engine searches it creates a random number between 1 and 100 and it plays the move where the added probabilities of the moves hit or exceed the random number for the first time.

e.g. the random number 50 is created, then move d2d4 is played because 46 is still less than 50, but 46 + 35 is exceeding 50.

This seems to work very well even although I use only a very small subset of the 7.4 Mio positions in the actual book.

How this opening theory knowledge impacts the overall strength of iCE I don't know. I assume not much. To be really helpful the book probably must be tuned a lot which I actually don't intend to do at the moment. It's a new point on the todo list however.