On Jul 7, 2010, at 5:07 AM, Jason House wrote:
On Jul 7, 2010, at 1:13 AM, Peter Drake <[email protected]> wrote:
Our hash codes are longs, incorporating:
- The stones on the board (Zobrist style)
- The current color to play (all bits are flipped if it's white to
play)
- The current simple ko point (also Zobrist style)
The last item was the catch. In a transposition table, you want to
include the simple ko point, because you don't want to conflate two
states, in only one of which some point (possibly a key point) is
illegal. In the superko table, on the other hand, you do NOT want
to include this information, because a repetition of a previous
position (with the same color to play) is a repetition, regardless
of the simple ko point.
If this is used as the key to your transposition table, are you ok
with two physical stone collections with different legal moves being
treated as _exactly_ the same search node? This can lead to subtle
bugs.
The only moves that would differ in legality are superkos. They're
rare enough that I'm willing to accept that.
(I'm not willing to accept Orego actually trying to play a move that
violates superko, which is why I've fixed that.)
I'm also okay with occasional collisions that give the same hash code
for very different boards. With 2^64 possible hash codes, it's rare
enough to ignore in the name of speed.
Peter Drake
http://www.lclark.edu/~drake/
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
