Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | The purpose of this Chapter is to describe the algorithm used in |
2 | GNU Go to determine eyes. | |
3 | ||
4 | @menu | |
5 | * Local Games:: Local games | |
6 | * Eye Space:: Eye space | |
7 | * Eye Space as Local Game:: Eye space as local game | |
8 | * Eye Example:: An example | |
9 | * Graphs:: Underlying graphs | |
10 | * Eye Shape:: Pattern matching | |
11 | * Eye Local Game Values:: Pattern matching | |
12 | * Eye Topology:: False eyes and half eyes | |
13 | * Eye Topology with Ko:: False eyes and half eyes with ko | |
14 | * False Margins:: False margins | |
15 | * Eye Functions:: Functions in @file{optics.c} | |
16 | @end menu | |
17 | ||
18 | @node Local Games | |
19 | @section Local games | |
20 | ||
21 | The fundamental paradigm of combinatorial game theory is that games | |
22 | can be added and in fact form a group. If @samp{G} and @samp{H} are | |
23 | games, then @samp{G+H} is a game in which each player on his turn | |
24 | has the option of playing in either move. We say that the game | |
25 | @samp{G+H} is the sum of the local games @samp{G} and @samp{H}. | |
26 | ||
27 | Each connected eyespace of a dragon affords a local game which yields | |
28 | a local game tree. The score of this local game is the number of eyes | |
29 | it yields. Usually if the players take turns and make optimal moves, | |
30 | the end scores will differ by 0 or 1. In this case, the local game may | |
31 | be represented by a single number, which is an integer or half | |
32 | integer. Thus if @samp{n(O)} is the score if @samp{O} moves first, | |
33 | both players alternate (no passes) and make alternate moves, and | |
34 | similarly @samp{n(X)}, the game can be represented by | |
35 | @samp{@{n(O)|n(X)@}}. Thus @{1|1@} is an eye, @{2|1@} is an eye plus a | |
36 | half eye, etc. | |
37 | ||
38 | The exceptional game @{2|0@} can occur, though rarely. We call | |
39 | an eyespace yielding this local game a CHIMERA. The dragon | |
40 | is alive if any of the local games ends up with a score of 2 | |
41 | or more, so @{2|1@} is not different from @{3|1@}. Thus @{3|1@} is | |
42 | NOT a chimera. | |
43 | ||
44 | Here is an example of a chimera: | |
45 | ||
46 | @example | |
47 | @group | |
48 | XXXXX | |
49 | XOOOX | |
50 | XO.OOX | |
51 | XX..OX | |
52 | XXOOXX | |
53 | XXXXX | |
54 | @end group | |
55 | @end example | |
56 | ||
57 | @node Eye Space | |
58 | @section Eye spaces | |
59 | ||
60 | In order that each eyespace be assignable to a dragon, | |
61 | it is necessary that all the dragons surrounding it | |
62 | be amalgamated (@pxref{Amalgamation}). This is the | |
63 | function of @code{dragon_eye()}. | |
64 | ||
65 | An EYE SPACE for a black dragon is a collection of vertices | |
66 | adjacent to a dragon which may not yet be completely closed off, | |
67 | but which can potentially become eyespace. If an open eye space is | |
68 | sufficiently large, it will yield two eyes. Vertices at the edge | |
69 | of the eye space (adjacent to empty vertices outside the eye space) | |
70 | are called MARGINAL. | |
71 | ||
72 | Here is an example from a game: | |
73 | ||
74 | @example | |
75 | @group | |
76 | ||
77 | |. X . X X . . X O X O | |
78 | |X . . . . . X X O O O | |
79 | |O X X X X . . X O O O | |
80 | |O O O O X . O X O O O | |
81 | |. . . . O O O O X X O | |
82 | |X O . X X X . . X O O | |
83 | |X O O O O O O O X X O | |
84 | |. X X O . O X O . . X | |
85 | |X . . X . X X X X X X | |
86 | |O X X O X . X O O X O | |
87 | ||
88 | @end group | |
89 | @end example | |
90 | ||
91 | Here the @samp{O} dragon which is surrounded in the center has open | |
92 | eye space. In the middle of this open eye space are three | |
93 | dead @samp{X} stones. This space is large enough that O cannot be | |
94 | killed. We can abstract the properties of this eye shape as follows. | |
95 | Marking certain vertices as follows: | |
96 | ||
97 | @example | |
98 | @group | |
99 | ||
100 | |- X - X X - - X O X O | |
101 | |X - - - - - X X O O O | |
102 | |O X X X X - - X O O O | |
103 | |O O O O X - O X O O O | |
104 | |! . . . O O O O X X O | |
105 | |X O . X X X . ! X O O | |
106 | |X O O O O O O O X X O | |
107 | |- X X O - O X O - - X | |
108 | |X - - X - X X X X X X | |
109 | |O X X O X - X O O X O | |
110 | ||
111 | @end group | |
112 | @end example | |
113 | ||
114 | @noindent | |
115 | the shape in question has the form: | |
116 | ||
117 | @example | |
118 | @group | |
119 | ||
120 | !... | |
121 | .XXX.! | |
122 | ||
123 | @end group | |
124 | @end example | |
125 | ||
126 | The marginal vertices are marked with an exclamation point (@samp{!}). | |
127 | The captured @samp{X} stones inside the eyespace are naturally marked @samp{X}. | |
128 | ||
129 | The precise algorithm by which the eye spaces are determined is | |
130 | somewhat complex. Documentation of this algorithm is in the | |
131 | comments in the source to the function @code{make_domains()} in | |
132 | @file{optics.c}. | |
133 | ||
134 | The eyespaces can be conveniently displayed using a colored | |
135 | ascii diagram by running @command{gnugo -E}. | |
136 | ||
137 | @node Eye Space as Local Game | |
138 | @section The eyespace as local game | |
139 | ||
140 | In the abstraction, an eyespace consists of a set of vertices | |
141 | labelled: | |
142 | ||
143 | @example | |
144 | ||
145 | ! . X | |
146 | ||
147 | @end example | |
148 | ||
149 | Tables of many eyespaces are found in the database | |
150 | @file{patterns/eyes.db}. Each of these may be thought of as a local | |
151 | game. The result of this game is listed after the eyespace in the form | |
152 | @code{:max,min}, where @code{max} is the number of eyes the pattern | |
153 | yields if @samp{O} moves first, while @code{min} is the number of eyes | |
154 | the pattern yields if @samp{X} moves first. The player who owns the eye | |
155 | space is denoted @samp{O} throughout this discussion. Since three eyes | |
156 | are no better than two, there is no attempt to decide whether the space | |
157 | yields two eyes or three, so max never exceeds 2. Patterns with min>1 | |
158 | are omitted from the table. | |
159 | ||
160 | For example, we have: | |
161 | ||
162 | @example | |
163 | @group | |
164 | Pattern 548 | |
165 | ||
166 | x | |
167 | xX.! | |
168 | ||
169 | :0111 | |
170 | ||
171 | @end group | |
172 | @end example | |
173 | ||
174 | Here notation is as above, except that @samp{x} means @samp{X} or | |
175 | @code{EMPTY}. The result of the pattern is not different if @samp{X} has | |
176 | stones at these vertices or not. | |
177 | ||
178 | We may abstract the local game as follows. The two players @samp{O} | |
179 | and @samp{X} take turns moving, or either may pass. | |
180 | ||
181 | RULE 1: @samp{O} for his move may remove any vertex marked @samp{!} | |
182 | or marked @samp{.}. | |
183 | ||
184 | RULE 2: @samp{X} for his move may replace a @samp{.} by an @samp{X}. | |
185 | ||
186 | RULE 3: @samp{X} may remove a @samp{!}. In this case, each @samp{.} | |
187 | adjacent to the @samp{!} which is removed becomes a @samp{!} . If an | |
188 | @samp{X} adjoins the @samp{!} which is removed, then that @samp{X} | |
189 | and any which are connected to it are also removed. Any @samp{.} which | |
190 | are adjacent to the removed @samp{X}'s then become @samp{.}. | |
191 | ||
192 | Thus if @samp{O} moves first he can transform the eyeshape in | |
193 | the above example to: | |
194 | ||
195 | @example | |
196 | @group | |
197 | ... or !... | |
198 | .XXX.! .XXX. | |
199 | @end group | |
200 | @end example | |
201 | ||
202 | However if @samp{X} moves he may remove the @samp{!} and the @samp{.}s | |
203 | adjacent to the @samp{!} become @samp{!} themselves. Thus if @samp{X} | |
204 | moves first he may transform the eyeshape to: | |
205 | ||
206 | @example | |
207 | @group | |
208 | !.. or !.. | |
209 | .XXX.! .XXX! | |
210 | @end group | |
211 | @end example | |
212 | ||
213 | NOTE: A nuance which is that after the @samp{X:1}, @samp{O:2} | |
214 | exchange below, @samp{O} is threatening to capture three X stones, | |
215 | hence has a half eye to the left of 2. This is subtle, and there are | |
216 | other such subtleties which our abstraction will not capture. Some of | |
217 | these at least can be dealt with by a refinements of the scheme, but | |
218 | we will content ourselves for the time being with a simplified model. | |
219 | ||
220 | @example | |
221 | @group | |
222 | ||
223 | |- X - X X - - X O X O | |
224 | |X - - - - - X X O O O | |
225 | |O X X X X - - X O O O | |
226 | |O O O O X - O X O O O | |
227 | |1 2 . . O O O O X X O | |
228 | |X O . X X X . 3 X O O | |
229 | |X O O O O O O O X X O | |
230 | |- X X O - O X O - - X | |
231 | |X - - X - X X X X X X | |
232 | |O X X O X - X O O X O | |
233 | ||
234 | @end group | |
235 | @end example | |
236 | ||
237 | We will not attempt to characterize the terminal states | |
238 | of the local game (some of which could be seki) or | |
239 | the scoring. | |
240 | ||
241 | @node Eye Example | |
242 | @section An example | |
243 | ||
244 | Here is a local game which yields exactly one | |
245 | eye, no matter who moves first: | |
246 | ||
247 | @example | |
248 | @group | |
249 | ||
250 | ! | |
251 | ... | |
252 | ...! | |
253 | ||
254 | @end group | |
255 | @end example | |
256 | ||
257 | Here are some variations, assuming @samp{O} moves first. | |
258 | ||
259 | @example | |
260 | @group | |
261 | ! (start position) | |
262 | ... | |
263 | ...! | |
264 | @end group | |
265 | ||
266 | ||
267 | @group | |
268 | ... (after @samp{O}'s move) | |
269 | ...! | |
270 | @end group | |
271 | ||
272 | ||
273 | @group | |
274 | ... | |
275 | ..! | |
276 | @end group | |
277 | ||
278 | ||
279 | @group | |
280 | ... | |
281 | .. | |
282 | @end group | |
283 | ||
284 | ||
285 | @group | |
286 | .X. (nakade) | |
287 | .. | |
288 | @end group | |
289 | @end example | |
290 | ||
291 | Here is another variation: | |
292 | ||
293 | @example | |
294 | ||
295 | @group | |
296 | ! (start) | |
297 | ... | |
298 | ...! | |
299 | @end group | |
300 | ||
301 | ||
302 | @group | |
303 | ! (after @samp{O}'s move) | |
304 | . . | |
305 | ...! | |
306 | @end group | |
307 | ||
308 | ||
309 | @group | |
310 | ! (after @samp{X}'s move) | |
311 | . . | |
312 | ..X! | |
313 | @end group | |
314 | ||
315 | ||
316 | @group | |
317 | . . | |
318 | ..X! | |
319 | @end group | |
320 | ||
321 | ||
322 | @group | |
323 | . ! | |
324 | .! | |
325 | @end group | |
326 | @end example | |
327 | ||
328 | ||
329 | @node Graphs | |
330 | @section Graphs | |
331 | ||
332 | It is a useful observation that the local game associated | |
333 | with an eyespace depends only on the underlying graph, which | |
334 | as a set consists of the set of vertices, in which two elements | |
335 | are connected by an edge if and only if they are adjacent on | |
336 | the Go board. For example the two eye shapes: | |
337 | ||
338 | @example | |
339 | ||
340 | .. | |
341 | .. | |
342 | ||
343 | and | |
344 | ||
345 | .... | |
346 | ||
347 | @end example | |
348 | ||
349 | @noindent | |
350 | though distinct in shape have isomorphic graphs, and consequently | |
351 | they are isomorphic as local games. This reduces the number of | |
352 | eyeshapes in the database @file{patterns/eyes.db}. | |
353 | ||
354 | A further simplification is obtained through our treatment of | |
355 | half eyes and false eyes. Such patterns are identified by the | |
356 | topological analysis (@pxref{Eye Topology}). | |
357 | ||
358 | A half eye is isomorphic to the pattern @code{(!.)} . To see this, | |
359 | consider the following two eye shapes: | |
360 | ||
361 | @example | |
362 | @group | |
363 | XOOOOOO | |
364 | X.....O | |
365 | XOOOOOO | |
366 | ||
367 | @end group | |
368 | and: | |
369 | @group | |
370 | ||
371 | XXOOOOO | |
372 | XOa...O | |
373 | XbOOOOO | |
374 | XXXXXXX | |
375 | ||
376 | @end group | |
377 | @end example | |
378 | ||
379 | These are equivalent eyeshapes, with isomorphic local games @{2|1@}. | |
380 | The first has shape: | |
381 | ||
382 | @example | |
383 | ||
384 | !.... | |
385 | ||
386 | @end example | |
387 | ||
388 | The second eyeshape has a half eye at @samp{a} which is taken when @samp{O} | |
389 | or @samp{X} plays at @samp{b}. This is found by the topological | |
390 | criterion (@pxref{Eye Topology}). | |
391 | ||
392 | The graph of the eye_shape, ostensibly @samp{....} is modified by replacing | |
393 | the left @samp{.} by @samp{!.} during graph matching. | |
394 | ||
395 | ||
396 | A false eye is isomorphic to the pattern @code{(!)} . To see this, | |
397 | consider the following eye shape: | |
398 | ||
399 | @example | |
400 | ||
401 | XXXOOOOOO | |
402 | X.Oa....O | |
403 | XXXOOOOOO | |
404 | ||
405 | @end example | |
406 | ||
407 | This is equivalent to the two previous eyeshapes, with an isomorphic | |
408 | local game @{2|1@}. | |
409 | ||
410 | This eyeshape has a false eye at @samp{a}. This is also found by the | |
411 | topological criterion. | |
412 | ||
413 | The graph of the eye_shape, ostensibly @samp{.....} is modified by replacing | |
414 | the left @samp{.} by @samp{!}. This is made directly in the eye data, | |
415 | not only during graph matching. | |
416 | ||
417 | @node Eye Shape | |
418 | @section Eye shape analysis | |
419 | ||
420 | The patterns in @file{patterns/eyes.db} are compiled into graphs | |
421 | represented essentially by arrays in @file{patterns/eyes.c}. | |
422 | ||
423 | Each actual eye space as it occurs on the board is also | |
424 | compiled into a graph. Half eyes are handled as follows. | |
425 | Referring to the example | |
426 | ||
427 | @example | |
428 | @group | |
429 | XXOOOOO | |
430 | XOa...O | |
431 | XbOOOOO | |
432 | XXXXXX | |
433 | @end group | |
434 | @end example | |
435 | ||
436 | @noindent | |
437 | repeated from the preceding discussion, the vertex at @samp{b} is | |
438 | added to the eyespace as a marginal vertex. The adjacency | |
439 | condition in the graph is a macro (in @file{optics.c}): two | |
440 | vertices are adjacent if they are physically adjacent, | |
441 | or if one is a half eye and the other is its key point. | |
442 | ||
443 | In @code{recognize_eyes()}, each such graph arising from an actual eyespace is | |
444 | matched against the graphs in @file{eyes.c}. If a match is found, the | |
445 | result of the local game is known. If a graph cannot be matched, its | |
446 | local game is assumed to be @{2|2@}. | |
447 | ||
448 | @node Eye Local Game Values | |
449 | @section Eye Local Game Values | |
450 | ||
451 | The game values in @file{eyes.db} are given in a simplified scheme which is | |
452 | flexible enough to represent most possibilities in a useful way. | |
453 | ||
454 | The colon line below the pattern gives the eye value of the matched | |
455 | eye shape. This consists of four digits, each of which is the number | |
456 | of eyes obtained during the following conditions: | |
457 | ||
458 | @enumerate | |
459 | @item The attacker moves first and is allowed yet another move because | |
460 | the defender plays tenuki. | |
461 | @item The attacker moves first and the defender responds locally. | |
462 | @item The defender moves first and the attacker responds locally. | |
463 | @item The defender moves first and is allowed yet another move because | |
464 | the attacker plays tenuki. | |
465 | @end enumerate | |
466 | ||
467 | The first case does @strong{not} necessarily mean that the attacker is | |
468 | allowed two consecutive moves. This is explained with an example | |
469 | later. | |
470 | ||
471 | Also, since two eyes suffice to live, all higher numbers also count | |
472 | as two. | |
473 | ||
474 | The following 15 cases are of interest: | |
475 | ||
476 | @itemize @bullet | |
477 | @item 0000 0 eyes. | |
478 | @item 0001 0 eyes, but the defender can threaten to make one eye. | |
479 | @item 0002 0 eyes, but the defender can threaten to make two eyes. | |
480 | @item 0011 1/2 eye, 1 eye if defender moves first, 0 eyes if attacker does. | |
481 | @item 0012 3/4 eyes, 3/2 eyes if defender moves first, 0 eyes if attacker does. | |
482 | @item 0022 1* eye, 2 eyes if defender moves first, 0 eyes if attacker does. | |
483 | @item 0111 1 eye, attacker can threaten to destroy the eye. | |
484 | @item 0112 1 eye, attacker can threaten to destroy the eye, defender can threaten to make another eye. | |
485 | @item 0122 5/4 eyes, 2 eyes if defender moves first, 1/2 eye if attacker does. | |
486 | @item 0222 2 eyes, attacker can threaten to destroy both. | |
487 | @item 1111 1 eye. | |
488 | @item 1112 1 eye, defender can threaten to make another eye. | |
489 | @item 1122 3/2 eyes, 2 eyes if defender moves first, 1 eye if attacker does. | |
490 | @item 1222 2 eyes, attacker can threaten to destroy one eye. | |
491 | @item 2222 2 eyes. | |
492 | @end itemize | |
493 | ||
494 | The 3/4, 5/4, and 1* eye values are the same as in Howard Landman's paper | |
495 | Eyespace Values in Go. Attack and defense points are only marked in | |
496 | the patterns when they have definite effects on the eye value, | |
497 | i.e. pure threats are not marked. | |
498 | ||
499 | Examples of all different cases can be found among the patterns in | |
500 | this file. Some of them might be slightly counterintuitive, so we | |
501 | explain one important case here. Consider | |
502 | ||
503 | @example | |
504 | @group | |
505 | Pattern 6141 | |
506 | ||
507 | X | |
508 | XX.@@x | |
509 | ||
510 | :1122 | |
511 | @end group | |
512 | @end example | |
513 | ||
514 | which e.g. matches in this position: | |
515 | ||
516 | @example | |
517 | @group | |
518 | .OOOXXX | |
519 | OOXOXOO | |
520 | OXXba.O | |
521 | OOOOOOO | |
522 | @end group | |
523 | @end example | |
524 | ||
525 | Now it may look like @samp{X} could take away both eyes by playing @samp{a} | |
526 | followed by @samp{b}, giving 0122 as eye value. This is where the subtlety | |
527 | of the definition of the first digit in the eye value comes into | |
528 | play. It does not say that the attacker is allowed two consecutive | |
529 | moves but only that he is allowed to play "another move". The | |
530 | crucial property of this shape is that when @samp{X} plays at a to destroy | |
531 | (at least) one eye, @samp{O} can answer at @samp{b}, giving: | |
532 | ||
533 | @example | |
534 | @group | |
535 | ||
536 | .OOOXXX | |
537 | OO.OXOO | |
538 | O.cOX.O | |
539 | OOOOOOO | |
540 | ||
541 | @end group | |
542 | @end example | |
543 | ||
544 | Now @samp{X} has to continue at @samp{c} in order to keep @samp{O} | |
545 | at one eye. After this @samp{O} plays tenuki and @samp{X} cannot | |
546 | destroy the remaining eye by another move. Thus the eye value is | |
547 | indeed 1122. | |
548 | ||
549 | As a final note, some of the eye values indicating a threat depend | |
550 | on suicide to be allowed, e.g. | |
551 | ||
552 | @example | |
553 | @group | |
554 | ||
555 | Pattern 301 | |
556 | ||
557 | X.X | |
558 | ||
559 | :1222 | |
560 | ||
561 | @end group | |
562 | @end example | |
563 | ||
564 | We always assume suicide to be allowed in this database. It is easy | |
565 | enough to sort out such moves at a higher level when suicide is | |
566 | disallowed. | |
567 | ||
568 | @node Eye Topology | |
569 | @section Topology of Half Eyes and False Eyes | |
570 | ||
571 | A HALF EYE is a pattern where an eye may or may not materialize, | |
572 | depending on who moves first. Here is a half eye for @code{O}: | |
573 | ||
574 | @example | |
575 | @group | |
576 | ||
577 | OOXX | |
578 | O.O. | |
579 | OO.X | |
580 | ||
581 | @end group | |
582 | @end example | |
583 | ||
584 | A FALSE EYE is an eye vertex which cannot become a proper eye. Here are | |
585 | two examples of false eyes for @code{O}: | |
586 | ||
587 | @example | |
588 | @group | |
589 | ||
590 | OOX OOX | |
591 | O.O O.OO | |
592 | XOO OOX | |
593 | ||
594 | @end group | |
595 | @end example | |
596 | ||
597 | We describe now the topological algorithm used to find half eyes | |
598 | and false eyes. In this section we ignore the possibility of ko. | |
599 | ||
600 | False eyes and half eyes can locally be characterized by the status of | |
601 | the diagonal intersections from an eye space. For each diagonal | |
602 | intersection, which is not within the eye space, there are three | |
603 | distinct possibilities: | |
604 | ||
605 | @itemize @bullet | |
606 | @item occupied by an enemy (@code{X}) stone, which cannot be captured. | |
607 | @item either empty and @code{X} can safely play there, or occupied | |
608 | by an @code{X} stone that can both be attacked and defended. | |
609 | @item occupied by an @code{O} stone, an @code{X} stone that can be attacked | |
610 | but not defended, or it's empty and @code{X} cannot safely play there. | |
611 | @end itemize | |
612 | ||
613 | We give the first possibility a value of two, the second a value of | |
614 | one, and the last a value of zero. Summing the values for the diagonal | |
615 | intersections, we have the following criteria: | |
616 | ||
617 | @itemize @bullet | |
618 | @item sum >= 4: false eye | |
619 | @item sum == 3: half eye | |
620 | @item sum <= 2: proper eye | |
621 | @end itemize | |
622 | ||
623 | If the eye space is on the edge, the numbers above should be decreased | |
624 | by 2. An alternative approach is to award diagonal points which are | |
625 | outside the board a value of 1. To obtain an exact equivalence we must | |
626 | however give value 0 to the points diagonally off the corners, i.e. | |
627 | the points with both coordinates out of bounds. | |
628 | ||
629 | The algorithm to find all topologically false eyes and half eyes is: | |
630 | ||
631 | For all eye space points with at most one neighbor in the eye space, | |
632 | evaluate the status of the diagonal intersections according to the | |
633 | criteria above and classify the point from the sum of the values. | |
634 | ||
635 | @node Eye Topology with Ko | |
636 | @section Eye Topology with Ko | |
637 | ||
638 | ||
639 | This section extends the topological eye analysis to handle ko. We | |
640 | distinguish between a ko in favor of @samp{O} and one in favor of @samp{X}: | |
641 | ||
642 | @example | |
643 | @group | |
644 | .?O? good for O | |
645 | OO.O | |
646 | O.O? | |
647 | XOX. | |
648 | .X.. | |
649 | ||
650 | @end group | |
651 | @group | |
652 | .?O? good for X | |
653 | OO.O | |
654 | OXO? | |
655 | X.X. | |
656 | .X.. | |
657 | @end group | |
658 | @end example | |
659 | ||
660 | Preliminarily we give the former the symbolic diagonal value @code{a} | |
661 | and the latter the diagonal value @code{b}. We should clearly have | |
662 | @code{0 < a < 1 < b < 2}. Letting @code{e} be the topological eye value | |
663 | (still the sum of the four diagonal values), we want to have the | |
664 | following properties: | |
665 | ||
666 | @example | |
667 | e <= 2 - proper eye | |
668 | 2 < e < 3 - worse than proper eye, better than half eye | |
669 | e = 3 - half eye | |
670 | 3 < e < 4 - worse than half eye, better than false eye | |
671 | e >= 4 - false eye | |
672 | @end example | |
673 | ||
674 | In order to determine the appropriate values of @code{a} and @code{b} we | |
675 | analyze the typical cases of ko contingent topological eyes: | |
676 | ||
677 | @example | |
678 | @group | |
679 | .X.. (slightly) better than proper eye | |
680 | (a) ..OO e < 2 | |
681 | OO.O | |
682 | O.OO e = 1 + a | |
683 | XOX. | |
684 | .X.. | |
685 | ||
686 | @end group | |
687 | ||
688 | @group | |
689 | .X.. better than half eye, worse than proper eye | |
690 | (a') ..OO 2 < e < 3 | |
691 | OO.O | |
692 | OXOO e = 1 + b | |
693 | X.X. | |
694 | .X.. | |
695 | ||
696 | @end group | |
697 | ||
698 | @group | |
699 | .X.. better than half eye, worse than proper eye | |
700 | (b) .XOO 2 < e < 3 | |
701 | OO.O | |
702 | O.OO e = 2 + a | |
703 | XOX. | |
704 | .X.. | |
705 | ||
706 | @end group | |
707 | ||
708 | @group | |
709 | .X.. better than false eye, worse than half eye | |
710 | (b') .XOO 3 < e < 4 | |
711 | OO.O | |
712 | OXOO e = 2 + b | |
713 | X.X. | |
714 | .X.. | |
715 | ||
716 | @end group | |
717 | ||
718 | @group | |
719 | .X.. | |
720 | XOX. (slightly) better than proper eye | |
721 | (c) O.OO e < 2 | |
722 | OO.O | |
723 | O.OO e = 2a | |
724 | XOX. | |
725 | .X.. | |
726 | ||
727 | @end group | |
728 | ||
729 | @group | |
730 | .X.. | |
731 | XOX. proper eye, some aji | |
732 | (c') O.OO e ~ 2 | |
733 | OO.O | |
734 | OXOO e = a + b | |
735 | X.X. | |
736 | .X.. | |
737 | ||
738 | @end group | |
739 | ||
740 | @group | |
741 | .X.. | |
742 | X.X. better than half eye, worse than proper eye | |
743 | (c'') OXOO 2 < e < 3 | |
744 | OO.O | |
745 | OXOO e = 2b | |
746 | X.X. | |
747 | .X.. | |
748 | ||
749 | @end group | |
750 | ||
751 | @group | |
752 | .X... | |
753 | XOX.. better than half eye, worse than proper eye | |
754 | (d) O.O.X 2 < e < 3 | |
755 | OO.O. | |
756 | O.OO. e = 1 + 2a | |
757 | XOX.. | |
758 | .X... | |
759 | ||
760 | @end group | |
761 | ||
762 | @group | |
763 | .X... | |
764 | XOX.. half eye, some aji | |
765 | (d') O.O.X e ~ 3 | |
766 | OO.O. | |
767 | OXOO. e = 1 + a + b | |
768 | X.X.. | |
769 | .X... | |
770 | ||
771 | @end group | |
772 | ||
773 | @group | |
774 | .X... | |
775 | X.X.. better than false eye, worse than half eye | |
776 | (d'') OXO.X 3 < e < 4 | |
777 | OO.O. | |
778 | OXOO. e = 1 + 2b | |
779 | X.X.. | |
780 | .X... | |
781 | ||
782 | @end group | |
783 | ||
784 | @group | |
785 | .X... | |
786 | XOX.. better than false eye, worse than half eye | |
787 | (e) O.OXX 3 < e < 4 | |
788 | OO.O. | |
789 | O.OO. e = 2 + 2a | |
790 | XOX.. | |
791 | .X... | |
792 | ||
793 | @end group | |
794 | ||
795 | @group | |
796 | .X... | |
797 | XOX.. false eye, some aji | |
798 | (e') O.OXX e ~ 4 | |
799 | OO.O. | |
800 | OXOO. e = 2 + a + b | |
801 | X.X.. | |
802 | .X... | |
803 | ||
804 | @end group | |
805 | ||
806 | @group | |
807 | .X... | |
808 | X.X.. (slightly) worse than false eye | |
809 | (e'') OXOXX 4 < e | |
810 | OO.O. | |
811 | OXOO. e = 2 + 2b | |
812 | X.X.. | |
813 | .X... | |
814 | ||
815 | @end group | |
816 | @end example | |
817 | ||
818 | It may seem obvious that we should use | |
819 | @example | |
820 | (i) a=1/2, b=3/2 | |
821 | @end example | |
822 | but this turns out to have some drawbacks. These can be solved by | |
823 | using either of | |
824 | @example | |
825 | (ii) a=2/3, b=4/3 | |
826 | (iii) a=3/4, b=5/4 | |
827 | (iv) a=4/5, b=6/5 | |
828 | ||
829 | @end example | |
830 | ||
831 | Summarizing the analysis above we have the following table for the | |
832 | four different choices of @code{a} and @code{b}. | |
833 | ||
834 | @example | |
835 | case symbolic a=1/2 a=2/3 a=3/4 a=4/5 desired | |
836 | value b=3/2 b=4/3 b=5/4 b=6/5 interval | |
837 | (a) 1+a 1.5 1.67 1.75 1.8 e < 2 | |
838 | (a') 1+b 2.5 2.33 2.25 2.2 2 < e < 3 | |
839 | (b) 2+a 2.5 2.67 2.75 2.8 2 < e < 3 | |
840 | (b') 2+b 3.5 3.33 3.25 3.2 3 < e < 4 | |
841 | (c) 2a 1 1.33 1.5 1.6 e < 2 | |
842 | (c') a+b 2 2 2 2 e ~ 2 | |
843 | (c'') 2b 3 2.67 2.5 2.4 2 < e < 3 | |
844 | (d) 1+2a 2 2.33 2.5 2.6 2 < e < 3 | |
845 | (d') 1+a+b 3 3 3 3 e ~ 3 | |
846 | (d'') 1+2b 4 3.67 3.5 3.4 3 < e < 4 | |
847 | (e) 2+2a 3 3.33 3.5 3.6 3 < e < 4 | |
848 | (e') 2+a+b 4 4 4 4 e ~ 4 | |
849 | (e'') 2+2b 5 4.67 4.5 4.4 4 < e | |
850 | ||
851 | @end example | |
852 | ||
853 | We can notice that (i) fails for the cases (c''), (d), (d''), and (e). | |
854 | The other three choices get all values in the correct intervals. The | |
855 | main distinction between them is the relative ordering of (c'') and (d) | |
856 | (or analogously (d'') and (e)). If we do a more detailed analysis of | |
857 | these we can see that in both cases @samp{O} can secure the eye | |
858 | unconditionally if he moves first while @samp{X} can falsify it with ko | |
859 | if he moves first. The difference is that in (c''), @samp{X} has to make | |
860 | the first ko threat, while in (d), O has to make the first ko threat. | |
861 | Thus (c'') is better for O and ought to have a smaller topological eye | |
862 | value than (d). This gives an indication that (iv) is the better choice. | |
863 | ||
864 | We can notice that any value of @code{a}, @code{b} satisfying | |
865 | @code{a+b=2} and @code{3/4<a<1} would have the same qualities as choice | |
866 | (iv) according to the analysis above. One interesting choice is | |
867 | @code{a=7/8, b=9/8} since these allow exact computations with floating | |
868 | point values having a binary mantissa. The latter property is shared by | |
869 | @code{a=3/4} and @code{a=1/2}. | |
870 | ||
871 | When there are three kos around the same eyespace, things become | |
872 | more complex. This case is, however, rare enough that we ignore it. | |
873 | ||
874 | ||
875 | @node False Margins | |
876 | @section False Margins | |
877 | ||
878 | The following situation is rare but special enough to warrant separate | |
879 | attention: | |
880 | ||
881 | @example | |
882 | @group | |
883 | OOOOXX | |
884 | OXaX.. | |
885 | ------ | |
886 | @end group | |
887 | @end example | |
888 | ||
889 | Here @samp{a} may be characterized by the fact that it is adjacent | |
890 | to O's eyespace, and it is also adjacent to an X group which cannot | |
891 | be attacked, but that an X move at 'a' results in a string with only | |
892 | one liberty. We call this a @dfn{false margin}. | |
893 | ||
894 | For the purpose of the eye code, O's eyespace should be parsed | |
895 | as @code{(X)}, not @code{(X!)}. | |
896 | ||
897 | @node Eye Functions | |
898 | @section Functions in @file{optics.c} | |
899 | ||
900 | The public function @code{make_domains()} calls the function | |
901 | @code{make_primary_domains()} which is static in @file{optics.c}. It's purpose | |
902 | is to compute the domains of influence of each color, used in determining eye | |
903 | shapes. @strong{Note}: the term influence as used here is distinct from the | |
904 | influence in influence.c. | |
905 | ||
906 | For this algorithm the strings which are not lively are invisible. Ignoring | |
907 | these, the algorithm assigns friendly influence to | |
908 | ||
909 | @enumerate | |
910 | @item every vertex which is occupied by a (lively) friendly stone, | |
911 | @item every empty vertex adjoining a (lively) friendly stone, | |
912 | @item every empty vertex for which two adjoining vertices (not | |
913 | on the first line) in the (usually 8) surrounding ones have friendly | |
914 | influence, with two CAVEATS explained below. | |
915 | @end enumerate | |
916 | ||
917 | Thus in the following diagram, @samp{e} would be assigned friendly influence | |
918 | if @samp{a} and @samp{b} have friendly influence, or @samp{a} and @samp{d}. It | |
919 | is not sufficent for @samp{b} and @samp{d} to have friendly influence, because | |
920 | they are not adjoining. | |
921 | ||
922 | @example | |
923 | uabc | |
924 | def | |
925 | ghi | |
926 | @end example | |
927 | ||
928 | The constraint that the two adjoining vertices not lie on the first | |
929 | line prevents influence from leaking under a stone on the third line. | |
930 | ||
931 | The first CAVEAT alluded to above is that even if @samp{a} and @samp{b} have | |
932 | friendly influence, this does not cause @samp{e} to have friendly influence if | |
933 | there is a lively opponent stone at @samp{d}. This constraint prevents | |
934 | influence from leaking past knight's move extensions. | |
935 | ||
936 | The second CAVEAT is that even if @samp{a} and @samp{b} have friendly influence | |
937 | this does not cause @samp{e} to have influence if there are lively opponent | |
938 | stones at @samp{u} and at @samp{c}. This prevents influence from leaking past | |
939 | nikken tobis (two space jumps). | |
940 | ||
941 | The corner vertices are handled slightly different. | |
942 | ||
943 | @example | |
944 | +--- | |
945 | |ab | |
946 | |cd | |
947 | @end example | |
948 | ||
949 | We get friendly influence at @samp{a} if we have friendly influence | |
950 | at @samp{b} or @samp{c} and no lively unfriendly stone at @samp{b}, @samp{c} | |
951 | or @samp{d}. | |
952 | ||
953 | Here are the public functions in @file{optics.c}, except some simple | |
954 | access functions used by autohelpers. The statically declared functions | |
955 | are documented in the source code. | |
956 | ||
957 | @itemize @bullet | |
958 | @item @code{void make_domains(struct eye_data b_eye[BOARDMAX], struct eye_data w_eye[BOARDMAX], int owl_call)} | |
959 | @findex make_domains | |
960 | @quotation | |
961 | This function is called from @code{make_dragons()} and from | |
962 | @code{owl_determine_life()}. It marks the black and white domains | |
963 | (eyeshape regions) and collects some statistics about each one. | |
964 | @end quotation | |
965 | @item @code{void partition_eyespaces(struct eye_data eye[BOARDMAX], int color)} | |
966 | @findex partition_eyespaces | |
967 | @quotation | |
968 | Find connected eyespace components and compute relevant statistics. | |
969 | @end quotation | |
970 | @item @code{void propagate_eye(int origin, struct eye_data eye[BOARDMAX])} | |
971 | @findex propagate_eye | |
972 | @quotation | |
973 | propagate_eye(origin) copies the data at the (origin) to the | |
974 | rest of the eye (invariant fields only). | |
975 | @end quotation | |
976 | @item @code{int find_eye_dragons(int origin, struct eye_data eye[BOARDMAX], int eye_color, int dragons[], int max_dragons)} | |
977 | @findex find_eye_dragons | |
978 | @quotation | |
979 | Find the dragon or dragons surrounding an eye space. Up to | |
980 | max_dragons dragons adjacent to the eye space are added to | |
981 | the dragon array, and the number of dragons found is returned. | |
982 | @end quotation | |
983 | @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)} | |
984 | @findex compute_eyes | |
985 | @quotation | |
986 | Given an eyespace with origin @code{pos}, this function computes the | |
987 | minimum and maximum numbers of eyes the space can yield. If max and | |
988 | min are different, then vital points of attack and defense are also | |
989 | generated. If @code{add_moves == 1}, this function may add a move_reason for | |
990 | @code{color} at a vital point which is found by the function. If | |
991 | @code{add_moves == 0}, set @code{color = EMPTY.} | |
992 | @end quotation | |
993 | @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])} | |
994 | @findex compute_eyes_pessimistic | |
995 | @quotation | |
996 | This function works like @code{compute_eyes()}, except that it also gives | |
997 | a pessimistic view of the chances to make eyes. Since it is intended | |
998 | to be used from the owl code, the option to add move reasons has | |
999 | been removed. | |
1000 | @end quotation | |
1001 | @item @code{void add_false_eye(int pos, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX])} | |
1002 | @findex add_false_eye | |
1003 | @quotation | |
1004 | turns a proper eyespace into a margin. | |
1005 | @end quotation | |
1006 | @item @code{int is_eye_space(int pos)} | |
1007 | @item @code{int is_proper_eye_space(int pos)} | |
1008 | @findex is_proper_eye_space | |
1009 | @findex is_eye_space | |
1010 | @quotation | |
1011 | These functions are used from constraints to identify eye spaces, | |
1012 | primarily for late endgame moves. | |
1013 | @end quotation | |
1014 | @item @code{int max_eye_value(int pos)} | |
1015 | @findex max_eye_value | |
1016 | @quotation | |
1017 | Return the maximum number of eyes that can be obtained from the | |
1018 | eyespace at @code{(i, j)}. This is most useful in order to determine | |
1019 | whether the eyespace can be assumed to produce any territory at | |
1020 | all. | |
1021 | @end quotation | |
1022 | @item @code{int is_marginal_eye_space(int pos)} | |
1023 | @item @code{int is_halfeye(struct half_eye_data heye[BOARDMAX], int pos)} | |
1024 | @item @code{int is_false_eye(struct half_eye_data heye[BOARDMAX], int pos)} | |
1025 | @findex is_marginal_eye_space | |
1026 | @findex is_halfeye | |
1027 | @findex is_false_eye | |
1028 | @quotation | |
1029 | These functions simply return information about an eyeshape that | |
1030 | has already been analyzed. (They do no real work.) | |
1031 | @end quotation | |
1032 | @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])} | |
1033 | @findex find_half_and_false_eyes | |
1034 | @quotation | |
1035 | Find topological half eyes and false eyes by analyzing the | |
1036 | diagonal intersections, as described in the Texinfo | |
1037 | documentation (Eyes/Eye Topology). | |
1038 | @end quotation | |
1039 | @item @code{float topological_eye(int pos, int color, struct eye_data my_eye[BOARDMAX],struct half_eye_data heye[BOARDMAX])} | |
1040 | @findex topological_eye | |
1041 | @quotation | |
1042 | See Texinfo documentation (Eyes:Eye Topology). Returns: | |
1043 | @itemize @bullet | |
1044 | @item 2 or less if @code{pos} is a proper eye for @code{color}; | |
1045 | @item between 2 and 3 if the eye can be made false only by ko | |
1046 | @item 3 if @code{pos} is a half eye; | |
1047 | @item between 3 and 4 if the eye can be made real only by ko | |
1048 | @item 4 or more if @code{pos} is a false eye. | |
1049 | @end itemize | |
1050 | Attack and defense points for control of the diagonals are stored | |
1051 | in the @code{heye[]} array. | |
1052 | @code{my_eye} is the eye space information with respect to @code{color}. | |
1053 | @end quotation | |
1054 | @item @code{int obvious_false_eye(int pos, int color)} | |
1055 | @findex obvious_false_eye | |
1056 | @quotation | |
1057 | Conservative relative of @code{topological_eye()}. Essentially the same | |
1058 | algorithm is used, but only tactically safe opponent strings on | |
1059 | diagonals are considered. This may underestimate the false/half eye | |
1060 | status, but it should never be overestimated. | |
1061 | @end quotation | |
1062 | @item @code{void set_eyevalue(struct eyevalue *e, int a, int b, int c, int d)} | |
1063 | @findex set_eyevalue | |
1064 | @quotation set parameters into the @code{struct eyevalue} as follows | |
1065 | (@pxref{Eye Local Game Values}): | |
1066 | @example | |
1067 | struct eyevalue @{ /* number of eyes if: */ | |
1068 | unsigned char a; /* attacker plays first twice */ | |
1069 | unsigned char b; /* attacker plays first */ | |
1070 | unsigned char c; /* defender plays first */ | |
1071 | unsigned char d; /* defender plays first twice */ | |
1072 | @}; | |
1073 | @end example | |
1074 | @end quotation | |
1075 | @item @code{int min_eye_threat(struct eyevalue *e)} | |
1076 | @findex min_eye_threat | |
1077 | @quotation | |
1078 | Number of eyes if attacker plays first twice (the threat of the first | |
1079 | move by attacker). | |
1080 | @end quotation | |
1081 | @item @code{int min_eyes(struct eyevalue *e)} | |
1082 | @findex min_eyes | |
1083 | @quotation | |
1084 | Number of eyes if attacker plays first followed by alternating play. | |
1085 | @end quotation | |
1086 | @item @code{int max_eyes(struct eyevalue *e)} | |
1087 | @findex max_eyes | |
1088 | @quotation | |
1089 | Number of eyes if defender plays first followed by alternating play. | |
1090 | @end quotation | |
1091 | @item @code{int max_eye_threat(struct eyevalue *e)} | |
1092 | @findex max_eye_threat | |
1093 | @quotation | |
1094 | Number of eyes if defender plays first twice (the threat of the first | |
1095 | move by defender). | |
1096 | @end quotation | |
1097 | @item @code{void add_eyevalues(struct eyevalue *e1, struct eyevalue *e2, struct eyevalue *sum)} | |
1098 | @findex add_eyevalues | |
1099 | @quotation | |
1100 | Add the eyevalues @code{*e1} and @code{*e2}, leaving the result in *sum. It is | |
1101 | safe to let @code{sum} be the same as @code{e1} or @code{e2}. | |
1102 | @end quotation | |
1103 | @item @code{char * eyevalue_to_string(struct eyevalue *e)} | |
1104 | @findex eyevalue_to_string | |
1105 | @quotation | |
1106 | Produces a string containing the eyevalue. @strong{Note}: the result string is | |
1107 | stored in a statically allocated buffer which will be overwritten the next | |
1108 | time this function is called. | |
1109 | @end quotation | |
1110 | @item @code{void test_eyeshape(int eyesize, int *eye_vertices)} | |
1111 | @findex test_eyeshape | |
1112 | /* Test whether the optics code evaluates an eyeshape consistently. */ | |
1113 | @item @code{int analyze_eyegraph(const char *coded_eyegraph, struct eyevalue *value, char *analyzed_eyegraph)} | |
1114 | @findex analyze_eyegraph | |
1115 | @quotation | |
1116 | Analyze an eye graph to determine the eye value and vital moves. | |
1117 | The eye graph is given by a string which is encoded with @samp{%} for | |
1118 | newlines and @samp{O} for spaces. E.g., the eye graph | |
1119 | ||
1120 | @example | |
1121 | ! | |
1122 | .X | |
1123 | !... | |
1124 | @end example | |
1125 | ||
1126 | is encoded as @code{OO!%O.X%!...}. (The encoding is needed for the GTP | |
1127 | interface to this function.) The result is an eye value and a (nonencoded) | |
1128 | pattern showing the vital moves, using the same notation as eyes.db. In the | |
1129 | example above we would get the eye value 0112 and the graph (showing ko threat | |
1130 | moves) | |
1131 | ||
1132 | @example | |
1133 | @ | |
1134 | .X | |
1135 | !.*. | |
1136 | @end example | |
1137 | ||
1138 | If the eye graph cannot be realized, 0 is returned, 1 otherwise. | |
1139 | @end quotation | |
1140 | @end itemize |