---------- Forwarded message ----------
From: Nic Schraudolph <[EMAIL PROTECTED]>
Date: Feb 14, 2007 2:18 AM
Subject: Fwd: [computer-go] Zobrist hashing with easy transformation comparison
To: Erik van der Werf <[EMAIL PROTECTED]>
Hi Erik,
could you please forward the following to the computer go mailing
list? For some reason my repeated attempts to post to it are
vanishing in a black hole... cheers,
- nic
Begin forwarded message:
From: Nic Schraudolph <[EMAIL PROTECTED]>
Date: 12 February 2007 10:45:50 GMT+11:00
To: computer-go <computer-go@computer-go.org>
Subject: Re: [computer-go] Zobrist hashing with easy transformation
comparison
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).
The bad news: a colleague here has proven that no standard
segmented Zobrist hash can work in less than 8 chunks - and that's
without color symmetry. That makes 16 chunks with color, not very
attractive!
The good news: I've developed a defect-free scheme including color
symmetry that works in only 6 chunks, and has a very efficient way
to compute a canonical hash (that is: without having to compute all
8/16 candidates). No contradiction to the above proof as it's not a
standard Zobrist hash. This is provably the minimal scheme.
Do sit on me - I really need to finish writing this up! In the
meantime, as long as you don't need color, the 8-chunk scheme Erik
posted works fine. Nick's (if I understood it correctly - I took
r_x, r_y, r_xy to mean reflection about vertical, horizontal, and
diagonal axis, respectively) has a problem though: for all
positions p, r_x(r_xy(r_x(r_xy(p)))) == p. Huima's scheme can't
work because it's really a 4-chunk scheme doubled up for color
symmetry.
- nic
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
