Re: computer-go: transpositions

[Daniel Bump <bump@xxxxxxxxxxxxxxxxxx>]

Mikael Thulin wrote:

> Implementing the transposition table for my tsumego solver shows
> to be a bit trickier than it have been in programs for other games.
> The presence of the ko rule gives that I have to include information
> about illegal points into the hash code for all positions. It also
> gives that I have to play/try all moves and see if they are legal
> before I can search for a position in the transposition table. One
> way to exclude the check for legal moves is to never store/use
> transpositions after a capture move. This works well unless you
> want to use the super-ko rule. With the super-ko rule illegal points
> can occur even without a previous capture. However in a tsumego
> solver the super-ko rule is preferable as it also prevent the search
> from running into useless eternal loops.

Here's a (currently untested) idea which might help avoid loops in
reading situations involving ko.

Evaluate the position twice. For the first evaluation, B is
appointed komaster, meaning that he can win any ko which comes
up. If B takes a ko, then for subsequent moves, W will never
consider taking the ko, because he cannot win it.

For the second evaluation, W is appointed komaster.

If the results of the two evaluations differ, then the position
is ko.

This should avoid loops unless a double ko comes up. In that case,
all bets are off, though it is possible that a refinement of this
idea can still work. For some flavors of double ko, it would just
be a matter of the komaster having to decide which ko he wants to
win.

Daniel Bump