| 1 | @menu |
| 2 | * Patterns Overview:: Overview of the pattern database. |
| 3 | * Pattern Classification:: The classification field |
| 4 | * Pattern Values:: The value field |
| 5 | * Helper Functions:: Helper Functions |
| 6 | * Autohelpers and Constraints:: Automatic generation of helper functions. |
| 7 | * Autohelper Actions:: Autohelper Actions |
| 8 | * Autohelper Functions:: Autohelper Functions |
| 9 | * Attack and Defense DB:: The Attack and defense moves database. |
| 10 | * Connections Database:: The connection database. |
| 11 | * Connection Functions:: Functions in @file{connections.c} |
| 12 | * Tuning:: Tuning the pattern database. |
| 13 | * PM Implementation:: Implementation. |
| 14 | * Symmetry & transformations:: Symmetry and transformations. |
| 15 | * Details:: Details of implementation. |
| 16 | * Grid optimization:: The ``grid'' optimization. |
| 17 | * Joseki Compiler:: The joseki compiler. |
| 18 | * Ladders in Joseki:: Example: ladders in joseki. |
| 19 | * Corner Matcher:: A special matcher for joseki patterns. |
| 20 | * Editing Patterns:: Emacs major mode for pattern files. |
| 21 | @end menu |
| 22 | |
| 23 | @node Patterns Overview |
| 24 | @section Overview |
| 25 | |
| 26 | @cindex pattern overview |
| 27 | @cindex pattern matching |
| 28 | @cindex pattern database |
| 29 | @cindex eye shapes database |
| 30 | @cindex defence shapes database |
| 31 | @cindex attack shapes database |
| 32 | @cindex connection shapes database |
| 33 | @cindex pattern.h |
| 34 | @cindex pattern.c |
| 35 | |
| 36 | Several pattern databases are in the patterns directory. This chapter |
| 37 | primarily discusses the patterns in @file{patterns.db}, @file{patterns2.db}, |
| 38 | and the pattern files @file{hoshi.db} etc. which are compiled from the SGF |
| 39 | files @file{hoshi.sgf} (@pxref{Joseki Compiler}). There is no essential |
| 40 | difference between these files, except that the ones in @file{patterns.db} and |
| 41 | @file{patterns2.db} are hand written. They are concatenated before being |
| 42 | compiled by @code{mkpat} into @file{patterns.c}. The purpose of the separate |
| 43 | file @file{patterns2.db} is that it is handy to move patterns into a new |
| 44 | directory in the course of organizing them. The patterns in @file{patterns.db} |
| 45 | are more disorganized, and are slowly being moved to @file{patterns2.db}. |
| 46 | |
| 47 | During the execution of @code{genmove()}, the patterns are matched in |
| 48 | @file{shapes.c} in order to find move reasons. |
| 49 | |
| 50 | The same basic pattern format is used by @file{attack.db}, @file{defense.db}, |
| 51 | @file{conn.db}, @file{apats.db} and @file{dpats.db}. However these patterns |
| 52 | are used for different purposes. These databases are discussed in other parts |
| 53 | of this documentation. The patterns in @file{eyes.db} are entirely different |
| 54 | and are documented elsewhere (@pxref{Eyes}). |
| 55 | |
| 56 | @cindex format of the pattern database |
| 57 | @cindex description of shapes |
| 58 | @cindex ascii description of shapes |
| 59 | |
| 60 | The patterns described in the databases are ascii representations, of |
| 61 | the form: |
| 62 | |
| 63 | Pattern EB112 |
| 64 | |
| 65 | @example |
| 66 | |
| 67 | ?X?.? jump under |
| 68 | O.*oo |
| 69 | O.... |
| 70 | o.... |
| 71 | ----- |
| 72 | |
| 73 | :8,ed,NULL |
| 74 | @end example |
| 75 | |
| 76 | Here @samp{O} marks a friendly stone, @samp{X} marks an enemy stone, @samp{.} marks |
| 77 | an empty vertex, @samp{*} marks O's next move, @samp{o} marks a square either |
| 78 | containing @samp{O} or empty but not @samp{X}. (The symbol @samp{x}, which does not |
| 79 | appear in this pattern, means @samp{X} or @samp{.}.) Finally @samp{?} Indicates a |
| 80 | location where we don't care what is there, except that it cannot be |
| 81 | off the edge of the board. |
| 82 | |
| 83 | The line of @samp{-}'s along the bottom in this example is the edge of the |
| 84 | board itself---this is an edge pattern. Corners can also be indicated. |
| 85 | Elements are not generated for @samp{?} markers, but they are not |
| 86 | completely ignored - see below. |
| 87 | |
| 88 | The line beginning @samp{:} describes various attributes of the pattern, such |
| 89 | as its symmetry and its class. Optionally, a function called a |
| 90 | ``helper'' can be provided to assist the matcher in deciding whether |
| 91 | to accept move. Most patterns do not require a helper, and this field |
| 92 | is filled with NULL. |
| 93 | |
| 94 | @findex shapes_callback |
| 95 | The matcher in @file{matchpat.c} searches the board for places where this |
| 96 | layout appears on the board, and the callback function |
| 97 | @code{shapes_callback()} in @file{shapes.c} registers the appropriate move |
| 98 | reasons. |
| 99 | |
| 100 | After the pattern, there is some supplementary information in the format: |
| 101 | @example |
| 102 | |
| 103 | :trfno, classification, [values], helper_function |
| 104 | |
| 105 | @end example |
| 106 | |
| 107 | Here trfno represents the number of transformations of the pattern to |
| 108 | consider, usually @samp{8} (no symmetry, for historical reasons), or one of |
| 109 | @samp{|}, @samp{\}, @samp{/}, @samp{-}, @samp{+}, @samp{X}, where the line |
| 110 | represents the axis of symmetry. (E.g. @samp{|} means symmetrical about a |
| 111 | vertical axis.) |
| 112 | |
| 113 | The above pattern could equally well be written on the left edge: |
| 114 | |
| 115 | @example |
| 116 | |
| 117 | |oOO? |
| 118 | |...X |
| 119 | |..*? |
| 120 | |..o. |
| 121 | |..o? |
| 122 | |
| 123 | :8,ed,NULL |
| 124 | @end example |
| 125 | |
| 126 | The program @code{mkpat} is capable of parsing patterns written this |
| 127 | way, or for that matter, on the top or right edges, or in any |
| 128 | of the four corners. As a matter of convention all the edge patterns |
| 129 | in @file{patterns.db} are written on the bottom edge or in the lower left |
| 130 | corners. In the @file{patterns/} directory there is a program called |
| 131 | @code{transpat} which can rotate or otherwise transpose patterns. |
| 132 | This program is not built by default---if you think you need it, |
| 133 | @code{make transpat} in the @file{patterns/} directory and |
| 134 | consult the usage remarks at the beginning of @file{patterns/transpat.c}. |
| 135 | |
| 136 | @node Pattern Classification |
| 137 | @section Pattern Attributes |
| 138 | |
| 139 | @cindex pattern attributes |
| 140 | @cindex shape attributes |
| 141 | |
| 142 | The attribute field in the @samp{:} line of a pattern consists of a sequence |
| 143 | of zero or more of the following characters, each with a different |
| 144 | meaning. The attributes may be roughly classified as @dfn{constraints}, |
| 145 | which determine whether or not the pattern is matched, and @dfn{actions}, |
| 146 | which describe what is to be done when the pattern is matched, typically |
| 147 | to add a move reason. |
| 148 | |
| 149 | @subsection Constraint Pattern Attributes |
| 150 | |
| 151 | @itemize |
| 152 | @item @samp{s} |
| 153 | @quotation |
| 154 | Safety of the move is not checked. This is appropriate for sacrifice |
| 155 | patterns. If this classification is omitted, the matcher requires that the |
| 156 | stone played cannot be trivially captured. Even with s classification, a check |
| 157 | for legality is made, though. |
| 158 | @end quotation |
| 159 | @item @samp{n} |
| 160 | @quotation |
| 161 | In addition to usual check that the stone played cannot be |
| 162 | trivially captured, it is also confirmed that an opponent |
| 163 | move here could not be captured. |
| 164 | @end quotation |
| 165 | @item @samp{O} |
| 166 | @quotation |
| 167 | It is checked that every friendly (@samp{O}) stone of the pattern belongs to a |
| 168 | dragon which has status (@pxref{Dragons}) @code{ALIVE} or |
| 169 | @code{UNKNOWN}. The @code{CRITICAL} matcher status is excluded. It is possible |
| 170 | for a string to have @code{ALIVE} status and still be tactically |
| 171 | critical, since it might be amalgamated into an ALIVE dragon, and the matcher |
| 172 | status is constant on the dragon. Therefore, an additional test is performed: |
| 173 | if the pattern contains a string which is tactically critical, and if @samp{*} |
| 174 | does not rescue it, the pattern is rejected. |
| 175 | @end quotation |
| 176 | @item @samp{o} |
| 177 | @quotation |
| 178 | It is checked that every friendly (@samp{O}) stone of the pattern |
| 179 | belongs to a dragon which is classified as @code{DEAD} or @code{UNKNOWN}. |
| 180 | @end quotation |
| 181 | @item @samp{X} |
| 182 | @quotation |
| 183 | It is checked that every opponent (@samp{X}) stone of the pattern |
| 184 | belongs to a dragon with status @code{ALIVE}, @code{UNKNOWN} or |
| 185 | @code{CRITICAL}. Note that there is an asymmetry with @samp{O} patterns, where |
| 186 | @code{CRITICAL} dragons are rejected. |
| 187 | @end quotation |
| 188 | @item @samp{x} |
| 189 | @quotation |
| 190 | It is checked that every opponent (@samp{X}) stone of the pattern |
| 191 | belongs to a dragon which is classified as @code{DEAD} or @code{UNKNOWN} |
| 192 | @end quotation |
| 193 | @end itemize |
| 194 | |
| 195 | @subsection Action Attributes |
| 196 | |
| 197 | @itemize |
| 198 | @item @samp{C} |
| 199 | @quotation |
| 200 | If two or more distinct O dragons occur in the pattern, the |
| 201 | move is given the move reasons that it connects each pair of |
| 202 | dragons. An exception is made for dragons where the underlying |
| 203 | worm can be tactically captured and is not defended by the |
| 204 | considered move. |
| 205 | @end quotation |
| 206 | @item @samp{c} |
| 207 | @quotation |
| 208 | Add strategical defense move reason for all our |
| 209 | dragons and a small shape bonus. This classification is |
| 210 | appropriate for weak connection patterns. |
| 211 | @end quotation |
| 212 | @item @samp{B} |
| 213 | @quotation |
| 214 | If two or more distinct @samp{X} dragons occur in the pattern, the |
| 215 | move is given the move reasons that it cuts each pair of |
| 216 | dragons. |
| 217 | @end quotation |
| 218 | @item @samp{e} |
| 219 | @quotation |
| 220 | The move makes or secures territory. |
| 221 | @end quotation |
| 222 | @item @samp{E} |
| 223 | @quotation |
| 224 | The move attempts increase influence and create/expand a moyo. |
| 225 | @end quotation |
| 226 | @item @samp{d} |
| 227 | @quotation |
| 228 | The move strategically defends all O dragons in the pattern, |
| 229 | except those that can be tactically captured and are not |
| 230 | tactically defended by this move. If any O dragon should |
| 231 | happen to be perfectly safe already, this only reflects in |
| 232 | the move reason being valued to zero. |
| 233 | @end quotation |
| 234 | @item @samp{a} |
| 235 | @quotation |
| 236 | The move strategically attacks all @samp{X} dragons in the pattern. |
| 237 | @end quotation |
| 238 | @item @samp{J} |
| 239 | @quotation |
| 240 | Standard joseki move. Unless there is an urgent move on the board these moves |
| 241 | are made as soon as they can be. This is equivalent to adding the @samp{d} |
| 242 | and @samp{a} classifications together with a minimum accepted value of 27. |
| 243 | @end quotation |
| 244 | @item @samp{F} |
| 245 | @quotation |
| 246 | This indicates a fuseki pattern. This is only effective together with |
| 247 | either the @samp{j} or @samp{t} classification, and is used to ensure |
| 248 | indeterministic play during fuseki. |
| 249 | @end quotation |
| 250 | @item @samp{j} |
| 251 | @quotation |
| 252 | Slightly less urgent joseki move. These moves will be made after those |
| 253 | with the @samp{J} classification. This adds the |
| 254 | @samp{e} and @samp{E} classifications. If the move has the @samp{F} |
| 255 | classification, it also gets a fixed value of 20.1, otherwise it |
| 256 | gets a minimum accepted value of 20. (This makes sure that GNU Go chooses |
| 257 | randomly between different moves that have @samp{jF} as classification.) |
| 258 | @end quotation |
| 259 | @item @samp{t} |
| 260 | @quotation |
| 261 | Minor joseki move (tenuki OK). This is equivalent to adding the @samp{e} and |
| 262 | @samp{E} classifications together with either a fixed value of 15.07 (if |
| 263 | the move has @samp{F} classification) or a minimum value of 15 (otherwise). |
| 264 | @end quotation |
| 265 | @item @samp{U} |
| 266 | @quotation |
| 267 | Urgent joseki move (never tenuki). This is equivalent to the @samp{d} and |
| 268 | @samp{a} classifications together with a shape bonus of 15 and a minimum |
| 269 | accepted value of 40. |
| 270 | @end quotation |
| 271 | @end itemize |
| 272 | |
| 273 | A commonly used class is @code{OX} (which rejects pattern if either side |
| 274 | has dead stones). The string @samp{-} may be used as a placeholder. (In |
| 275 | fact any characters other than the above and @samp{,} are ignored.) |
| 276 | |
| 277 | The types @samp{o} and @samp{O} could conceivably appear in a class, meaning it |
| 278 | applies only to @code{UNKNOWN}. @samp{X} and @samp{x} could similarly be used together. |
| 279 | All classes can be combined arbitrarily. |
| 280 | |
| 281 | @node Pattern Values |
| 282 | @section Pattern Attributes |
| 283 | |
| 284 | The second and following fields in the @samp{:} line of a pattern |
| 285 | are optional and of the form @code{value1(x),value2(y),...}. The available set |
| 286 | of values are as follows. |
| 287 | |
| 288 | @itemize @bullet |
| 289 | @item @code{terri(x)} |
| 290 | @findex terri |
| 291 | @quotation |
| 292 | Forces the territorial value of the move to be at least x. |
| 293 | @end quotation |
| 294 | @item @code{minterri(x)} |
| 295 | @findex minterri |
| 296 | @quotation |
| 297 | Forces the territorial value of the move to be at least x. |
| 298 | @end quotation |
| 299 | @item @code{maxterri(x)} |
| 300 | @findex maxterri |
| 301 | @quotation |
| 302 | Forces the territorial value of the move to be at most x. |
| 303 | @end quotation |
| 304 | @item @code{value(x)} |
| 305 | @findex value |
| 306 | @quotation |
| 307 | Forces the final value of the move to be at least x. |
| 308 | @end quotation |
| 309 | @item @code{minvalue(x)}, @code{maxvalue(x)} |
| 310 | @findex minvalue |
| 311 | @findex maxvalue |
| 312 | @quotation |
| 313 | Forces the final value of the move to be at least/most x. |
| 314 | @end quotation |
| 315 | @item @code{shape(x)} |
| 316 | @findex shape |
| 317 | @quotation |
| 318 | Adds x to the move's shape value. |
| 319 | @end quotation |
| 320 | @item @code{followup(x)} |
| 321 | @findex followup |
| 322 | @quotation |
| 323 | Adds x to the move's followup value. |
| 324 | @end quotation |
| 325 | @end itemize |
| 326 | |
| 327 | The meaning of these values is documented in @xref{Move Generation}. |
| 328 | |
| 329 | @node Helper Functions |
| 330 | @section Helper Functions |
| 331 | |
| 332 | @cindex helper functions in pattern matching |
| 333 | |
| 334 | Helper functions can be provided to assist the matcher in deciding |
| 335 | whether to accept a pattern, register move reasons, and setting |
| 336 | various move values. The helper is supplied with the compiled pattern |
| 337 | entry in the table, and the (absolute) position on the board of the |
| 338 | @samp{*} point. |
| 339 | |
| 340 | One difficulty is that the helper must be able to cope with all the |
| 341 | possible transformations of the pattern. To help with this, the OFFSET |
| 342 | macro is used to transform relative pattern coordinates to absolute |
| 343 | board locations. |
| 344 | |
| 345 | The actual helper functions are in @file{helpers.c}. They are declared |
| 346 | in @file{patterns.h}. |
| 347 | |
| 348 | As an example to show how to write a helper function, we consider |
| 349 | a hypothetical helper called @code{wedge_helper}. Such a helper |
| 350 | used to exist, but has been replaced by a constraint. Due to |
| 351 | its simplicity it's still a good example. The helper begins with a |
| 352 | comment: |
| 353 | |
| 354 | @example |
| 355 | /* |
| 356 | |
| 357 | ?O. ?Ob |
| 358 | .X* aX* |
| 359 | ?O. ?Oc |
| 360 | |
| 361 | :8,C,wedge_helper |
| 362 | */ |
| 363 | @end example |
| 364 | |
| 365 | The image on the left is the actual pattern. On the right we've taken |
| 366 | this image and added letters to label @code{apos}, @code{bpos}, and |
| 367 | @code{cpos}. The position of *, the point where GNU Go will move if the |
| 368 | pattern is adopted, is passed through the parameter @code{move}. |
| 369 | |
| 370 | @example |
| 371 | int |
| 372 | wedge_helper(ARGS) |
| 373 | @{ |
| 374 | int apos, bpos, cpos; |
| 375 | int other = OTHER_COLOR(color); |
| 376 | int success = 0; |
| 377 | |
| 378 | apos = OFFSET(0, -2); |
| 379 | bpos = OFFSET(-1, 0); |
| 380 | cpos = OFFSET(1, 0); |
| 381 | |
| 382 | if (TRYMOVE(move, color)) @{ |
| 383 | if (TRYMOVE(apos, other)) @{ |
| 384 | if (board[apos] == EMPTY || attack(apos, NULL)) |
| 385 | success = 1; |
| 386 | else if (TRYMOVE(bpos, color)) @{ |
| 387 | if (!safe_move(cpos, other)) |
| 388 | success = 1; |
| 389 | popgo(); |
| 390 | @} |
| 391 | popgo(); |
| 392 | @} |
| 393 | popgo(); |
| 394 | @} |
| 395 | |
| 396 | return success; |
| 397 | @} |
| 398 | |
| 399 | @end example |
| 400 | |
| 401 | The @code{OFFSET} lines tell GNU Go the positions of the three stones at |
| 402 | @samp{a}, @samp{b}, and @samp{c}. To decide whether the pattern |
| 403 | guarantees a connection, we do some reading. First we use the |
| 404 | @code{TRYMOVE} macro to place an @samp{O} at @samp{move} and let |
| 405 | @samp{X} draw back to @samp{a}. Then we ask whether @samp{O} can capture |
| 406 | these stones by calling @code{attack()}. The test if there is a stone at |
| 407 | @samp{a} before calling @code{attack()} is in this position not really |
| 408 | necessary but it's good practice to do so, because if the attacked stone |
| 409 | should happen to already have been captured while placing stones, GNU Go |
| 410 | would crash with an assertion failure. |
| 411 | |
| 412 | If this attack fails we let @samp{O} connect at @samp{b} and use the |
| 413 | @code{safe_move()} function to examine whether a cut by @samp{X} at |
| 414 | @samp{c} could be immediately captured. Before we return the result we |
| 415 | need to remove the stones we placed from the reading stack. This is done |
| 416 | with the function @code{popgo()}. |
| 417 | |
| 418 | @node Autohelpers and Constraints |
| 419 | @section Autohelpers and Constraints |
| 420 | |
| 421 | @cindex generation of helper functions |
| 422 | @cindex Autohelpers |
| 423 | |
| 424 | In addition to the hand-written helper functions in @file{helpers.c}, GNU Go |
| 425 | can automatically generate helper functions from a diagram with labels |
| 426 | and an expression describing a constraint. The constraint diagram, |
| 427 | specifying the labels, is placed below the @samp{:} line and the constraint |
| 428 | expression is placed below the diagram on line starting with a @samp{;}. |
| 429 | Constraints can only be used to accept or reject a pattern. If the |
| 430 | constraint evaluates to zero (false) the pattern is rejected, |
| 431 | otherwise it's accepted (still conditioned on passing all other tests |
| 432 | of course). To give a simple example we consider a connection pattern. |
| 433 | |
| 434 | @example |
| 435 | |
| 436 | Pattern Conn311 |
| 437 | |
| 438 | O*. |
| 439 | ?XO |
| 440 | |
| 441 | :8,C,NULL |
| 442 | |
| 443 | O*a |
| 444 | ?BO |
| 445 | |
| 446 | ;oplay_attack_either(*,a,a,B) |
| 447 | |
| 448 | @end example |
| 449 | |
| 450 | Here we have given the label @samp{a} to the empty spot to the right of |
| 451 | the considered move and the label @samp{B} to the @samp{X} stone in the |
| 452 | pattern. In addition to these, @samp{*} can also be used as a label. A |
| 453 | label may be any lowercase or uppercase ascii letter except @code{OoXxt}. By |
| 454 | convention we use uppercase letters for @samp{X} stones and lowercase for @samp{O} |
| 455 | stones and empty intersections. When labeling a stone that's part of a |
| 456 | larger string in the pattern, all stones of the string should be marked |
| 457 | with the label. (These conventions are not enforced by the pattern |
| 458 | compiler, but to make the database consistent and easy to read they |
| 459 | should be followed.) |
| 460 | |
| 461 | The labels can now be used in the constraint expression. In this example |
| 462 | we have a reading constraint which should be interpreted as "Play an |
| 463 | @samp{O} stone at @samp{*} followed by an @samp{X} stone at |
| 464 | @samp{a}. Accept the pattern if @samp{O} now can capture either at |
| 465 | @samp{a} or at @samp{B} (or both strings)." |
| 466 | |
| 467 | The functions that are available for use in the constraints are listed |
| 468 | in the section `Autohelpers Functions' below. Technically the |
| 469 | constraint expression is transformed by mkpat into an automatically |
| 470 | generated helper function in @file{patterns.c}. The functions in the |
| 471 | constraint are replaced by C expressions, often functions calls. In |
| 472 | principle any valid C code can be used in the constraints, but there |
| 473 | is in practice no reason to use anything more than boolean and |
| 474 | arithmetic operators in addition to the autohelper functions. |
| 475 | Constraints can span multiple lines, which are then concatenated. |
| 476 | |
| 477 | @node Autohelper Actions |
| 478 | @section Autohelper Actions |
| 479 | |
| 480 | @cindex autohelper actions |
| 481 | |
| 482 | As a complement to the constraints, which only can accept or reject a |
| 483 | pattern, one can also specify an action to perform when the pattern |
| 484 | has passed all tests and finally has been accepted. |
| 485 | |
| 486 | Example: |
| 487 | |
| 488 | @example |
| 489 | |
| 490 | Pattern EJ4 |
| 491 | |
| 492 | ...*. continuation |
| 493 | .OOX. |
| 494 | ..XOX |
| 495 | ..... |
| 496 | ----- |
| 497 | |
| 498 | :8,Ed,NULL |
| 499 | |
| 500 | ...*. never play a here |
| 501 | .OOX. |
| 502 | .aXOX |
| 503 | ..... |
| 504 | ----- |
| 505 | |
| 506 | >antisuji(a) |
| 507 | |
| 508 | @end example |
| 509 | |
| 510 | The line starting with @samp{>} is the action line. In this case it tells |
| 511 | the move generation that the move at a should not be considered, |
| 512 | whatever move reasons are found by other patterns. The action line |
| 513 | uses the labels from the constraint diagram. Both constraint and |
| 514 | action can be used in the same pattern. If the action only needs to |
| 515 | refer to @samp{*}, no constraint diagram is required. Like constraints, |
| 516 | actions can span multiple lines. |
| 517 | |
| 518 | Here is a partial list of the autohelper macros which are typically |
| 519 | called from action lines. This list is not complete. If you cannot find an |
| 520 | autohelper macro in an action line in this list, consult @file{mkpat.c} to |
| 521 | find out what function in the engine is actually called. If no |
| 522 | macro exists which does what you want, you can add macros by |
| 523 | editing the list in @file{mkpat.c}. |
| 524 | |
| 525 | @itemize |
| 526 | @item @code{antisuji(a);} |
| 527 | @quotation |
| 528 | Mark @samp{a} as an antisuji, that is, a move that must never |
| 529 | be played. |
| 530 | @end quotation |
| 531 | @item @code{replace(a,*)} |
| 532 | @quotation |
| 533 | This is appropriate if the move at @samp{*} is definitely better |
| 534 | than the move at @samp{a}. The macro adds a point redistribution rule. Any |
| 535 | points which are assigned to @samp{a} during the move generation |
| 536 | by any move reason are redistributed to @samp{*}. |
| 537 | @end quotation |
| 538 | @item @code{prevent_attack_threat(a)} |
| 539 | @quotation |
| 540 | Add a reverse followup value because the opponent's move here |
| 541 | would threaten to capture @samp{a}. |
| 542 | @end quotation |
| 543 | @item @code{threaten_to_save(a)} |
| 544 | @quotation |
| 545 | Add a followup value because the move at @samp{*} threatens to |
| 546 | rescue the dead string at @samp{a}. |
| 547 | @end quotation |
| 548 | @item @code{defend_against_atari(a)} |
| 549 | @quotation |
| 550 | Estimate the value of defending the string @samp{a} which can be put into |
| 551 | atari and add this as a reverse followup value. |
| 552 | @end quotation |
| 553 | @item @code{add_defend_both_move(a,b);} |
| 554 | @quotation |
| 555 | @end quotation |
| 556 | @item @code{add_cut_move(c,d);} |
| 557 | @quotation |
| 558 | Add to the move reasons that the move at @samp{*} threatens to cut |
| 559 | @samp{c} and @samp{d}. |
| 560 | @end quotation |
| 561 | @end itemize |
| 562 | |
| 563 | @node Autohelper Functions |
| 564 | @section Autohelper Functions |
| 565 | |
| 566 | The autohelper functions are translated into C code by the program in |
| 567 | @file{mkpat.c}. To see exactly how the functions are implemented, |
| 568 | consult the autohelper function definitions in that file. Autohelper |
| 569 | functions can be used in both constraint and action lines. |
| 570 | |
| 571 | @example |
| 572 | |
| 573 | @code{lib(x)} |
| 574 | @code{lib2(x)} |
| 575 | @code{lib3(x)} |
| 576 | @code{lib4(x)} |
| 577 | |
| 578 | @end example |
| 579 | |
| 580 | Number of first, second, third, and fourth order liberties of a worm |
| 581 | respectively. @xref{Worms and Dragons}, the documentation on worms for |
| 582 | definitions. |
| 583 | |
| 584 | @example |
| 585 | |
| 586 | @code{xlib(x)} |
| 587 | @code{olib(x)} |
| 588 | |
| 589 | @end example |
| 590 | |
| 591 | The number of liberties that an enemy or own stone, respectively, |
| 592 | would obtain if played at the empty intersection @samp{x}. |
| 593 | |
| 594 | @example |
| 595 | @code{xcut(x)} |
| 596 | @code{ocut(x)} |
| 597 | @end example |
| 598 | |
| 599 | Calls @code{cut_possible} (@pxref{General Utilities}) to determine |
| 600 | whether @samp{X} or @samp{O} can cut at the empty intersection @samp{x}. |
| 601 | |
| 602 | @example |
| 603 | @code{ko(x)} |
| 604 | @end example |
| 605 | |
| 606 | True if @samp{x} is either a stone or an empty point involved in a ko |
| 607 | position. |
| 608 | |
| 609 | @example |
| 610 | @code{status(x)} |
| 611 | @end example |
| 612 | |
| 613 | The matcher status of a dragon. status(x) returns an integer that can have the |
| 614 | values @code{ALIVE}, @code{UNKNOWN}, @code{CRITICAL}, or @code{DEAD} |
| 615 | (@pxref{Worms and Dragons}). |
| 616 | |
| 617 | @example |
| 618 | @code{alive(x)} |
| 619 | @code{unknown(x)} |
| 620 | @code{critical(x)} |
| 621 | @code{dead(x)} |
| 622 | @end example |
| 623 | |
| 624 | Each function true if the dragon has the corresponding matcher status and |
| 625 | false otherwise (@pxref{Worms and Dragons}). |
| 626 | |
| 627 | @example |
| 628 | @code{status(x)} |
| 629 | @end example |
| 630 | |
| 631 | Returns the status of the dragon at @samp{x} (@pxref{Worms and Dragons}). |
| 632 | |
| 633 | @example |
| 634 | @code{genus(x)} |
| 635 | @end example |
| 636 | |
| 637 | The number of eyes of a dragon. It is only meaningful to compare this |
| 638 | value against 0, 1, or 2. |
| 639 | |
| 640 | @example |
| 641 | |
| 642 | @code{xarea(x)} |
| 643 | @code{oarea(x)} |
| 644 | @code{xmoyo(x)} |
| 645 | @code{omoyo(x)} |
| 646 | @code{xterri(x)} |
| 647 | @code{oterri(x)} |
| 648 | |
| 649 | @end example |
| 650 | |
| 651 | These functions call @code{whose_territory()}, @code{whose_moyo()} |
| 652 | and @code{whose_area()} (@pxref{Territory and Moyo}). For example |
| 653 | @code{xarea(x)} evaluates to true if @samp{x} is either a living enemy stone |
| 654 | or an empty point within the opponent's ``area''. The function @code{oarea(x)} |
| 655 | is analogous but with respect to our stones and area. The main difference |
| 656 | between area, moyo, and terri is that area is a very far reaching kind of |
| 657 | influence, moyo gives a more realistic estimate of what may turn in to |
| 658 | territory, and terri gives the points that already are believed to be secure |
| 659 | territory. |
| 660 | |
| 661 | @example |
| 662 | @code{weak(x)} |
| 663 | @end example |
| 664 | |
| 665 | True for a dragon that is perceived as weak. |
| 666 | |
| 667 | @example |
| 668 | |
| 669 | @code{attack(x)} |
| 670 | @code{defend(x)} |
| 671 | |
| 672 | @end example |
| 673 | |
| 674 | Results of tactical reading. @code{attack(x)} is true if the worm can be |
| 675 | captured, @code{defend(x)} is true if there also is a defending move. Please |
| 676 | notice that @code{defend(x)} will return false if there is no attack on the |
| 677 | worm. |
| 678 | |
| 679 | @example |
| 680 | |
| 681 | @code{safe_xmove(x)} |
| 682 | @code{safe_omove(x)} |
| 683 | |
| 684 | @end example |
| 685 | |
| 686 | True if an enemy or friendly stone, respectively, can safely be played at |
| 687 | @samp{x}. By safe it is understood that the move is legal and that it cannot |
| 688 | be captured right away. |
| 689 | |
| 690 | @example |
| 691 | |
| 692 | @code{legal_xmove(x)} |
| 693 | @code{legal_omove(x)} |
| 694 | |
| 695 | @end example |
| 696 | |
| 697 | True if an enemy or friendly stone, respectively, can legally be played at x. |
| 698 | |
| 699 | @example |
| 700 | |
| 701 | o_somewhere(x,y,z, ...) |
| 702 | x_somewhere(x,y,z, ...) |
| 703 | |
| 704 | @end example |
| 705 | |
| 706 | True if O (respectively X) has a stone at one of the labelled vertices. |
| 707 | In the diagram, these vertices should be marked with a @samp{?}. |
| 708 | |
| 709 | @example |
| 710 | |
| 711 | odefend_against(x,y) |
| 712 | xdefend_against(x,y) |
| 713 | |
| 714 | @end example |
| 715 | |
| 716 | True if an own stone at @samp{x} would stop the enemy from safely playing at |
| 717 | @samp{y}, and conversely for the second function. |
| 718 | |
| 719 | @example |
| 720 | |
| 721 | @code{does_defend(x,y)} |
| 722 | @code{does_attack(x,y)} |
| 723 | |
| 724 | @end example |
| 725 | |
| 726 | True if a move at @samp{x} defends/attacks the worm at @samp{y}. For |
| 727 | defense a move of the same color as @samp{y} is tried and for attack a move of |
| 728 | the opposite color. |
| 729 | |
| 730 | @example |
| 731 | |
| 732 | @code{xplay_defend(a,b,c,...,z)} |
| 733 | @code{oplay_defend(a,b,c,...,z)} |
| 734 | @code{xplay_attack(a,b,c,...,z)} |
| 735 | @code{oplay_attack(a,b,c,...,z)} |
| 736 | |
| 737 | @end example |
| 738 | |
| 739 | These functions make it possible to do more complex reading |
| 740 | experiments in the constraints. All of them work so that first the |
| 741 | sequence of moves @samp{a},@samp{b},@samp{c},... is played through with |
| 742 | alternating colors, starting with @samp{X} or @samp{O} as indicated by |
| 743 | the name. Then it is tested whether the worm at @samp{z} can be attacked or |
| 744 | defended, respectively. It doesn't matter who would be in turn to move, |
| 745 | a worm of either color may be attacked or defended. For attacks the |
| 746 | opposite color of the string being attacked starts moving and for |
| 747 | defense the same color starts. The defend functions return true if the |
| 748 | worm cannot be attacked in the position or if it can be attacked but |
| 749 | also defended. The attack functions return true if there is a way to |
| 750 | capture the worm, whether or not it can also be defended. If there is no |
| 751 | stone present at @samp{z} after the moves have been played, it is assumed that |
| 752 | an attack has already been successful or a defense has already failed. |
| 753 | If some of the moves should happen to be illegal, typically because it |
| 754 | would have been suicide, the following moves are played as if nothing |
| 755 | has happened and the attack or defense is tested as usual. It is assumed |
| 756 | that this convention will give the relevant result without requiring a |
| 757 | lot of special cases. |
| 758 | |
| 759 | The special label @samp{?} can be used to represent a tenuki. |
| 760 | Thus @code{oplay_defend(a,?,b,c)} tries moves by @samp{O} at @samp{a} and |
| 761 | @samp{b}, as if @samp{X} plays the second move in another part of |
| 762 | the board, then asks if @samp{c} can be defended. The tenuki cannot |
| 763 | be the first move of the sequence, nor does it need to be: |
| 764 | instead of @code{oplay_defend(?,a,b,c)} you can use |
| 765 | @code{xplay_defend(a,b,c)}. |
| 766 | |
| 767 | @example |
| 768 | @code{xplay_defend_both(a,b,c,...,y,z)} |
| 769 | @code{oplay_defend_both(a,b,c,...,y,z)} |
| 770 | @code{xplay_attack_either(a,b,c,...,y,z)} |
| 771 | @code{oplay_attack_either(a,b,c,...,y,z)} |
| 772 | |
| 773 | @end example |
| 774 | |
| 775 | These functions are similar to the previous ones. The difference is |
| 776 | that the last *two* arguments denote worms to be attacked or defended |
| 777 | simultaneously. Obviously @samp{y} and @samp{z} must have the same color. If either |
| 778 | location is empty, it is assumed that an attack has been successful or |
| 779 | a defense has failed. The typical use for these functions is in |
| 780 | cutting patterns, where it usually suffices to capture either |
| 781 | cutstone. |
| 782 | |
| 783 | The function @code{xplay_defend_both} plays alternate moves |
| 784 | beginning with an @samp{X} at @samp{a}. Then it passes the last |
| 785 | two arguments to @code{defend_both} in |
| 786 | @file{engine/utils.c}. This function checks to determine |
| 787 | whether the two strings can be simultaneously defended. |
| 788 | |
| 789 | The function @code{xplay_attack_either} plays alternate |
| 790 | moves beginning with an @samp{X} move at @samp{a}. Then it passes |
| 791 | the last two arguments to @code{attack_either} in |
| 792 | @file{engine/utils.c}. This function looks for a move |
| 793 | which captures at least one of the two strings. In its |
| 794 | current implementation @code{attack_either} only looks |
| 795 | for uncoordinated attacks and would thus miss a double |
| 796 | atari. |
| 797 | |
| 798 | @example |
| 799 | @code{xplay_connect(a,b,c,...,y,z)} |
| 800 | @code{oplay_connect(a,b,c,...,y,z)} |
| 801 | @code{xplay_disconnect(a,b,c,...,y,z)} |
| 802 | @code{oplay_disconnect(a,b,c,...,y,z)} |
| 803 | |
| 804 | @end example |
| 805 | |
| 806 | The function @code{xplay_connect(a,b,c,...,y,z)} begins |
| 807 | with an @samp{X} move at @samp{a}, then an @samp{O} |
| 808 | move at @samp{b}, and so forth, then finally calls |
| 809 | @code{string_connect()} to determine whether |
| 810 | @samp{x} and @samp{y} can be connected. The other |
| 811 | functions are similar (@pxref{Connection Reading}). |
| 812 | |
| 813 | @example |
| 814 | |
| 815 | @code{xplay_break_through(a,b,c,...,x,y,z)} |
| 816 | @code{oplay_break_through(a,b,c,...,x,y,z)} |
| 817 | |
| 818 | @end example |
| 819 | |
| 820 | These functions are used to set up a position like |
| 821 | |
| 822 | @example |
| 823 | |
| 824 | .O. .y. |
| 825 | OXO xXz |
| 826 | |
| 827 | @end example |
| 828 | |
| 829 | @noindent |
| 830 | and @samp{X} aims at capturing at least one of @samp{x}, @samp{y}, and |
| 831 | @samp{z}. If this succeeds @samp{1} is returned. If it doesn't, @samp{X} |
| 832 | tries instead to cut through on either side and if this succeeds, |
| 833 | @samp{2} is returned. Of course the same shape with opposite colors can |
| 834 | also be used. |
| 835 | |
| 836 | Important notice: @samp{x}, @samp{y}, and @samp{z} must be given in the |
| 837 | order they have in the diagram above, or any reflection and/or rotation |
| 838 | of it. |
| 839 | |
| 840 | @example |
| 841 | seki_helper(x) |
| 842 | @end example |
| 843 | |
| 844 | Checks whether the string at @samp{x} can attack any surrounding |
| 845 | string. If so, return false as the move to create a seki (probably) |
| 846 | wouldn't work. |
| 847 | |
| 848 | @example |
| 849 | threaten_to_save(x) |
| 850 | @end example |
| 851 | |
| 852 | Calls @code{add_followup_value} to add as a move reason a conservative |
| 853 | estimate of the value of saving the string @samp{x} by capturing one opponent |
| 854 | stone. |
| 855 | |
| 856 | @example |
| 857 | area_stone(x) |
| 858 | @end example |
| 859 | |
| 860 | Returns the number of stones in the area around @samp{x}. |
| 861 | |
| 862 | @example |
| 863 | area_space(x) |
| 864 | @end example |
| 865 | |
| 866 | Returns the amount of space in the area around @samp{x}. |
| 867 | |
| 868 | @example |
| 869 | @code{eye(x)} |
| 870 | @code{proper_eye(x)} |
| 871 | @code{marginal_eye(x)} |
| 872 | @end example |
| 873 | |
| 874 | True if @samp{x} is an eye space for either color, a non-marginal eye space |
| 875 | for either color, or a marginal eye space for either color, |
| 876 | respectively. |
| 877 | |
| 878 | @example |
| 879 | @code{antisuji(x)} |
| 880 | @end example |
| 881 | |
| 882 | Tell the move generation that @samp{x} is a substandard move that never should |
| 883 | be played. |
| 884 | |
| 885 | @example |
| 886 | same_dragon(x,y) |
| 887 | same_worm(x,y) |
| 888 | @end example |
| 889 | |
| 890 | Return true if @samp{x} and @samp{y} are the same dragon or worm respectively. |
| 891 | |
| 892 | @example |
| 893 | @code{dragonsize(x)} |
| 894 | @code{wormsize(x)} |
| 895 | @end example |
| 896 | |
| 897 | Number of stones in the indicated dragon or worm. |
| 898 | |
| 899 | @example |
| 900 | @code{add_connect_move(x,y)} |
| 901 | @code{add_cut_move(x,y)} |
| 902 | @code{add_attack_either_move(x,y)} |
| 903 | @code{add_defend_both_move(x,y)} |
| 904 | @end example |
| 905 | |
| 906 | Explicitly notify the move generation about move reasons for the move |
| 907 | in the pattern. |
| 908 | |
| 909 | @example |
| 910 | @code{halfeye(x)} |
| 911 | @end example |
| 912 | |
| 913 | Returns true if the empty intersection at @samp{x} is a half eye. |
| 914 | |
| 915 | @example |
| 916 | @code{remove_attack(x)} |
| 917 | @end example |
| 918 | |
| 919 | Inform the tactical reading that a supposed attack does in fact not |
| 920 | work. |
| 921 | |
| 922 | @example |
| 923 | @code{potential_cutstone(x)} |
| 924 | @end example |
| 925 | |
| 926 | True if @code{cutstone2} field from worm data is larger than one. This |
| 927 | indicates that saving the worm would introduce at least two new |
| 928 | cutting points. |
| 929 | |
| 930 | @example |
| 931 | @code{not_lunch(x,y)} |
| 932 | @end example |
| 933 | |
| 934 | Prevents the misreporting of @samp{x} as lunch for @samp{y}. |
| 935 | For example, the following pattern tells GNU Go that even |
| 936 | though the stone at @samp{a} can be captured, it should not |
| 937 | be considered ``lunch'' for the dragon at @samp{b}, because |
| 938 | capturing it does not produce an eye: |
| 939 | |
| 940 | @example |
| 941 | XO| ba| |
| 942 | O*| O*| |
| 943 | oo| oo| |
| 944 | ?o| ?o| |
| 945 | |
| 946 | > not_lunch(a,b) |
| 947 | @end example |
| 948 | |
| 949 | @example |
| 950 | @code{vital_chain(x)} |
| 951 | @end example |
| 952 | |
| 953 | Calls @code{vital_chain} to determine whether capturing |
| 954 | the stone at @samp{x} will result in one eye for an adjacent |
| 955 | dragon. The current implementation just checks that the stone |
| 956 | is not a singleton on the first line. |
| 957 | |
| 958 | @example |
| 959 | @code{amalgamate(x,y)} |
| 960 | @end example |
| 961 | |
| 962 | Amalgamate (join) the dragons at @samp{x} and @samp{y} (@pxref{Worms and Dragons}). |
| 963 | |
| 964 | @example |
| 965 | @code{amalgamate_most_valuable(x,y,z)} |
| 966 | @end example |
| 967 | |
| 968 | Called when @samp{x}, @samp{y}, @samp{z} point to three (preferably distinct) |
| 969 | dragons, in situations such as this: |
| 970 | |
| 971 | @example |
| 972 | |
| 973 | .O.X |
| 974 | X*OX |
| 975 | .O.X |
| 976 | |
| 977 | @end example |
| 978 | |
| 979 | In this situation, the opponent can play at @samp{*}, preventing |
| 980 | the three dragons from becoming connected. However @samp{O} |
| 981 | can decide which cut to allow. The helper amalgamates the |
| 982 | dragon at @samp{y} with either @samp{x} or @samp{z}, |
| 983 | whichever is largest. |
| 984 | |
| 985 | @example |
| 986 | make_proper_eye(x) |
| 987 | @end example |
| 988 | |
| 989 | This autohelper should be called when @samp{x} is an eyespace |
| 990 | which is misidentified as marginal. It is reclassified as |
| 991 | a proper eyespace (@pxref{Eye Space}). |
| 992 | |
| 993 | @example |
| 994 | remove_halfeye(x) |
| 995 | @end example |
| 996 | |
| 997 | Remove a half eye from the eyespace. This helper should not be run after |
| 998 | @code{make_dragons} is finished, since by that time the eyespaces have |
| 999 | already been analyzed. |
| 1000 | |
| 1001 | @example |
| 1002 | remove_eyepoint(x) |
| 1003 | @end example |
| 1004 | |
| 1005 | Remove an eye point. This function can only be used before the |
| 1006 | segmentation into eyespaces. |
| 1007 | |
| 1008 | @example |
| 1009 | @code{owl_topological_eye(x,y)} |
| 1010 | @end example |
| 1011 | |
| 1012 | Here @samp{x} is an empty intersection which may be an |
| 1013 | eye or half eye for some dragon, and @samp{y} is a |
| 1014 | stone of the dragon, used only to determine the color |
| 1015 | of the eyespace in question. Returns the sum of the values |
| 1016 | of the diagonal intersections, relative to @samp{x}, as |
| 1017 | explained in @xref{Eye Topology}, equal to 4 or more if the |
| 1018 | eye at @samp{x} is false, 3 if it is a half eye, and 2 if it |
| 1019 | is a true eye. |
| 1020 | |
| 1021 | @example |
| 1022 | @code{owl_escape_value(x)} |
| 1023 | @end example |
| 1024 | |
| 1025 | Returns the escape value at @samp{x}. This is only useful in owl |
| 1026 | attack and defense patterns. |
| 1027 | |
| 1028 | @node Attack and Defense DB |
| 1029 | @section Attack and Defense Database |
| 1030 | |
| 1031 | The patterns in @file{attack.db} and @file{defense.db} are used to assist the |
| 1032 | tactical reading in finding moves that attacks or defends worms. The |
| 1033 | matching is performed during @code{make_worms()}, at the time when the |
| 1034 | tactical status of all worms is decided. None of the classes described |
| 1035 | above are useful in these databases, instead we have two other |
| 1036 | classes. |
| 1037 | |
| 1038 | @table @samp |
| 1039 | @item D |
| 1040 | For each @samp{O} worm in the pattern that can be tactically captured |
| 1041 | (@code{worm[m][n].attack_code != 0}), the move at @samp{*} is |
| 1042 | tried. If it is found to defend the stone, this is registered as a |
| 1043 | reason for the move @samp{*} and the defense point of the worm is set to |
| 1044 | @samp{*}. |
| 1045 | @item A |
| 1046 | For each @samp{X} worm in the pattern, it's tested whether the move |
| 1047 | at @samp{*} captures the worm. If that is the case, this is |
| 1048 | registered as a reason for the move at @samp{*}. The attack point of |
| 1049 | the worm is set to @samp{*} and if it wasn't attacked before, a |
| 1050 | defense is searched for. |
| 1051 | @end table |
| 1052 | |
| 1053 | Furthermore, @samp{A} patterns can only be used in @file{attack.db} and |
| 1054 | @samp{D} patterns only in @file{defense.db}. Unclassified patterns may |
| 1055 | appear in these databases, but then they must work through actions to be |
| 1056 | effective. |
| 1057 | |
| 1058 | @node Connections Database |
| 1059 | @section The Connections Database |
| 1060 | |
| 1061 | @cindex connections database |
| 1062 | @cindex connection shapes database |
| 1063 | |
| 1064 | The patterns in @file{conn.db} are used for helping @code{make_dragons()} |
| 1065 | amalgamate worms into dragons and to some extent for modifying eye spaces. |
| 1066 | The patterns in this database use the classifications @samp{B}, |
| 1067 | @samp{C}, and @samp{e}. @samp{B} patterns are used for finding cutting points, |
| 1068 | where amalgamation should not be performed, @samp{C} patterns are used for |
| 1069 | finding existing connections, over which amalgamation is to be done, and |
| 1070 | @samp{e} patterns are used for modifying eye spaces and reevaluating lunches. |
| 1071 | There are also some patterns without classification, which use action lines to |
| 1072 | have an impact. These are matched together with the @samp{C} patterns. Further |
| 1073 | details and examples can be found in @xref{Worms and Dragons}. |
| 1074 | |
| 1075 | We will illustrate these databases by example. In this situation: |
| 1076 | |
| 1077 | @example |
| 1078 | XOO |
| 1079 | O.O |
| 1080 | ... |
| 1081 | @end example |
| 1082 | @noindent |
| 1083 | @samp{X} cannot play safely at the cutting point, so the @samp{O} dragons |
| 1084 | are to be amalgamated. Two patterns are matched here: |
| 1085 | |
| 1086 | @example |
| 1087 | Pattern CC204 |
| 1088 | |
| 1089 | O |
| 1090 | . |
| 1091 | O |
| 1092 | |
| 1093 | :+,C |
| 1094 | |
| 1095 | O |
| 1096 | A |
| 1097 | O |
| 1098 | |
| 1099 | ;!safe_xmove(A) && !ko(A) && !xcut(A) |
| 1100 | |
| 1101 | Pattern CC205 |
| 1102 | |
| 1103 | XO |
| 1104 | O. |
| 1105 | |
| 1106 | :\,C |
| 1107 | |
| 1108 | AO |
| 1109 | OB |
| 1110 | |
| 1111 | ;attack(A) || (!safe_xmove(B) && !ko(B) && !xcut(B)) |
| 1112 | @end example |
| 1113 | |
| 1114 | The constraints are mostly clear. For example the second |
| 1115 | pattern should not be matched if the @samp{X} stone cannot |
| 1116 | be attacked and @samp{X} can play safely at @samp{B}, or |
| 1117 | if @samp{B} is a ko. The constraint @code{!xcut(B)} means |
| 1118 | that connection has not previously been inhibited by |
| 1119 | @code{find_cuts}. For example consider this situation: |
| 1120 | |
| 1121 | @example |
| 1122 | |
| 1123 | OOXX |
| 1124 | O.OX |
| 1125 | X..O |
| 1126 | X.OO |
| 1127 | @end example |
| 1128 | @noindent |
| 1129 | The previous pattern is matched here twice, yet @samp{X} can push |
| 1130 | in and break one of the connections. To fix this, we include |
| 1131 | a pattern: |
| 1132 | |
| 1133 | @example |
| 1134 | Pattern CB11 |
| 1135 | |
| 1136 | ?OX? |
| 1137 | O!OX |
| 1138 | ?*!O |
| 1139 | ??O? |
| 1140 | |
| 1141 | :8,B |
| 1142 | |
| 1143 | ?OA? |
| 1144 | OaOB |
| 1145 | ?*bO |
| 1146 | ??O? |
| 1147 | |
| 1148 | ; !attack(A) && !attack(B) && !xplay_attack(*,a,b,*) && !xplay_attack(*,b,a,*) |
| 1149 | @end example |
| 1150 | |
| 1151 | After this pattern is found, the @code{xcut} autohelper macro will return |
| 1152 | true at any of the points @samp{*}, @samp{a} and @samp{b}. Thus the |
| 1153 | patterns @code{CB204} and @code{CB205} will not be matched, and the dragons will |
| 1154 | not be amalgamated. |
| 1155 | |
| 1156 | @node Connection Functions |
| 1157 | @section Connections Functions |
| 1158 | |
| 1159 | Here are the public functions in @file{connections.c}. |
| 1160 | |
| 1161 | @itemize @bullet |
| 1162 | @item @code{static void cut_connect_callback(int m, int n, int color, |
| 1163 | struct pattern *pattern, int ll, void *data)} |
| 1164 | @findex cut_connect_callback |
| 1165 | @quotation |
| 1166 | Try to match all (permutations of) connection patterns at @code{(m,n)}. |
| 1167 | For each match, if it is a B pattern, set cutting point in worm |
| 1168 | data structure and make eye space marginal for the connection |
| 1169 | inhibiting entries of the pattern. If it is a @samp{C} pattern, amalgamate |
| 1170 | the dragons in the pattern. |
| 1171 | @end quotation |
| 1172 | @item @code{void find_cuts(void)} |
| 1173 | @findex find_cuts |
| 1174 | @quotation |
| 1175 | Find cutting points which should inhibit amalgamations and sever |
| 1176 | the adjacent eye space. This goes through the connection database |
| 1177 | consulting only patterns of type B. When such a function is found, |
| 1178 | the function @code{cut_connect_callback} is invoked. |
| 1179 | @end quotation |
| 1180 | @item @code{void find_connections(void)} |
| 1181 | @findex find_connections |
| 1182 | @quotation |
| 1183 | Find explicit connection patterns and amalgamate the involved dragons. |
| 1184 | This goes through the connection database consulting patterns except those of |
| 1185 | type B, E or e. When such a function is found, the function |
| 1186 | @code{cut_connect_callback} is invoked. |
| 1187 | @end quotation |
| 1188 | @item void modify_eye_spaces1(void) |
| 1189 | @findex modify_eye_spaces1 |
| 1190 | @quotation |
| 1191 | Find explicit connection patterns and amalgamate the involved dragons. |
| 1192 | This goes through the connection database consulting only patterns |
| 1193 | of type E (@pxref{Connections Database}). When such a function is found, the |
| 1194 | function @code{cut_connect_callback} is invoked. |
| 1195 | @end quotation |
| 1196 | @item void modify_eye_spaces1(void) |
| 1197 | @findex modify_eye_spaces1 |
| 1198 | @quotation |
| 1199 | Find explicit connection patterns and amalgamate the involved dragons. |
| 1200 | This goes through the connection database consulting only patterns |
| 1201 | of type e (@pxref{Connections Database}). When such a function is found, the |
| 1202 | function @code{cut_connect_callback} is invoked. |
| 1203 | @end quotation |
| 1204 | @end itemize |
| 1205 | |
| 1206 | @node Tuning |
| 1207 | @section Tuning the Pattern databases |
| 1208 | |
| 1209 | @cindex tuning the pattern database |
| 1210 | @cindex tuning the shapes database |
| 1211 | |
| 1212 | Since the pattern databases, together with the valuation of move |
| 1213 | reasons, decide GNU Go's personality, much time can be devoted to |
| 1214 | ``tuning'' them. Here are some suggestions. |
| 1215 | |
| 1216 | If you want to experiment with modifying the pattern database, invoke |
| 1217 | with the @option{-a} option. This will cause every pattern to be evaluated, |
| 1218 | even when some of them may be skipped due to various optimizations. |
| 1219 | |
| 1220 | You can obtain a Smart Game Format (SGF) record of your game in at least |
| 1221 | two different ways. One is to use CGoban to record the game. You can |
| 1222 | also have GNU Go record the game in Smart Game Format, using the @option{-o} |
| 1223 | option. It is best to combine this with @option{-a}. Do not try to read the SGF |
| 1224 | file until the game is finished and you have closed the game |
| 1225 | window. This does not mean that you have to play the game out to its |
| 1226 | conclusion. You may close the CGoban window on the game and GNU Go |
| 1227 | will close the SGF file so that you can read it. |
| 1228 | |
| 1229 | If you record a game in SGF form using the @option{-o} option, GNU Go will add |
| 1230 | labels to the board to show all the moves it considered, with their |
| 1231 | values. This is an extremely useful feature, since one can see at a |
| 1232 | glance whether the right moves with appropriate weights are being |
| 1233 | proposed by the move generation. |
| 1234 | |
| 1235 | First, due to a bug of unknown nature, it occasionally happens |
| 1236 | that GNU Go will not receive the @code{SIGTERM} signal from CGoban that it |
| 1237 | needs to know that the game is over. When this happens, the SGF file |
| 1238 | ends without a closing parenthesis, and CGoban will not open the |
| 1239 | file. You can fix the file by typing: |
| 1240 | |
| 1241 | @example |
| 1242 | |
| 1243 | echo ")" >>[filename] |
| 1244 | |
| 1245 | @end example |
| 1246 | |
| 1247 | @noindent |
| 1248 | at the command line to add this closing parenthesis. Or you could |
| 1249 | add the ) using an editor. |
| 1250 | |
| 1251 | Move values exceeding 99 (these should be rare) can be displayed by |
| 1252 | CGoban but you may have to resize the window in order to see all three |
| 1253 | digits. Grab the lower right margin of the CGoban window and pull it |
| 1254 | until the window is large. All three digits should be visible. |
| 1255 | |
| 1256 | If you are playing a game without the @option{-o} option and you wish to |
| 1257 | analyze a move, you may still use CGoban's ``Save Game'' button to get |
| 1258 | an SGF file. It will not have the values of the moves labelled, of |
| 1259 | course. |
| 1260 | |
| 1261 | Once you have a game saved in SGF format, you can analyze any |
| 1262 | particular move by running: |
| 1263 | |
| 1264 | @example |
| 1265 | |
| 1266 | gnugo -l [filename] -L [move number] -t -a -w |
| 1267 | |
| 1268 | @end example |
| 1269 | |
| 1270 | @noindent |
| 1271 | to see why GNU Go made that move, and if you make changes to the |
| 1272 | pattern database and recompile the program, you may ask GNU Go to |
| 1273 | repeat the move to see how the behavior changes. If you're using |
| 1274 | emacs, it's a good idea to run GNU Go in a shell in a buffer (M-x |
| 1275 | shell) since this gives good navigation and search facilities. |
| 1276 | |
| 1277 | Instead of a move number, you can also give a board coordinate to @option{-L} |
| 1278 | in order to stop at the first move played at this location. If you |
| 1279 | omit the @option{-L} option, the move after those in the file will be |
| 1280 | considered. |
| 1281 | |
| 1282 | If a bad move is proposed, this can have several reasons. To begin |
| 1283 | with, each move should be valued in terms of actual points on the |
| 1284 | board, as accurately as can be expected by the program. If it's not, |
| 1285 | something is wrong. This may have two reasons. One possibility is that |
| 1286 | there are reasons missing for the move or that bogus reasons have been |
| 1287 | found. The other possibility is that the move reasons have been |
| 1288 | misevaluated by the move valuation functions. Tuning of patterns is |
| 1289 | with a few exceptions a question of fixing the first kind of problems. |
| 1290 | |
| 1291 | If there are bogus move reasons found, search through the trace output |
| 1292 | for the pattern that is responsible. (Some move reasons, e.g. most |
| 1293 | tactical attack and defense, do not originate from patterns. If no |
| 1294 | pattern produced the bogus move reason, it is not a tuning problem.) |
| 1295 | Probably this pattern was too general or had a faulty constraint. Try |
| 1296 | to make it more specific or correct bugs if there were any. If the |
| 1297 | pattern and the constraint looks right, verify that the tactical |
| 1298 | reading evaluates the constraint correctly. If not, this is either a |
| 1299 | reading bug or a case where the reading is too complicated for GNU Go. |
| 1300 | |
| 1301 | If a connecting move reason is found, but the strings are already |
| 1302 | effectively connected, there may be missing patterns in @file{conn.db}. |
| 1303 | Similarly, worms may be incorrectly amalgamated due to some too |
| 1304 | general or faulty pattern in @file{conn.db}. To get trace output from the |
| 1305 | matching of patterns in @file{conn.db} you need to add a second |
| 1306 | @option{-t} option. |
| 1307 | |
| 1308 | If a move reason is missing, there may be a hole in the database. It |
| 1309 | could also be caused by some existing pattern being needlessly |
| 1310 | specific, having a faulty constraint, or being rejected due to a |
| 1311 | reading mistake. Unless you are familiar with the pattern databases, |
| 1312 | it may be hard to verify that there really is a pattern missing. Look |
| 1313 | around the databases to try to get a feeling for how they are |
| 1314 | organized. (This is admittedly a weak point of the pattern databases, |
| 1315 | but the goal is to make them more organized with time.) If you decide |
| 1316 | that a new pattern is needed, try to make it as general as possible, |
| 1317 | without allowing incorrect matches, by using proper classification |
| 1318 | from among snOoXx and constraints. The reading functions can be put to |
| 1319 | good use. The reason for making the patterns as general as they can be |
| 1320 | is that we need a smaller number of them then, which makes the |
| 1321 | database much easier to maintain. Of course, if you need too |
| 1322 | complicated constraints, it's usually better to split the pattern. |
| 1323 | |
| 1324 | If a move has the correct set of reasons but still is misevaluated, |
| 1325 | this is usually not a tuning problem. There are, however, some |
| 1326 | possibilities to work around these mistakes with the use of patterns. |
| 1327 | In particular, if the territorial value is off because @code{delta_terri()} |
| 1328 | give strange results, the (min)terri and maxterri values can be set by |
| 1329 | patterns as a workaround. This is typically done by the endgame |
| 1330 | patterns, where we can know the (minimum) value fairly well from the |
| 1331 | pattern. If it should be needed, (min)value and maxvalue can be used |
| 1332 | similarly. These possibilities should be used conservatively though, |
| 1333 | since such patterns are likely to become obsolete when better (or at |
| 1334 | least different) functions for e.g. territory estimation are being |
| 1335 | developed. |
| 1336 | |
| 1337 | In order to choose between moves with the same move reasons, e.g. |
| 1338 | moves that connect two dragons in different ways, patterns with a |
| 1339 | nonzero shape value should be used. These should give positive shape |
| 1340 | values for moves that give good shape or good aji and negative values |
| 1341 | for bad shape and bad aji. Notice that these values are additive, so |
| 1342 | it's important that the matches are unique. |
| 1343 | |
| 1344 | Sente moves are indicated by the use of the pattern followup value. |
| 1345 | This can usually not be estimated very accurately, but a good rule is |
| 1346 | to be rather conservative. As usual it should be measured in terms of |
| 1347 | actual points on the board. These values are also additive so the same |
| 1348 | care must be taken to avoid unintended multiple matches. |
| 1349 | |
| 1350 | You can also get a visual display of the dragons using the @option{-T} |
| 1351 | option. The default GNU Go configuration tries to build a |
| 1352 | version with color support using either curses or the |
| 1353 | ansi escape sequences. You are more likely to find color |
| 1354 | support in rxvt than xterm, at least on many systems, so |
| 1355 | we recommend running: |
| 1356 | |
| 1357 | @example |
| 1358 | gnugo -l [filename] -L [move number] -T |
| 1359 | @end example |
| 1360 | |
| 1361 | @noindent |
| 1362 | in an rxvt window. If you do not see a color display, |
| 1363 | and if your host is a GNU/Linux machine, try this again |
| 1364 | in the Linux console. |
| 1365 | |
| 1366 | Worms belonging to the same dragon are labelled with the same letters. |
| 1367 | The colors indicate the value of the field @code{dragon.safety}, which |
| 1368 | is set in @file{moyo.c}. |
| 1369 | |
| 1370 | @format |
| 1371 | Green: GNU Go thinks the dragon is alive |
| 1372 | Yellow: Status unknown |
| 1373 | Blue: GNU Go thinks the dragon is dead |
| 1374 | Red: Status critical (1.5 eyes) or weak by the algorithm |
| 1375 | in @file{moyo.c} |
| 1376 | @end format |
| 1377 | |
| 1378 | @cindex eliminate the randomness |
| 1379 | |
| 1380 | If you want to get the same game over and over again, you can |
| 1381 | eliminate the randomness in GNU Go's play by providing a fixed |
| 1382 | random seed with the @option{-r} option. |
| 1383 | |
| 1384 | |
| 1385 | @node PM Implementation |
| 1386 | @section Implementation |
| 1387 | |
| 1388 | @cindex implementation of pattern matching |
| 1389 | |
| 1390 | The pattern code in GNU Go is fairly straightforward conceptually, but |
| 1391 | because the matcher consumes a significant part of the time in |
| 1392 | choosing a move, the code is optimized for speed. Because of this |
| 1393 | there are implementation details which obscure things slightly. |
| 1394 | |
| 1395 | |
| 1396 | In GNU Go, the ascii @file{.db} files are precompiled into tables (see |
| 1397 | @file{patterns.h}) by a standalone program @file{mkpat.c}, and the resulting |
| 1398 | @file{.c} files are compiled and linked into the main GNU Go executable. |
| 1399 | |
| 1400 | Each pattern is compiled to a header, and a sequence of elements, |
| 1401 | which are (notionally) checked sequentially at every position and |
| 1402 | orientation of the board. These elements are relative to the pattern |
| 1403 | 'anchor' (or origin). One @samp{X} or @samp{O} stone is (arbitrarily) chosen to |
| 1404 | represent the origin of the pattern. (We cannot dictate one or the |
| 1405 | other since some patterns contain only one colour or the other.) All |
| 1406 | the elements are in co-ordinates relative to this position. So a |
| 1407 | pattern matches "at" board position @code{(m,n,o)} if the the pattern anchor |
| 1408 | stone is on @code{(m,n)}, and the other elements match the board when the |
| 1409 | pattern is transformed by transformation number @samp{o}. (See below for |
| 1410 | the details of the transformations, though these should not be |
| 1411 | necessary) |
| 1412 | |
| 1413 | |
| 1414 | @node Symmetry & transformations, Details, PM Implementation, Patterns |
| 1415 | @section Symmetry and transformations |
| 1416 | |
| 1417 | @cindex symmetry and transformations |
| 1418 | @cindex symmetry and transformations of shapes |
| 1419 | |
| 1420 | In general, each pattern must be tried in each of 8 different |
| 1421 | permutations, to reflect the symmetry of the board. But some |
| 1422 | patterns have symmetries which mean that it is unnecessary |
| 1423 | (and therefore inefficient) to try all eight. The first |
| 1424 | character after the @samp{:} can be one of @samp{8},@samp{|},@samp{\},@samp{/}, |
| 1425 | @samp{X}, @samp{-}, @samp{+}, representing the axes of symmetry. It can also |
| 1426 | be @samp{O}, representing symmetry under 180 degrees rotation. |
| 1427 | |
| 1428 | @format |
| 1429 | transformation I - | . \ l r / |
| 1430 | ABC GHI CBA IHG ADG CFI GDA IFC |
| 1431 | DEF DEF FED FED BEH BEH HEB HEB |
| 1432 | GHI ABC IHG CBA CFI ADG IFC GDA |
| 1433 | |
| 1434 | a b c d e f g h |
| 1435 | @end format |
| 1436 | |
| 1437 | Then if the pattern has the following symmetries, the |
| 1438 | following are true: |
| 1439 | |
| 1440 | @example |
| 1441 | |
| 1442 | | c=a, d=b, g=e, h=f |
| 1443 | - b=a, c=d, e=f, g=h |
| 1444 | \ e=a, g=b, f=c, h=d |
| 1445 | / h=a, f=b, g=c, e=d |
| 1446 | O a=d, b=c, e=h, f=g |
| 1447 | X a=d=e=h, b=c=f=g |
| 1448 | + a=b=c=d, e=f=g=h |
| 1449 | |
| 1450 | @end example |
| 1451 | |
| 1452 | We can choose to use transformations a,d,f,g as the unique |
| 1453 | transformations for patterns with either @samp{|}, @samp{-}, @samp{\}, or |
| 1454 | @samp{/} symmetry. |
| 1455 | |
| 1456 | Thus we choose to order the transformations a,g,d,f,h,b,e,c and choose |
| 1457 | first 2 for @samp{X} and @samp{+}, the first 4 for @samp{|}, @samp{-}, |
| 1458 | @samp{/}, and @samp{\}, the middle 4 for @samp{O}, and all 8 for |
| 1459 | non-symmetrical patterns. |
| 1460 | |
| 1461 | Each of the reflection operations (e-h) is equivalent to reflection |
| 1462 | about one arbitrary axis followed by one of the rotations (a-d). We |
| 1463 | can choose to reflect about the axis of symmetry (which causes no |
| 1464 | net change) and can therefore conclude that each of e-h is |
| 1465 | equivalent to the reflection (no-op) followed by a-d. This argument |
| 1466 | therefore extends to include @samp{-} and @samp{/} as well as @samp{|} |
| 1467 | and @samp{\}. |
| 1468 | |
| 1469 | @node Details |
| 1470 | @section Implementation Details |
| 1471 | |
| 1472 | @cindex pattern matching optimization |
| 1473 | @cindex grid optimization |
| 1474 | |
| 1475 | @enumerate |
| 1476 | @item An entry in the pattern header states whether the anchor is an @samp{X} or |
| 1477 | an @samp{O}. This helps performance, since all transformations can be |
| 1478 | rejected at once if the anchor stone does not match. (Ideally, we |
| 1479 | could just define that the anchor is always @samp{O} or always @samp{X}, but some |
| 1480 | patterns contain no @samp{O} and some contain no @samp{X}.) |
| 1481 | |
| 1482 | @item The pattern header contains the size of the pattern (ie the |
| 1483 | co-ordinates of the top left and bottom right elements) relative to |
| 1484 | the anchor. This allows the pattern can be rejected quickly if there |
| 1485 | is not room for the pattern to fit around the anchor stone in a given |
| 1486 | orientation (ie it is too near the edge of the board). The bounding |
| 1487 | box information must first be transformed like the elements before it |
| 1488 | can be tested, and after transforming, we need to work out where the |
| 1489 | top-left and bottom-right corners are. |
| 1490 | |
| 1491 | @item The edge constraints are implemented by notionally padding the |
| 1492 | pattern with rows or columns of @samp{?} until it is exactly 19 (or |
| 1493 | whatever the current board size is) elements wide or high. Then the |
| 1494 | pattern is quickly rejected by (ii) above if it is not at the edge. So |
| 1495 | the example pattern above is compiled as if it was written |
| 1496 | |
| 1497 | |
| 1498 | @example |
| 1499 | |
| 1500 | "example" |
| 1501 | .OO???????????????? |
| 1502 | *XX???????????????? |
| 1503 | o?????????????????? |
| 1504 | :8,80 |
| 1505 | |
| 1506 | @end example |
| 1507 | |
| 1508 | @item The elements in a pattern are sorted so that non-space |
| 1509 | elements are checked before space elements. It is hoped that, |
| 1510 | for most of the game, more squares are empty, and so the |
| 1511 | pattern can be more quickly rejected doing it this way. |
| 1512 | |
| 1513 | @item The actual tests are performed using an 'and-compare' |
| 1514 | sequence. Each board position is a 2-bit quantity. |
| 1515 | %00 for empty, %01 for @samp{O}, %10 for @samp{X}. |
| 1516 | We can test for an exact match by and-ing with %11 (no-op), |
| 1517 | then comparing with 0, 1 or 2. The test for @samp{o} is the |
| 1518 | same as a test for 'not-X', ie not %10. So and with %01 |
| 1519 | should give 0 if it matches. Similarly @samp{x} is a test that |
| 1520 | bit 0 is not set. |
| 1521 | |
| 1522 | @end enumerate |
| 1523 | |
| 1524 | @node Grid optimization |
| 1525 | @section The ``Grid'' Optimization |
| 1526 | |
| 1527 | The comparisons between pattern and board are performed as 2-bit |
| 1528 | bitwise operations. Therefore they can be performed in parallel, |
| 1529 | 16-at-a-time on a 32-bit machine. |
| 1530 | |
| 1531 | Suppose the board is layed out as follows : |
| 1532 | |
| 1533 | @example |
| 1534 | |
| 1535 | .X.O....OO |
| 1536 | XXXXO..... |
| 1537 | .X..OOOOOO |
| 1538 | X.X....... |
| 1539 | ....X...O. |
| 1540 | |
| 1541 | @end example |
| 1542 | |
| 1543 | @noindent |
| 1544 | which is internally stored internally in a 2d array (binary) |
| 1545 | |
| 1546 | @example |
| 1547 | |
| 1548 | 00 10 00 01 00 00 00 00 01 01 |
| 1549 | 10 10 10 10 01 00 00 00 00 00 |
| 1550 | 00 10 00 00 01 01 01 01 01 01 |
| 1551 | 10 00 10 00 00 00 00 00 00 00 |
| 1552 | 00 00 00 00 10 00 00 00 01 00 |
| 1553 | |
| 1554 | @end example |
| 1555 | |
| 1556 | @noindent |
| 1557 | we can compile this to a composite array in which each element |
| 1558 | stores the state of a 4x4 grid of squares : |
| 1559 | |
| 1560 | @example |
| 1561 | |
| 1562 | ???????? ???????? ???????? ... |
| 1563 | ??001000 00100001 10000100 |
| 1564 | ??101010 10101010 10101001 |
| 1565 | ??001000 00100000 10000001 |
| 1566 | |
| 1567 | ??001000 00100001 ... |
| 1568 | ??101010 10101010 |
| 1569 | ??001000 00100000 |
| 1570 | ??001000 10001000 |
| 1571 | |
| 1572 | ... |
| 1573 | |
| 1574 | ??100010 ... |
| 1575 | ??000000 |
| 1576 | ???????? |
| 1577 | ???????? |
| 1578 | |
| 1579 | @end example |
| 1580 | |
| 1581 | Where '??' is off the board. |
| 1582 | |
| 1583 | We can store these 32-bit composites in a 2d merged-board array, |
| 1584 | substituting the illegal value %11 for '??'. |
| 1585 | |
| 1586 | Similarly, for each pattern, mkpat produces appropriate 32-bit and-value |
| 1587 | masks for the pattern elements near the anchor. It is a simple matter |
| 1588 | to test the pattern with a similar test to (5) above, but for 32-bits |
| 1589 | at a time. |
| 1590 | |
| 1591 | @node Joseki Compiler |
| 1592 | @section The Joseki Compiler |
| 1593 | |
| 1594 | @cindex joseki |
| 1595 | @cindex how GNU Go learns new joseki |
| 1596 | @cindex the joseki compiler |
| 1597 | @cindex teaching josekis to GNU Go |
| 1598 | |
| 1599 | GNU Go includes a joseki compiler in @file{patterns/joseki.c}. This processes |
| 1600 | an SGF file (with variations) and produces a sequence of patterns |
| 1601 | which can then be fed back into mkpat. The joseki database is currently in files |
| 1602 | in @file{patterns/} called @file{hoshi.sgf}, @file{komoku.sgf}, @file{sansan.sgf}, |
| 1603 | @file{mokuhazushi.sgf} and @file{takamoku.sgf}. This division can be revised |
| 1604 | whenever need arises. |
| 1605 | |
| 1606 | The SGF files are transformed into the pattern database @file{.db} format by |
| 1607 | the program in @file{joseki.c}. These files are in turn transformed into C |
| 1608 | code by the program in @file{mkpat.c} and the C files are compiled and linked |
| 1609 | into the GNU Go binary. |
| 1610 | |
| 1611 | Not every node in the SGF file contributes a pattern. The nodes which |
| 1612 | contribute patterns have the joseki in the upper right corner, with |
| 1613 | the boundary marked with a square mark and other information to determine |
| 1614 | the resulting pattern marked in the comments. |
| 1615 | |
| 1616 | The intention is that the move valuation should be able to choose |
| 1617 | between the available variations by normal valuation. When this fails |
| 1618 | the primary workaround is to use shape values to increase or decrease |
| 1619 | the value. It is also possible to add antisuji variations to forbid |
| 1620 | popular suboptimal moves. As usual constraints can be used, e.g. to |
| 1621 | condition a variation on a working ladder. |
| 1622 | |
| 1623 | The joseki format has the following components for each SGF node: |
| 1624 | |
| 1625 | @itemize @bullet |
| 1626 | @item |
| 1627 | A square mark (@code{SQ} or @code{MA} property) to decide how large part of the |
| 1628 | board should be included in the pattern. |
| 1629 | @item A move (@samp{W} or @samp{B} property) with the natural interpretation. |
| 1630 | If the square mark is missing or the move is a pass, no pattern is |
| 1631 | produced for the node. |
| 1632 | @item Optional labels (@code{LB} property), which must be a single letter each. |
| 1633 | If there is at least one label, a constraint diagram will be |
| 1634 | produced with these labels. |
| 1635 | @item A comment (@samp{C} property). As the first character it should have one of the |
| 1636 | following characters to decide its classification: |
| 1637 | @itemize @minus |
| 1638 | @item @samp{U} - urgent move |
| 1639 | @item @samp{S} or @samp{J} - standard move |
| 1640 | @item @samp{s} or @samp{j} - lesser joseki |
| 1641 | @item @samp{T} - trick move |
| 1642 | @item @samp{t} - minor joseki move (tenuki OK) |
| 1643 | @item @samp{0} - antisuji (@samp{A} can also be used) |
| 1644 | @end itemize |
| 1645 | The rest of the line is ignored, as is the case of the letter. If neither of |
| 1646 | these is found, it's assumed to be a standard joseki move. |
| 1647 | |
| 1648 | In addition to this, rows starting with the following characters are |
| 1649 | recognized: |
| 1650 | @itemize @minus |
| 1651 | @item @samp{#} - Comments. These are copied into the patterns file, above the diagram. |
| 1652 | @item @samp{;} - Constraints. These are copied into the patterns file, below the |
| 1653 | constraint diagram. |
| 1654 | @item @samp{>} - Actions. These are copied into the patterns file, below the |
| 1655 | constraint diagram. |
| 1656 | @item @samp{:} - Colon line. This is a little more complicated, but the colon |
| 1657 | line of the produced patterns always start out with ":8,s" for |
| 1658 | transformation number and sacrifice pattern class (it usually |
| 1659 | isn't a sacrifice, but it's pointless spending time checking for |
| 1660 | tactical safety). Then a joseki pattern class character is |
| 1661 | appended and finally what is included on the colon line in the |
| 1662 | comment for the SGF node. |
| 1663 | @end itemize |
| 1664 | @end itemize |
| 1665 | |
| 1666 | Example: If the comment in the SGF file looks like |
| 1667 | |
| 1668 | @example |
| 1669 | F |
| 1670 | :C,shape(3) |
| 1671 | ;xplay_attack(A,B,C,D,*) |
| 1672 | @end example |
| 1673 | |
| 1674 | @noindent |
| 1675 | the generated pattern will have a colon line |
| 1676 | |
| 1677 | @example |
| 1678 | :8,sjC,shape(3) |
| 1679 | @end example |
| 1680 | |
| 1681 | @noindent |
| 1682 | and a constraint |
| 1683 | |
| 1684 | @example |
| 1685 | ;xplay_attack(A,B,C,D,*) |
| 1686 | @end example |
| 1687 | |
| 1688 | @node Ladders in Joseki |
| 1689 | @section Ladders in Joseki |
| 1690 | |
| 1691 | As an example of how to use autohelpers with the |
| 1692 | Joseki compiler, we consider an example where a Joseki |
| 1693 | is bad if a ladder fails. Assume we have the taisha and are |
| 1694 | considering connecting on the outside with the pattern |
| 1695 | |
| 1696 | @example |
| 1697 | --------+ |
| 1698 | ........| |
| 1699 | ........| |
| 1700 | ...XX...| |
| 1701 | ...OXO..| |
| 1702 | ...*O...| |
| 1703 | ....X...| |
| 1704 | ........| |
| 1705 | ........| |
| 1706 | @end example |
| 1707 | |
| 1708 | But this is bad unless we have a ladder in our favor. To check this we |
| 1709 | add a constraint which may look like |
| 1710 | |
| 1711 | @example |
| 1712 | --------+ |
| 1713 | ........| |
| 1714 | ........| |
| 1715 | ...XX...| |
| 1716 | ...OXO..| |
| 1717 | ...*OAC.| |
| 1718 | ....DB..| |
| 1719 | ........| |
| 1720 | ........| |
| 1721 | |
| 1722 | ;oplay_attack(*,A,B,C,D) |
| 1723 | @end example |
| 1724 | |
| 1725 | In order to accept the pattern we require that the constraint on the |
| 1726 | semicolon line evaluates to true. This particular constraint has the |
| 1727 | interpretation "Play with alternating colors, starting with @samp{O}, |
| 1728 | on the intersections @samp{*}, @samp{A}, @samp{B}, and @samp{C}. Then check |
| 1729 | whether the stone at @samp{D} can be captured." I.e. play to this position |
| 1730 | |
| 1731 | @example |
| 1732 | --------+ |
| 1733 | ........| |
| 1734 | ........| |
| 1735 | ...XX...| |
| 1736 | ...OXO..| |
| 1737 | ...OOXX.| |
| 1738 | ....XO..| |
| 1739 | ........| |
| 1740 | ........| |
| 1741 | @end example |
| 1742 | |
| 1743 | @noindent |
| 1744 | and call @code{attack()} to see whether the lower @samp{X} stone can be |
| 1745 | captured. This is not limited to ladders, but in this particular case the |
| 1746 | reading will of course involve a ladder. |
| 1747 | |
| 1748 | The constraint diagram above with letters is how it looks in the @file{.db} |
| 1749 | file. The joseki compiler knows how to create these from labels in |
| 1750 | the SGF node. @file{Cgoban} has an option to create one letter labels, |
| 1751 | but this ought to be a common feature for SGF editors. |
| 1752 | |
| 1753 | Thus in order to implement this example in SGF, one would add labels |
| 1754 | to the four intersections and a comment: |
| 1755 | |
| 1756 | @example |
| 1757 | ;oplay_attack(*,A,B,C,D) |
| 1758 | @end example |
| 1759 | |
| 1760 | The appropriate constraint (autohelper macro) will then be added |
| 1761 | to the Joseki @file{.db} file. |
| 1762 | |
| 1763 | @node Corner Matcher |
| 1764 | @section Corner Matcher |
| 1765 | |
| 1766 | @cindex implementation of pattern matching |
| 1767 | @cindex joseki |
| 1768 | @cindex corner matcher |
| 1769 | |
| 1770 | GNU Go uses a special matcher for joseki patterns. It has certain constraints |
| 1771 | on the patterns it can match, but is much faster and takes far less space to |
| 1772 | store patterns than the standard matcher. |
| 1773 | |
| 1774 | Patterns used with corner matcher have to qualify the following conditions: |
| 1775 | |
| 1776 | @itemize @bullet |
| 1777 | @item They must be matchable only at a corner of the board (hence the name of |
| 1778 | the matcher). |
| 1779 | @item They can consist only of @samp{O}, @samp{X} and @samp{.} elements. |
| 1780 | @item Of all pattern values (@pxref{Pattern Values}), corner matcher only |
| 1781 | support @code{shape(x)}. This is not because the matcher cannot handle other |
| 1782 | values in principle, just they are currently not used in joseki databases. |
| 1783 | @end itemize |
| 1784 | |
| 1785 | Corner matcher was specifically designed for joseki patterns and they of |
| 1786 | course satisfy all the conditions above. With some modifications corner |
| 1787 | matcher could be used for fuseki patterns as well, but fullboard matcher |
| 1788 | does its work just fine. |
| 1789 | |
| 1790 | The main idea of the matcher is very same to the one of DFA matcher |
| 1791 | (@pxref{Pattern matching with DFA}): check all available patterns at once, |
| 1792 | not a single pattern at a time. A modified version of DFA matcher could be |
| 1793 | used for joseki pattern matching, but its database would be very large. |
| 1794 | Corner matcher capitalizes on the fact that there are relatively few |
| 1795 | stones in each such pattern. |
| 1796 | |
| 1797 | Corner pattern database is organized into a tree. Nodes of the tree are |
| 1798 | called ``variations''. Variations represent certain sets of stones in a |
| 1799 | corner of the board. Root variation corresponds to an empty corner and a |
| 1800 | step down the tree is equivalent to adding a stone to the corner. Each |
| 1801 | variation has several properties: |
| 1802 | |
| 1803 | @itemize @minus |
| 1804 | @item stone position relative to the corner, |
| 1805 | @item a flag determining whether the stone color must be equal to the first |
| 1806 | matched stone color, |
| 1807 | @item number of stones in the corner area (see below) of the variation stone. |
| 1808 | @end itemize |
| 1809 | |
| 1810 | By corner area we define a rectangle which corners are the current corner of |
| 1811 | the board and the position of the stone (inclusive). For instance, if the |
| 1812 | current board corner is A19 then corner area of a stone at C18 consists |
| 1813 | of A18, A19, B18, B19, C18 and C19. |
| 1814 | |
| 1815 | Variation which is a direct child of the root variation matches if there |
| 1816 | is any stone at the variation position and the stone is alone in its |
| 1817 | corner area. |
| 1818 | |
| 1819 | Variation at a deeper level of the tree matches if there is a stone of |
| 1820 | specified color in variation position and the number of stones in its |
| 1821 | corner area is equal to the number specified in variation structure. |
| 1822 | |
| 1823 | When a certain variation matches, all its children has to be checked |
| 1824 | recursively for a match. |
| 1825 | |
| 1826 | All leaf variations and some inner ones have patterns attached to them. |
| 1827 | For a pattern to match, it is required that its @emph{parent} variation |
| 1828 | matches. In addition, it is checked that pattern is being matched for |
| 1829 | the appropriate color (using its variation ``stone color'' field) and |
| 1830 | that the number of stones in the area where the pattern is being matched |
| 1831 | is indeed equal to the number of stones in the pattern. The ``stone |
| 1832 | position'' property of the pattern variation determines the move suggested |
| 1833 | by the pattern. |
| 1834 | |
| 1835 | Consider this joseki pattern which has four stones: |
| 1836 | |
| 1837 | @example |
| 1838 | ------+ |
| 1839 | ......| |
| 1840 | ......| |
| 1841 | .O*...| |
| 1842 | .XXO..| |
| 1843 | ......| |
| 1844 | ......| |
| 1845 | @end example |
| 1846 | |
| 1847 | To encode it for the corner matcher, we have to use five variations, |
| 1848 | each next being a child of previous: |
| 1849 | |
| 1850 | @multitable {Tree level} {Position} {``other''} {Number of stones} |
| 1851 | @item Tree level @tab Position @tab Color @tab Number of stones |
| 1852 | @item 1 @tab R16 @tab ``same'' @tab 1 |
| 1853 | @item 2 @tab P17 @tab ``same'' @tab 1 |
| 1854 | @item 3 @tab Q16 @tab ``other'' @tab 2 |
| 1855 | @item 4 @tab P16 @tab ``other'' @tab 4 |
| 1856 | @item 5 @tab Q17 @tab ``same'' @tab 1 |
| 1857 | @end multitable |
| 1858 | |
| 1859 | The fifth variation should have an attached pattern. Note that the stone |
| 1860 | color for the fifth variation is ``same'' because the first matched stone |
| 1861 | for this pattern is @samp{O} which stands for the stones of the player |
| 1862 | to whom moves are being suggested with @samp{*}. |
| 1863 | |
| 1864 | The tree consists of all variations for all patterns combined together. |
| 1865 | Variations for each patterns are sorted to allow very quick tree branch |
| 1866 | rejection and at the same time keep the database small enough. More |
| 1867 | details can be found in comments in file @file{mkpat.c} |
| 1868 | |
| 1869 | Corner matcher resides in @file{matchpat.c} in two functions: |
| 1870 | @code{corner_matchpat()} and @code{do_corner_matchpat()}. The former computes |
| 1871 | @code{num_stones[]} array which holds number of stones in corner areas of |
| 1872 | different intersections of the board for all possible transformations. |
| 1873 | @code{corner_matchpat()} also matches top-level variations. |
| 1874 | @code{do_corner_matchpat()} is responsible for recursive matching on the |
| 1875 | variation tree and calling callback function upon pattern match. |
| 1876 | |
| 1877 | Tree-like database for corner matcher is generated by @code{mkpat} program. |
| 1878 | Database generator consists of several functions, most important are: |
| 1879 | @code{corner_best_element()}, @code{corner_variation_new()}, |
| 1880 | @code{corner_follow_variation()} and @code{corner_add_pattern()}. |
| 1881 | |
| 1882 | @node Editing Patterns |
| 1883 | @section Emacs Mode for Editing Patterns |
| 1884 | |
| 1885 | @cindex editing patterns |
| 1886 | @cindex editing pattern database |
| 1887 | |
| 1888 | If you use GNU Emacs (XEmacs might work too), you can try a special |
| 1889 | mode for editing GNU Go pattern databases. The mode resides in |
| 1890 | @file{patterns/gnugo-db.el}. |
| 1891 | |
| 1892 | Copy the file to @file{emacs/site-lisp} directory. You can then load |
| 1893 | the mode with @code{(require 'gnugo-db)}. It makes sense to put this |
| 1894 | line into your configuration file (@file{~/.emacs}). You can either |
| 1895 | use @command{gnugo-db-mode} command to switch to pattern editing mode, |
| 1896 | or use the following code snippet to make Emacs do this automatically |
| 1897 | upon opening a file with @file{.db} suffix: |
| 1898 | |
| 1899 | @example |
| 1900 | (setq auto-mode-alist |
| 1901 | (append |
| 1902 | auto-mode-alist |
| 1903 | '(("\\.db\\'" . gnugo-db-mode)))) |
| 1904 | @end example |
| 1905 | |
| 1906 | Pattern editing mode provides the following features: |
| 1907 | |
| 1908 | @itemize @minus |
| 1909 | @item |
| 1910 | highlighting of keywords (@code{Pattern}, @code{goal_elements} and |
| 1911 | @code{callback_data}) and comments, |
| 1912 | |
| 1913 | @item |
| 1914 | making paragraphs equal to patterns (@kbd{M-h}, @kbd{M-@{}, @kbd{M-@}} |
| 1915 | and others operate on patterns), |
| 1916 | |
| 1917 | @item |
| 1918 | commands for pattern creation with automatic name selection (@kbd{C-c |
| 1919 | C-p}) and copying main diagram to constraint diagram (@kbd{C-c C-c}), |
| 1920 | |
| 1921 | @item |
| 1922 | automated indentation of constraints and side comments (pattern |
| 1923 | descriptions). |
| 1924 | @end itemize |