Re: [gnugo-devel] bug report

[Gunnar Farnebäck]

Liu Zheng wrote:
>     I use gnugo 3.8 to practice dead-live problem as attachment file,
> gnugo plays as white.
>     The command line is: gnugo --mode gtp --capture-all-dead
> --chinese-rules --monte-carlo --level 100

It should first be noted that level 100 is very much untested and
would be expected to go on forever in most positions.

>     1. The final position is wrong, gnugo should pass and the white
> can be a both-live, i suppose it a bug.

This is quite interesting. The position is like this:

   A B C D E F
 6 O X . X X X 6
 5 O X X X . X 5
 4 O O O O X . 4
 3 . X + O O X 3
 2 X X X O X X 2
 1 . O O O X . 1
   A B C D E F

The lower left is a seki. White can't play any move there without
dying, black can play either A1, A3, or C3 to gain one point
under Chinese rules.

White at the move correctly passes if the level is 0-45 and
incorrectly plays A1 or A3 (depending on random seed) if the
level is 46 or higher. This is regardless of --capture-all-dead,
--chinese-rules, or --monte-carlo.

>     notes:
>     2. Though in the docs there are no level 100, if i just set as
> level 10, the first round gnugo will resign.

It doesn't for me, but you can always forbid resigning with the
--never-resign option.

>     3. if i don't set monte-carlo option, so the first round gnugo
> will play the wrong position.

You mean fail to play B1 at move 2?

>     Wish it useful for gnugo to become stronger and I hope gnugo can
> play absolutely correct at small board.
>     BTW, the first of black is not the best choice, I just want to see
> if the opponent can't play correct, is it possible gnugo can win. The
> best choice for black can kill all white.
>
>     If it is really a bug please inform me, I will be very happy. And
> if just add some pattern database, please tell me how to repair it,
> Thank you very much!

Let's see what's going on. Something bad seems to happen with the
life and death reading. It's a bit complex how things interact in
a seki position but analyzing the reading of A4 turns out to be
revealing.

$ gnugo -l /tmp/bug.sgf -L 12 --decide-dragon A4 --level 45
finished examine_position
A4 cannot be attacked (1 variations)
A4 is alive as it stands

Looks reasonable.

$ gnugo -l /tmp/bug.sgf -L 12 --decide-dragon A4 --level 46
finished examine_position
A4 cannot be attacked (1 variations) result uncertain
A4 is alive as it stands result uncertain

But here's something fishy; there's really nothing to be uncertain
about. Adding some more traces gives:

$ gnugo -l /tmp/bug.sgf -L 12 --decide-dragon A4 --level 46 -t
finished examine_position
owl_attack A4
Inessential string found at B3.
Variation 0: ALIVE (owl node limit reached)
A4 cannot be attacked (1 variations) result uncertain
owl_defend A4
Inessential string found at B3.
Variation 0: ALIVE (owl node limit reached)
A4 is alive as it stands result uncertain

Well, this absolutely doesn't make sense. Owl node limit definitely
shouldn't be reached at level 46 after analyzing a single node! But
it's not a great mystery if you look closer at the code. Relevant here
is line 815 of engine/utils.c:

    owl_node_limit      = OWL_NODE_LIMIT * pow(1.5, depth_level);

OWL_NODE_LIMIT defaults to 1000 and depth_level is level - 10. This
gives the right hand side a value of 1.4561e9 for level 45 and
2.1842e9 for level 46. But the left hand side is an int, which on
practically all platforms is 32 bits wide, causing the latter value to
overflow and turn to the negative side. So indeed, there's a bug
involved here. Thanks for reporting so we could find it.

----

Looking back at move 2, --monte-carlo can help but only if the position
is considered as non-final, which it only was due to the
owl_node_limit bug for level > 45. Here it makes sense to check the
semeai reading for the lower left corner.

$ gnugo -l /tmp/bug.sgf -L 2 --decide-semeai A4/A2 --level 10
finished examine_position
Analyzing semeai between A4 and A2, white moves first
Semeai defense of A4: result 0 PASS
Semeai attack of A2: result 0 PASS
18 nodes

Analyzing semeai between A2 and A4, black moves first
Semeai defense of A2: result WIN C1
Semeai attack of A4: result WIN C1
27 nodes

Too bad, it couldn't find any defense of A4. Adding "-o vars.sgf"
gives an sgf file of the variation tree, showing that B1 is never
considered. This, however, can be fixed by adding a pattern, such as

| Pattern D848
| # gf New pattern. (3.9.1)
|
| |oxoo         stop eye with nakade shape
| |XXXO
| |.*.o
| +----
|
| :8,s,value(35)

which would go into patterns/owl_defendpats.db. After adding this
pattern we instead get

$ gnugo -l /tmp/bug.sgf -L 2 --decide-semeai A4/A2 --level 10
finished examine_position
Analyzing semeai between A4 and A2, white moves first
Semeai defense of A4: result WIN B1
Semeai attack of A2: result 0 B1
83 nodes

Analyzing semeai between A2 and A4, black moves first
Semeai defense of A2: result WIN C1
Semeai attack of A4: result WIN C1
27 nodes

which correctly say that white can get seki by playing B1 and would
get killed if black were to move first.

Unfortunately this isn't quite enough to solve the whole problem since
white still passes if asked to generate a move. But investigating that
will have to wait until I have more time.

/Gunnar