Re: computer-go: Huima's hash function

["Antoine de Maricourt" <antoine.de-maricourt@xxxxxxx>]

> Antoine, can you give us an example where the addition (modulo chunk)
fails,
> like Huima describes for XOR?  I had no problems with it, but maybe I
> wasn't looking hard enough.  The problem Huima describes is specifically
> that certain positions map to a zero hash value, same as the empty board.
> You phrase it more generally - have you seen examples where different
> positions map to the same *non-zero* hash value?

>From Huima's paper:
- let S be the size of the board
- let p be a point with coordinates (x,y), where x and y range from 0 to S-1
inclusive
- r(p) has coordinates (y,S-x) [90° rotation]
- m(p) has coordinates (S-x,y) [mirroring along vertical axis]
- Hb(p) is the hash value for point p with a black stone on it
- let * be the operator that combines the chunks (z0, z1, ...) [xor, add, or
any other commutative operator]

Now:
- let p0 be a point that does no lie on any symmetry axis of the board
- let p1 = r(r(p))
- let p2 = m(r(p))
- let p3 = r(r(p2))

we have:
Hb(p0) = z0.z1.z2.z3... with Huima's notation [I only consider the left half
part of the hash value]
Hb(p1) = z2.z3.z0.z1...
Hb(p2) = z0.z3.z2.z1...
Hb(p3) = z2.z1.z0.z3...

- let B0 the board position with black stones at p0 and p1, and all other
points empty
- let B1 the board position with black stones at p2 and p3 and all other
points empty

H(B0) = Hb(p0)*Hb(p1) = (z0*z2).(z1*z3).(z2*z0).(z3*z1)
H(B1) = Hb(p2)*Hb(p1) = (z0*z2).(z3*z1).(z2*z0).(z1*z3)

Since * is commutative (and we need it to be!), we have H(B0)=H(B1)
but B0 != B1.

This property does not depend on *, nor on the way Hb(p) is generated,
nor on the size of the hash key (64, 128 bits or even more).

OK, but B0 and B1 have a symmetry relation. So we could maybe accept
that, since the goal was to quickly find symmetry relations.

Now, let B be a board position without self symmetry, and with p0, p1, p2
and p3 empty.

H(B+B0) = H(B)*H(B0)
H(B+B1) = H(B)*H(B1) = H(B+B1)

B+B0 and B+B1 have no symmetry relation (their difference have), but
still hash to the same value.

> BTW, a nice way to hash a ko point (= empty point where the simple ko rule
> forbids to play) is to put both a black and white stone on it.
Side-to-play

Nice trick

    Antoine.