Author: Robert Hyatt
Date: 08:00:21 09/25/98
Go up one level in this thread
On September 25, 1998 at 08:56:30, Roberto Waldteufel wrote: > >On September 24, 1998 at 21:17:30, Peter McKenzie wrote: > >>Is there a standard format for opening books, so that they can be exchanged >>between programs? >> >>If not, is anyone interested in defining such a format? >> >>Regards, >>Peter > >Hi Peter, > >My own program uses a non-standard method for storing the positions in its >opening book, which has the advantage of being quite compact for storage. At the >cost of a bit more space, I think the best option for a standard format would be >EPD, which is already supported by many programs. Furthermore, Manfred >Rosenbloom's excellent (free) program EPD2DIAG allows construction and editing >of EPD files suitable for use as an opening book. You might like to look into >this before defining something new. The main improvemnts that might be achieved >for large opening books are along the lines of reducing the space needed to >store the files, and to this end my own method is quite efficient, but could be >improved further, although only at the cost of much more complicated >encoding/decoding of positions. > >Here is the method I use to store a position: > >the first 8 bytes are a bitboard of occupied squares. Then for each occupied >square in a predefined order I use 4 bits to identify the piece of that square. >Thus a full board (32 pieces) requires 24 bytes (8+16) . Every exchange reduces >the number of pieces by 2, so also reduces the lengthe of the position code by >one byte. To be more exact, I should include castling rights and en-passant >square, but I must confess that at present I just rely on there not being any >conflicts here in the realm of the opening positions, and so I ignore these >important distinctions between apparantly identical positions. Any good new >standard should devote a few extra bits to store this information, as EPD does. > >Of course, the positions are then variable in length, so I store the length as >an extra byte in the file from which the program reads the book positions at >start-up. > >Best wishes, >Roberto I do this much simpler. If you ignore the learning, and the counters for how many times a move was played by GM players and how many wins/losses/etc it has, I store only the hash signature. Then, to find if a move is in the book, I generate the list of legal moves in this position, make one, take the *new* hash signature and look in the book file for a match. If I "hit" this move is a "book move." However, searching thru millions of signatures would be *very* slow, so I modify this slightly. When I build the book, suppose I am at ply=N and have some moves that are known book moves; I make them one at a time and remember the resulting hash signatures. But I don't put these in the book as they are. I take the upper 16 bits of the hash signature from the position *before* any of the moves are made (called the parent hash signature) and combine that with the lower 48 bits of the hash signature from the positions *after* the book mvoes were made. After building the book, I sort the signatures, which puts positions with a common parent together in the file, then build an index to the start of a group with the same "parent signature" in the upper 16 bits. Now I only have to search this "cluster" which lets me play book moves at the rate of 10 in under a second on a chess server...
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.