RE: computer-go: Bad interaction between caching and superko?

["Grajdeanu, Adrian" <adrian.grajdeanu@xxxxxxx>]

-----Original Message-----
From: David Fotland [mailto:fotland@xxxxxxxxxxxxxxxxx]
Sent: Saturday, 23 February, 2002 17:07
To: computer-go@xxxxxxxxxxxxxxxxx
Subject: Re: computer-go: Bad interaction between caching and superko?



Don't use superko :)  None of the major rule sets use superko, and superko
causes some strange and unintuitive behavior (please no ko flames :)

Many Faces just recognizes simple ko during lookahead.  With simple ko there
is a single illegal move, and you can include the illegal point as part of 
the position
state that is cached.  Then there is no problem.

David Fotland

At 04:25 PM 2/19/2002 -0800, you wrote:
>Is it possible to cache search results when using superko?  I'm worried
that
>a cache result might be invalid, because different moves are legal
depending
>on the move sequence.  Here's an example:
>
>        L
>       / \
>      R   R
>      |   |
>      L*  L
>      |   |
>      R   R
>     / \ /
>  LOSE  L
>        |
>        R
>       / \
>      L*  WIN
>
>This diagram shows a search tree.  WIN means that L wins; LOSE means he
>loses.  The L* positions are identical.  In this particular search L always
>loses.
>
>However, it seems like we get the wrong answer if we try to cache
>intermediate results.  If we search the left branch first, then the
>bottommost move from R->L* is illegal.  So R must move to WIN, and the
>bottom two nodes are recorded as wins for L.  When we search the right
>branch, we reuse this cached result when we encounter the middle L node and
>erroneously conclude that L can win by following the right branch.  Can
>anyone spot a flaw in this logic?
>
>Maybe there's a simple way to detect when it's legal to reuse cached search
>results?  My preliminary conclusion is that there's not, since an illegal
>move like R->L* can occur far from the main line and still affect the
search
>result.
>
>If the problem is real, and there's no easy fix, does it matter?  Do search
>spaces like this one come up often enough in real go problems to worry
>about?  I'd like a program that's provably correct, but I'm willing to live
>with rare incorrect results if it lets me gain the speedup from using a
>position cache.
>
>How have others dealt with this problem?
>
>Thanks,
>
>Scott Roy

David Fotland