Re: computer-go: Huima's hash function

[Nicol Schraudolph <schraudo@xxxxxxxxxxx>]

> Having two tables of (19x19) values in the range that pleases you ( say 32
> bits ). One table will be labeled Black and the other White.  Initialise
> both tables with random values.
> 
> To evaluate the hash value, start with a value of 0, and for each point on
> the board where there is a stone, XOR your current value, with the
> corresponding value of the Black or White table according to the stone
> color.  By corresponding value, I mean to index into the table with the
> stone position.

This is standard Zobrist hashing.  Huima's variation is to compose the
hash value from 8 equal-sized chunks, and have board rotation, mirroring,
and color reversal correspond to group-theoretically analogous permutations
of the chunks.

The advantage is that to match equivalent board positions, you do not need
to rotate, mirror, etc. the entire board; you can perform the analogous
operations directly on the hash value.  The disadvantage is that since
the composition from chunks imposes severe constraints on the possible
hash values, they need to be longer.  From my experience 64 bits is the
absolute minimum, if you want to avoid any clashes you may need 128 bit.

> > It seems to me that this function has some very undesirable properties,
> > that is: some different positions map to the same hash value in a
> > predictible way that does not depend from the random generator.
> >
> > Huima points it out at the very end of his paper, and suggests the use
> > of addition modulo 256 to combine values instead of xor, but
> > unfortunately this do not solve the problem.

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?

It is important to make sure all chunks in the hash value for any given
point that ought to be distinct are so indeed - with just 8-bit chunks it
is otherwise quite possible to get undesired identitites.

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
can be hashed by a black or white stone on an "extra" point off the board.
For Huima's hash, that extra point needs to obey the same symmetries as
tengen, otherwise you'll lose it under rotation or mirroring...

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