Commit | Line | Data |
---|---|---|
7eeb782e AT |
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 |