Author: Adrien Regimbald
Date: 19:24:32 06/20/00
Go up one level in this thread
Hello, >Here is a quick explanation. On the front of the book, I have 32,768 indices >to "clusters" in the book. A "cluster" is any book positions that have the >upper 15 bits identical (hence the cluster/index concept). Once you know the >hash signature you want to look for, you take the upper 15 bits, index into >the cluster indices, and that gives you a point in the book.bin file that you >fseek() to. > >Now the cute part. My hash signatures in the book are created in a different >way than the usual hash signatures. The upper 16 bits of the book hash comes >from the _parent_ position... The right 48 bits comes from the _child_ >position. > >Why? > >This puts all book positions that have a _common_ parent in the same cluster >(yes, along with some others that have the same common parent signature but >are not relevant). I now fseek to the cluster, do one I/O, and I get _all_ >possible book positions from this parent position, rather than randomly doing >I/O all over the book. > >Works great for very fast games. I build the book like this: > >Parse every move and emit a normal hash signature as above (16 bits for parent >position, 48 bits for new child position). I then sort this (I sort it in >chunks to avoid needing gigabytes of memory.) Now I fseek() beyond the first >32K indices (128kb) and start reading the sorted chunks and merging them. At >any time the upper 15 bits change, I update the last cluster start, write out >the completed cluster (first 4 bytes of a cluster is number of moves in the >cluster). I continue until all the sort files are merged into the book file, >then I back up and write all the cluster indices I have been storing in an >array. > >Quick, easy, and _very_ fast to access. And it prevents some ugly >transpositions due to the hash signature having the parent and child signatures >merged. IE e4 e5 Nf3 a6 Bb5 and black might well play Nc6 which leads to a >known book position. Of course axb6 would be much better. This scheme at least >defeats that kind of stuff, although it also causes a few useful transpostions >back into book to be delayed for one move. Hmm.. I never thought of that.. I have one doubt plaguing my mind though: It seems that this sort of parent/child setup would be good for lightning/very fast games where it is frequent to make blunders of this sort .. but in a standard length game against a strong opponent, I have the impression that you will not reach that sort of situation, and are much more likely to benefit from getting the transposition back into book instead.. One question - is the grouping of parent/child positions like that all together really beneficial in practice? I was under the understanding that binary file access is pretty much constant-time regardless of the position in the file, unless you need to switch cylenders a lot, or the binary file is scattered completely - no contigous blocks. What size of a book would you need to actually notice a benefit with this? Regards, Adrien.
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.