Taking the min of the 8 rotated and reflected values is safe enough.
Yes, the probability density will be eight times higher at the low
end, so you're left with 61 bits and change worth of collision
protection instead of 64. If that's not enough, then you can use a
bigger hash size, as has been mentioned. And since all practical hash
table sizes are far less than 2^61, let alone 2^64, I think that
(minimum hash % hash_table_size) should work fine as a key to your
hash table, while -- and this may be different from what Jason had in
mind -- the formula ((bit-reverse of mininum hash) % hash_table_size))
will, if hash_table_size is a multiple of 8, needlessly favor hash
values that are even or multiples of 4 or 8.
On Dec 20, 2007 1:33 PM, Don Dailey <[EMAIL PROTECTED]> wrote:
> > If you are going to compute all 8 hash keys, you can just add them up
> > at the end instead of picking the minimum. Wouldn't that be better?
>
> I think that's pretty workable. XOR is definitely wrong here. If
> you use xor, then the empty board would hash to the same value as the
> position after a stone (of either color) is placed on e5 as well as any
> other symmetry like this. I also think symetries like putting a black
> stone on 2 points across from each other (such as in diagonal corners)
> would create a zero hash because you have 2 sets of 4 hashes that cancel
> each other. I think addition as Álvaro suggests fixes this.
No, the problem you identified applies to addition too. There is no
100% certainty of collision, but there is a very elevated probability
of it. The eight symmetries include reflections and 180 degree
rotations, all of which have the property that s(s(p)) = p. Suppose
your symmetry transformation exchanges points a and c, and points b
and d. How does the sum of the Zobrist hashes compare for the set
{a,b} versus the set {a,d}? They will collide if
(a XOR b) + (c XOR d) = (a XOR d) + (c XOR b)
If (but not only if) ((a XOR c) AND (b XOR d)) == 0 then a collision
is guaranteed. The probability of this is closer to 2^-32 than to
2^-64.
I suggest that those who are interested follow Erik's link
(http://computer-go.org/pipermail/computer-go/2007-February/thread.html#8653),
as this is not the first or second (or probably even third) time this
issue has come up, and as people have warned several times before, it
is easy to get wrong. I vaguely remember that somebody found a safe
set of Zobrist values that allows reflections to be detected without
recomputation and without greatly increasing the collision probability
was found, but I don't remember the details. I also vaguely remember
hearing that the "random values with rotated nybbles" approach is
broken too.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
