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

[Jean-Pierre Vesinet <jpvesinet@xxxxxxxxxx>]

Mikael Thulin wrote:
> When one create a hashcode for a go position one have to have
> a way to include which moves that are illegal by the ko-rule
> into the hashcode.

I suppose it is a good idea to add a boolean flag to the situations stored
in the hashtable to indicate whether the situation arises in the current
line of play. The flag is cleared when the search backtracks. Of course this
is only possible for "depth first" search algorithms.

If you come upon a situation whose flag is set, then you have a cycle. Then
your algorithm can safely backtrack.

By situation I mean position + next player color (let's suppose situational
superko is in use).

Even when using rules that do not enforce superko, you still need to check
cycles because:
1. your program must not loop endlessly,
2. there may be special rules in this case (no result, for example, in
Japanese rules).

> Every illegal point have to included into the hashcode.

Not only illegal points, but the entire history of this situation (all the
previous situations)!

What happens if, during the search, you come upon an already evaluated
situation whose flag is not set (different line of play)? Can your algorithm
use the already computed value for the situation, even though this situation
has been reached by different means ? It could be a transposition, but it
could also be a completely different sequence. I am not even sure whether
this case exists (a situation that can be reached by two different move
sequences from a starting situation, and having two different values because
of superko). By value I mean whatever is used for nodes comparison in a
min-max or alpha-beta or better algorithm. It can be a binary or integer
value.

Maybe in some very "superko intensive" problems such as 2x2 go ? If someone
has an example, please post it to this list.

My guess is that even the best tsumego solvers such as Thomas Wolf's reuse
the situation values each time they pop up again during search.

GoTools has a special option for checking :

<start of quote>
1. whether the outcome is based on a double ko, i.e. the looser would
have won if (s)he would have won both ko's which are going on at the
same time. Possible reason to investigate this: If nothing else is on
the board than the life&death problem then the side to recapture first
can not win both kos. But if the life&death position is only part of a
more complex board position with more kos going on then the situation
is different. To be clear: GoTools does not just record whether there
are two kos in the life&death position but whether they were essential
for the outcome of the life&death fight.

2. Whether the outcome is based on a cycle in which no side needs
extra external threats (chosei, triple ko) as explained earlier.
<end of quote>

Sorry If there are more questions than answers in this post, but I could use
some advice on these issues, too...

Jean-Pierre