File: EYES

package info (click to toggle)
gnugo 2.4-2
  • links: PTS
  • area: main
  • in suites: potato
  • size: 1,816 kB
  • ctags: 1,828
  • sloc: ansic: 22,091; tcl: 401; sh: 376; makefile: 202
file content (403 lines) | stat: -rw-r--r-- 10,462 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
                        EYES IN GNU GO

After briefly reviewing the algorithm by which GNU Go 2.0 attempted
to understand life and death, we will describe the algorithm used
in GNU Go 2.4.

                  GNU GO 2.0 ALGORITHMS

GNU Go 2.0 tends to err on the side of pessimism in assessing
eye shape.  That is, if it says a group has two eyes it probably
does but it might see only one or no eyes for some groups which
are actually alive.

This is because GNU Go's algorithm is unfinished. What is now
needed is to determine when a large eye space or open eye will
actually yield two eyes. To give a simple example, GNU Go doesn't
know that this X group is alive:

OOOOOOOO
OXXXXXXO
OX....XO
OXXXXXO
OOOOOOO

We review briefly the process by which GNU Go determines eyeshape.

First, a (for example) blackbordered cavity such as the one above is 
seen as an eye for the black bordered group surrounding it.

Second, a graybordered cavity containing an inessential worm
is seen as an eye. For example, if O plays inside, we have:

OOOOOOOO
OXXXXXXO
OX.O..XO
OXXXXXO
OOOOOOO

The cavity is now a graybordered one containing an inessential
worm.

Adjustment is made to the eye count as reckoned above by use
of the half eye database to recognize that certain eyes are 
false ones, or are half eyes whose resolution depends on who 
moves there first.

Finally, ``open eyes'' are found. This is a concept which needed
refinement. Here is the definition used in GNU Go 2.0.

We consider an empty vertex to be an OPEN EYE of a dragon if
its border color is gray, and it is a liberty of the dragon
and of distance at least 4 from every dragon of the opposite
color, and is not a half eye or false eye.

All the dragons around an open eye are amalgamated. The
algorithm which does this in GNU Go 2.0 is called dragon_ring.
Another algorithm, called dragon_pair, amalgamates dragons
which are connected and cannot be cut.



                  EYES IN GNU GO 2.4

GNU Go 2.4 uses a different algorithm for computing the
eye space.  The purpose of this document is to describe
this algorithm in detail.



                      LOCAL GAMES

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



                     EYE SPACES

In GNU Go 2.4 the amalgamation of dragons proceeds as before but
the open eyespaces as defined in GNU Go 2.0 are replaced by a
more refined concept. The algorithm which amalgamates dragons
surrounding an open eye, called dragon_ring in GNU Go 2.0 has
been replaced by a similar algorithm called 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
eoe space. In the middle of this open eye space are three
dead o stones. This space is large enough that O cannot be
killed. However GNU Go 2.0 does not know this. It finds:

> dragon size 21, value 346, genus 0, half eyes 0, open eyes 0, 
> escape factor 0, status dead

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
src/optics.c.

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



           THE EYESPACE AS A LOCAL GAME

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 1

  x
!x*x

:2,1

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 

 |- 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

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


                AN EXAMPLE

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!


. !
.!


                      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:

..
 ..

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 tabulated in the
database hey.h. During make_worms, which runs before the
eye space analysis, the half eye and false eye patterns are
tabulated in the array half_eye.

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
XXXXXX

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 Pattern 7 in hey.db:

ooo      half eye
OhO
*OX

and it is recorded in the half_eye array as follows. If (i,j)
are the coordinates of the point a, half_eye[i][j].type==HALF_EYE
and (half_eye[i][j].ki, half_eye[i][j].kj) are the coordinates of b.

The graph of the eye_shape, ostensibly .... is modified by replacing
the left . by !.



               EYE SHAPE ANALYSIS

The patterns in patterns/eyes.db are compiled into graphs
represented essentially by linked lists 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}.