Author: David Mitchell
Date: 01:17:45 05/17/04
Go up one level in this thread
On May 16, 2004 at 08:30:48, Uri Blass wrote: >Suppose that you have a book of 2^20 positions. >Suppose that you need in average 16 bytes for every position(to store >positions,moves and some more information like learning value for every move). > >I do not like the idea to store only positions in book and I think that the the >job of making all moves in book positions to find more book moves can be done in >the time of creating the book. > >I can think of 3 ways to find if a position is in book > >1)To do a binary search in the file that has the positions(Disadvantage:you do >more searches in the file relative to other ways and you basically need to probe >the file 20 times only to find if a position is in book). > >2)To have a special file that has the exact place that you need to search based >on the last 20 bits of the hash key(disadvantage if you add a single position to >your book you may need to change almost 2^20 numbers in this file because if the >place of one position is changed the place of all positions after it is changed) > >3)Not to have a special file of the exact places but to know the right place to >search because you know that your book has 96 bytes for every 20 bits of the >hash key when usually part of the bytes have meaningless 0's. > >Distadvantage:Your book is bigger than neccesary(96 Mbytes instead of 16 Mbytes) >and there is a risk that it is not going to be enough to store all the positions >and moves(the main problem is not having many positions with the same last 20 >bits in the hash key but having many moves for the same position that can >increase the bytes that you need for one position significantly if you need 4 >bytes for every move). > >Uri Just was reading this in the paper on Rookie 2.0. Lots of info on Rookie's program, but the simple answer is that yes, it stores all positions in it's opening book. Biggest advantage is to easily allow transpositions back into some book line, after an unusual move by the opponent, and to allow easy programming of the book learning feature. To cut down on size, Rookie color adjusts all positions, regardless of whose turn it is to move, as if it were white's turn to move, adjusting the board if necessary. Along with the position itself, Rookie 2.0 keeps data on the percentage of games won from this position by the side to move, and the number of times this position has been found in it's database of games used to create it's book. As mentioned elsewhere, the positions are then sorted lexicographically, and the search to find it is a binary search. To be considered for a book move, the position before, as well as the resulting position, must both be in the book. The rookie 2.0 paper is some 75+ pages or so, but worth reading. I'm sure you can google it up. Bound to give you some good idea's. My experience with binary searches is that they are faster, and more efficient than you are giving them credit for. In one program for geneology work, a binary search in BASIC is used on two test files, each with 500 records. On a humble laptop it finds all duplicate entries in zero elapsed seconds. This is checking each file on the disk, not in arrays in memory. (Of course, what makes it so fast is that Windows "pre-loads" ALL the disk data used, in one read, even though my program didn't request it). More RAM is always good, and one pat on the back for Windows. Good luck, and let us know what you decide, please. dave
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.