[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The purpose of this Chapter is to describe the algorithm used in GNU Go to determine eyes.
8.1 Local games | ||
8.2 Eye spaces | Eye space | |
8.3 The eyespace as local game | Eye space as local game | |
8.4 An example | ||
8.5 Graphs | Underlying graphs | |
8.6 Eye shape analysis | Pattern matching | |
8.7 Eye Local Game Values | Pattern matching | |
8.8 Topology of Half Eyes and False Eyes | False eyes and half eyes | |
8.9 Eye Topology with Ko | False eyes and half eyes with ko | |
8.10 False Margins | False margins | |
8.11 Functions in `optics.c' |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The fundamental paradigm of combinatorial game theory is that games can be added and in fact form a group. If `G' and `H' are games, then `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 `G+H' is the sum of the local games `G' and `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 `n(O)' is the score if `O' moves first, both players alternate (no passes) and make alternate moves, and similarly `n(X)', the game can be represented by `{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:
XXXXX XOOOX XO.OOX XX..OX XXOOXX XXXXX |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
In order that each eyespace be assignable to a dragon,
it is necessary that all the dragons surrounding it
be amalgamated (see section 7.2 Amalgamation). This is the
function of 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:
|. 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 |
Here the `O' dragon which is surrounded in the center has open eye space. In the middle of this open eye space are three dead `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:
|- 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 |
the shape in question has the form:
!... .XXX.! |
The marginal vertices are marked with an exclamation point (`!'). The captured `X' stones inside the eyespace are naturally marked `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 make_domains()
in
`optics.c'.
The eyespaces can be conveniently displayed using a colored
ascii diagram by running gnugo -E
.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
In the abstraction, an eyespace consists of a set of vertices labelled:
! . X |
Tables of many eyespaces are found in the database
`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
:max,min
, where max
is the number of eyes the pattern
yields if `O' moves first, while min
is the number of eyes
the pattern yields if `X' moves first. The player who owns the eye
space is denoted `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:
Pattern 548 x xX.! :0111 |
Here notation is as above, except that `x' means `X' or
EMPTY
. The result of the pattern is not different if `X' has
stones at these vertices or not.
We may abstract the local game as follows. The two players `O' and `X' take turns moving, or either may pass.
RULE 1: `O' for his move may remove any vertex marked `!' or marked `.'.
RULE 2: `X' for his move may replace a `.' by an `X'.
RULE 3: `X' may remove a `!'. In this case, each `.' adjacent to the `!' which is removed becomes a `!' . If an `X' adjoins the `!' which is removed, then that `X' and any which are connected to it are also removed. Any `.' which are adjacent to the removed `X''s then become `.'.
Thus if `O' moves first he can transform the eyeshape in the above example to:
... or !... .XXX.! .XXX. |
However if `X' moves he may remove the `!' and the `.'s adjacent to the `!' become `!' themselves. Thus if `X' moves first he may transform the eyeshape to:
!.. or !.. .XXX.! .XXX! |
NOTE: A nuance which is that after the `X:1', `O:2' exchange below, `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.
|- 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 |
We will not attempt to characterize the terminal states of the local game (some of which could be seki) or the scoring.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Here is a local game which yields exactly one eye, no matter who moves first:
! ... ...! |
Here are some variations, assuming `O' moves first.
! (start position) ... ...! ... (after `O''s move) ...! ... ..! ... .. .X. (nakade) .. |
Here is another variation:
! (start) ... ...! ! (after `O''s move) . . ...! ! (after `X''s move) . . ..X! . . ..X! . ! .! |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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:
.. .. and .... |
though distinct in shape have isomorphic graphs, and consequently they are isomorphic as local games. This reduces the number of eyeshapes in the database `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 (see section 8.8 Topology of Half Eyes and False Eyes).
A half eye is isomorphic to the pattern (!.)
. To see this,
consider the following two eye shapes:
XOOOOOO X.....O XOOOOOO and: XXOOOOO XOa...O XbOOOOO XXXXXXX |
These are equivalent eyeshapes, with isomorphic local games {2|1}. The first has shape:
!.... |
The second eyeshape has a half eye at `a' which is taken when `O' or `X' plays at `b'. This is found by the topological criterion (see section 8.8 Topology of Half Eyes and False Eyes).
The graph of the eye_shape, ostensibly `....' is modified by replacing the left `.' by `!.' during graph matching.
A false eye is isomorphic to the pattern (!)
. To see this,
consider the following eye shape:
XXXOOOOOO X.Oa....O XXXOOOOOO |
This is equivalent to the two previous eyeshapes, with an isomorphic local game {2|1}.
This eyeshape has a false eye at `a'. This is also found by the topological criterion.
The graph of the eye_shape, ostensibly `.....' is modified by replacing the left `.' by `!'. This is made directly in the eye data, not only during graph matching.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The patterns in `patterns/eyes.db' are compiled into graphs represented essentially by arrays in `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
XXOOOOO XOa...O XbOOOOO XXXXXX |
repeated from the preceding discussion, the vertex at `b' is added to the eyespace as a marginal vertex. The adjacency condition in the graph is a macro (in `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 recognize_eyes()
, each such graph arising from an actual eyespace is
matched against the graphs in `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}.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The game values in `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:
The first case does 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:
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
Pattern 6141 X XX.@x :1122 |
which e.g. matches in this position:
.OOOXXX OOXOXOO OXXba.O OOOOOOO |
Now it may look like `X' could take away both eyes by playing `a' followed by `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 `X' plays at a to destroy (at least) one eye, `O' can answer at `b', giving:
.OOOXXX OO.OXOO O.cOX.O OOOOOOO |
Now `X' has to continue at `c' in order to keep `O' at one eye. After this `O' plays tenuki and `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.
Pattern 301 X.X :1222 |
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.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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 O
:
OOXX O.O. OO.X |
A FALSE EYE is an eye vertex which cannot become a proper eye. Here are
two examples of false eyes for O
:
OOX OOX O.O O.OO XOO OOX |
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:
X
) stone, which cannot be captured.
X
can safely play there, or occupied
by an X
stone that can both be attacked and defended.
O
stone, an X
stone that can be attacked
but not defended, or it's empty and X
cannot safely play there.
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:
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.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This section extends the topological eye analysis to handle ko. We distinguish between a ko in favor of `O' and one in favor of `X':
.?O? good for O OO.O O.O? XOX. .X.. .?O? good for X OO.O OXO? X.X. .X.. |
Preliminarily we give the former the symbolic diagonal value a
and the latter the diagonal value b
. We should clearly have
0 < a < 1 < b < 2
. Letting e
be the topological eye value
(still the sum of the four diagonal values), we want to have the
following properties:
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 |
In order to determine the appropriate values of a
and b
we
analyze the typical cases of ko contingent topological eyes:
.X.. (slightly) better than proper eye (a) ..OO e < 2 OO.O O.OO e = 1 + a XOX. .X.. .X.. better than half eye, worse than proper eye (a') ..OO 2 < e < 3 OO.O OXOO e = 1 + b X.X. .X.. .X.. better than half eye, worse than proper eye (b) .XOO 2 < e < 3 OO.O O.OO e = 2 + a XOX. .X.. .X.. better than false eye, worse than half eye (b') .XOO 3 < e < 4 OO.O OXOO e = 2 + b X.X. .X.. .X.. XOX. (slightly) better than proper eye (c) O.OO e < 2 OO.O O.OO e = 2a XOX. .X.. .X.. XOX. proper eye, some aji (c') O.OO e ~ 2 OO.O OXOO e = a + b X.X. .X.. .X.. X.X. better than half eye, worse than proper eye (c'') OXOO 2 < e < 3 OO.O OXOO e = 2b X.X. .X.. .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... .X... XOX.. half eye, some aji (d') O.O.X e ~ 3 OO.O. OXOO. e = 1 + a + b X.X.. .X... .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... .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... .X... XOX.. false eye, some aji (e') O.OXX e ~ 4 OO.O. OXOO. e = 2 + a + b X.X.. .X... .X... X.X.. (slightly) worse than false eye (e'') OXOXX 4 < e OO.O. OXOO. e = 2 + 2b X.X.. .X... |
It may seem obvious that we should use
(i) a=1/2, b=3/2 |
(ii) a=2/3, b=4/3 (iii) a=3/4, b=5/4 (iv) a=4/5, b=6/5 |
Summarizing the analysis above we have the following table for the
four different choices of a
and b
.
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 |
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 `O' can secure the eye unconditionally if he moves first while `X' can falsify it with ko if he moves first. The difference is that in (c"), `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 a
, b
satisfying
a+b=2
and 3/4<a<1
would have the same qualities as choice
(iv) according to the analysis above. One interesting choice is
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
a=3/4
and 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.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The following situation is rare but special enough to warrant separate attention:
OOOOXX OXaX.. ------ |
Here `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 false margin.
For the purpose of the eye code, O's eyespace should be parsed
as (X)
, not (X!)
.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Here are the public functions in `optics.c', except some simple access functions used by autohelpers. The statically declared functions are documented in the source code.
void make_domains(struct eye_data b_eye[BOARDMAX], struct eye_data w_eye[BOARDMAX], int owl_call)
This function is called frommake_dragons()
and fromowl_determine_life()
. It marks the black and white domains (eyeshape regions) and collects some statistics about each one.
void compute_eyes(int pos, int *max, int *min, int *attack_point, int *defense_point, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX], int add_moves, int color)
Given an eyespace with origin 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.
void compute_eyes_pessimistic(int pos, int *max, int *min, int *pessimistic_min, int *attack_point, int *defense_point, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX])
This function works like compute_eyes()
, except that it also gives
a pessimistic view of the chances to make eyes.
void propagate_eye(int origin, struct eye_data eye[BOARDMAX])
Copies the data at origin
to the rest of the eye (invariant
fields only).
static int recognize_eye(int pos, int *attack_point, int *defense_point, int *max, int *min, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX], int add_moves, int color)
Declared static but documented here because of its importance. The life code supplies an alternative version of this function calledrecognize_eye2()
. Herepos
is the origin of an eyespace. Returns 1 if there is a pattern in `eyes.db' matching the eyespace, or 0 if no match is found. If there is a key point for attack,*attack_point
is set to its location, orNO_MOVE
if there is none. Similarly*defense_point
is the location of a vital defense point.*min
and*max
are the minimum and maximum number of eyes that can be made in this eyespace respectively. Vital attack/defense points exist if and only if*min != *max
. Ifadd_moves==1
, this function may add a move_reason forcolor
at a vital point which is found by the function. Ifadd_moves==0
, setcolor==EMPTY
.
void add_false_eye(int pos, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX])
This function turns a proper eyespace into a margin.
float topological_eye(int pos, int color, struct eye_data b_eye[BOARDMAX], struct eye_data w_eye[BOARDMAX], struct half_eye_data heye[BOARDMAX])
See See section 8.8 Topology of Half Eyes and False Eyes. Evaluate the eye space atpos
topologically (see section 8.8 Topology of Half Eyes and False Eyes). Returns 2 or less ifpos
is a proper eye forcolor
; between 2 and 3 if the eye can be made false only by ko; 3 ifpos
is a half eye; between 3 and 4 if the eye can be made real only by ko; 4 ifpos
is a false eye. Attack and defense points for control of the diagonals are stored in theheye[]
array.
[ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |