[gnugo-devel] A very annoying bug

[Gunnar Farneback]

In the handtalk game handtalk12.sgf (available in CVS), GNU Go was hit
by a bug (sort of) that is more than a little annoying. This does not
happen very frequently, thankfully, but when it happens it can be very
devastating. The first loss in the Computer Go Ladder against Indigo
long ago was directly caused by the same kind of problem.

To explain what happens we have to start at move 195, black T19.
There's nothing wrong with this move, but it sets up the stage for a
systematic misanalysis of the coming moves. This is first visible at
move 199, black E19. Although my current version gives a slightly
different valuation, the list of top moves clearly shows a problem:

1. J8  18.09
2. H14 17.86
3. E19 16.31
4. J3  15.78
5. K5  15.67
6. K4  15.67
7. D9  15.67
8. Q19 15.58
9. C10 15.55
10. J13 15.53

Most of these are very small, quite a few even -1 points gote. The
one exception is Q19, which does win the upper right semeai, but
unfortunately it doesn't come out at top. The problem with the
valuation is that all the irrelevant moves also are supposed to
tactically capture R19. This is primarily caused by a mistake by
small_semeai(). The traces for move 199 say

  small semeai found at R19, T19
  small semeai: changing defense of R19 to S19

I haven't tried to analyze where the semeai analysis goes wrong, but
clearly S19 is an ineffective defense. There are real defenses of R19
at N19 and O15, but neither the tactical reading, nor small_semeai(),
is capable of finding them.

What happens next is that moves which attack or defend something are
tested to see if they happen to attack or defend something more. This
is a very important thing to do, but in this case it introduces
mistakes. For an example we look at E19, which captures F19 with ko.

To determine whether it also attacks R19 we trymove() black E19,
increase the depth limits by one (to avoid horizon problems), and ask
the tactical reading whether R19 can be defended. The tactical reading
can't find any defense (the defenses at N19 and O15 are still beyond
it). Thus it looks like E19 does have an effect. To guard against the
possibility that there is a defense found by other means (such as
small_semeai()) it also tests whether the old defense move works, in
this case S19. As noticed before, however, this move doesn't help at
all.

Effectively, every move with a tactical effect, including those
capturing defenseless stones, are thought to also attack R19, which
obviously is very valuable. The result in the game is that GNU Go
plays no less than 11 clearly suboptimal or outright stupid moves,
namely

199 E19 (not even sente, although white does respond)
203 J2  (some yose value, but not a big move)
207 D19 (wasted ko threat)
209 H14 (some reduction of aji but basically -1 point gote)
211 G15 (minor reduction of aji but basically -1 point gote)
215 H16 (-1 point gote, misses urgent block at D12)
219 A15 (does save A16, but very inefficiently)
221 H13 (somewhat okay, but locally worse than G13
233 J3  (-1 point gote)
239 K5  (-1 point gote)
241 J13 (-1 point gote)

The end result is white wins by 16.5 points. The loss incurred by the
moves listed above was definitely larger than this margin.

What can we do to solve this problem?
* First we can of course fix the mistake by small_semeai(), which we
  should do anyway. This doesn't do anything about the potential for
  escalated problems though.
* Second we can turn off the search for additional attack/defense
  points. This would solve the problem but would probably cause a
  substantial decrease in playing strength.
* Third we can avoid testing completely irrelevant moves for
  additional attack/defense points. This could in theory be
  implemented using the active areas in the persistent cache. In
  practice there are complications due to the facts that the active
  areas aren't very sharp and that the persistent cache is selective
  and doesn't store entries for all reads. In summary this is a good
  idea in principle but with implementation difficulties. It's unclear
  whether it will be possible to completely eliminate the problem in
  this way, but it should definitely suffice to reduce it. It should
  also help to improve speed somewhat.
* Fourth we should try to eliminate the need for (a separate)
  small_semeai(). The real root of the problem is that the tactical
  reading code doesn't have sole responsibility for the tactical
  analysis. Changing this should robustly solve the problem.

The only thing that can be considered before 3.2 is solving the
mistake by small_semeai(), and only if it's caused by a plain bug
rather than a design problem. The last two items are well worth
thinking of for the next development series though.

/Gunnar