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