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

[met@xxxxxxxxxxxxxx]

Jean-Pierre wrote
> 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.
This does only solve the problem to find a cycle. The problem I tried to
raise
was how to create a correct hashcode for the positions i.e what proerties
do I
have to include to get a hashcode that are unique for positions with
different
evaluations (under the super-ko rule).

> 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).
Yes. That is my second question: How should I treat cycles in a program
that solves tsumego without the super-ko rule?

> > Every illegal point have to included into the hashcode.
> Not only illegal points, but the entire history of this situation (all
the
> previous situations)!
Absolutly true! Do you have any suggestions on how to construct hash
codes with that property?

> What happens if, during the search, you come upon an already evaluated
> situation whose flag is not set (different line of play)?

How do you mean that the situation is the same. Just board layout and
player
at move? illegal moves included? set of previous positions included?

> Can your algorithm
> use the already computed value for the situation, even though this
situation
> has been reached by different means?

It depends on how identical the position. With all properties (board
layout,
player at move, illegal moves and the set of previous positions) included I
would say, yes!

> It could be a transposition, but it
> could also be a completely different sequence.

It could be a different sequence if not all the above properties is used
but
otherwise I would say that it is a transposition. or?

> 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).

I'm not sure what case you are looking for but I think that my post
"Hashcoding
under the super-ko rule" shows such a position. Does it?

> 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.
But how? :-)

I think the solution for my program is to extend the evaluation from "true
and false"
to "true, false and unknown" and assign unknown to the cyclic-positions.
This will
solve the problem but unfortunatly the increase from two to three "values"
will
increase the search tree quite a bit. (I know that Thomas Wolf's GoTools
only
use true and false as values for that reason)

Regards,
Mikael Thulin