Re[2]: [gnugo-devel] life & death (3.3.5)

[Paul Pogonyshev]

me:
>> in the position below black is to play, state of the white group is
>> ko. since there're no threats, it is alive.
>>  ...
>> i tried to play black and started an attack that can be answered:
>>   a7 - a8
>>   a6 - e3 ???   this mistake killed the entire white group
>>   a5 - f3
>>   g3 - pass
>>
>> the strangest thing is that gnu go thinks that white group is still
>> alive and that black stones inside are dead. even if all white stones
>> was connected, it would be seki!

Arend:
> This is indeed bad, and we should add the position after a7-a8-a6 to our
> regression tests. The eye space analysis is going wrong here.

the position after a7-a8-a6:

       A B C D E F G H J
      -------------------
   9 | . X X X . . . . . |  9
   8 | O O . X . X . . . |  8
   7 | X . O X . . X . . |  7
   6 | X O O X . . . . . |  6
   5 | . . O X X X . . . |  5
   4 | O O X X . . X . . |  4
   3 | X O O O . . . . . |  3
   2 | X X X X X X . . . |  2
   1 | . . . . . . . . . |  1
      -------------------
       A B C D E F G H J

can't say i know gnu go engine well, but here is what i think is going
on:
   - eye-space analyzing in life.c and optics.c doesn't consider the
     fact that strings at A4 and at C7 (as well as at A8 and at C7)
     are not connected. linear five vertices eye shape is considered
     to give 2 eyes unconditionally (per eyes.db).
   - owl reading doesn't go deep enough to find that A5 is a critical
     point.

i think we could implement the following concept:
   - list all the strings the dragon consists of (A8, C7, A4).
   - check if they are connectable with moves outside eye shape (A8 and
     C7 can be connected by C8, A4 and C7 cannot be connected).
   - separate the dragon into parts which must be connected (in case
     of attack) with moves inside eye shape (2 parts A8+C7 and A4).
   - enumerate common liberties/connections of different parts (here
     goes the vague part) - parts can be "connected" by A5 or B5.
   - note that black A5 forces us to play B5 sooner or later (black
     can just make atari).
     thus, we have to analyze the following eye shape :

        X .
        X
        X

     gnu go can easily determine it gives only one eye.

this gives a quick way to analyze some moves inside an eye shape. as i
can see, it doesn't matter we "play" (for analyzing purposes) the forced
move (B5) immediatly. for instance, if the situation was

       A B C D E F G H J
      -------------------
   9 | . X X X . . . . . |  9
   8 | O O . X . X . . . |  8
   7 | . . O X . . X . . |  7
   6 | X O O X . . . . . |  6
   5 | . . O X X X . . . |  5
   4 | O O X X . . X . . |  4
   3 | X O O O . . . . . |  3
   2 | X X X X X X . . . |  2
   1 | . . . . . . . . . |  1
      -------------------
       A B C D E F G H J

(no black stone at A7) and we were analyzing the same move, we would
get the following shape:

        . .
        X
        X

it is alive, and correct defense move (A7) is the correct answer to A5
threat. (note that although we "played" B5, we are still first to
play. B5 is placed just for simplicity, since it has to be placed now
or then if we want to live. on other hand, it's probably no use for
black to play B5)

well, this is an intricate explanation, but i think i managed to
formulate the main idea. maybe it would allow to impove life & death
code somewhat.

Paul Pogonyshev

  p.s. don't blame me if i missed something - i'm just studying the
       engine ;) in the end, it didn't play the correct move.