Updated README: Equal sign not required with `--mode` flag.

[sgk-go] / doc / eyes.texi

The purpose of this Chapter is to describe the algorithm used in
GNU Go to determine eyes.

@menu
* Local Games::                 Local games
* Eye Space::                   Eye space
* Eye Space as Local Game::     Eye space as local game
* Eye Example::                 An example
* Graphs::                      Underlying graphs
* Eye Shape::                   Pattern matching
* Eye Local Game Values::       Pattern matching
* Eye Topology::                False eyes and half eyes
* Eye Topology with Ko::        False eyes and half eyes with ko
* False Margins::               False margins
* Eye Functions::               Functions in @file{optics.c}
@end menu

@node Local Games
@section Local games

The fundamental paradigm of combinatorial game theory is that games
can be added and in fact form a group. If @samp{G} and @samp{H} are
games, then @samp{G+H} is a game in which each player on his turn
has the option of playing in either move. We say that the game
@samp{G+H} is the sum of the local games @samp{G} and @samp{H}.

Each connected eyespace of a dragon affords a local game which yields
a local game tree. The score of this local game is the number of eyes
it yields. Usually if the players take turns and make optimal moves,
the end scores will differ by 0 or 1. In this case, the local game may
be represented by a single number, which is an integer or half
integer. Thus if @samp{n(O)} is the score if @samp{O} moves first,
both players alternate (no passes) and make alternate moves, and
similarly @samp{n(X)}, the game can be represented by
@samp{@{n(O)|n(X)@}}. Thus @{1|1@} is an eye, @{2|1@} is an eye plus a
half eye, etc.

The exceptional game @{2|0@} can occur, though rarely. We call
an eyespace yielding this local game a CHIMERA.  The dragon
is alive if any of the local games ends up with a score of 2
or more, so @{2|1@} is not different from @{3|1@}. Thus @{3|1@} is
NOT a chimera. 

Here is an example of a chimera:

@example
@group
XXXXX
XOOOX
XO.OOX
XX..OX
XXOOXX
XXXXX
@end group
@end example

@node Eye Space
@section Eye spaces

In order that each eyespace be assignable to a dragon,
it is necessary that all the dragons surrounding it
be amalgamated (@pxref{Amalgamation}). This is the
function of @code{dragon_eye()}.

An EYE SPACE for a black dragon is a collection of vertices
adjacent to a dragon which may not yet be completely closed off,
but which can potentially become eyespace. If an open eye space is
sufficiently large, it will yield two eyes. Vertices at the edge
of the eye space (adjacent to empty vertices outside the eye space)
are called MARGINAL.

Here is an example from a game:

@example
@group

 |. X . X X . . X O X O 
 |X . . . . . X X O O O
 |O X X X X . . X O O O
 |O O O O X . O X O O O
 |. . . . O O O O X X O
 |X O . X X X . . X O O
 |X O O O O O O O X X O
 |. X X O . O X O . . X
 |X . . X . X X X X X X
 |O X X O X . X O O X O

@end group
@end example

Here the @samp{O} dragon which is surrounded in the center has open
eye space. In the middle of this open eye space are three
dead @samp{X} stones. This space is large enough that O cannot be
killed. We can abstract the properties of this eye shape as follows.
Marking certain vertices as follows:

@example
@group

 |- X - X X - - X O X O 
 |X - - - - - X X O O O
 |O X X X X - - X O O O
 |O O O O X - O X O O O
 |! . . . O O O O X X O
 |X O . X X X . ! X O O
 |X O O O O O O O X X O
 |- X X O - O X O - - X
 |X - - X - X X X X X X
 |O X X O X - X O O X O

@end group
@end example

@noindent
the shape in question has the form:

@example
@group

!...
  .XXX.!

@end group
@end example

The marginal vertices are marked with an exclamation point (@samp{!}).
The captured @samp{X} stones inside the eyespace are naturally marked @samp{X}.

The precise algorithm by which the eye spaces are determined is
somewhat complex. Documentation of this algorithm is in the
comments in the source to the function @code{make_domains()} in
@file{optics.c}.

The eyespaces can be conveniently displayed using a colored 
ascii diagram by running @command{gnugo -E}.

@node Eye Space as Local Game
@section The eyespace as local game

In the abstraction, an eyespace consists of a set of vertices
labelled:

@example

!  .  X

@end example

Tables of many eyespaces are found in the database
@file{patterns/eyes.db}. Each of these may be thought of as a local
game. The result of this game is listed after the eyespace in the form
@code{:max,min}, where @code{max} is the number of eyes the pattern
yields if @samp{O} moves first, while @code{min} is the number of eyes
the pattern yields if @samp{X} moves first. The player who owns the eye
space is denoted @samp{O} throughout this discussion. Since three eyes
are no better than two, there is no attempt to decide whether the space
yields two eyes or three, so max never exceeds 2. Patterns with min>1
are omitted from the table.

For example, we have:

@example
@group
Pattern 548

 x
xX.!

:0111

@end group
@end example

Here notation is as above, except that @samp{x} means @samp{X} or 
@code{EMPTY}.  The result of the pattern is not different if @samp{X} has
stones at these vertices or not.

We may abstract the local game as follows. The two players @samp{O}
and @samp{X} take turns moving, or either may pass.

RULE 1: @samp{O} for his move may remove any vertex marked @samp{!}
or marked @samp{.}.

RULE 2: @samp{X} for his move may replace a @samp{.} by an @samp{X}. 

RULE 3: @samp{X} may remove a @samp{!}. In this case, each @samp{.}
adjacent to the @samp{!} which is removed becomes a @samp{!} . If an
@samp{X} adjoins the @samp{!} which is removed, then that @samp{X}
and any which are connected to it are also removed. Any @samp{.} which
are adjacent to the removed @samp{X}'s then become @samp{.}.

Thus if @samp{O} moves first he can transform the eyeshape in
the above example to:

@example
@group
 ...            or      !...
  .XXX.!                  .XXX.
@end group
@end example

However if @samp{X} moves he may remove the @samp{!} and the @samp{.}s
adjacent to the @samp{!} become @samp{!} themselves. Thus if @samp{X}
moves first he may transform the eyeshape to:

@example
@group
 !..           or    !..
  .XXX.!              .XXX!
@end group
@end example

NOTE: A nuance which is that after the @samp{X:1}, @samp{O:2}
exchange below, @samp{O} is threatening to capture three X stones,
hence has a half eye to the left of 2.  This is subtle, and there are
other such subtleties which our abstraction will not capture. Some of
these at least can be dealt with by a refinements of the scheme, but
we will content ourselves for the time being with a simplified model.

@example
@group

 |- X - X X - - X O X O 
 |X - - - - - X X O O O
 |O X X X X - - X O O O
 |O O O O X - O X O O O
 |1 2 . . O O O O X X O
 |X O . X X X . 3 X O O
 |X O O O O O O O X X O
 |- X X O - O X O - - X
 |X - - X - X X X X X X
 |O X X O X - X O O X O

@end group
@end example

We will not attempt to characterize the terminal states
of the local game (some of which could be seki) or
the scoring. 

@node Eye Example
@section An example

Here is a local game which yields exactly one
eye, no matter who moves first:

@example
@group

!
...
...!

@end group
@end example

Here are some variations, assuming @samp{O} moves first.

@example
@group
!        (start position)
...
...!
@end group


@group
...      (after @samp{O}'s move)
...!
@end group


@group
... 
..!
@end group


@group
... 
..
@end group


@group
.X.       (nakade)
..
@end group
@end example

Here is another variation:

@example

@group
!         (start)
...
...!
@end group


@group
!         (after @samp{O}'s move)
. .
...!
@end group


@group
!         (after @samp{X}'s move)
. .
..X!
@end group


@group
. .
..X!
@end group


@group
. !
.!
@end group
@end example


@node Graphs
@section Graphs

It is a useful observation that the local game associated
with an eyespace depends only on the underlying graph, which
as a set consists of the set of vertices, in which two elements
are connected by an edge if and only if they are adjacent on
the Go board. For example the two eye shapes:

@example

..
 ..

and

....

@end example

@noindent
though distinct in shape have isomorphic graphs, and consequently
they are isomorphic as local games. This reduces the number of
eyeshapes in the database @file{patterns/eyes.db}.

A further simplification is obtained through our treatment of
half eyes and false eyes. Such patterns are identified by the
topological analysis (@pxref{Eye Topology}).

A half eye is isomorphic to the pattern @code{(!.)} . To see this,
consider the following two eye shapes:

@example
@group 
XOOOOOO
X.....O
XOOOOOO

@end group
and:
@group

XXOOOOO
XOa...O
XbOOOOO
XXXXXXX

@end group
@end example

These are equivalent eyeshapes, with isomorphic local games @{2|1@}.
The first has shape:

@example

!....

@end example

The second eyeshape has a half eye at @samp{a} which is taken when @samp{O} 
or @samp{X} plays at @samp{b}. This is found by the topological
criterion (@pxref{Eye Topology}).

The graph of the eye_shape, ostensibly @samp{....} is modified by replacing
the left @samp{.} by @samp{!.} during graph matching.


A false eye is isomorphic to the pattern @code{(!)} . To see this,
consider the following eye shape:

@example

XXXOOOOOO
X.Oa....O
XXXOOOOOO

@end example

This is equivalent to the two previous eyeshapes, with an isomorphic
local game @{2|1@}.

This eyeshape has a false eye at @samp{a}. This is also found by the
topological criterion.

The graph of the eye_shape, ostensibly @samp{.....} is modified by replacing
the left @samp{.} by @samp{!}. This is made directly in the eye data,
not only during graph matching.

@node Eye Shape
@section Eye shape analysis

The patterns in @file{patterns/eyes.db} are compiled into graphs
represented essentially by arrays in @file{patterns/eyes.c}.

Each actual eye space as it occurs on the board is also
compiled into a graph. Half eyes are handled as follows.
Referring to the example 

@example
@group
XXOOOOO
XOa...O
XbOOOOO
XXXXXX
@end group
@end example

@noindent
repeated from the preceding discussion, the vertex at @samp{b} is
added to the eyespace as a marginal vertex. The adjacency
condition in the graph is a macro (in @file{optics.c}): two
vertices are adjacent if they are physically adjacent, 
or if one is a half eye and the other is its key point.

In @code{recognize_eyes()}, each such graph arising from an actual eyespace is
matched against the graphs in @file{eyes.c}.  If a match is found, the
result of the local game is known. If a graph cannot be matched, its
local game is assumed to be @{2|2@}.

@node Eye Local Game Values
@section Eye Local Game Values

The game values in @file{eyes.db} are given in a simplified scheme which is
flexible enough to represent most possibilities in a useful way.

The colon line below the pattern gives the eye value of the matched
eye shape. This consists of four digits, each of which is the number
of eyes obtained during the following conditions:

@enumerate
@item The attacker moves first and is allowed yet another move because
the defender plays tenuki.
@item The attacker moves first and the defender responds locally.
@item The defender moves first and the attacker responds locally.
@item The defender moves first and is allowed yet another move because
the attacker plays tenuki.
@end enumerate

The first case does @strong{not} necessarily mean that the attacker is
allowed two consecutive moves. This is explained with an example
later.

Also, since two eyes suffice to live, all higher numbers also count
as two.

The following 15 cases are of interest:

@itemize @bullet
@item 0000 0 eyes.
@item 0001 0 eyes, but the defender can threaten to make one eye.
@item 0002 0 eyes, but the defender can threaten to make two eyes.
@item 0011 1/2 eye, 1 eye if defender moves first, 0 eyes if attacker does.
@item 0012 3/4 eyes, 3/2 eyes if defender moves first, 0 eyes if attacker does.
@item 0022 1* eye, 2 eyes if defender moves first, 0 eyes if attacker does.
@item 0111 1 eye, attacker can threaten to destroy the eye.
@item 0112 1 eye, attacker can threaten to destroy the eye, defender can threaten to make another eye.
@item 0122 5/4 eyes, 2 eyes if defender moves first, 1/2 eye if attacker does.
@item 0222 2 eyes, attacker can threaten to destroy both.
@item 1111 1 eye.
@item 1112 1 eye, defender can threaten to make another eye.
@item 1122 3/2 eyes, 2 eyes if defender moves first, 1 eye if attacker does.
@item 1222 2 eyes, attacker can threaten to destroy one eye.
@item 2222 2 eyes.
@end itemize

The 3/4, 5/4, and 1* eye values are the same as in Howard Landman's paper
Eyespace Values in Go. Attack and defense points are only marked in
the patterns when they have definite effects on the eye value,
i.e. pure threats are not marked.

Examples of all different cases can be found among the patterns in
this file. Some of them might be slightly counterintuitive, so we
explain one important case here. Consider

@example
@group
Pattern 6141

 X
XX.@@x

:1122
@end group
@end example

which e.g. matches in this position:

@example
@group
.OOOXXX
OOXOXOO
OXXba.O
OOOOOOO
@end group
@end example

Now it may look like @samp{X} could take away both eyes by playing @samp{a}
followed by @samp{b}, giving 0122 as eye value. This is where the subtlety
of the definition of the first digit in the eye value comes into
play. It does not say that the attacker is allowed two consecutive
moves but only that he is allowed to play "another move". The
crucial property of this shape is that when @samp{X} plays at a to destroy
(at least) one eye, @samp{O} can answer at @samp{b}, giving:

@example
@group

.OOOXXX
OO.OXOO
O.cOX.O
OOOOOOO

@end group
@end example

Now @samp{X} has to continue at @samp{c} in order to keep @samp{O}
at one eye. After this @samp{O} plays tenuki and @samp{X} cannot
destroy the remaining eye by another move. Thus the eye value is
indeed 1122.

As a final note, some of the eye values indicating a threat depend
on suicide to be allowed, e.g.

@example
@group

Pattern 301
 
X.X

:1222

@end group
@end example

We always assume suicide to be allowed in this database. It is easy
enough to sort out such moves at a higher level when suicide is
disallowed.

@node Eye Topology
@section Topology of Half Eyes and False Eyes

A HALF EYE is a pattern where an eye may or may not materialize,
depending on who moves first. Here is a half eye for @code{O}:

@example
@group

   OOXX
   O.O.
   OO.X

@end group
@end example

A FALSE EYE is an eye vertex which cannot become a proper eye. Here are
two examples of false eyes for @code{O}:

@example
@group

   OOX         OOX
   O.O         O.OO
   XOO         OOX

@end group
@end example

We describe now the topological algorithm used to find half eyes
and false eyes. In this section we ignore the possibility of ko.

False eyes and half eyes can locally be characterized by the status of
the diagonal intersections from an eye space. For each diagonal
intersection, which is not within the eye space, there are three
distinct possibilities:

@itemize @bullet
@item occupied by an enemy (@code{X}) stone, which cannot be captured.
@item either empty and @code{X} can safely play there, or occupied
   by an @code{X} stone that can both be attacked and defended.
@item occupied by an @code{O} stone, an @code{X} stone that can be attacked
   but not defended, or it's empty and @code{X} cannot safely play there.
@end itemize

We give the first possibility a value of two, the second a value of
one, and the last a value of zero. Summing the values for the diagonal
intersections, we have the following criteria:

@itemize @bullet
@item sum >= 4: false eye
@item sum == 3: half eye
@item sum <= 2: proper eye
@end itemize

If the eye space is on the edge, the numbers above should be decreased
by 2. An alternative approach is to award diagonal points which are
outside the board a value of 1. To obtain an exact equivalence we must
however give value 0 to the points diagonally off the corners, i.e.
the points with both coordinates out of bounds.

The algorithm to find all topologically false eyes and half eyes is:

For all eye space points with at most one neighbor in the eye space,
evaluate the status of the diagonal intersections according to the
criteria above and classify the point from the sum of the values.

@node  Eye Topology with Ko
@section Eye Topology with Ko


This section extends the topological eye analysis to handle ko. We
distinguish between a ko in favor of @samp{O} and one in favor of @samp{X}:

@example
@group
.?O?   good for O
OO.O
O.O?
XOX.
.X..

@end group
@group
.?O?   good for X
OO.O
OXO?
X.X.
.X..
@end group
@end example

Preliminarily we give the former the symbolic diagonal value @code{a}
and the latter the diagonal value @code{b}. We should clearly have
@code{0 < a < 1 < b < 2}. Letting @code{e} be the topological eye value
(still the sum of the four diagonal values), we want to have the
following properties:

@example
e <= 2     - proper eye
2 < e < 3  - worse than proper eye, better than half eye
e = 3      - half eye
3 < e < 4  - worse than half eye, better than false eye
e >= 4     - false eye
@end example

In order to determine the appropriate values of @code{a} and @code{b} we
analyze the typical cases of ko contingent topological eyes:

@example
@group
      .X..      (slightly) better than proper eye
(a)   ..OO          e < 2
      OO.O
      O.OO      e = 1 + a
      XOX.
      .X..

@end group

@group      
      .X..      better than half eye, worse than proper eye
(a')  ..OO      2 < e < 3
      OO.O
      OXOO      e = 1 + b
      X.X.
      .X..

@end group
      
@group
      .X..      better than half eye, worse than proper eye
(b)   .XOO      2 < e < 3
      OO.O
      O.OO      e = 2 + a
      XOX.
      .X..

@end group
      
@group
      .X..      better than false eye, worse than half eye
(b')  .XOO      3 < e < 4
      OO.O
      OXOO      e = 2 + b
      X.X.
      .X..

@end group
      
@group
      .X..
      XOX.      (slightly) better than proper eye
(c)   O.OO          e < 2
      OO.O
      O.OO      e = 2a
      XOX.
      .X..

@end group
      
@group
      .X..
      XOX.      proper eye, some aji
(c')  O.OO      e ~ 2
      OO.O
      OXOO      e = a + b
      X.X.
      .X..

@end group
      
@group
      .X..
      X.X.      better than half eye, worse than proper eye
(c'') OXOO      2 < e < 3
      OO.O
      OXOO      e = 2b
      X.X.
      .X..

@end group
      
@group
      .X...
      XOX..     better than half eye, worse than proper eye
(d)   O.O.X     2 < e < 3
      OO.O.
      O.OO.     e = 1 + 2a
      XOX..
      .X...

@end group
      
@group
      .X...
      XOX..     half eye, some aji
(d')  O.O.X     e ~ 3
      OO.O.
      OXOO.     e = 1 + a + b
      X.X..
      .X...

@end group
      
@group
      .X...
      X.X..     better than false eye, worse than half eye
(d'') OXO.X     3 < e < 4
      OO.O.
      OXOO.     e = 1 + 2b
      X.X..
      .X...

@end group
      
@group
      .X...
      XOX..     better than false eye, worse than half eye
(e)   O.OXX     3 < e < 4
      OO.O.
      O.OO.     e =  2 + 2a
      XOX..
      .X...

@end group
      
@group
      .X...
      XOX..     false eye, some aji
(e')  O.OXX     e ~ 4
      OO.O.
      OXOO.     e = 2 + a + b
      X.X..
      .X...

@end group
      
@group
      .X...
      X.X..     (slightly) worse than false eye
(e'') OXOXX     4 < e
      OO.O.
      OXOO.     e = 2 + 2b
      X.X..
      .X...

@end group
@end example      

It may seem obvious that we should use
@example
(i)   a=1/2, b=3/2
@end example
but this turns out to have some drawbacks. These can be solved by
using either of
@example
(ii)  a=2/3, b=4/3
(iii) a=3/4, b=5/4
(iv)  a=4/5, b=6/5

@end example

Summarizing the analysis above we have the following table for the
four different choices of @code{a} and @code{b}.

@example
case    symbolic        a=1/2   a=2/3   a=3/4   a=4/5   desired
        value           b=3/2   b=4/3   b=5/4   b=6/5   interval
(a)     1+a             1.5     1.67    1.75    1.8         e < 2
(a')    1+b             2.5     2.33    2.25    2.2     2 < e < 3
(b)     2+a             2.5     2.67    2.75    2.8     2 < e < 3
(b')    2+b             3.5     3.33    3.25    3.2     3 < e < 4
(c)     2a              1       1.33    1.5     1.6         e < 2
(c')    a+b             2       2       2       2           e ~ 2
(c'')   2b              3       2.67    2.5     2.4     2 < e < 3
(d)     1+2a            2       2.33    2.5     2.6     2 < e < 3
(d')    1+a+b           3       3       3       3           e ~ 3
(d'')   1+2b            4       3.67    3.5     3.4     3 < e < 4
(e)     2+2a            3       3.33    3.5     3.6     3 < e < 4
(e')    2+a+b           4       4       4       4           e ~ 4
(e'')   2+2b            5       4.67    4.5     4.4     4 < e

@end example

We can notice that (i) fails for the cases (c''), (d), (d''), and (e).
The other three choices get all values in the correct intervals. The
main distinction between them is the relative ordering of (c'') and (d)
(or analogously (d'') and (e)). If we do a more detailed analysis of
these we can see that in both cases @samp{O} can secure the eye
unconditionally if he moves first while @samp{X} can falsify it with ko
if he moves first. The difference is that in (c''), @samp{X} has to make
the first ko threat, while in (d), O has to make the first ko threat.
Thus (c'') is better for O and ought to have a smaller topological eye
value than (d). This gives an indication that (iv) is the better choice.

We can notice that any value of @code{a}, @code{b} satisfying
@code{a+b=2} and @code{3/4<a<1} would have the same qualities as choice
(iv) according to the analysis above. One interesting choice is
@code{a=7/8, b=9/8} since these allow exact computations with floating
point values having a binary mantissa. The latter property is shared by
@code{a=3/4} and @code{a=1/2}.

When there are three kos around the same eyespace, things become
more complex. This case is, however, rare enough that we ignore it.


@node False Margins
@section False Margins

The following situation is rare but special enough to warrant separate
attention:

@example
@group
   OOOOXX
   OXaX..
   ------
@end group
@end example

Here @samp{a} may be characterized by the fact that it is adjacent
to O's eyespace, and it is also adjacent to an X group which cannot
be attacked, but that an X move at 'a' results in a string with only
one liberty. We call this a @dfn{false margin}. 

For the purpose of the eye code, O's eyespace should be parsed
as @code{(X)}, not @code{(X!)}.

@node Eye Functions
@section Functions in @file{optics.c}

The public function @code{make_domains()} calls the function
@code{make_primary_domains()} which is static in @file{optics.c}. It's purpose
is to compute the domains of influence of each color, used in determining eye
shapes. @strong{Note}: the term influence as used here is distinct from the
influence in influence.c.

For this algorithm the strings which are not lively are invisible. Ignoring
these, the algorithm assigns friendly influence to

@enumerate
@item every vertex which is occupied by a (lively) friendly stone, 
@item every empty vertex adjoining a (lively) friendly stone,
@item every empty vertex for which two adjoining vertices (not
on the first line) in the (usually 8) surrounding ones have friendly
influence, with two CAVEATS explained below.
@end enumerate

Thus in the following diagram, @samp{e} would be assigned friendly influence
if @samp{a} and @samp{b} have friendly influence, or @samp{a} and @samp{d}. It
is not sufficent for @samp{b} and @samp{d} to have friendly influence, because
they are not adjoining.

@example
       uabc
        def
        ghi
@end example

The constraint that the two adjoining vertices not lie on the first
line prevents influence from leaking under a stone on the third line.

The first CAVEAT alluded to above is that even if @samp{a} and @samp{b} have
friendly influence, this does not cause @samp{e} to have friendly influence if
there is a lively opponent stone at @samp{d}. This constraint prevents
influence from leaking past knight's move extensions.

The second CAVEAT is that even if @samp{a} and @samp{b} have friendly influence
this does not cause @samp{e} to have influence if there are lively opponent
stones at @samp{u} and at @samp{c}. This prevents influence from leaking past
nikken tobis (two space jumps).  

The corner vertices are handled slightly different.

@example
   +---
   |ab
   |cd
@end example

We get friendly influence at @samp{a} if we have friendly influence
at @samp{b} or @samp{c} and no lively unfriendly stone at @samp{b}, @samp{c}
or @samp{d}.

Here are the public functions in @file{optics.c}, except some simple
access functions used by autohelpers. The statically declared functions
are documented in the source code.

@itemize @bullet 
@item @code{void make_domains(struct eye_data b_eye[BOARDMAX], struct eye_data w_eye[BOARDMAX], int owl_call)}
@findex make_domains
@quotation
This function is called from @code{make_dragons()} and from
@code{owl_determine_life()}. It marks the black and white domains
(eyeshape regions) and collects some statistics about each one.
@end quotation
@item @code{void partition_eyespaces(struct eye_data eye[BOARDMAX], int color)}
@findex partition_eyespaces
@quotation
Find connected eyespace components and compute relevant statistics.
@end quotation
@item @code{void propagate_eye(int origin, struct eye_data eye[BOARDMAX])}
@findex propagate_eye
@quotation
propagate_eye(origin) copies the data at the (origin) to the
rest of the eye (invariant fields only).
@end quotation
@item @code{int find_eye_dragons(int origin, struct eye_data eye[BOARDMAX], int eye_color, int dragons[], int max_dragons)}
@findex find_eye_dragons
@quotation
Find the dragon or dragons surrounding an eye space. Up to
max_dragons dragons adjacent to the eye space are added to
the dragon array, and the number of dragons found is returned.
@end quotation
@item @code{void compute_eyes(int pos, struct eyevalue *value, int *attack_point, int *defense_point, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX], int add_moves)}
@findex compute_eyes
@quotation
Given an eyespace with origin @code{pos}, this function computes the
minimum and maximum numbers of eyes the space can yield. If max and
min are different, then vital points of attack and defense are also
generated. If @code{add_moves == 1}, this function may add a move_reason for
@code{color} at a vital point which is found by the function. If 
@code{add_moves == 0}, set @code{color = EMPTY.}
@end quotation
@item @code{void compute_eyes_pessimistic(int pos, struct eyevalue *value, int *pessimistic_min, int *attack_point, int *defense_point, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX])}
@findex compute_eyes_pessimistic
@quotation
This function works like @code{compute_eyes()}, except that it also gives
a pessimistic view of the chances to make eyes. Since it is intended
to be used from the owl code, the option to add move reasons has
been removed.
@end quotation
@item @code{void add_false_eye(int pos, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX])}
@findex add_false_eye
@quotation
turns a proper eyespace into a margin. 
@end quotation
@item @code{int is_eye_space(int pos)}
@item @code{int is_proper_eye_space(int pos)}
@findex is_proper_eye_space
@findex is_eye_space
@quotation
These functions are used from constraints to identify eye spaces,
primarily for late endgame moves.
@end quotation
@item @code{int max_eye_value(int pos)}
@findex max_eye_value
@quotation
Return the maximum number of eyes that can be obtained from the
eyespace at @code{(i, j)}. This is most useful in order to determine
whether the eyespace can be assumed to produce any territory at
all.
@end quotation
@item @code{int is_marginal_eye_space(int pos)}
@item @code{int is_halfeye(struct half_eye_data heye[BOARDMAX], int pos)}
@item @code{int is_false_eye(struct half_eye_data heye[BOARDMAX], int pos)}
@findex is_marginal_eye_space
@findex is_halfeye
@findex is_false_eye
@quotation
These functions simply return information about an eyeshape that
has already been analyzed. (They do no real work.)
@end quotation
@item @code{void find_half_and_false_eyes(int color, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX], int find_mask[BOARDMAX])}
@findex find_half_and_false_eyes
@quotation
Find topological half eyes and false eyes by analyzing the
diagonal intersections, as described in the Texinfo
documentation (Eyes/Eye Topology).
@end quotation
@item @code{float topological_eye(int pos, int color, struct eye_data my_eye[BOARDMAX],struct half_eye_data heye[BOARDMAX])}
@findex topological_eye
@quotation
See Texinfo documentation (Eyes:Eye Topology). Returns:
@itemize @bullet
@item 2 or less if @code{pos} is a proper eye for @code{color};
@item between 2 and 3 if the eye can be made false only by ko
@item 3 if @code{pos} is a half eye;
@item between 3 and 4 if the eye can be made real only by ko
@item 4 or more if @code{pos} is a false eye.
@end itemize
Attack and defense points for control of the diagonals are stored
in the @code{heye[]} array.
@code{my_eye} is the eye space information with respect to @code{color}.
@end quotation
@item @code{int obvious_false_eye(int pos, int color)}
@findex obvious_false_eye
@quotation
Conservative relative of @code{topological_eye()}. Essentially the same
algorithm is used, but only tactically safe opponent strings on
diagonals are considered. This may underestimate the false/half eye
status, but it should never be overestimated.
@end quotation
@item @code{void set_eyevalue(struct eyevalue *e, int a, int b, int c, int d)}
@findex set_eyevalue
@quotation set parameters into the @code{struct eyevalue} as follows
(@pxref{Eye Local Game Values}):
@example
struct eyevalue @{ /* number of eyes if: */
  unsigned char a; /* attacker plays first twice */
  unsigned char b; /* attacker plays first */
  unsigned char c; /* defender plays first */
  unsigned char d; /* defender plays first twice */
@};
@end example
@end quotation
@item @code{int min_eye_threat(struct eyevalue *e)}
@findex min_eye_threat
@quotation
Number of eyes if attacker plays first twice (the threat of the first
move by attacker).
@end quotation
@item @code{int min_eyes(struct eyevalue *e)}
@findex min_eyes
@quotation
Number of eyes if attacker plays first followed by alternating play. 
@end quotation
@item @code{int max_eyes(struct eyevalue *e)}
@findex max_eyes
@quotation
Number of eyes if defender plays first followed by alternating play. 
@end quotation
@item @code{int max_eye_threat(struct eyevalue *e)}
@findex max_eye_threat
@quotation
Number of eyes if defender plays first twice (the threat of the first
move by defender).
@end quotation
@item @code{void add_eyevalues(struct eyevalue *e1, struct eyevalue *e2, struct eyevalue *sum)}
@findex add_eyevalues
@quotation
Add the eyevalues @code{*e1} and @code{*e2}, leaving the result in *sum. It is
safe to let @code{sum} be the same as @code{e1} or @code{e2}.
@end quotation
@item @code{char * eyevalue_to_string(struct eyevalue *e)}
@findex eyevalue_to_string
@quotation
Produces a string containing the eyevalue. @strong{Note}: the result string is
stored in a statically allocated buffer which will be overwritten the next
time this function is called.
@end quotation
@item @code{void test_eyeshape(int eyesize, int *eye_vertices)}
@findex test_eyeshape
/* Test whether the optics code evaluates an eyeshape consistently. */
@item @code{int analyze_eyegraph(const char *coded_eyegraph, struct eyevalue *value, char *analyzed_eyegraph)}
@findex analyze_eyegraph
@quotation
Analyze an eye graph to determine the eye value and vital moves.
The eye graph is given by a string which is encoded with @samp{%} for
newlines and @samp{O} for spaces. E.g., the eye graph

@example
  !
 .X
!...
@end example
	
is encoded as @code{OO!%O.X%!...}. (The encoding is needed for the GTP
interface to this function.) The result is an eye value and a (nonencoded)
pattern showing the vital moves, using the same notation as eyes.db. In the
example above we would get the eye value 0112 and the graph (showing ko threat
moves)

@example
  @  
 .X  
!.*.
@end example

If the eye graph cannot be realized, 0 is returned, 1 otherwise.
@end quotation
@end itemize