[gnugo-devel] Player of local games.

[Gunnar Farneback]

I've put up a patch at
http://www.lysator.liu.se/~gunnar/gnugo/patches/gunnar_3_20.1

This implements functionality to compute eye values according to the
local game model described in doc/eyes.texi and to find vital points.
The main idea is to transform the eye evaluation problem into a
tactical style life and death reading problem.

Consider this eyeshape:

  .
 ..
....

In order to make this into a tactical problem we need to enclose the
eyespace by a connected group of stones (let's say white) without any
more eyes or potential for eyes. The simplest way to do this is to use
the somewhat brutal trick of filling the entire board with white
stones except for the eyeshape,

   A B C D E F G H J K L M N O P Q R S T
19 O O O O O O O O O O O O O O O O O O O 19
18 O O O O O O O O O O O O O O O O O O O 18
17 O O O O O O O O O O O O O O O O O O O 17
16 O O O O O O O O O O O O O O O O O O O 16
15 O O O O O O O O O O O O O O O O O O O 15
14 O O O O O O O O O O O O O O O O O O O 14
13 O O O O O O O O O O O O O O O O O O O 13
12 O O O O O O O O . O O O O O O O O O O 12
11 O O O O O O O . . O O O O O O O O O O 11
10 O O O O O O . . . . O O O O O O O O O 10
 9 O O O O O O O O O O O O O O O O O O O 9
 8 O O O O O O O O O O O O O O O O O O O 8
 7 O O O O O O O O O O O O O O O O O O O 7
 6 O O O O O O O O O O O O O O O O O O O 6
 5 O O O O O O O O O O O O O O O O O O O 5
 4 O O O O O O O O O O O O O O O O O O O 4
 3 O O O O O O O O O O O O O O O O O O O 3
 2 O O O O O O O O O O O O O O O O O O O 2
 1 O O O O O O O O O O O O O O O O O O O 1
   A B C D E F G H J K L M N O P Q R S T

Now the eye value can be determined by reading with the goal to
capture all white stones on the board.

For a more interesting example, add a black stone and two marginal
vertices in the eyespace,

  !
 .X
!...

To accomodate for the margins we add two small invincible black groups
in direct contact with each margin. Notice that all white stones
remain connected.

   A B C D E F G H J K L M N O P Q R S T
19 . O O O O O O O O O O O O O O O O O O 19
18 O O O O O O O O X X X O O O O O O O O 18
17 O O O O O O O O X . X O O O O O O O O 17
16 O O O O O O O O X X X O O O O O O O O 16
15 O O O O O O O O X . X O O O O O O O O 15
14 O O O O O O O O X X X O O O O O O O O 14
13 O O O O O O O O X O O O O O O O O O O 13
12 O O O O O O O O . O O O O O O O O O O 12
11 O O O O O O O . X O O O O O O O O O O 11
10 O O O O O O . . . . O O O O O O O O O 10
 9 O O O O O O X O O O O O O O O O O O O 9
 8 O O O O X X X O O O O O O O O O O O O 8
 7 O O O O X . X O O O O O O O O O O O O 7
 6 O O O O X X X O O O O O O O O O O O O 6
 5 O O O O X . X O O O O O O O O O O O O 5
 4 . O O O X X X O O O O O O O O O O O O 4
 3 X X . O O O O O O O O O O O O O O O O 3
 2 X . X O O O O O O O O O O O O O O O O 2
 1 . X X O O O O O O O O O O O O O O O O 1
   A B C D E F G H J K L M N O P Q R S T

Additionally we have added an invincible black group in the lower
left corner to provide for two outer liberties of the white stones at
A4 and C3. Sometimes these are necessary for correct evaluation.
Finally we add an extra eye at A19. This is used when we want to
distinguish between 0 and 1 (or 2) eyes since the tactical life and
death reading by itself only cares about two eyes or not. When trying
to distinguish between 1 (or 0) and 2 eyes we first fill in A19 again.

Depending on the tactical life and death status with or without the
extra eye we can determine the number of eyes. By evaluating
tactical life and death status after having made a move we can also
identify ko threats and critical moves.

For practical use of this code I have added a GTP command
analyze_eyegraph. This takes as input an encoded version of the eye
graph (since GTP only allows one line commands and spaces are not so
significant). The above example would be

analyze_eyegraph OO!%O.X%!...

i.e. "%" represents newline and "O" represents space. The result is

= 0112
  @  
 .X  
!.*. 

telling us that the eye value is 0112 (see the preamble of eyes.db for
an explanation of eye values) and the vital points are encoded in the
eye graph in the same way as in eyes.db. Notice that in this example
the "vital" moves are ko threats since the number of eyes (one) is
already settled.

Enjoy.

/Gunnar