[computer-go] Zobrist hashing with easy transformation comparison

[Łukasz Lew]

On 2/10/07, Antoine de Maricourt <antoine.de-maricourt at m4x.org> wrote:
> Hi,
>
> did you read Anti Huima's paper? The idea looks similar, but
> unfortunately it does not work. I provided a proof of the defect on this
> list (end of 2002 if I remember well). It's not that easy to get a
> working scheme. In fact there is only one combination with 8 chunks of
> data. In 2002 I exchanged a lot of email with Nici Schraudolph, and we
> found the right scheme. We wanted to write a paper, but we did not (it
> takes time, and I had not that much time - mathematic and computer go is
> just a hobby for me).
>
> After having the right scheme, the tricky part is to perform a
> statistical analysis: unfortunately introducing constraints to deal with
> symetries weakens the hash key. The probability of collision becomes non
> uniform and depends on the board configuration. In short: if you take
> two different random board configurations, then the probability that
> they have the same key becomes higher if one of the configuration has
> self symetries.
>
> If there is strong interest, I can post the scheme.
Please do.

> But I'm not sure I
> will post the statistical analysis (it was almost ten hand writen pages,
> and I'm not sure I still have them).
Have You performed an empirical test for collisions?

Best,
Łukasz Lew

>
> Antoine.
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>