Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Dabbaba needs an openingbook

Author: Robert Hyatt

Date: 18:04:08 05/27/98

Go up one level in this thread


On May 27, 1998 at 19:33:30, Dan Newman wrote:

>On May 27, 1998 at 16:45:38, Jens Baek Nielsen wrote:
>
>>My chessprogram Dabbaba needs an openingbook.
>>See below - is this the right way to make it?
>>
>>I consider having a textfile like in this format:
>>e2e4# e7e5# g1f3# b8c6#...
>>----  ----  ----  g8f6#...
>>----  c7c5#...
>>d2d4#...
>>( the # could be a mark as in Genius (!/-/./ ) to indicate how often a
>>move should be played)
>>
>>=====>Does such a textfile exist, that everybody can copy and use?
>>
>>A program DABBBOOK.EXE should read this textfile and generate a file
>>DABBABA.BOK like this, that Dabbaba uses as its book:
>>  8 bytes hashkey
>>  1 byte from
>>  1 byte to
>>  1 byte for the #-mark.
>>-------
>> 11 bytes pr. position; ca. 9.000 positions in 100K.
>>By using the hashkey much space is required, but transpositions are
>>handled.
>>
>>Greetings Jens (jensbaek@silkeborg.bib.dk)
>
>Hi,
>
>The format of book entries I use is this:
>
>    struct book_entry {
>        unsigned long hashindex;
>        unsigned long hashkey;
>        unsigned short white_wins;
>        unsigned short black_wins;
>        unsigned short draws;
>    };
>
>No need to put the move into the entry.  The idea I use is
>to generate all legal moves at the root, then try each one
>and look up the resultant position in the book.  Those moves
>whose resultant positions are not found in the book are
>ignored; the remaining moves can be scored in some way using
>the win/loss/draw data from the book, or perhaps selected
>from randomly, or whatever.  (One can of course have other
>data stored in the book--such as learning data, etc.--which
>can be used to make a move selection.)
>
>I have been using PGN files as a source of move sequences
>from which to generate my book (Bob Hyatt's medium PGN file
>for experimentation).  Currently I've got about a million
>positions in my book--no doubt many of which are junk.  At
>least my program no longer opens with such brilliancies as
>1. a4, followed by 2. a5 (got to add some more eval).
>
>In order to speed up lookup, it is important that the
>positions be organized in some order.  One could for instance
>sort all the entries in numerical order (treating the hashcode
>as a number) and use a binary search to find the entries.  For
>a small book this would probably be OK, but I was afraid that
>the sort done during generation might take too long if the
>number of positions were large and that the binary lookup
>during a game might take too long as well.
>
>What I did was to group the positions into 2**N chunks as
>determined by the N lowest order bits of hashcode during the
>book generation process.  I maintain a file and a fixed size
>buffer in memory for each chunk.  Each buffer accumulates
>Win/loss/draw counts for each of its positions.  When a chunk's
>buffer is full and a position (not yet in the buffer) must be
>added, the data in the buffer is flushed and appended to the
>chunk's file.  In a later pass, the contents of each file are
>sorted and data for duplicate positions merged.
>
>Finally, I write out the book which consists of a count of the
>number of chunks, an index to the start of each chunk, and
>then the chunks themselves.  During lookup, the chess program
>figures out which chunk from the index, snarfs up the whole
>chunk into memory, and does a linear search through the chunk.
>(I intend to make this a binary search at some point.)
>
>Currently I have a noticeable (though under 1 sec) delay,
>presumably due to all the disk activity.  I'm going to try out
>more chunks to see if this helps.  I think Bob Hyatt does
>something a bit more clever with the organization of positions
>so that he needs do fewer, or perhaps only one, read.
>
>-Dan.


here's the scheme I've used for about 20 years now:  make each hash
signature in two parts...  the lower 48 bits of the hash signature from
the book position, the upper 16 bits from the hash signature of the
*parent* position.  When sorting, all the has signatures from the same
parent will be in one "clump" on disk.  If you measure the size of this
"clump" and do some clever indexing, you can get away with doing *one*
I/O to read in *every* possible position that can be produced by playing
a book move from the current position.  (you will also have positions
from
other parent positions as well since you only took 16 bits from the
parent
hash key) but this turns out to be not very big overall...  and you can
play bullet chess without keeping the entire book in memory, and still
make 10 moves without using a second off of your clock...



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.