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

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> [Mikael Thulin] The problem I tried to raise was how to create a correct
> hashcode for the positions i.e what properties do I have to include to
> get a hashcode that are unique for positions with different evaluations
> (under the super-ko rule).

This is a good problem. Smart Go uses a solution that almost eliminates the
issue, but doesn't solve it completely.

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.
This means that two sequences that lead to the same position will get the
same hash code if exactly the same stones were captured at the same move
numbers. (If no stones are captured in the sequence, the hash code is
trivially the same.) If stones get captured at different move numbers or in
a different order, the positions would not have the same hash code.

This almost eliminates hashing problems created because a move was legal in
one branch and illegal in another. Unfortunately, it also slightly reduces
the effectiveness of the hash table, as some changes in move order that
would not affect subsequent play are no longer recognized as transpositions.

Anders Kierulf
www.smartgo.com