Author: Dan Newman
Date: 14:30:25 01/30/99
Go up one level in this thread
On January 30, 1999 at 13:00:13, Normand M. Blais wrote:
>I want to implement a Book repertory for my chess program and I need some help.
>How do I proceed? I need a mean to store the moves and later to retrieve them.
>Any help will be appreciated.
>
>Thank you,
>
>Normand Blais
One thing you can do is store positions rather than moves. The
idea is that you generate all the moves at the root, make each one
in turn, looking up the resultant position in the opening book to
see if it's there, and if so, how good it is. This automatically
handles transpositions. Here is what I use as a book entry:
struct book_entry_t {
unsigned long hashcode1; // First half of 64-bit hashcode.
unsigned long hashcode2; // Second half.
int white_wins;
int black_wins;
int draws;
};
The hashcode is just the position hashcode used for the transposition
table, three position repetition rule, etc. The other values are
counts of wins, losses, and draws found in the PGN file used to
generate the book.
In order to avoid excessively long lookup times I have the positions
partially sorted on the basis of the last N bits of the hashcode;
positions with the same last N bits are placed together in the book.
The book file has two parts: an index and the main part containing
the position data. The index has 2**N entries and contains byte
offsets into the main part of the book file. So, to lookup a
position, I first calculate an offset into the index using the
last N bits of the position hashcode and retrieve the byte offset
to the chunk of position data that contains the position (if it's
in the book). I then search linearly through the chunk for the
position. (I plan to change this to a binary search.)
The win/loss/draw data can be used to calculate some measure that
the program can use to decide on which move to take.
Other fields could be added for learning and so forth.
Bob Hyatt does something a bit more complicated in Crafty so that
positions that are children of the same position are clustered
together. This makes the access much faster. IIRC, he uses part
of the parent position's hashcode (N bits say) in combination with
part of the child position's hashcode (64-N bits) as a signature.
Anyway, you can look at Crafty's code to see the details.
-Dan.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.