Author: Robert Hyatt
Date: 18:36:13 03/26/05
Go up one level in this thread
On March 26, 2005 at 11:32:16, Anson T J wrote: >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? You can really pick any number you want. I chose 32768 because that number, times the max cluster size, gives the total number of book positions, and it was "big enough" for "enormous.pgn". You could make it as big as you choose, of course... > >> >>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? I suppose it is possible, but 64 bits is 64 bits... > >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. Something in intuition says "either way has so few collisions that they can be ignored..." > >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? Instantly. In fact, if you play your cards right, no I/O needs to be done. Just copy the book.bin files to /dev/null (linux) which pre-loads the entire file into memory (filesystem cache). Now when you do a book probe, it takes a fraction of a microsecond, rather than milliseconds for the physical I/O... :) But even without that "trick" it can find a book move in a few ms, all my disks are 15K SCSI so they are "fast enough". :)
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.