Re: [gnugo-devel] Critical dragons and cache problem

[Arend Bayer]

Stéphane wrote:

> Here is another example of cache issues affective the
> critical status of groups. In the following game Black
> plays C13 at move 64, threatening to catch C15-16 in a
> ladder and to revive its dead corner.
>
>      White (O) has captured 0 pieces
>      Black (X) has captured 0 pieces
>
>      A B C D E F G H J K L M N O P Q R S T
>   19 . . . . . . . . . . . . . . . . . . . 19
>   18 . O X . . . . . . . . . . . . O . . . 18
>   17 . O X O O . O . . X . X . O . . O . . 17
>   16 . X O X . . . . . + X O . . . X X . . 16
>   15 . . O X . . . . . . . O . . . . . . . 15
>   14 . O . X . . . X . X . . . . . X . . . 14
>   13 . .(X). . . . . . . . O . . . . . . . 13
>   12 . . . O . . . . . O . . . . . . . . . 12
>   11 . . . . . . . . . . . . . . . . . . . 11
>   10 . . . + . . . . . + . . . . . X . O . 10
>    9 . . . . . . . . . . . . . . . . . . .  9
>    8 . . . . . . . . . . . . . . . . O . .  8
>    7 . O O . . . . . . . . . . . . O . . .  7
>    6 . X X O . . . . . . . . . . X X O . .  6
>    5 . . . . . . . . . . . X . . . . O . .  5
>    4 . . X O . . . . . O . . . X . X X O .  4
>    3 . . X X . X . . . . . O O X . . . X .  3
>    2 . . . . . . . . . . . . X O X . . . .  2
>    1 . . . . . . . . . . . . . . O . . . .  1
>      A B C D E F G H J K L M N O P Q R S T
>
>
> Gnu Go correctly see that and protects the corner when launched with
>
>     gnugo -l cache_problem.sgf -t -T --until 64 --mode ascii
>
>
> However when gnugo plays through the whole game, the engine now thinks
> that the Black B16 and C17-18 stones are dead (even if it correctly
> acknowledges that C15-16 are critical for White). It plays C12, letting
> the corner die, which cost maybe 20 points since it means D17-E17-G17
> becomes weak as well.
>
>     gnugo -l cache_problem.sgf -T --replay white
>
>
> This is probably a cache problem : as I anderstand it, the last move
> (Black C13) is probably not in the active area used for the owl-reading
> of C16 and C17 when they were put dead in the cache.

You are right. For reference, you can check this by doing:

gnugo -l cache_problem.sgf -L 62 -d0x200000 --quiet

The very first cache entry shows:
 Stored result in cache (entry 0):
movenum         = 61
tactical_nodes  = 942
routine         = OWL_ATTACK
(apos)          = C18
(bpos)          = PASS
(cpos)          = PASS
result          = 5
(move)          = C19
(move2)         = PASS
   A B C D E F G H J K L M N O P Q R S T
19 . . . . . . . ? ? ? ? ? ? ? ? ? ? ? ? 19
18 . o[x]. . . . ? ? ? ? ? ? ? ? ? ? ? ? 18
17 . o x o o . o . ? ? ? ? ? ? ? ? ? ? ? 17
16 . ? o ? . ? . ? ? ? ? ? ? ? ? ? ? ? ? 16
15 ? . o ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 15
14 ? ? . ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 14
13 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 13
12 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 12
11 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 11
10 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 10
 9 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 9
 8 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 8
 7 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 7
 6 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 6
 5 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 5
 4 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4
 3 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3
 2 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2
 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1
   A B C D E F G H J K L M N O P Q R S T

I.e. C13 is just not part of the active area.

I think the position is vaguely similar to one posted by SP Lee and
analysed by Gunnar, where the critical area was too small in a semeai
situation.

> But I really think we should do something about critical situations
> like that, because it means we can fine-tune the regression at will
> and still see gnugo play blunders in similar situations in real games.

Agreed.

> If this is indeed a cache issue, I can see two ways to solve it :
>
>     1) extend the active area, maybe including second-order liberties
>        of stones used to kill a group.
>
>     2) add a rule in examine_position() which says that any dead
>        opponent worm adjacent to an own owl-critical dragon should be
>        tested owl-critical with the cache, whatever the cache thinks.
>
>     3) any better idea ?
>
>
> I don't know how to do (1) at the moment nor if it is a good idea.
> If nobody objects, I would like to implement (2) and see how it works.

A slight disadvantage of (2) is that it complicates the flow a little.
I.e. after all owl analysis' have been done, you have to redo a couple
of them. (If you want to do it this way, I think you should do that
inside make_dragons.)

I have yet another suggestion: Add the worm status of all parts of the
dragons, and their direct worm neighbours, to the data stored and
compared in the persistent owl cache. At move 62, C16 is lively, at move
64, it is critical -- this alone should be enough to invalidate the
persistent cache result.

It might also be time to think about systematic improvements of the
persistent cache. There are two ideas mentioned by authors of other Go
programs:

1. SmartGo stores the status of virtually every intersection that ever
got tested in the course of the reading process. (Which would mean that,
if it at some point looks at all neighbours with 2 liberties, it would
have to mark all neighbours' liberties as far as I understand.) This
gives a big active area. To reduce this somewhat, it only stores the
active area of the smalles tree needed to prove the result (i.e., after
the reading has been done, it redoes it, using the previous results, and
only playing the successful move in case of a win).

2. WinHonte stores the complete search tree (DAG to be precise) that is
needed to prove the result. Then at the next move, the cache is not
used to make a final result about the result, but only to order moves
(that is, the move that was successful last time gets tried first).
The point is that "correct" move ordering can make the search faster by
a magnitude, and this is deemed sufficient.

No. 1 doesn't sound to be easily doable in the gnugo framework to me.
But no. 2 does make a lot of sense, and it might be worth trying. (For
the owl reading, that is.)

Arend