Making an Opening Book

[cms271828]

Hi, I'm trying to put together an opening book, but still I'm a bit unsure how.

I want to build an array of 64-bit values,and use the zobrist key of the current position to index the correct entry.

So with a 64-bit key, and table size 2^16, that would leave 16 free bits in the entry to store some info.

I have a lot of pgn files to use, I would like to do it so that for positions that are the same(with same side to move), I use the move that is played the most frequently.

Perhaps one way (I'm using java), when I scan through the pgn files, I get a new position, I could create an object containing all the moves played for that position, and their frequencies. Then when I goto fill in that free 16 bits, I can use the move played most frequently.

I think I would need to xor in the side to move into the position, so same positions with different sides to move, would be treated as different positions.

I have a couple of other concerns, such as how deep into a pgn game should I scan, seems pointless to use anything later than opening moves, and doing this could overwrite positions that occur more frequently too.

Is my idea any good, thanks for any help.

[Harald]

Hi, I'm trying to put together an opening book, but still I'm a bit unsure how.

I want to build an array of 64-bit values,and use the zobrist key of the current position to index the correct entry.

So with a 64-bit key, and table size 2^16, that would leave 16 free bits in the entry to store some info.

I have a lot of pgn files to use, I would like to do it so that for positions that are the same(with same side to move), I use the move that is played the most frequently.

Perhaps one way (I'm using java), when I scan through the pgn files, I get a new position, I could create an object containing all the moves played for that position, and their frequencies. Then when I goto fill in that free 16 bits, I can use the move played most frequently.

I think I would need to xor in the side to move into the position, so same positions with different sides to move, would be treated as different positions.

I have a couple of other concerns, such as how deep into a pgn game should I scan, seems pointless to use anything later than opening moves, and doing this could overwrite positions that occur more frequently too.

Is my idea any good, thanks for any help.

If you only use 16 bit in one entry you only have one move to play.
That would be a boring opening database. And it could easily be attacked.
Consider using a list of moves (with statistics attached to it). Either make
it a fixed list of 0 to 5 moves using another 64=4*16 move bits and
generic probability (50, 25, 13, 8, 4 percent) or a real data structure
with fixed M moves (move, win percentage) or (move, #win, #draw, #loss)
or use a dynamic data structure for a different number of moves for each position.
The move list of a position may stop after <= 5 percent or <= 10 times played.

These filters of win percentage or number of moves played from a
position in a PGN database can be used as a filter when you retrieve
opening positions from the PGN database. Another filter may be the
players' ELO (> 2200) or ELO difference (< 200).

I did the PGN scanning and some of the filters in a Python program
myself but I did not have the time to finish my own opening book.
I have not decided whether I use an hash index plus linear lists or a
kind of tree with the key split in portions of 8 bit, each an index in an
array of pointers to the next 8 bit branch or NULL if there is no more entry.

If you want the position-move-entries to have a fixed size you can store a
pointer or offset in them, pointing to a raw data array with all the dynamic infos.
If this array grows too big you can split it into parts and load the
parts on the fly in a cache.

Harald

[Colin]

Thanks, I don't want to get too heavy with opening book, so I'll probably ignore ELO ratings.

I'm not sure what you mean by generic probability, I was thinking..
suppose a position with white to move has the following moves attached with frequencies shown A(10),B(8),C(15),D(2),E(4)
Then the total is 39, so thats a 10 in 39 chance of playing move A, and so on, so I can use the same probabilities when choosing the move to play.

When scanning pgn files, I'm not sure how many moves (plies) deep I should go, cause its pointless going into middlegame or beyond.

Is 2^16 a good size for a table?
My TT takes up 2^22 64-bit values (2^21 entries), so anything less than 2^18 will be neglible compared to TT, so won't cause memory error.

Thanks again.

[Harald Johnsen]

Hi, I'm trying to put together an opening book, but still I'm a bit unsure how.

I want to build an array of 64-bit values,and use the zobrist key of the current position to index the correct entry.

So with a 64-bit key, and table size 2^16, that would leave 16 free bits in the entry to store some info.

You don't need to have your book in memory. You can still use your zobrist key to index your position and find it on your on disk book.
Then you are not limited by the size of the book.

I have a lot of pgn files to use, I would like to do it so that for positions that are the same(with same side to move), I use the move that is played the most frequently.

What if the frequent move is a bad move ?

I have a couple of other concerns, such as how deep into a pgn game should I scan, seems pointless to use anything later than opening moves, and doing this could overwrite positions that occur more frequently too.

Is my idea any good, thanks for any help.

You should not have collisions when you build your book and since this is an off line process you can use a lot more memory for this hash table.

HJ.

[Richard Allbert]

Hi Colin,

Here's what I did...

I took 2600.pgn, a database I found on Dann Corbits' site, lots of games elo 2600+.

I wrote a function which "plays" the first 10 (or whatever I define) moves of each game, storing the hashkey for the position before the move along with the move played.

After each moves, the function checks for duplicates before storing, maintaining a frequency index.

The data is stored in a binary file, structure:

Code: Select all

struct s_binentry
{
    unsigned __int64 k;
    char m[5];
    int freq;
};

These are written in a binary file which is accessed during play.

When used in play, the engine selects randomly from the top most frequently played moves.

Richard

[Colin]

Thanks, I can't find that file 2600.png.

I looked here... http://www.horizonchess.com/FAQ/Winboar ... tml#online
Theres a reference to Dann Corbit's site, and the file, but I can't see the file.

When creating the zobrist for the position, should I xor in the side to move, as well as castling rights, and ep pawn data, I think I need to do all of those to distinguish different positions, especially the side to move is important.

Thanks

[Richard Allbert]

Yes, you do need all of those things....

If you pm me your email address, I can send you 2600.pgn - although I imagine any database filtered for +2600 elo would do

[Colin]

Excellent,

It is colin-java@hotmail.com.

Thanks very much