Author: Dan Newman
Date: 16:33:30 05/27/98
Go up one level in this thread
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.
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.