| 1 | @menu |
| 2 | * Worms:: Worms |
| 3 | * Amalgamation:: How two Worms are amalgamated. |
| 4 | * Connection:: Connections. |
| 5 | * Half Eyes:: Half Eyes and False Eyes. |
| 6 | * Dragons:: Union of WORMS. |
| 7 | * Dragons in Color:: Colored display of DRAGONS. |
| 8 | @end menu |
| 9 | |
| 10 | Before considering its move, GNU Go collects some data in several |
| 11 | arrays. Two of these arrays, called @code{worm} and @code{dragon}, are |
| 12 | discussed in this document. Others are discussed in @xref{Eyes}. |
| 13 | |
| 14 | This information is intended to help evaluate the connectedness, eye |
| 15 | shape, escape potential and life status of each group. |
| 16 | |
| 17 | Later routines called by @code{genmove()} will then have access to this |
| 18 | information. This document attempts to explain the philosophy and |
| 19 | algorithms of this preliminary analysis, which is carried out by the |
| 20 | two routines @code{make_worm()} and @code{make_dragon()} in |
| 21 | @file{dragon.c}. |
| 22 | |
| 23 | @cindex dragon |
| 24 | @cindex worm |
| 25 | @cindex string |
| 26 | A @dfn{worm} is a maximal set of stones on the board which are connected |
| 27 | along the horizontal and vertical lines, and are of the same color. |
| 28 | We often say @dfn{string} instead of worm. |
| 29 | |
| 30 | A @dfn{dragon} is a union of strings of the same color which will be |
| 31 | treated as a unit. The dragons are generated anew at each move. If two strings |
| 32 | are in the dragon, it is the computer's working hypothesis that they will live |
| 33 | or die together and are effectively connected. |
| 34 | |
| 35 | The purpose of the dragon code is to allow the computer to formulate |
| 36 | meaningful statements about life and death. To give one example, |
| 37 | consider the following situation: |
| 38 | @example |
| 39 | |
| 40 | OOOOO |
| 41 | OOXXXOO |
| 42 | OX...XO |
| 43 | OXXXXXO |
| 44 | OOOOO |
| 45 | |
| 46 | @end example |
| 47 | |
| 48 | The X's here should be considered a single group with one three-space |
| 49 | eye, but they consist of two separate strings. Thus we must |
| 50 | amalgamate these two strings into a single dragon. Then the assertion |
| 51 | makes sense, that playing at the center will kill or save the dragon, |
| 52 | and is a vital point for both players. It would be difficult to |
| 53 | formulate this statement if the X's are not perceived as a unit. |
| 54 | |
| 55 | The present implementation of the dragon code involves simplifying |
| 56 | assumptions which can be refined in later implementations. |
| 57 | |
| 58 | @node Worms |
| 59 | @section Worms |
| 60 | @cindex worm |
| 61 | |
| 62 | The array @code{struct worm_data worm[MAX_BOARD]} collects information about |
| 63 | the worms. We will give definitions of the various fields. Each field has |
| 64 | constant value at each vertex of the worm. We will define each field. |
| 65 | |
| 66 | @example |
| 67 | |
| 68 | struct worm_data @{ |
| 69 | int color; |
| 70 | int size; |
| 71 | float effective_size; |
| 72 | int origin; |
| 73 | int liberties; |
| 74 | int liberties2; |
| 75 | int liberties3; |
| 76 | int liberties4; |
| 77 | int lunch; |
| 78 | int cutstone; |
| 79 | int cutstone2; |
| 80 | int genus; |
| 81 | int inessential; |
| 82 | int invincible; |
| 83 | int unconditional_status; |
| 84 | int attack_points[MAX_TACTICAL_POINTS]; |
| 85 | int attack_codes[MAX_TACTICAL_POINTS]; |
| 86 | int defense_points[MAX_TACTICAL_POINTS]; |
| 87 | int defend_codes[MAX_TACTICAL_POINTS]; |
| 88 | int attack_threat_points[MAX_TACTICAL_POINTS]; |
| 89 | int attack_threat_codes[MAX_TACTICAL_POINTS]; |
| 90 | int defense_threat_points[MAX_TACTICAL_POINTS]; |
| 91 | int defense_threat_codes[MAX_TACTICAL_POINTS]; |
| 92 | @}; |
| 93 | @end example |
| 94 | |
| 95 | @itemize @bullet |
| 96 | @item @code{color} |
| 97 | @quotation |
| 98 | The color of the worm. |
| 99 | @end quotation |
| 100 | @item @code{size} |
| 101 | @quotation |
| 102 | This field contains the cardinality of the worm. |
| 103 | @end quotation |
| 104 | @item @code{effective_size} |
| 105 | @quotation |
| 106 | @cindex effective size (worm) |
| 107 | This is the number of stones in a worm plus the number |
| 108 | of empty intersections that are at least as close to this worm as to any |
| 109 | other worm. Intersections that are shared are counted with equal |
| 110 | fractional values for each worm. This measures the direct territorial |
| 111 | value of capturing a worm. @dfn{effective_size} is a floating point number. |
| 112 | Only intersections at a distance of 4 or less are counted. |
| 113 | @end quotation |
| 114 | @item @code{origin} |
| 115 | @quotation |
| 116 | @cindex origin (worm) |
| 117 | Each worm has a distinguished member, called its @dfn{origin}. |
| 118 | The purpose of this field is to make it easy to determine when two vertices |
| 119 | lie in the same worm: we compare their origin. Also if we wish to perform some |
| 120 | test once for each worm, we simply perform it at the origin and ignore the |
| 121 | other vertices. The origin is characterized by the test: |
| 122 | @example |
| 123 | worm[pos].origin == pos. |
| 124 | @end example |
| 125 | @end quotation |
| 126 | @item @code{liberties} |
| 127 | @item @code{liberties2} |
| 128 | @item @code{liberties3} |
| 129 | @item @code{liberties4} |
| 130 | @quotation |
| 131 | @cindex liberties (worm) |
| 132 | @cindex liberties, higher order (worm) |
| 133 | For a nonempty worm the field liberties is the number of liberties of the |
| 134 | string. This is supplemented by @code{LIBERTIES2}, @code{LIBERTIES3} and |
| 135 | @code{LIBERTIES4}, which are the number of second order, third order, and |
| 136 | fourth order liberties, respectively. |
| 137 | The definition of liberties of order >1 is adapted to the |
| 138 | problem of detecting the shape of the surrounding |
| 139 | empty space. In particular we want to be able to see if a group |
| 140 | is loosely surrounded. A @dfn{liberty of order n} is an empty |
| 141 | vertex which may be connected to the string by placing n |
| 142 | stones of the same color on the board, but no fewer. The |
| 143 | path of connection may pass through an intervening group |
| 144 | of the same color. The stones placed at distance >1 may |
| 145 | not touch a group of the opposite color. Connections through |
| 146 | ko are not permitted. Thus in the following configuration: |
| 147 | @example |
| 148 | |
| 149 | .XX... We label the .XX.4. |
| 150 | XO.... liberties of XO1234 |
| 151 | XO.... order < 5 of XO1234 |
| 152 | ...... the O group: .12.4. |
| 153 | .X.X.. .X.X.. |
| 154 | |
| 155 | @end example |
| 156 | |
| 157 | The convention that liberties of order >1 may not touch a |
| 158 | group of the opposite color means that knight's moves and |
| 159 | one space jumps are perceived as impenetrable barriers. |
| 160 | This is useful in determining when the string is becoming |
| 161 | surrounded. |
| 162 | |
| 163 | The path may also not pass through a liberty at distance |
| 164 | 1 if that liberty is flanked by two stones of the opposing color. This |
| 165 | reflects the fact that the O stone is blocked from expansion to the |
| 166 | left by the two X stones in the following situation: |
| 167 | @example |
| 168 | |
| 169 | X. |
| 170 | .O |
| 171 | X. |
| 172 | |
| 173 | @end example |
| 174 | @cindex distance from liberty to dragon |
| 175 | We say that n is the @dfn{distance} of the liberty of order n from the dragon. |
| 176 | @end quotation |
| 177 | @item @code{lunch} |
| 178 | @quotation |
| 179 | @cindex lunch (worm) |
| 180 | If nonzero, @code{lunch} points to a boundary worm which can be easily |
| 181 | captured. (It does not matter whether or not the string can be |
| 182 | defended.) |
| 183 | @end quotation |
| 184 | @end itemize |
| 185 | |
| 186 | We have two distinct notions of cutting stone, which we keep track |
| 187 | of in the separate fields @code{worm.cutstone} and @code{worm.cutstone2}. |
| 188 | We use currently use both concepts in parallel. |
| 189 | |
| 190 | @itemize |
| 191 | @item @code{cutstone} |
| 192 | @quotation |
| 193 | @cindex cutting stone |
| 194 | This field is equal to 2 for cutting stones, 1 for potential cutting |
| 195 | stones. Otherwise it is zero. Definitions for this field: a @dfn{cutting |
| 196 | stone} is one adjacent to two enemy strings, which do not have a liberty in |
| 197 | common. The most common type of cutting string is in this situation: |
| 198 | |
| 199 | @example |
| 200 | |
| 201 | XO |
| 202 | OX |
| 203 | |
| 204 | @end example |
| 205 | @cindex cutting stone, potential |
| 206 | @cindex potential cutting stone |
| 207 | |
| 208 | A @dfn{potential cutting stone} is adjacent to two enemy strings which do |
| 209 | share a liberty. For example, X in: |
| 210 | |
| 211 | @example |
| 212 | |
| 213 | XO |
| 214 | O. |
| 215 | |
| 216 | @end example |
| 217 | |
| 218 | For cutting strings we set @code{worm[].cutstone=2}. For |
| 219 | potential cutting strings we set @code{worm[].cutstone=1}. |
| 220 | @end quotation |
| 221 | @item @code{cutstone2} |
| 222 | @quotation |
| 223 | Cutting points are identified by the patterns in the connections |
| 224 | database. Proper cuts are handled by the fact that attacking and |
| 225 | defending moves also count as moves cutting or connecting the |
| 226 | surrounding dragons. The @code{cutstone2} field is set during |
| 227 | @code{find_cuts()}, called from @code{make_domains()}. |
| 228 | @end quotation |
| 229 | @findex find_cuts |
| 230 | @findex make_domains |
| 231 | @item @code{genus} |
| 232 | @quotation |
| 233 | @cindex genus (worm) |
| 234 | There are two separate notions of @dfn{genus} for worms and |
| 235 | dragons. The dragon notion is more important, so |
| 236 | @code{dragon[pos].genus} is a far more useful field than |
| 237 | @code{worm[pos].genus}. Both fields are intended as approximations |
| 238 | to the number of eyes. The @dfn{genus} of a string is the number |
| 239 | of connected components of its complement, minus one. It is |
| 240 | an approximation to the number of eyes of the string. |
| 241 | @end quotation |
| 242 | @item @code{inessential} |
| 243 | @quotation |
| 244 | @cindex inessential string |
| 245 | An @dfn{inessential} string is one which meets a |
| 246 | criterion designed to guarantee that it has no life |
| 247 | potential unless a particular surrounding string of the |
| 248 | opposite color can be killed. More precisely an |
| 249 | @dfn{inessential string} is a string S of genus zero, |
| 250 | not adjacent to any opponent string which can be easily |
| 251 | captured, and which has no edge liberties or second |
| 252 | order liberties, and which satisfies the following |
| 253 | further property: If the string is removed from the |
| 254 | board, then the remaining cavity only borders worms of the |
| 255 | opposite color. |
| 256 | |
| 257 | @end quotation |
| 258 | @findex unconditional_life |
| 259 | @item @code{invincible} |
| 260 | @quotation |
| 261 | @cindex invincible worm |
| 262 | An @dfn{invincible} worm is one which GNU Go thinks |
| 263 | cannot be captured. Invincible worms are computed by the |
| 264 | function @code{unconditional_life()} which tries to |
| 265 | find those worms of the given color that can never be captured, |
| 266 | even if the opponent is allowed an arbitrary number of consecutive |
| 267 | moves. |
| 268 | @end quotation |
| 269 | @item unconditional_status |
| 270 | @quotation |
| 271 | Unconditional status is also set by the function |
| 272 | @code{unconditional_life}. This is set @code{ALIVE} for stones which are |
| 273 | invincible. Stones which can not be turned invincible even if the |
| 274 | defender is allowed an arbitrary number of consecutive moves are given |
| 275 | an unconditional status of @code{DEAD}. Empty points where the opponent |
| 276 | cannot form an invincible worm are called unconditional territory. The |
| 277 | unconditional status is set to @code{WHITE_TERRITORY} or |
| 278 | @code{BLACK_TERRITORY} depending on who owns the territory. Finally, if |
| 279 | a stone can be captured but is adjacent to unconditional territory of |
| 280 | its own color, it is also given the unconditional status @code{ALIVE}. |
| 281 | In all other cases the unconditional status is @code{UNKNOWN}. |
| 282 | |
| 283 | To make sense of these definitions it is important to notice that any |
| 284 | stone which is alive in the ordinary sense (even if only in seki) can be |
| 285 | transformed into an invincible group by some number of consecutive |
| 286 | moves. Well, this is not entirely true because there is a rare class of |
| 287 | seki groups not satisfying this condition. Exactly which these are is |
| 288 | left as an exercise for the reader. Currently @code{unconditional_life}, |
| 289 | which strictly follows the definitions above, calls such seki groups |
| 290 | unconditionally dead, which of course is a misfeature. It is possible to |
| 291 | avoid this problem by making the algorithm slightly more complex, but |
| 292 | this is left for a later revision. |
| 293 | @end quotation |
| 294 | @item @code{int attack_points[MAX_TACTICAL_POINTS]} |
| 295 | @item @code{attack_codes[MAX_TACTICAL_POINTS]} |
| 296 | @item @code{int defense_points[MAX_TACTICAL_POINTS];} |
| 297 | @item @code{int defend_codes[MAX_TACTICAL_POINTS];} |
| 298 | @quotation |
| 299 | If the tactical reading code (@pxref{Tactical Reading}) finds that the |
| 300 | worm can be attacked, @code{attack_points[0]} is a point of attack, and |
| 301 | @code{attack_codes[0]} is the attack code, @code{WIN}, @code{KO_A} or |
| 302 | @code{KO_B}. If multiple attacks are known, @code{attack_points[k]} and |
| 303 | @code{attack_codes[k]} are used. Similarly with the defense |
| 304 | codes and defense points. |
| 305 | @end quotation |
| 306 | @item @code{int attack_threat_points[MAX_TACTICAL_POINTS];} |
| 307 | @item @code{int attack_threat_codes[MAX_TACTICAL_POINTS];} |
| 308 | @item @code{int defense_threat_points[MAX_TACTICAL_POINTS];} |
| 309 | @item @code{int defense_threat_codes[MAX_TACTICAL_POINTS];} |
| 310 | @quotation |
| 311 | These are points that threaten to attack or defend a worm. |
| 312 | @end quotation |
| 313 | @end itemize |
| 314 | |
| 315 | The function @code{makeworms()} will generate data for all worms. |
| 316 | |
| 317 | @node Amalgamation |
| 318 | @section Amalgamation |
| 319 | @cindex amalgamation of worms into dragons |
| 320 | |
| 321 | A dragon, we have said, is a group of stones which are treated as a |
| 322 | unit. It is a working hypothesis that these stones will live or die |
| 323 | together. Thus the program will not expect to disconnect an opponent's |
| 324 | strings if they have been amalgamated into a single dragon. |
| 325 | |
| 326 | The function @code{make_dragons()} will amalgamate worms into dragons by |
| 327 | maintaining separate arrays @code{worm[]} and @code{dragon[]} containing |
| 328 | similar data. Each dragon is a union of worms. Just as the data maintained in |
| 329 | @code{worm[]} is constant on each worm, the data in |
| 330 | @code{dragon[]} is constant on each dragon. |
| 331 | |
| 332 | Amalgamation of worms in GNU Go proceeds as follows. |
| 333 | First we amalgamate all boundary components of an eyeshape. Thus in |
| 334 | the following example: |
| 335 | |
| 336 | @example |
| 337 | |
| 338 | .OOOO. The four X strings are amalgamated into a |
| 339 | OOXXO. single dragon because they are the boundary |
| 340 | OX..XO components of a blackbordered cave. The |
| 341 | OX..XO cave could contain an inessential string |
| 342 | OOXXO. with no effect on this amalgamation. |
| 343 | XXX... |
| 344 | |
| 345 | @end example |
| 346 | @findex dragon_eye |
| 347 | |
| 348 | The code for this type of amalgamation is in the routine |
| 349 | @code{dragon_eye()}, discussed further in EYES. |
| 350 | |
| 351 | Next, we amalgamate strings which seem uncuttable. We amalgamate dragons |
| 352 | which either share two or more common liberties, or share one liberty |
| 353 | into the which the opponent cannot play without being |
| 354 | captured. (ignores ko rule). |
| 355 | |
| 356 | @example |
| 357 | |
| 358 | X. X.X XXXX.XXX X.O |
| 359 | .X X.X X......X X.X |
| 360 | XXXXXX.X OXX |
| 361 | |
| 362 | @end example |
| 363 | |
| 364 | A database of connection patterns may be found in @file{patterns/conn.db}. |
| 365 | |
| 366 | @node Connection |
| 367 | @section Connection |
| 368 | @cindex connections |
| 369 | |
| 370 | The fields @code{black_eye.cut} and @code{white_eye.cut} are set where the |
| 371 | opponent can cut, and this is done by the B (break) class patterns in |
| 372 | @file{conn.db}. There are two important uses for this field, which can be |
| 373 | accessed by the autohelper functions @code{xcut()} and @code{ocut()}. The |
| 374 | first use is to stop amalgamation in positions like |
| 375 | |
| 376 | @example |
| 377 | |
| 378 | ..X.. |
| 379 | OO*OO |
| 380 | X.O.X |
| 381 | ..O.. |
| 382 | |
| 383 | @end example |
| 384 | |
| 385 | @noindent |
| 386 | where X can play at * to cut off either branch. What happens |
| 387 | here is that first connection pattern CB1 finds the double cut |
| 388 | and marks * as a cutting point. Later the C (connection) class |
| 389 | patterns in conn.db are searched to find secure connections |
| 390 | over which to amalgamate dragons. Normally a diagonal |
| 391 | connection would be deemed secure and amalgamated by connection |
| 392 | pattern CC101, but there is a constraint requiring that neither of |
| 393 | the empty intersections is a cutting point. |
| 394 | @findex amalgamate_most_valuable_helper |
| 395 | |
| 396 | A weakness with this scheme is that X can only cut one connection, not |
| 397 | both, so we should be allowed to amalgamate over one of the connections. |
| 398 | This is performed by connection pattern CC401, which with the help of |
| 399 | @code{amalgamate_most_valuable_helper()} decides which connection to |
| 400 | prefer. |
| 401 | |
| 402 | The other use is to simplify making alternative connection patterns to |
| 403 | the solid connection. Positions where the diag_miai helper thinks a |
| 404 | connection is necessary are marked as cutting points by connection |
| 405 | pattern 12. Thus we can write a connection pattern like @code{CC6}: |
| 406 | |
| 407 | @example |
| 408 | |
| 409 | ?xxx? straight extension to connect |
| 410 | XOO*? |
| 411 | O...? |
| 412 | |
| 413 | :8,C,NULL |
| 414 | |
| 415 | ?xxx? |
| 416 | XOOb? |
| 417 | Oa..? |
| 418 | |
| 419 | ;xcut(a) && odefend_against(b,a) |
| 420 | |
| 421 | @end example |
| 422 | |
| 423 | @noindent |
| 424 | where we verify that a move at @code{*} would stop the enemy from safely |
| 425 | playing at the cutting point, thus defending against the cut. |
| 426 | |
| 427 | @node Half Eyes |
| 428 | @section Half Eyes and False Eyes |
| 429 | @cindex half eye |
| 430 | @cindex false eye |
| 431 | |
| 432 | A @dfn{half eye} is a place where, if the defender plays first, an eye |
| 433 | will materialize, but where if the attacker plays first, no eye will |
| 434 | materialize. A @dfn{false eye} is a vertex which is surrounded by a |
| 435 | dragon yet is not an eye. Here is a half eye: |
| 436 | |
| 437 | @example |
| 438 | @group |
| 439 | |
| 440 | XXXXX |
| 441 | OO..X |
| 442 | O.O.X |
| 443 | OOXXX |
| 444 | |
| 445 | @end group |
| 446 | @end example |
| 447 | |
| 448 | Here is a false eye: |
| 449 | |
| 450 | @example |
| 451 | @group |
| 452 | |
| 453 | XXXXX |
| 454 | XOO.X |
| 455 | O.O.X |
| 456 | OOXXX |
| 457 | |
| 458 | @end group |
| 459 | @end example |
| 460 | |
| 461 | The "topological" algorithm for determining half and false eyes |
| 462 | is described elsewhere (@pxref{Eye Topology}). |
| 463 | |
| 464 | The half eye data is collected in the dragon array. Before this is done, |
| 465 | however, an auxiliary array called half_eye_data is filled with |
| 466 | information. The field @code{type} is 0, or else @code{HALF_EYE} or |
| 467 | @code{FALSE_EYE} depending on which type is found; the fields |
| 468 | @code{attack_point[]} point to up to 4 points to attack |
| 469 | the half eye, and similarly @code{defense_point[]} gives points |
| 470 | to defend the half eye. |
| 471 | |
| 472 | @example |
| 473 | @group |
| 474 | |
| 475 | struct half_eye_data half_eye[MAX_BOARD]; |
| 476 | |
| 477 | struct half_eye_data @{ |
| 478 | float value; /* Topological eye value */ |
| 479 | int type; /* HALF_EYE or FALSE_EYE */ |
| 480 | int num_attacks; /* Number of attacking points */ |
| 481 | int attack_point[4]; /* The moves to attack a topological halfeye */ |
| 482 | int num_defends; /* Number of defending points */ |
| 483 | int defense_point[4]; /* The moves to defend a topological halfeye */ |
| 484 | @}; |
| 485 | |
| 486 | @end group |
| 487 | @end example |
| 488 | |
| 489 | The array @code{struct half_eye_data half_eye[MAX_BOARD]} |
| 490 | contains information about half and false eyes. If the type is |
| 491 | @code{HALF_EYE} then up to four moves are recorded which can |
| 492 | either attack or defend the eye. In rare cases the attack points |
| 493 | could be different from the defense points. |
| 494 | |
| 495 | @node Dragons |
| 496 | @section Dragons |
| 497 | @cindex dragons |
| 498 | |
| 499 | The array @code{struct dragon_data dragon[MAX_BOARD]} |
| 500 | collects information about the dragons. We will give definitions of the |
| 501 | various fields. Each field has constant value at each vertex of the |
| 502 | dragon. (Fields will be discussed below.) |
| 503 | |
| 504 | @example |
| 505 | |
| 506 | struct dragon_data @{ |
| 507 | int color; /* its color */ |
| 508 | int id; /* the index into the dragon2 array */ |
| 509 | int origin; /* the origin of the dragon. Two vertices */ |
| 510 | /* are in the same dragon iff they have */ |
| 511 | /* same origin. */ |
| 512 | int size; /* size of the dragon */ |
| 513 | float effective_size; /* stones and surrounding spaces */ |
| 514 | int crude_status; /* (ALIVE, DEAD, UNKNOWN, CRITICAL)*/ |
| 515 | int status; /* best trusted status */ |
| 516 | @}; |
| 517 | |
| 518 | extern struct dragon_data dragon[BOARDMAX]; |
| 519 | |
| 520 | @end example |
| 521 | |
| 522 | Other fields attached to the dragon are contained in the @code{dragon_data2} |
| 523 | struct array. (Fields will be discussed below.) |
| 524 | |
| 525 | @example |
| 526 | |
| 527 | struct dragon_data2 @{ |
| 528 | int origin; |
| 529 | int adjacent[MAX_NEIGHBOR_DRAGONS]; |
| 530 | int neighbors; |
| 531 | int hostile_neighbors; |
| 532 | int moyo_size; |
| 533 | float moyo_territorial_value; |
| 534 | int safety; |
| 535 | float weakness; |
| 536 | float weakness_pre_owl; |
| 537 | int escape_route; |
| 538 | struct eyevalue genus; |
| 539 | int heye; |
| 540 | int lunch; |
| 541 | int surround_status; |
| 542 | int surround_size; |
| 543 | int semeais; |
| 544 | int semeai_margin_of_safety; |
| 545 | int semeai_defense_point; |
| 546 | int semeai_defense_certain; |
| 547 | int semeai_attack_point; |
| 548 | int semeai_attack_certain; |
| 549 | int owl_threat_status; |
| 550 | int owl_status; |
| 551 | int owl_attack_point; |
| 552 | int owl_attack_code; |
| 553 | int owl_attack_certain; |
| 554 | int owl_second_attack_point; |
| 555 | int owl_defense_point; |
| 556 | int owl_defense_code; |
| 557 | int owl_defense_certain; |
| 558 | int owl_second_defense_point; |
| 559 | int owl_attack_kworm; |
| 560 | int owl_defense_kworm; |
| 561 | @}; |
| 562 | |
| 563 | extern struct dragon_data2 *dragon2; |
| 564 | |
| 565 | @end example |
| 566 | |
| 567 | The difference between the two arrays is that the @code{dragon} array |
| 568 | is indexed by the board, and there is a copy of the dragon data |
| 569 | at every stone in the dragon, while there is only one copy of |
| 570 | the dragon2 data. The dragons are numbered, and the @code{id} field |
| 571 | of the dragon is a key into the dragon2 array. Two macros DRAGON |
| 572 | and DRAGON2 are provided for gaining access to the two arrays. |
| 573 | |
| 574 | @example |
| 575 | #define DRAGON2(pos) dragon2[dragon[pos].id] |
| 576 | #define DRAGON(d) dragon[dragon2[d].origin] |
| 577 | @end example |
| 578 | |
| 579 | Thus if you know the position @code{pos} of a stone in the dragon |
| 580 | you can access the dragon array directly, for example accessing the |
| 581 | origin with @code{dragon[pos].origin}. However if you need a field |
| 582 | from the dragon2 array, you can access it using the DRAGON2 macro, |
| 583 | for example you can access its neighor dragons by |
| 584 | |
| 585 | @example |
| 586 | for (k = 0; k < DRAGON2(pos).neighbors; k++) @{ |
| 587 | int d = DRAGON2(pos).adjacent[k]; |
| 588 | int apos = dragon2[d].origin; |
| 589 | do_something(apos); |
| 590 | @} |
| 591 | @end example |
| 592 | |
| 593 | Similarly if you know the dragon number (which is @code{dragon[pos].id}) |
| 594 | then you can access the @code{dragon2} array directly, or you can |
| 595 | access the @code{dragon} array using the DRAGON macro. |
| 596 | |
| 597 | Here are the definitions of each field in the @code{dragon} arrray. |
| 598 | |
| 599 | @itemize @bullet |
| 600 | @item @code{color} |
| 601 | @quotation |
| 602 | @cindex color (dragon) |
| 603 | The color of the dragon. |
| 604 | @end quotation |
| 605 | @item @code{id} |
| 606 | @cindex dragon number |
| 607 | @quotation |
| 608 | The dragon number, used as a key into the @code{dragon2} array. |
| 609 | @end quotation |
| 610 | @item origin |
| 611 | @cindex dragon origin |
| 612 | @quotation |
| 613 | The origin of the dragon is a unique particular vertex |
| 614 | of the dragon, useful for determining when two vertices belong |
| 615 | to the same dragon. Before amalgamation the worm origins are |
| 616 | copied to the dragon origins. Amalgamation of two dragons |
| 617 | amounts to changing the origin of one. |
| 618 | @end quotation |
| 619 | @item size |
| 620 | @cindex dragon size |
| 621 | @quotation |
| 622 | The number of stones in the dragon. |
| 623 | @end quotation |
| 624 | @item effective size |
| 625 | @cindex effective size |
| 626 | @quotation |
| 627 | The sum of the effective sizes of the constituent worms. |
| 628 | Remembering that vertices equidistant between two or more worms are |
| 629 | counted fractionally in @code{worm.effective_size}, this equals the |
| 630 | cardinality of the dragon plus the number of empty vertices which are |
| 631 | nearer this dragon than any other. |
| 632 | @end quotation |
| 633 | @item crude_status |
| 634 | @quotation |
| 635 | (ALIVE, DEAD, UNKNOWN, CRITICAL). An early measure of the life |
| 636 | potential of the dragon. It is computed before the owl code is |
| 637 | run and is superceded by the status as soon as that becomes |
| 638 | available. |
| 639 | @end quotation |
| 640 | @item status |
| 641 | @cindex dragon status |
| 642 | @quotation |
| 643 | The dragon status is the best measure of the dragon's health. |
| 644 | It is computed after the owl code is run, then revised again |
| 645 | when the semeai code is run. |
| 646 | @end quotation |
| 647 | @end itemize |
| 648 | |
| 649 | Here are definitions of the fields in the @code{dragon2} array. |
| 650 | |
| 651 | @itemize @bullet |
| 652 | @item origin |
| 653 | @quotation |
| 654 | The origin field is duplicated here. |
| 655 | @end quotation |
| 656 | @item adjacent |
| 657 | @item @code{adjacent[MAX_NEIGHBOR_DRAGONS]} |
| 658 | @cindex neighbor dragons |
| 659 | @cindex adjacent dragons |
| 660 | @findex find_neighbor_dragons |
| 661 | @quotation |
| 662 | Dragons of either color near the given one are called @dfn{neighbors}. |
| 663 | They are computed by the function @code{find_neighbor_dragons()}. |
| 664 | The @code{dragon2.adjacent} array gives the dragon numbers of |
| 665 | these dragons. |
| 666 | @end quotation |
| 667 | @item @code{neighbors} |
| 668 | @cindex neighbor dragons |
| 669 | @cindex adjacent dragons |
| 670 | @findex find_neighbor_dragons |
| 671 | @quotation |
| 672 | Dragons of either color near the given one are called @dfn{neighbors}. |
| 673 | They are computed by the function @code{find_neighbor_dragons()}. |
| 674 | The @code{dragon2.adjacent} array gives the dragon numbers of |
| 675 | these dragons. |
| 676 | @end quotation |
| 677 | @item neighbors |
| 678 | @quotation |
| 679 | The number of neighbor dragons. |
| 680 | @end quotation |
| 681 | @item hostile_neighbors |
| 682 | @quotation |
| 683 | The number of neighbor dragons of the opposite color. |
| 684 | @end quotation |
| 685 | @item moyo_size |
| 686 | @item float moyo_territorial_value |
| 687 | @findex compute_surrounding_moyo_sizes |
| 688 | @quotation |
| 689 | The function @code{compute_surrounding_moyo_sizes()} assigns |
| 690 | a size and a territorial value to the moyo around |
| 691 | each dragon (@pxref{Territory and Moyo}). This is the |
| 692 | moyo size. They are recorded in these fields. |
| 693 | @end quotation |
| 694 | @item safety |
| 695 | @cindex dragon safety |
| 696 | @quotation |
| 697 | The dragon safety can take on one of the values |
| 698 | @itemize @minus |
| 699 | @item TACTICALLY_DEAD - a dragon consisting of a single worm found dead by the |
| 700 | reading code (very reliable) |
| 701 | @item ALIVE - found alive by the owl or semeai code |
| 702 | @item STRONGLY_ALIVE - alive without much question |
| 703 | @item INVINCIBLE - definitively alive even after many tenukis |
| 704 | @item ALIVE_IN_SEKI - determined to be seki by the semeai code |
| 705 | @item CRITICAL - lives or dies depending on who moves first |
| 706 | @item DEAD - found to be dead by the owl code |
| 707 | @item INESSENTIAL - the dragon is unimportant (e.g. nakade stones) and dead |
| 708 | @end itemize |
| 709 | @end quotation |
| 710 | @item weakness |
| 711 | @item weakness_pre_owl |
| 712 | @cindex dragon weakness |
| 713 | @cindex weakness |
| 714 | @quotation |
| 715 | A floating point measure of the safety of a dragon. The dragon |
| 716 | weakness is a number between 0. and 1., higher numbers for |
| 717 | dragons in greater need of safety. The field @code{weakness_pre_owl} |
| 718 | is a preliminary computation before the owl code is run. |
| 719 | @end quotation |
| 720 | @item escape_route |
| 721 | @cindex dragon escape_route |
| 722 | @cindex escape_route |
| 723 | @findex compute_escape |
| 724 | @quotation |
| 725 | A measure of the dragon's potential to escape towards safety, |
| 726 | in case it cannot make two eyes locally. Documentation |
| 727 | may be found in @ref{Escape}. |
| 728 | @end quotation |
| 729 | @item struct eyevalue genus |
| 730 | @cindex dragon genus |
| 731 | @cindex genus |
| 732 | @quotation |
| 733 | The approximate number of eyes the dragon can be expected to |
| 734 | get. Not guaranteed to be accurate. The eyevalue struct, which |
| 735 | is used throughout the engine, is declared thus: |
| 736 | @example |
| 737 | |
| 738 | struct eyevalue @{ |
| 739 | unsigned char a; /* # of eyes if attacker plays twice */ |
| 740 | unsigned char b; /* # of eyes if attacker plays first */ |
| 741 | unsigned char c; /* # of eyes if defender plays first */ |
| 742 | unsigned char d; /* # of eyes if defender plays twice */ |
| 743 | @}; |
| 744 | |
| 745 | @end example |
| 746 | @end quotation |
| 747 | @item heye |
| 748 | @quotation |
| 749 | Location of a half eye attached to the dragon. |
| 750 | @end quotation |
| 751 | @item lunch |
| 752 | @cindex dragon lunch |
| 753 | @cindex lunch |
| 754 | @quotation |
| 755 | If nonzero, this is the location of a boundary string which |
| 756 | can be captured. In contrast with worm lunches, a dragon |
| 757 | lunch must be able to defend itself. |
| 758 | @end quotation |
| 759 | @item surround_status |
| 760 | @item surround_size |
| 761 | @cindex surround_status |
| 762 | @cindex surround_size |
| 763 | @cindex surround |
| 764 | @quotation |
| 765 | In estimating the safety of a dragon it is useful to know if |
| 766 | it is @dfn{surrounded}. See @ref{Surrounded Dragons} and |
| 767 | the comments in @file{surround.c} for more information about the |
| 768 | algorithm. Used in computing the escape_route, and also callable |
| 769 | from patterns (currently used by CB258). |
| 770 | @end quotation |
| 771 | @item semeais |
| 772 | @item semeai_defense_point |
| 773 | @item semeai_defense_certain |
| 774 | @item semeai_attack_point |
| 775 | @item semeai_attack_certain |
| 776 | @cindex semeai |
| 777 | @cindex semeai_defense_point |
| 778 | @cindex semeai_defense_certain |
| 779 | @cindex semeai_attack_point |
| 780 | @cindex semeai_attack_certain |
| 781 | @quotation |
| 782 | If two dragons of opposite color both have the status CRITICAL |
| 783 | or DEAD they are in a @dfn{semeai} (capturing race), and their |
| 784 | status must be adjudicated by the function |
| 785 | @code{owl_analyze_semeai()} in @file{owl.c}, which attempts to |
| 786 | determine which is alive, which dead, or if the result is |
| 787 | seki, and whether it is important who moves first. The |
| 788 | function @file{new_semeai()} in @file{semeai.c} attempts |
| 789 | to revise the statuses and to generate move reasons based |
| 790 | on these results. The field @code{dragon2.semeais} is nonzero |
| 791 | if the dragon is an element of a semeai, and equals the |
| 792 | number of semeais (seldom more than one). The semeai defense |
| 793 | and attack points are locations the defender or attacker |
| 794 | must move to win the semeai. The field @code{semeai_margin_of_safety} |
| 795 | is intended to indicate whether the semeai is close or not |
| 796 | but currently this field is not maintained. The fields |
| 797 | @code{semeai_defense_certain} and @code{semeai_attack_certain} |
| 798 | indicate that the semeai code was able to finish analysis |
| 799 | without running out of nodes. |
| 800 | @end quotation |
| 801 | @item owl_status |
| 802 | @quotation |
| 803 | This is a classification similar to @code{dragon.crude_status}, but |
| 804 | based on the life and death reading in @file{owl.c}. |
| 805 | The owl code (@pxref{The Owl Code}) is skipped for dragons |
| 806 | which appear safe by certain heuristics. If the owl code |
| 807 | is not run, the owl status is @code{UNCHECKED}. |
| 808 | If @code{owl_attack()} determines that the dragon cannot be |
| 809 | attacked, it is classified as @code{ALIVE}. Otherwise, |
| 810 | @code{owl_defend()} is run, and if it can be defended it |
| 811 | is classified as @code{CRITICAL}, and if not, as @code{DEAD}. |
| 812 | @end quotation |
| 813 | @item owl_attack_point |
| 814 | @cindex owl_attack_point |
| 815 | @quotation |
| 816 | If the dragon can be attacked this is the point to attack the dragon. |
| 817 | @end quotation |
| 818 | @item owl_attack_code |
| 819 | @cindex owl_attack_code |
| 820 | @quotation |
| 821 | The owl attack code, It can be WIN, KO_A, KO_B or 0 (@pxref{Return Codes}). |
| 822 | @end quotation |
| 823 | @item owl_attack_certain |
| 824 | @cindex owl_attack_certain |
| 825 | @quotation |
| 826 | The owl reading is able to finish analyzing the attack |
| 827 | without running out of nodes. |
| 828 | @end quotation |
| 829 | @item owl_second_attack_point |
| 830 | @cindex owl_second_attack_point |
| 831 | @quotation |
| 832 | A second attack point. |
| 833 | @end quotation |
| 834 | @item owl_defense_point |
| 835 | @cindex owl_defense_point |
| 836 | @quotation |
| 837 | If the dragon can be defended, this is the place to play. |
| 838 | @end quotation |
| 839 | @item owl_defense_code |
| 840 | @cindex owl_defense_code |
| 841 | @quotation |
| 842 | The owl defense code, It can be WIN, KO_A, KO_B or 0 (@pxref{Return Codes}). |
| 843 | @end quotation |
| 844 | @item owl_defense_certain |
| 845 | @cindex owl_defense_certain |
| 846 | @quotation |
| 847 | The owl code is able to finish analyzing the defense without |
| 848 | running out of nodes. |
| 849 | @end quotation |
| 850 | @item owl_second_defense_point |
| 851 | @cindex owl_second_defense_point |
| 852 | @quotation |
| 853 | A second owl defense point. |
| 854 | @end quotation |
| 855 | @end itemize |
| 856 | |
| 857 | @node Dragons in Color |
| 858 | @section Colored Dragon Display |
| 859 | @cindex colored display |
| 860 | |
| 861 | You can get a colored ASCII display of the board in which each dragon |
| 862 | is assigned a different letter; and the different values of |
| 863 | @code{dragon.status} values (@code{ALIVE}, @code{DEAD}, @code{UNKNOWN}, |
| 864 | @code{CRITICAL}) have different colors. This is very handy for debugging. |
| 865 | A second diagram shows the values of @code{owl.status}. If this |
| 866 | is @code{UNCHECKED} the dragon is displayed in White. |
| 867 | |
| 868 | Save a game in sgf format using CGoban, or using the @option{-o} option with |
| 869 | GNU Go itself. |
| 870 | |
| 871 | Open an @command{xterm} or @command{rxvt} window. You may also use the Linux |
| 872 | console. Using the console, you may need to use ``SHIFT-PAGE UP'' to see the |
| 873 | first diagram. Xterm will only work if it is compiled with color support---if |
| 874 | you do not see the colors try @command{rxvt}. Make the background color black |
| 875 | and the foreground color white. |
| 876 | |
| 877 | Execute: |
| 878 | |
| 879 | @command{gnugo -l [filename] -L [movenum] -T} to get the colored display. |
| 880 | |
| 881 | The color scheme: Green = @code{ALIVE}; Yellow = @code{UNKNOWN}; |
| 882 | Cyan = @code{DEAD} and Red = @code{CRITICAL}. Worms which have been |
| 883 | amalgamated into the same dragon are labelled with the same letter. |
| 884 | |
| 885 | Other useful colored displays may be obtained by using instead: |
| 886 | |
| 887 | @itemize @bullet |
| 888 | @item the option -E to display eye spaces (@pxref{Eyes}). |
| 889 | @item the option -m 0x0180 to display territory, moyo and area |
| 890 | (@pxref{Territory and Moyo}). |
| 891 | @end itemize |
| 892 | |
| 893 | The colored displays are documented elsewhere (@pxref{Colored Display}). |
| 894 | |