Author: Roberto Waldteufel
Date: 19:11:36 09/25/98
Go up one level in this thread
On September 25, 1998 at 11:00:21, Robert Hyatt wrote: >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... Hmmm....what if you have a book line that leads to a slight edge, but through some other line you reach a position where you have two legal moves (among others), one of which transposes to a position from the line with the slight edge, and is therefore a "book" move by transposition, and the other of which leads to a really big advantage? How do you determine that the second move is better than the first? Your method seems much more efficient for a large opening book, but maybe for a small "handpicked" repertoire, eg in preparation for a known strong opponent whose previous games you can study in advance, I wonder if hashing is necessary, since the table would be very sparse, and a binary (or even linear) search becomes feasibe for a small book of only a few thousand positions. I imagine there is a cut-off point beyond which hashing is more efficient, but I have no idea what it is. For millions of positions I am sure hashing is far superior to other methods. Best wishes, Roberto
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.