RE: computer-go: Huima's hash function

[Hellwig Geisse <Hellwig.Geisse@xxxxxxxxxxxxxxxxx>]

On 12-Sep-02 Antoine de Maricourt wrote:
> Hi,
> 
> did somebody already used Huima's hash function [1] in pratical application?
> or study in more depth the statistical properties of this function?
> 
> 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.
> 
> [1] A Group Theoretic Zobrist Hash Function

The whole point in Antti Huima's paper is the construction
of a hash function with the property that the hash value
for a position which differs from an original one only in
rotating, mirroring, or exchange of colors can easily be
computed from the old hash value, i.e. without recalculating
the function over the whole board. But this procedure does not
yield the same hash value for those rotated, mirrored, etc.
positions.

I quote from the abstract of his paper:

"We present a Zobrist hash function with the extra property that
if z is the hash value of a position p, then the values z' for the
positions p' that are obtained from p by exchanging the colors, by
rotating the position and by mirroring can be efficiently calculated
from z alone. Still, z and z' are different."

What Huima points out in the notes at the end of his paper is that
"the implementation of Sec. 2 has the undesirable property that for
example the position where there are four black stones on the four
central side hoshi points hash to the hash value zero. This is an
anomaly." This anomaly can be avoided e.g. by bytewise addition
modulo 256 instead of XORing the values.

I don't know whether any realistic Go program spends enough time
in calculating hash values so that this speedup may save a noticeable
amount of time.

Regards,
Hellwig