Author: Anson T J
Date: 08:32:16 03/26/05
Go up one level in this thread
On March 26, 2005 at 10:46:18, Robert Hyatt wrote: >On March 26, 2005 at 10:29:23, Anson T J wrote: > >>How does Crafty grab a book move so quickly? Are there any experts who >>understand how the positions are represented inside the book file and the >>algorithm works to zero in on a book move so quickly? > > >crafty uses the high-order 16 bits of the hash signature as a "cluster number". >On the front of the book.bin file, I have 32768 pointers (actually just byte >offsets into the file) that point to the start of each of these "clusters" where >the position _after_ the move is made is guaranteed to exist, if it exists at >all. That is very smart, but why only 32,768 pointers and not 2^16 of them? > >How do I guarantee that? Easy, for each 64 bit hash signature in the book, the >leftmost 16 bits (the cluster index) comes from the position _before_ a move is >made, the rightmost 48 bits comes from the position _after_ the book move is >made. This way all possible book moves from the same parent position will be in >the same cluster, which means one disk read and I have all potential resulting >positions after any known book move is made. Of course a cluster has book moves >from several different parent positions since the most significant 16 bits is >not unique for each parent position. But this way, I do just one I/O which >makes it fast... That is also very Crafty. Given a position and a Hash Key when searching for book moves, is it possible that you might end up with a clash if you take 16 bits from the starting position and using 48 bits from the destination? The hash key concept was new to me, I'm not sure of the stats of a possible clash when using 64 bits, or how much more likely a clash is if you use 16 bits from Start_Pos and 48 bits from the Dest_pos. Thanks a lot for your speedy reply. Can you tell me how fast Crafty can locate book moves in a large book like you use on the ICC Server?
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.