Re: computer-go: Huima's hash function

[Nicol Schraudolph <schraudo@xxxxxxxxxxx>]

Very enlightening, Antoine - thank you.  For the sake of correctness of
this nice proof, a few typos I noted:

> - let p1 = r(r(p))
                 p0

> - let p2 = m(r(p))
                 p0

> H(B1) = Hb(p2)*Hb(p1) = (z0*z2).(z3*z1).(z2*z0).(z1*z3)
                    p3

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

Now the next question is, is this defect an inevitable consequence of
enforcing the symmetry relations?  The answer is, fortunately, no: here
is a construction that avoids it, at the cost of doubling the number
of chunks from 8 to 16: again considering only the left-hand side, let

  p0  = z0.z1.z2.z3.z4.z5.z6.z7...
r(p0) = z2.z3.z4.z5.z6.z7.z0.z1...
m(p0) = z7.z6.z5.z4.z3.z2.z1.z0...

This obeys the necessary invariances, namely r^4 = m^2 = I (identity).
But now:

H(B0) = (z0*z4).(z1*z5).(z2*z6).(z3*z7)...
H(B1) = (z1*z5).(z0*z4).(z7*z3).(z6*z2)...

are no longer equal.  Open questions for discussion:

- can we prove this 16-chunk scheme to be correct?
- could the problem be fixed using less than 16 chunks?

Incidentally, doubling the chunks does not necessarily mean we have to
increase the length of the hash - how about using 16 4-bit chunks?  We
can still require all chunks in the value for a generic (non-symmetric)
board position to be different: there are 16! permutations of the integers
from 0 to 15, of which we can use 1/16th (accounting for board symmetries).
Should still be plenty, no?

Best,

- Nici.

-- 
    Dr. Nicol N. Schraudolph               http://www.inf.ethz.ch/~schraudo/
    Institute of Computational Science             mobile:  +41-76-585-3877
    ETH Zentrum, HRS H5  (Hirschengraben 84)       office:      -1-632-7942
    CH-8092 Zuerich, Switzerland                      fax:            -1374