Chris Pollett > Students >

    ( Print View )


    [Project Blog]











    [Project Code-TAR GZ]


Extension to Chess game database lookup logic

Description: GNU chess program's game database (book) lookup logic was enhanced such that the lookups were made much faster and efficiently.

Anytime GNU chess program tries to lookup moves from the game database (book.dat) if has to do the following:
1. Based upon current played board position generate all legal next moves.
2. For each move, calculate the hashkey for the current board.
3. Do a sequential digest search for the hashkey in bookpos[] array. If the hashkey is found, then there is a book move, if not then continue looking.
4. If more than one book move is found then select the one with highest wins.

Currently bookpos stores the following:

book struct

As an extension to this book lookup logic I modified the information that is stored in bookpos such that for each white move read from the game database I store all the winning next black moves with the total number of wins.

Assuming user is playing white and computer is playing black.
We can just store the following in new format:

New book struct

With this extension when the game starts, the book lookups will be faster because now the program has to only generate current board's HashKey, find the matching HashKey from the book and then look at the next black winning moves and pick the one with highest number of moves. Information stored in book.dat will also be similar format. Thus we can skip generating the legal moves and calculating Hash Key and doing a lookup each time.

Example 1: GNU Chess with original logic:

Book lookup without extension

Example 2: GNU Chess with Book Extension:

Book lookup with extension

Without the extension the GNU chess program had to generate following number of moves, calculate HashKey for each of those moves and had to search the book for the number of slots mentioned below for just first five moves.

BookQuery: Legal moves generated = 20, Number hash slots searched = 13
BookQuery: Legal moves generated = 29, Number hash slots searched = 13
BookQuery: Legal moves generated = 30, Number hash slots searched = 16
BookQuery: Legal moves generated = 32, Number hash slots searched = 18
BookQuery: Legal moves generated = 30, Number hash slots searched = 16

All these were skipped in the extension where we stored the 4 possible next black winning moves. As the game progress, the number of legal moves will increase and so the book search will take more time without the above extension.

GNU chess program when run with -B option run the program with this extension.

Book Extension Code:

Book extension code1

Book extension code2

Book extension code3

Book extension code4

Book extension code5