Opening Book

[Bernd Nürnberger]

Hi Volker,

thanks for sharing your ideas.

don't get them exactly.. can't imagine how to see what move belongs to what position...

but I think it's more or less a matter of taste whether to do it this way or by a binary search in a file.. seems to be about equally expensive (searching milliions of nodes in mem <-> doing some hundred disc seeks..).. for cache the second seems to be better..

Bernd

[Gabriel Guillory]

Hi Bernd,

Sorry, I didn't read all the Post, but you seem to look for a way of creating an opening book. If it can be helpful, PgnScanner can do that and the extraction of moves is now at disposal with some explanation an some part of code on :
http://echecs.ramonville.free.fr/pgnsca ... er_eng.htm
Sorry, it's in a french document but I suppose that it may be understandable after a Google translation. And then, there are also some diagrams

Best regards
--
GG

[Bernd Nürnberger]

Hi Gabriel,

thanks for your link. I think for the mere opening book, simpler data structures (as described in other postings) than yours are more appropriate. For example just key and score of each position.

I plan to create my opening book on base of a collecting of games with participants of high elo. Therefor your utility could be useful (but I don't have windows , I think there is a similiar utility for Unix resp. open source named pgnextract), but I think, there are already many collections of those games and simply "catting" them together is enough for me...

Greetings,

Bernd

[YvesLejeail]

(1)
I don't think you need to store the moves in the book, just the positions and a score for each position. The score is the number of times the position was reached in the PGN collection. That's a very simple way to score book positions, but it's enough to make sure that your program isn't likely to play any weird moves from the book.

Hi, I'm also interested in the creation of a book for my engine. But I don't understand your method, Ilari. How do your programme know that it can walk from a position to an other? Do you use a move generator and xor the move with the precedent position to look if this new position is available in the book
Yves

[David Weller]

Hi Yves,

I think you figured it out!

For each available move in your current position:

make move()
probe book()
save score (if there is one)
unmove()

Then, choose any of the available 'book' moves for which you have a score

-David

[YvesLejeail]

Thanks for the reply David, and very nice chin faces
Yves

[Ilari Pihlajisto]

A balanced tree is simply more efficient than a non-balanced one. And as I said it's a a lot more efficient when you're adding new positions to an existing book file. Here's how my engine does it:

1. Create an Avl tree
2. Add moves from the book file to the tree
3. Read the PGN file(s) and add the new positions to the tree
4. Write the tree in the book file

Now think what would happen in step 2 if I used a normal binary tree. I'd get a worst case scenario (a linked list instead of a tree) because the positions in the book are already in perfect order. And even if the positions were scattered randomly a balanced tree would still be more efficient.

[Dann Corbit]

A balanced tree is simply more efficient than a non-balanced one. And as I said it's a a lot more efficient when you're adding new positions to an existing book file. Here's how my engine does it:

1. Create an Avl tree
2. Add moves from the book file to the tree
3. Read the PGN file(s) and add the new positions to the tree
4. Write the tree in the book file

Now think what would happen in step 2 if I used a normal binary tree. I'd get a worst case scenario (a linked list instead of a tree) because the positions in the book are already in perfect order. And even if the positions were scattered randomly a balanced tree would still be more efficient.

Why not store the book as a simple list and load it into a hash table?
Access is O(1) and order is irrelevant.

[Bernd Nürnberger]

Why not store the book as a simple list and load it into a hash table?
Access is O(1) and order is irrelevant.

Hi Dann,

maybe, there is more "wasted" space using a hash table.. and you have to handle collisions.. access time seems to be not that criticial..

Greets,

Bernd

[Ilari Pihlajisto]

maybe, there is more "wasted" space using a hash table.. and you have to handle collisions.. access time seems to be not that criticial..

Exactly why I don't use a hash table. And how do I write the positions to the book file if I use a hash table? ...without any expensive sorting that is.

[Oliver Uwira]

Why not store the book as a simple list and load it into a hash table?
Access is O(1) and order is irrelevant.

Hi Dann,

maybe, there is more "wasted" space using a hash table.. and you have to handle collisions.. access time seems to be not that criticial..

Greets,

Bernd

I believe that the collision problem could be solved quite easily by using open addressing because the book hashtable wouldn't be very densely populated. But it's a waste of space nontheless.

Would it be an idea to calculate a minimal perfect hash then? I reckon that would take a lot of time (too much?) for a large book...

Viele Gr??e,
Oliver

[Bernd Nürnberger]

Why not store the book as a simple list and load it into a hash table?
Access is O(1) and order is irrelevant.

Hi Dann,

maybe, there is more "wasted" space using a hash table.. and you have to handle collisions.. access time seems to be not that criticial..

Greets,

Bernd

I believe that the collision problem could be solved quite easily by using open addressing because the book hashtable wouldn't be very densely populated. But it's a waste of space nontheless.

Would it be an idea to calculate a minimal perfect hash then? I reckon that would take a lot of time (too much?) for a large book...

Viele Gr??e,
Oliver

yes, open hashing would be a solution to the problem... imo a hashtable is nethertheless not an appropriate data structure for the opening book. the main point here is that it is really not time critical... and i don't think that it's worth the megs for the hash table just to find opening move some milli seconds faster..

Bernd

[Dann Corbit]

You know exactly how many enties there are -- after all you built the book. So you can make the table exactly the right size if you like.

A fairly standard trick is to just poke them into your existing hash table with a hash type of "book entry".

A hash table is simpler, faster and less bug prone than an AVL tree but use whatever you like.