Pseudo random number and hashing. Two ways to get into trouble quickly.
The idea of combining all 8 transformations is appealing on modern
processors because you can eliminate all conditional branching. But
maybe this is not practical after all.
If speed is not a concern, you could simple hash the 64x8 bit value
itself with a good mixing hash function, such as md4 or md5. But even
this doesn't work unless you establish some kind of ordering first,
such as sorting them before hashing them.
- Don
Eric Boesch wrote:
> 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/
>
>
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
