[computer-go] Zobrist hashing with easy transformation comparison

[Nick Apperson]

Sorry for posting then,  I didn't realize that it had been tried.  I may
work through the problem and try to get it to work in order to fully
understand why it in fact does not work.  If by some miracle I manage to get
something working with a collision rate of 1/(2^61) I'll certainly post it.
Thanks for the info.

- Nick

On 2/9/07, Erik van der Werf <erikvanderwerf at gmail.com> wrote:
>
> Nick,
>
> The basic idea of what you're describing is well known. It was first
> published by Antti Huima several years ago. Unfortunately though, his
> implementation was flawed. I didn't check your code but likely it
> suffers from a similar defect. It is possible to fix the defects in
> Huima's scheme. If you ignore colour symmetry it's relatively easy to
> find a defect-free xor-based scheme that works with 8 segments. The
> more interesting part is in finding the minimal number of segments,
> and then proving correctness.
>
> Nic Schraudolph has done some interesting work on this, but as far as
> I know he still hasn't published it. Maybe if we all sit on him we can
> finally get him to finish it :-)
>
> Erik
>
>
> On 2/9/07, Nick Apperson <apperson at gmail.com> wrote:
> > Hey all,
> >
> >     I was thinking about our conversation and i decided to design a
> zobrist
> > class that allows for easy comparison to check and see if 2 different
> > zobrist values are equivalent after a rotation etc...  It updates the
> > zobrist in such a way that it can transform them and after trying 8
> > possiblilities, it can determine if they are equal.  There are actually
> > quite a few optimizations that could be performed on it, but I just
> wanted
> > to post the basic idea.   See the following source code for the basic
> idea:
> >
> >  http://www.nicholasapperson.com/computergo/zobrist.h
> >
> >  Essentially it works so that it hashes the played stone as each of the
> > rotated forms and stores that in each of the 8 bytes used.  The bytes
> are
> > arranged in an order such that flipping the 2 DWORDs results in the
> zobrist
> > value for if there was a rotation in the x axis, flipping WORDs results
> in a
> > reflection across the y axis and swapping bytes results in a reflection
> > across the y=x line.  Order obviously matters in the case of xy so the
> > transformation is assumed to take place after the other
> reflections.  For
> > example:
> >
> >  if we have 0x1234567890ABCDEF as a zobrist value,
> >
> >  0x90ABCDEF12345678 would be the zobrist of the position with a
> reflection
> > across the x-axis
> >
> >
> >  Anyway, I'm sure there is a bug or two, but I wanted to get your alls
> > thoughts.
> >
> >  - Nick
> > _______________________________________________
> > computer-go mailing list
> > computer-go at computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> >
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070209/2198f003/attachment.htm