On Thu, 2007-02-08 at 15:55 -0500, Don Dailey wrote: > The children of one parent almost certainly will have different 64 bit > keys than the children of the other parent.
Not if the parents collide. (apart from symmetry/canonical considerations): if H(A)==H(B), then after applying move 'm' -->> H(A) ^ some_constant == H(B) ^ some_constant So if you use Zobrist[move] as a some_constant value (which I understand you do), then if both parent moves A,B have a successor move (coordinate+color) in common, the resulting hashes for the successors will also collide. > I don't see how you can conclude that I'm not getting much extra > safety. > > By the way, I use zobrist hashing with XOR to generate these keys and > do all the rotations - choosing the smallest key of the 8 possible > tranforms as the "cannonical" key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... > hash to this same key but the positions are symetrically equivalent. You mean: _after the canonisation_ they hash to the same key. > > You could of course look at it backwards, what are the odds that > 2 child keys will match? If you can find 2 that do match, what are For two children of the same parent, this is (given an adequate Zobrist table) impossible. After canonisation, this is unclear (but can be guaranteed by careful construction of the Zobrist tables). > the odds that their parents will also have a matching key? I > think this is very unlikely. I think this is just as likely as the other way around, since the ^ is its own inverse function. HTH, AvK _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
