RE: computer-go: transpositions (less unclear?)

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> > [AK] Smart Go modifies the hash code for all moves that capture stones.
> > The hash modification is based on:
> > (a) the move number, and
> > (b) the stones that got captured.
> 
> [MT] I have now tested your suggestion!
> What other properties do you include into the hash code?

Just normal Zobrist hashing with board position and player to move.
The hash modification is in addition to those. To be more precise,
here's the code I use:

    Point firstCapturedStone = m_capturedStones.Top();
    int index = 2*MaxPoint + m_moveNumber % 64 + firstCapturedStone;
    m_hash.Xor(index);

(This assumes that in the exact same position, the stones will be
captured in the same sequence, so looking at the first captured
stone is sufficient.)

> [MT] I think I have an idea of when the suggested hashcoding
> failes. This is one of the hashing failures reported by my
> program:
> ...

You're right. While this method seems effective in Smart Go, it would
not solve the example you give, as the same stones are captured in the
same ply. Possibly the technique could be made more effective by
including the capturing move as an additional hash modification, but
it would remain a heuristic, not an exact solution.

Let's hear from other Go programmers how they address this issue: How
do you include enough history in the hash code to avoid recognizing two
positions as identical when they differ in current or future illegal
moves, without losing the great benefit of transposition tables?

Anders Kierulf
www.smartgo.com