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

[met@xxxxxxxxxxxxxx]

Thanks for reply Jean-Pierre!

Jean-Pierre wrote
> Mikael Thulin wrote:
> You did not give an example of such a case. I would very
> much like to see one. Your example, just as mine in the
> previous post is an example of a crucial move, prevented
> by the superko rule.
> Let me explain again. The same situation "A" must be
> reached by two different move sequences starting from
> the same position "S" (not transpositions, this move
> sequence is NOT a cycle) AND have a different value
> BECAUSE of superko. That seems difficult to construct.
> It may even be impossible...
> Starting situation "S" -------alternate play------------> Situation "A"
> Starting situation "S" ---different alternate play----> Situation "A"
> The two situations "A" are identical, but their minmax value
> is not, because of different move history and superko.
I try again (I'm sure I'm worng but I don't get it) :-)

Alternate play:

A)
Last move: # 7-3
+ O + + + # #
O O O O # # +
# # # # # + #
Status: white can NOT save the 2-2 string

S)
Last move: O 1-5
+ O + + O # #
O O O O # # +
# # # # # + #
Illegal: # 1-4
Status: black can capture the 2-2 string


Different alternate play:

A)
Last move: # 7-3
+ O + + + # #
O O O O # # +
# # # # # + #
Status: white can NOT save the 2-2 string

P1)
Last move: O pass
+ O + + + # #
O O O O # # +
# # # # # + #
Status: white can NOT save the 2-2 string

P2)
Last move: # 1-4
+ O + # + # #
O O O O # # +
# # # # # + #
Status: white can NOT save the 2-2 string

P3)
Last move: O Pass
+ O + # + # #
O O O O # # +
# # # # # + #
Status: black can capture the 2-2 string

P4)
Last move: # 1-3
+ O # # + # #
O O O O # # +
# # # # # + #
Status: white can save the 2-2 string

S)
Last move: O 1-5
+ O + + O # #
O O O O # # +
# # # # # + #
Illegal: # 1-4
Status: black can NOT capture the 2-2 string

S gets a differnt value in the two variations. What do
I get wrong?

If that status from the first evaluation of S  is stored in
the transposition table. Then the "wrong" value for S
will be retreived from the table when the position is
reached the second time. The "wrong" value will be
backed up to P4 and stored for that position.

> I believe this case is either impossible or extremely
> unlikely. So maybe we don't need to worry about it?

I don't think that it's that unlikely, it is this that I do worry
about. (this is where my current implementation is wrong)
I still need you to explain the differens between "positional
super-ko" and "situational super- ko"?
> > > 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?
> No, only board layout and next player are repeated.
> > > Can your algorithm use the already computed value
> > > for the situation, even though
> > > this situation has been reached by different means?
Then the answer is NO but my program is reusing the
computed value for the moment. I have not encoutered any
wrong values at the root of the tree but I have verified that it
do happen deeper down the tree.

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

Yes, it can be a different sequence.
(see the diagrams above)

> > 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.
> If you mean recompute the value of the situation each time
> it is found during the search, it would slow down enormously
> the search (without necessity in most if not all cases).

Do you have any other suggestion on how to solve this?

If I want *many* transpositions I shall not use the super-ko
rule. (this gives an tremendeous speed-up) but the problem
is what to do with cycles. When I detect an cycle I have to stop
the search (otherwise I get a loop) but what value shall I back-
up to the previous position? (with the super-ko in place I just
back-up failure for the player trying to complete the cycle) As
I dont want to use the super-ko rule (as it brings the number
of transpositions to a minimum) I have to find a different way
to solve this. Suggestions?

I guess that it means that I have to recalculate the value for
positions with an unknown value. I don't think it will have such
a big impact though. It should be rare that the same cyclic
position will be encountered twice as the transposition table
will contain evaluated positions prior to the one causing the
cycle.

Maybe I should research if the "unknown-value" or the
"super-ko" is more efficient. It might be enough material
for a paper :-)

> GoTools does not look for the best move sequence in actual
> play: it only finds the stone-killing or stone-saving sequence,
> regardless of the score. This explains why GoTools does not
> recognize seki, for instance.
This goes for my program as well.


Phu... :-)

Thanks for your cooperation. This discussion make me think
twice. I have learnt a lot.

Regards,
Mikael Thulin