Re: computer-go: Huima's hash function

["Jeffrey Rainy" <jrainy@xxxxxxxxxxxx>]

I didn't read the article you mention, and the only link I found to it was
broken, so, please take the following with a grain of salt. I might not know
what I'm talking about. ;-)

What are the desirable properties of your hash function ?

If you want efficiency(as in easy to calculate) and minimal overlap of board
position to hash values, I would suggest :

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.

I think this hash would spread evenly the board position into the hash
space, and that you can't do much simpler.  It requires 19x19x2 values to be
stored, but you need only one copy of that.

You might consider orienting/flipping the board so that identical rotated
position map to the same hash, but I don't think this would be very useful.

Does this hash suffer from any defects I don't know about ?

Jeffrey.

----- Original Message -----
From: "Antoine de Maricourt" <antoine.de-maricourt@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Sent: Thursday, September 12, 2002 16:36
Subject: computer-go: Huima's hash function


> 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
>