Author: Robert Hyatt
Date: 10:42:13 10/02/01
Go up one level in this thread
On October 02, 2001 at 12:51:15, Tony Werten wrote: >On October 01, 2001 at 23:37:02, Robert Hyatt wrote: > >>On October 01, 2001 at 17:46:57, Alvaro Jose Povoa Cardoso wrote: >> >>>On October 01, 2001 at 17:36:26, Robert Hyatt wrote: >>> >>>>On October 01, 2001 at 16:55:21, Alvaro Jose Povoa Cardoso wrote: >>>> >>>>>I know this question was probably made many times, but I wasn't listening :) >>>>>Could someone please explain in detail the Crafty openings book binary format? >>>>>Does it represent positions and not moves? >>>>> >>>>>Best regards, >>>>>Alvaro Cardoso >>>> >>>> >>>>Yes. It is essentially hash signatures produced by making moves and then >>>>updating the hash signature after each move and storing it. >>>> >>>>It uses a cute "grouping" scheme so that all the signatures that share a >>>>common "parent" position are lumped together in the book file so that one I/O >>>>operation will read in all possible book moves for any position. >>> >>>Could you please explain this grouping scheme? >>> >> >> >> >> >>Sure. I take the upper 16 bits of the parent position hash signature, and >>combine that with the lower 48 bits of the "children" signatures. I sort >>the file into ascending sequence, so that all positions with the same 16 bit >>parent signature part are grouped together. That gets all children of the >>same parent into consecutive file positions. I then build a set of indices >>that point to each of these "clusters". (A cluster is all book positions that >>match in the upper 16 bits). I have a pointer to each cluster, and the first >>thing in a cluster is the number of bytes in that cluster. I read the first >>4 bytes the index points to to get the number of bytes in the cluster, then >>I read in the entire cluster. I search it sequentially for each hash signature >>match after trying a legal move. >> >>Simple and effective. >> > >I don't see how this can handle either move- or color transpositions. > >Tony > I don't handle color transpositions at all. As far as move transpositions, it works fine except for the single bad case I don't want it to work in. It requires that the current position be a known book position, and the new position must be a known book position. If that is met, then this will catch transpositions just fine. IE e4 e5 Nf3 Nc6 Bb5 [Bb5 is the book move we want to find.] after Nf3 Nc6 e4 e5 Bb5 is found just fine. It won't find some transpositions until one more move has been played, ie e4 e5 Bb5 a6 Nf3 and now I do _not_ want to play Nc6, which would take us back into a known book line. I want to play axb5 and win that hanging piece. My approach won't transpose back in here. If you don't take steps to prevent this, your approach might look really silly at times... I would rather search, and perhaps find that Nc6 is the best move here, by a search, and then after my opponent plays Ba4 I will find a normal book move as the starting and ending positions are both in the book now... >> >> >> >>>Also, did you ever noticed any anomalies by using the hash signatures scheme >>>due the non existing 'one to one relation' bettween positions and hash >>>signatures? In other words, could a program make a wrong opening move because of >>>hashing inconsistencies/limitations? >>> >>>Thank you, >>>Alvaro Cardoso >> >> >>It has never happened to me. I have heard others fight with this problem, >>but it was never clear (to me) whether it was a hash signature collision or >>whether it was some other sort of bug...
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.