Re: [gnugo-devel] Semeai reading

[Terry McIntyre]

You may already be acquainted with Richard Hunter's book on this
topic, referenced at
http://senseis.xmp.net/?CountingLibertiesAndWinningCapturingRaces

It looks like his approach could be translated into quite effective algorithms.

In my experience, it is far too easy to beat Gnugo 3.7.11 in semeai
races, this weakness could be rectified.

Regarding node limitations: these may be set too low for today's
gigabyte machines,
but it would be even better to make the semeai algorithms more efficient.

Thanks, all!


On Dec 19, 2007 1:23 PM, Gunnar Farnebäck <address@hidden> wrote:
> 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
>
>
> _______________________________________________
> gnugo-devel mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/gnugo-devel
>



-- 
Terry McIntyre
UNIX for hire
Software Development, Systems Administration, Security
address@hidden