Author: Robert Hyatt
Date: 18:58:33 06/20/00
Go up one level in this thread
On June 20, 2000 at 12:52:06, Gian-Carlo Pascutto wrote: >On June 20, 2000 at 09:10:40, Robert Hyatt wrote: > >>Ignore this. To parse a move, I do the following: >> >>generate all moves >> >>use the input text to eliminate moves from the list, one by one. IE if the >>input move starts with N, then I eliminate everything but knight moves. I >>then parse source/destination/promotion/check/etc and eliminate moves that >>don't fit the requirement. If I end up with one move, it is _the_ move. If >>I end up with zero, the move parsed is illegal. If I end up with more than >>one move left, the move parsed is ambiguous. > >My explanation must have been insufficent, as this is the same as >Faile/Extract do. The only difference is that they first parse in the >source/dest/etc and then do the elimination, not after every step. The >difference in efficiency is very minor I think. > >>In Cray Blitz, we built the book by parsing each move, and then doing a short >>search from each resulting position to be sure we weren't walking into obvious >>blunders. If a score was exceptionally low or high, the search was extended >>to a couple of minutes if needed. It took us a few days to build our book >>because of this, but we didn't do it very often. And yes, that was _days_ as >>in 24 hour non-stop computing. > >But was it worth it? > >A related question: could you explain how Crafty's binary book building >works? I've tried figuring it out from the source, but it was a bit over >my head. > >-- >GCP 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. If I wasn't clear, let me know...
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.