[gnugo-devel] Semeai reading

[Gunnar Farnebäck]

With the help of STS-RV it's easier to see where GNU Go goes wrong in
semeai reading. The analysis below is based on STS-RV_1.tst, which
mostly features semeai problems where both colors have one big eye
each. What varies is the shape and size of the big eyes, the number of
common liberties, and the number of outer liberties. All of these are
fairly straighforward to analyze. First fill the outer liberties, then
fill up the opponent's eye. If you're ahead, continue with the common
liberties, followed by repeated filling of the eyespace after each
capture. Of course also capture opponent stones in your own eye when
your stones are in atari. There's no reason why GNU Go shouldn't be
able to read this right.

Current CVS is failing 54 out of 208 tests in STS-RV_1. So what goes
wrong? Here are a number of recurring problems, some with examples:

1. Tactical reading mistake of a three liberty string causes an
   overamalgamation which the semeai reading can't recover from.
   STS-RV_1:23

   9 O O O . . .
   8 X X O . . .
   7 . X O O . .
   6 X X X O . .
   5 . . X O . .
   4 O O O X X .
   3 . O . X . X
   2 O O . X X X
   1 X X X X . X
     A B C D E F

   A8 is considered tactically dead.

2. The same thing but for a two liberty string. STS-RV_1:58

      A B C D E F G H
   19 O . X X O X . X
   18 O . X O O X X X
   17 O O O O O X . X
   16 X X X O X X X X
   15 X O X X O O O O
   14 . O O X O . O .
   13 X . X X O O O X
   12 X X X O . O . X
   11 O O O O O O . X

   A19 is considered tactically dead.

3. Common liberties are played before eyefilling. STS-RV_1:56

      D E F G H J K L M N O P Q
   16 X . . O O O O . . . . O X 16
   15 O O O O O O O X X X X O O 15
   14 O O O X X X X O O O X X X 14
   13 O O X X . X . O . O O X . 13
   12 O O X . O X X O X X O X X 12
   11 . O X X . X X O . O O X X 11
   10 O O O X X X O O O O X X X 10
    9 . O O O O X O O X X X X . 9
    8 O X X . O O X X X X . X X 8
      D E F G H J K L M N O P Q

   White plays K13 instead of G12. (Second move choice, see also item
   6.)

4. Opponent stones in maximally filled eyespace are captured while
   there is still an open common liberty, so own stones are not in
   atari.

5. In low liberty situations, stones inside big eyes look like lunches
   and not eyespace, causing the eye evaluation to go wrong. As a
   consequence the other player may look ahead on eyes (one eye beats
   no eye) and incorrectly be declared winner.

6. As above, but instead of a premature termination of reading a move
   to capture lunch inside own eyespace is generated, which tends to
   be fatal. STS-RV_1:56

   Same position as in 3. First move choice for white is to capture
   lunch at M11.

7. Outer liberty detection mistakenly finds a move inside the
   opponent's big eye. STS-RV_1:68

      A B C D E F G H J K L
   19 O O O . X X O . X O O
   18 . X O O X . O . X O O
   17 . X . O X X . X X O O
   16 O . O O X X X X O O .
   15 O O O O O X O O O . O
   14 O X X X X O O O O O O
   13 X X X X . . . . . . .

   Black finds A18 as a supposed outer liberty, when it is in fact an
   incorrect eyefilling move (white responds at A17).

8. Common liberties are played although the opponent is ahead. After
   failing pass should be considered, aiming for seki.

9. Unjustified branching causes the semeai nodes to be exhausted,
   leading to a mostly random result being returned.

The real killer is item 6. It causes much of the semeai reading in
these tests to become nonsensical, also when the right result is
returned.

/Gunnar