Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | @cindex Reading code |
2 | @cindex Reading process | |
3 | @cindex Trying hypothetical moves | |
4 | @cindex Usage of the stack in reading | |
5 | @cindex reading DEPTH | |
6 | @cindex Depth of reading | |
7 | @cindex reading.c | |
8 | @cindex reading.h | |
9 | ||
10 | The process of visualizing potential moves done by you and your | |
11 | opponent to learn the result of different moves is called | |
12 | "reading". GNU Go does three distinct types of reading: @dfn{tactical | |
13 | reading} which typically is concerned with the life and death of | |
14 | individual strings, @dfn{Owl reading} which is concerned | |
15 | with the life and death of dragons, and @dfn{connection reading}. | |
16 | In this Chapter, we document | |
17 | the tactical reading code, which is in @file{engine/reading.c}. | |
18 | ||
19 | @menu | |
20 | * Reading Basics:: Reading Basics | |
21 | * Hashing:: Hashing of positions | |
22 | * Persistent Cache:: Persistent Reading Cache | |
23 | * Ko:: Ko handling | |
24 | * A Ko Example:: A Ko Example | |
25 | * Another Ko Example:: Another Ko Example | |
26 | * Alternate Komaster Schemes:: Alternate Komaster Schemes | |
27 | * Superstrings:: Superstrings | |
28 | * Debugging:: Debugging the reading code | |
29 | * Connection Reading:: Connection Reading | |
30 | @end menu | |
31 | ||
32 | @node Reading Basics | |
33 | @section Reading Basics | |
34 | ||
35 | What we call @emph{Tactical Reading} is the analysis whether there is | |
36 | a direct capture of a single string, or whether there is a move to prevent | |
37 | such a direct capture. | |
38 | ||
39 | If the reading module finds out that the string can get captured, this | |
40 | answer should (usually) be trusted. However, if it says it can be defended, | |
41 | this does not say as much. It is often the case that such a string has | |
42 | no chance to make a life, but that it cannot be captured within the | |
43 | horizon (and the cutoff heuristics) of the tactical reading. | |
44 | ||
45 | The tactical reading is done by the functions in @file{engine/reading.c}. | |
46 | It is a minimax search that declares win for the attacker once he can | |
47 | physically take the string off board, whereas the defense is considered | |
48 | successful when the string has sufficiently many liberties. A string with | |
49 | five liberties is always considered alive. At higher depth within the | |
50 | search tree even fewer liberties cause GNU Go to give up the attack, | |
51 | @xref{depthparams}. | |
52 | ||
53 | The reading code makes use of a stack onto which board positions can | |
54 | be pushed. The parameter @code{stackp} is zero if GNU Go is | |
55 | examining the true board position; if it is higher than zero, then | |
56 | GNU Go is examining a hypothetical position obtained by playing | |
57 | several moves. | |
58 | ||
59 | The most important public reading functions are @code{attack} and | |
60 | @code{find_defense}. These are wrappers for functions @code{do_attack} and | |
61 | @code{do_find_defense} which are declared statically in @file{reading.c}. The | |
62 | functions @code{do_attack} and @code{do_find_defense} call each other | |
63 | recursively. | |
64 | ||
65 | @subsection Organization of the reading code | |
66 | ||
67 | The function @code{do_attack} and @code{do_find_defense} are wrappers | |
68 | themselves and call @code{attack1}, @code{attack2}, @code{attack3} or | |
69 | @code{attack4} resp. @code{defend1}, @code{defend1}, @code{defend1} | |
70 | or @code{defend1} depending on the number of liberties. | |
71 | ||
72 | These are fine-tuned to generate and try out the moves in an efficient | |
73 | order. They generate a few moves themselves (mostly direct liberties | |
74 | of the string), and then call helper functions called @code{..._moves} | |
75 | which suggest less obvious moves. Which of these functions get called | |
76 | depends on the number of liberties and of the current search depth. | |
77 | ||
78 | @subsection Return Codes | |
79 | @anchor{Return Codes} | |
80 | @cindex return codes | |
81 | @cindex reading return codes | |
82 | ||
83 | The return codes of the reading (and owl) functions and owl can | |
84 | be @code{0}, @code{KO_B}, @code{KO_A} or @code{WIN}. Each reading | |
85 | function determines whether a particular player (assumed to have the | |
86 | move) can solve a specific problem, typically attacking or defending | |
87 | a string. | |
88 | ||
89 | A return code of @code{WIN} means success, 0 failure, while @code{KO_A} and | |
90 | @code{KO_B} are success conditioned on ko. A function returns @code{KO_A} | |
91 | if the position results in ko and that the player to move | |
92 | will get the first ko capture (so the opponent has to make the | |
93 | first ko threat). A return code of @code{KO_B} means that the player | |
94 | to move will have to make the first ko threat. | |
95 | ||
96 | @anchor{Experimental Owl Extension} | |
97 | If GNU Go is compiled with the configure option | |
98 | @option{--enable-experimental-owl-ext} then the owl functions also have | |
99 | possible return codes of @code{GAIN} and @code{LOSS}. A code of @code{GAIN} | |
100 | means that the attack (or defense) does not succeed, but that in the process | |
101 | of trying to attack or defend, an opponent's worm is captured. A code | |
102 | of @code{LOSS} means that the attack or defense succeeds, but that another | |
103 | friendly worm dies during the attack or defense. | |
104 | ||
105 | @subsection Reading cutoff and depth parameters | |
106 | @anchor{depthparams} | |
107 | ||
108 | Depth of reading is controlled by the parameters @code{depth} | |
109 | and @code{branch_depth}. The @code{depth} has a default value | |
110 | @code{DEPTH} (in @file{liberty.h}), which is set to 16 in the | |
111 | distribution, but it may also be set at the command line using | |
112 | the @option{-D} or @option{--depth} option. If @code{depth} is | |
113 | increased, GNU Go will be stronger and slower. GNU Go will read | |
114 | moves past depth, but in doing so it makes simplifying | |
115 | assumptions that can cause it to miss moves. | |
116 | ||
117 | Specifically, when @code{stackp > depth}, GNU Go assumes that as | |
118 | soon as the string can get 3 liberties it is alive. This | |
119 | assumption is sufficient for reading ladders. | |
120 | ||
121 | The @code{branch_depth} is typically set a little below @code{depth}. | |
122 | Between @code{branch_depth} and @code{depth}, attacks on strings with | |
123 | 3 liberties are considered, but branching is inhibited, so fewer | |
124 | variations are considered. | |
125 | ||
126 | %@findex small_semeai | |
127 | %Currently the reading code does not try to defend a string by | |
128 | %attacking a boundary string with more than two liberties. Because | |
129 | %of this restriction, it can make oversights. A symptom of this is | |
130 | %two adjacent strings, each having three or four liberties, each | |
131 | %classified as @code{DEAD}. To resolve such situations, a function | |
132 | %@code{small_semeai()} (in @file{engine/semeai.c}) looks for such | |
133 | %pairs of strings and corrects their classification. | |
134 | ||
135 | The @code{backfill_depth} is a similar variable with a default 12. Below | |
136 | this depth, GNU Go will try "backfilling" to capture stones. | |
137 | For example in this situation: | |
138 | ||
139 | @example | |
140 | @group | |
141 | ||
142 | .OOOOOO. on the edge of the board, O can capture X but | |
143 | OOXXXXXO in order to do so he has to first play at a in | |
144 | .aObX.XO preparation for making the atari at b. This is | |
145 | -------- called backfilling. | |
146 | ||
147 | @end group | |
148 | @end example | |
149 | ||
150 | Backfilling is only tried with @code{stackp <= backfill_depth}. The | |
151 | parameter @code{backfill_depth} may be set using the @option{-B} | |
152 | option. | |
153 | ||
154 | The @code{fourlib_depth} is a parameter with a default of only 7. | |
155 | Below this depth, GNU Go will try to attack strings with | |
156 | four liberties. The @code{fourlib_depth} may be set using the | |
157 | @option{-F} option. | |
158 | ||
159 | The parameter @code{ko_depth} is a similar cutoff. If | |
160 | @code{stackp<ko_depth}, the reading code will make experiments | |
161 | involving taking a ko even if it is not legal to do so (i.e., it | |
162 | is hypothesized that a remote ko threat is made and answered | |
163 | before continuation). This parameter may be set using the | |
164 | @option{-K} option. | |
165 | ||
166 | @cindex reading.c | |
167 | ||
168 | @itemize @bullet | |
169 | @item @code{int attack(int str, int *move)} | |
170 | @findex attack | |
171 | @quotation | |
172 | Determines if the string at @code{str} can | |
173 | be attacked, and if so, @code{*move} returns the attacking move, | |
174 | unless @code{*movei} is a null pointer. (Use null pointers if | |
175 | you are interested in the result of the attack but not the | |
176 | attacking move itself.) Returns @code{WIN}, if the attack succeeds, | |
177 | 0 if it fails, and @code{KO_A} or @code{KO_B} if the result depends on ko | |
178 | @ref{Return Codes}. | |
179 | @end quotation | |
180 | @findex find_defense | |
181 | @item @code{find_defense(int str, int *move)} | |
182 | @quotation | |
183 | Attempts to find a move that will save the string at @code{str}. It | |
184 | returns true if such a move is found, with @code{*move} the location | |
185 | of the saving move (unless @code{*move} is a null pointer). It is not | |
186 | checked that tenuki defends, so this may give an erroneous answer if | |
187 | @code{!attack(str)}. Returns @code{KO_A} or @code{KO_B} if the | |
188 | result depends on ko @xref{Return Codes}. | |
189 | @end quotation | |
190 | @findex safe_move | |
191 | @item @code{safe_move(int str, int color)} : | |
192 | @quotation | |
193 | The function @code{safe_move(str, color)} checks whether a move at | |
194 | @code{str} is illegal or can immediately be captured. If @code{stackp==0} | |
195 | the result is cached. If the move only can be captured by a ko, it's | |
196 | considered safe. This may or may not be a good convention. | |
197 | @end quotation | |
198 | @end itemize | |
199 | ||
200 | @node Hashing | |
201 | @section Hashing of Positions | |
202 | ||
203 | @cindex Hashing of positions | |
204 | @cindex Reading optimisation | |
205 | @cindex Speedup of reading process | |
206 | @cindex Zobrist hashing algorithm | |
207 | @cindex Transposition table | |
208 | ||
209 | To speed up the reading process, we note that a position can be | |
210 | reached in several different ways. In fact, it is a very common | |
211 | occurrence that a previously checked position is rechecked, often | |
212 | within the same search but from a different branch in the recursion | |
213 | tree. | |
214 | ||
215 | This wastes a lot of computing resources, so in a number of places, we | |
216 | store away the current position, the function we are in, and which worm | |
217 | is under attack or to be defended. When the search for this position | |
218 | is finished, we also store away the result of the search and which | |
219 | move made the attack or defense succeed. | |
220 | ||
221 | All this data is stored in a hash table, sometimes also called a | |
222 | transposition table, where Go positions are the key and results of the | |
223 | reading for certain functions and groups are the data. You can increase | |
224 | the size of the Hash table using the @option{-M} or @option{--memory} | |
225 | option @pxref{Invoking GNU Go}. | |
226 | ||
227 | The hash table is created once and for all at the beginning of | |
228 | the game by the function @code{hashtable_new()}. Although hash | |
229 | memory is thus allocated only once in the game, the table is | |
230 | reinitialized at the beginning of each move by a call to | |
231 | @code{hashtable_clear()} from @code{genmove()}. | |
232 | ||
233 | @menu | |
234 | * Hash Calculation:: Calculation of the hash value | |
235 | * Hash Organization:: Organization of the hash table | |
236 | * Hash Structures:: Structures in @file{hash.h} | |
237 | @end menu | |
238 | ||
239 | @node Hash Calculation | |
240 | @subsection Calculation of the hash value | |
241 | ||
242 | The hash algorithm is called Zobrist hashing, and is a standard | |
243 | technique for go and chess programming. The algorithm as used by us | |
244 | works as follows: | |
245 | ||
246 | @cindex go position | |
247 | @cindex position | |
248 | ||
249 | @enumerate | |
250 | @item First we define a @dfn{go position}. This positions consists of | |
251 | @itemize @bullet | |
252 | @item the actual board, i.e. the locations and colors of the stones | |
253 | @item A @dfn{ko point}, if a ko is going on. The ko point is defined as | |
254 | the empty point where the last single stone was situated before | |
255 | it was captured. | |
256 | @end itemize | |
257 | ||
258 | It is not necessary to specify the color to move (white or black) | |
259 | as part of the position. The reason for this is that read results | |
260 | are stored separately for the various reading functions such as | |
261 | @code{attack3}, and it is implicit in the calling function which | |
262 | player is to move. | |
263 | ||
264 | @item For each location on the board we generate random numbers: | |
265 | @itemize @bullet | |
266 | @item A number which is used if there is a white stone on this location | |
267 | @item A number which is used if there is a black stone on this location | |
268 | @item A number which is used if there is a ko on this location | |
269 | @end itemize | |
270 | ||
271 | These random numbers are generated once at initialization time and | |
272 | then used throughout the life time of the hash table. | |
273 | ||
274 | @item The hash key for a position is the XOR of all the random numbers | |
275 | which are applicable for the position (white stones, black stones, and | |
276 | ko position). | |
277 | @end enumerate | |
278 | ||
279 | @node Hash Organization | |
280 | @subsection Organization of the hash table | |
281 | ||
282 | The hash table consists of 3 parts: | |
283 | ||
284 | @cindex Hash node | |
285 | @cindex Read result | |
286 | ||
287 | @itemize @bullet | |
288 | @item An area which contains so called @dfn{Hash Nodes}. Each hash node | |
289 | contains: | |
290 | @itemize @minus | |
291 | @item A go position as defined above. | |
292 | @item A computed hash value for the position | |
293 | @item A pointer to Read Results (see below) | |
294 | @item A pointer to another hash node. | |
295 | @end itemize | |
296 | ||
297 | @item An area with so called Read Results. These are used to store | |
298 | which function was called in the go position, which string was | |
299 | under attack or to be defended, and the result of the reading. | |
300 | ||
301 | Each Read Result contains: | |
302 | @itemize @minus | |
303 | @item the function ID (an int between 0 and 255), the position of the | |
304 | string under attack and a depth value, which is used to | |
305 | determine how deep the search was when it was made, packed into | |
306 | one 32 bit integer. | |
307 | @item The result of the search (a numeric value) and a position to | |
308 | play to get the result packed into one 32 bit integer. | |
309 | @item A pointer to another Read Result. | |
310 | @end itemize | |
311 | ||
312 | @item An array of pointers to hash nodes. This is the hash table | |
313 | proper. | |
314 | ||
315 | @end itemize | |
316 | ||
317 | When the hash table is created, these 3 areas are allocated using | |
318 | @code{malloc()}. When the hash table is populated, all contents are taken | |
319 | from the Hash nodes and the Read results. No further allocation is | |
320 | done and when all nodes or results are used, the hash table is full. | |
321 | Nothing is deleted from the hash table except when it is totally | |
322 | emptied, at which point it can be used again as if newly initialized. | |
323 | ||
324 | @findex hashtable_search | |
325 | When a function wants to use the hash table, it looks up the current | |
326 | position using @code{hashtable_search()}. If the position doesn't already | |
327 | exist there, it can be entered using | |
328 | ||
329 | @findex hashtable_enter_position | |
330 | @code{hashtable_enter_position()}. | |
331 | ||
332 | @findex hashtable_enter_position | |
333 | Once the function has a pointer to the hash node containing a | |
334 | function, it can search for a result of a previous search using | |
335 | @code{hashnode_search()}. If a result is found, it can be used, and | |
336 | if not, a new result can be entered after a search using | |
337 | @findex hashnode_new_result | |
338 | @code{hashnode_new_result()}. | |
339 | ||
340 | Hash nodes which hash to the same position in the hash table | |
341 | (collisions) form a simple linked list. Read results for the same | |
342 | position, created by different functions and different attacked or | |
343 | defended strings also form a linked list. | |
344 | ||
345 | This is deemed sufficiently efficient for now, but the representation | |
346 | of collisions could be changed in the future. It is also not | |
347 | determined what the optimum sizes for the hash table, the number of | |
348 | positions and the number of results are. | |
349 | ||
350 | @node Hash Structures | |
351 | @subsection Hash Structures | |
352 | ||
353 | The basic hash structures are declared in @file{engine/hash.h} and | |
354 | @file{engine/cache.c} | |
355 | ||
356 | @example | |
357 | typedef struct hashposition_t @{ | |
358 | Compacttype board[COMPACT_BOARD_SIZE]; | |
359 | int ko_pos; | |
360 | @} Hashposition; | |
361 | @end example | |
362 | ||
363 | Represents the board and optionally the location of a ko, | |
364 | which is an illegal move. The player whose move is next | |
365 | is not recorded. | |
366 | ||
367 | @example | |
368 | typedef struct @{ | |
369 | Hashvalue hashval; | |
370 | Hashposition hashpos; | |
371 | @} Hash_data; | |
372 | @end example | |
373 | ||
374 | Represents the return value of a function (@code{hashval}) and | |
375 | the board state (@code{hashpos}). | |
376 | ||
377 | @example | |
378 | typedef struct read_result_t @{ | |
379 | unsigned int data1; | |
380 | unsigned int data2; | |
381 | ||
382 | struct read_result_t *next; | |
383 | @} Read_result; | |
384 | @end example | |
385 | ||
386 | The data1 field packs into 32 bits the following fields: | |
387 | ||
388 | @example | |
389 | ||
390 | komaster: 2 bits (EMPTY, BLACK, WHITE, or GRAY) | |
391 | kom_pos : 10 bits (allows MAX_BOARD up to 31) | |
392 | routine : 4 bits (currently 10 different choices) | |
393 | str1 : 10 bits | |
394 | stackp : 5 bits | |
395 | ||
396 | @end example | |
397 | ||
398 | The data2 field packs into 32 bits the following fields: | |
399 | ||
400 | @example | |
401 | ||
402 | status : 2 bits (0 free, 1 open, 2 closed) | |
403 | result1: 4 bits | |
404 | result2: 4 bits | |
405 | move : 10 bits | |
406 | str2 : 10 bits | |
407 | ||
408 | @end example | |
409 | ||
410 | The @code{komaster} and @code{(kom_pos)} field are | |
411 | documented in @xref{Ko}. | |
412 | ||
413 | When a new result node is created, 'status' is set to 1 'open'. | |
414 | This is then set to 2 'closed' when the result is entered. The main | |
415 | use for this is to identify open result nodes when the hashtable is | |
416 | partially cleared. Another potential use for this field is to | |
417 | identify repeated positions in the reading, in particular local | |
418 | double or triple kos. | |
419 | ||
420 | @example | |
421 | typedef struct hashnode_t @{ | |
422 | Hash_data key; | |
423 | Read_result * results; | |
424 | struct hashnode_t * next; | |
425 | @} Hashnode; | |
426 | @end example | |
427 | ||
428 | The hash table consists of hash nodes. Each hash node consists of | |
429 | The hash value for the position it holds, the position itself and | |
430 | the actual information which is purpose of the table from the start. | |
431 | ||
432 | There is also a pointer to another hash node which is used when | |
433 | the nodes are sorted into hash buckets (see below). | |
434 | ||
435 | @example | |
436 | typedef struct hashtable @{ | |
437 | size_t hashtablesize; /* Number of hash buckets */ | |
438 | Hashnode ** hashtable; /* Pointer to array of hashnode lists */ | |
439 | ||
440 | int num_nodes; /* Total number of hash nodes */ | |
441 | Hashnode * all_nodes; /* Pointer to all allocated hash nodes. */ | |
442 | int free_node; /* Index to next free node. */ | |
443 | ||
444 | int num_results; /* Total number of results */ | |
445 | Read_result * all_results; /* Pointer to all allocated results. */ | |
446 | int free_result; /* Index to next free result. */ | |
447 | @} Hashtable; | |
448 | @end example | |
449 | ||
450 | The hash table consists of three parts: | |
451 | ||
452 | @itemize @bullet | |
453 | @item The hash table proper: a number of hash buckets with collisions | |
454 | being handled by a linked list. | |
455 | @item The hash nodes. These are allocated at creation time and are | |
456 | never removed or reallocated in the current implementation. | |
457 | @item The results of the searches. Since many different searches can | |
458 | be done in the same position, there should be more of these than | |
459 | hash nodes. | |
460 | @end itemize | |
461 | ||
462 | @node Persistent Cache | |
463 | @section Persistent Reading Cache | |
464 | ||
465 | @cindex persistent cache | |
466 | @findex store_persistent_reading_cache | |
467 | @findex purge_persistent_reading_cache | |
468 | @findex purge_persistent_connection_cache | |
469 | @findex purge_persistent_breakin_cache | |
470 | @findex purge_persistent_owl_cache | |
471 | ||
472 | @findex search_persistent_reading_cache | |
473 | @findex store_persistent_reading_cache | |
474 | ||
475 | Some calculations can be safely saved from move to move. If the | |
476 | opponent's move is not close to our worm or dragon, we do not have to | |
477 | reconsider the life or death of that group on the next move. So | |
478 | the result is saved in a persistent cache. Persistent caches are used for | |
479 | are used in the engine for several types of read results. | |
480 | ||
481 | @itemize @bullet | |
482 | @item Tactical reading | |
483 | @item Owl reading | |
484 | @item Connection reading | |
485 | @item Breakin code | |
486 | @end itemize | |
487 | ||
488 | In this section we will discuss the persistent caching of tactical | |
489 | reading but the same principles apply to the other persistent caches. | |
490 | ||
491 | Persistent caching is an important performance feature. However it | |
492 | can lead to mistakes and debugging problems---situations where GNU | |
493 | Go generates the right move during debugging but plays a wrong move | |
494 | during a game. If you suspect a persistent cache effect you may | |
495 | try loading the sgf file with the @option{--replay} option and see if the | |
496 | mistake is repeated (@pxref{Invoking GNU Go}). | |
497 | ||
498 | The function @code{store_persistent_cache()} is called only | |
499 | by @code{attack} and @code{find_defense}, never from their | |
500 | static recursive counterparts @code{do_attack} and @code{do_defend}. | |
501 | The function @code{store_persistent_reading_cache()} attempts to | |
502 | cache the most expensive reading results. The function | |
503 | @code{search_persistent_reading_cache} attempts to retrieve a | |
504 | result from the cache. | |
505 | ||
506 | If all cache entries are occupied, we try to replace the least useful | |
507 | one. This is indicated by the score field, which is initially the | |
508 | number of nodes expended by this particular reading, and later | |
509 | multiplied by the number of times it has been retrieved from the | |
510 | cache. | |
511 | ||
512 | Once a (permanent) move is made, a number of cache entries immediately become | |
513 | invalid. These are cleaned away by the function | |
514 | @code{purge_persistent_reading_cache().} To have a criterion | |
515 | for when a result may be purged, the function | |
516 | @code{store_persistent_cache()} computes the | |
517 | @dfn{reading shadow} and @dfn{active area}. If a permanent | |
518 | move is subsequently played in the active area, the cached | |
519 | result is invalidated. We now explain this algorithm in detail. | |
520 | ||
521 | @cindex reading shadow | |
522 | ||
523 | The @dfn{reading shadow} is the concatenation of all moves in all | |
524 | variations, as well as locations where an illegal move has been tried. | |
525 | ||
526 | Once the read is finished, the reading shadow is expanded | |
527 | to the @dfn{active area} which may be cached. The | |
528 | intention is that as long as no stones are played in the | |
529 | active area, the cached value may safely be used. | |
530 | ||
531 | Here is the algorithm used to compute the active area. | |
532 | This algorithm is in the function @code{store_persistent_reading_cache()}. | |
533 | The most expensive readings so far are stored in the persistent cache. | |
534 | ||
535 | @itemize @bullet | |
536 | @item | |
537 | The reading shadow and the string under attack are marked | |
538 | with the character @samp{1}. We also include the successful | |
539 | move, which is most often a part of the reading shadow, but | |
540 | sometimes not, for example with the function @code{attack1()}. | |
541 | ||
542 | @item | |
543 | Next the reading shadow is expanded by marking strings and | |
544 | empty vertices adjacent to the area marked @samp{1} with | |
545 | the character @samp{2}. | |
546 | ||
547 | @item | |
548 | Next vertices adjacent to empty vertices marked @samp{2} are | |
549 | labelled with the character @samp{3}. | |
550 | ||
551 | @item | |
552 | Next all vertices adjacent to previously marked vertices. These are | |
553 | marked @samp{-1} instead of the more logical @samp{4} because it | |
554 | is slightly faster to code this way. | |
555 | ||
556 | @item | |
557 | If the stack pointer is >0 we add the moves already played from the | |
558 | moves stack with mark 4. | |
559 | @end itemize | |
560 | ||
561 | @node Ko | |
562 | @section Ko Handling | |
563 | ||
564 | The principles of ko handling are the same for tactical reading and | |
565 | owl reading. | |
566 | ||
567 | We have already mentioned (@pxref{Reading Basics}) that GNU Go | |
568 | uses a return code of @code{KO_A} or @code{KO_B} if the result depends on | |
569 | ko. The return code of @code{KO_B} means that the position can be won | |
570 | provided the player whose move calls the function can come up | |
571 | with a sufficiently large ko threat. In order to verify this, | |
572 | the function must simulate making a ko threat and having it | |
573 | answered by taking the ko even if it is illegal. We call such an | |
574 | experimental taking of the ko a @dfn{conditional} ko capture. | |
575 | ||
576 | Conditional ko captures are accomplished by the function @code{tryko()}. | |
577 | This function is like @code{trymove()} except that | |
578 | it does not require legality of the move in question. | |
579 | ||
580 | The static reading functions, and the global functions @code{do_attack} | |
581 | and @code{do_find_defense} consult parameters @code{komaster}, | |
582 | @code{kom_pos}, which are declared static in @file{board.c}. These mediate ko | |
583 | captures to prevent the occurrence of infinite loops. During | |
584 | reading, the komaster values are pushed and popped from a stack. | |
585 | ||
586 | Normally @code{komaster} is @code{EMPTY} but it can also be | |
587 | @samp{BLACK}, @samp{WHITE}, @code{GRAY_BLACK}, @code{GRAY_WHITE} or | |
588 | @code{WEAK_KO}. The komaster is set to @code{color} when @code{color} makes a | |
589 | conditional ko capture. In this case @code{kom_pos} is set to the location of | |
590 | the captured ko stone. | |
591 | ||
592 | If the opponent is komaster, the reading functions will not try to | |
593 | take the ko at @code{kom_pos}. Also, the komaster is normally not | |
594 | allowed to take another ko. The exception is a nested ko, characterized | |
595 | by the condition that the captured ko stone is at distance 1 both | |
596 | vertically and horizontally from @code{kom_pos}, which is the location | |
597 | of the last stone taken by the komaster. Thus in this situation: | |
598 | ||
599 | @example | |
600 | ||
601 | .OX | |
602 | OX*X | |
603 | OmOX | |
604 | OO | |
605 | ||
606 | @end example | |
607 | ||
608 | Here if @samp{m} is the location of @code{kom_pos}, then the move at | |
609 | @samp{*} is allowed. | |
610 | ||
611 | The rationale behind this rule is that in the case where there are | |
612 | two kos on the board, the komaster cannot win both, and by becoming | |
613 | komaster he has already chosen which ko he wants to win. But in the | |
614 | case of a nested ko, taking one ko is a precondition to taking the | |
615 | other one, so we allow this. | |
616 | ||
617 | If the komaster's opponent takes a ko, then both players have taken one ko. In | |
618 | this case @code{komaster} is set to @code{GRAY_BLACK} or @code{GRAY_WHITE} and | |
619 | after this further ko captures are even further restricted. | |
620 | ||
621 | If the ko at @code{kom_pos} is filled, then the komaster reverts to | |
622 | @code{EMPTY}. | |
623 | ||
624 | In detail, the komaster scheme is as follows. Color @samp{O} is to move. | |
625 | This scheme is known as scheme 5 since in versions of GNU Go through | |
626 | 3.4, several different schemes were included. | |
627 | ||
628 | @itemize @bullet | |
629 | @item 1. Komaster is EMPTY. | |
630 | @itemize @minus | |
631 | @item 1a. Unconditional ko capture is allowed. | |
632 | @quotation | |
633 | Komaster remains EMPTY if previous move was not a ko capture. | |
634 | Komaster is set to WEAK_KO if previous move was a ko capture | |
635 | and kom_pos is set to the old value of board_ko_pos. | |
636 | @end quotation | |
637 | @item 1b) Conditional ko capture is allowed. | |
638 | @quotation | |
639 | Komaster is set to O and kom_pos to the location of the ko, where a stone was | |
640 | just removed. | |
641 | @end quotation | |
642 | @end itemize | |
643 | @item 2. Komaster is O: | |
644 | @itemize @minus | |
645 | @item 2a) Only nested ko captures are allowed. Kom_pos is moved to the | |
646 | new removed stone. | |
647 | @item 2b) If komaster fills the ko at kom_pos then komaster reverts to | |
648 | EMPTY. | |
649 | @end itemize | |
650 | @item 3. Komaster is X: | |
651 | @quotation | |
652 | Play at kom_pos is not allowed. Any other ko capture | |
653 | is allowed. If O takes another ko, komaster becomes GRAY_X. | |
654 | @end quotation | |
655 | @item 4. Komaster is GRAY_O or GRAY_X: | |
656 | @quotation | |
657 | Ko captures are not allowed. If the ko at kom_pos is | |
658 | filled then the komaster reverts to EMPTY. | |
659 | @end quotation | |
660 | @item 5. Komaster is WEAK_KO: | |
661 | @itemize @minus | |
662 | @item 5a) After a non-ko move komaster reverts to EMPTY. | |
663 | @item 5b) Unconditional ko capture is only allowed if it is nested ko capture. | |
664 | @quotation | |
665 | Komaster is changed to WEAK_X and kom_pos to the old value of | |
666 | board_ko_pos. | |
667 | @end quotation | |
668 | @item 5c) Conditional ko capture is allowed according to the rules of 1b. | |
669 | @end itemize | |
670 | @end itemize | |
671 | ||
672 | @node A Ko Example | |
673 | @section A Ko Example | |
674 | ||
675 | To see the komaster scheme in action, consider this position | |
676 | from the file @file{regressions/games/life_and_death/tripod9.sgf}. | |
677 | We recommend studying this example by examining the variation file | |
678 | produced by the command: | |
679 | ||
680 | @example | |
681 | gnugo -l tripod9.sgf --decide-dragon C3 -o vars.sgf | |
682 | @end example | |
683 | ||
684 | In the lower left hand corner, there are kos at A2 and B4. | |
685 | Black is unconditionally dead because if W wins either ko | |
686 | there is nothing B can do. | |
687 | ||
688 | @example | |
689 | @group | |
690 | ||
691 | 8 . . . . . . . . | |
692 | 7 . . O . . . . . | |
693 | 6 . . O . . . . . | |
694 | 5 O O O . . . . . | |
695 | 4 O . O O . . . . | |
696 | 3 X O X O O O O . | |
697 | 2 . X X X O . . . | |
698 | 1 X O . . . . . . | |
699 | A B C D E F G H | |
700 | ||
701 | @end group | |
702 | @end example | |
703 | ||
704 | This is how the komaster scheme sees this. B (i.e. X) starts by | |
705 | taking the ko at B4. W replies by taking the ko at A1. The board | |
706 | looks like this: | |
707 | ||
708 | @example | |
709 | @group | |
710 | ||
711 | 8 . . . . . . . . | |
712 | 7 . . O . . . . . | |
713 | 6 . . O . . . . . | |
714 | 5 O O O . . . . . | |
715 | 4 O X O O . . . . | |
716 | 3 X . X O O O O . | |
717 | 2 O X X X O . . . | |
718 | 1 . O . . . . . . | |
719 | A B C D E F G H | |
720 | ||
721 | @end group | |
722 | @end example | |
723 | ||
724 | Now any move except the ko recapture (currently illegal) | |
725 | at A1 loses for B, so B retakes the ko and becomes komaster. | |
726 | The board looks like this: | |
727 | ||
728 | @example | |
729 | @group | |
730 | ||
731 | 8 . . . . . . . . komaster: BLACK | |
732 | 7 . . O . . . . . kom_pos: A2 | |
733 | 6 . . O . . . . . | |
734 | 5 O O O . . . . . | |
735 | 4 O X O O . . . . | |
736 | 3 X . X O O O O . | |
737 | 2 . X X X O . . . | |
738 | 1 X O . . . . . . | |
739 | A B C D E F G H | |
740 | ||
741 | @end group | |
742 | @end example | |
743 | ||
744 | W takes the ko at B3 after which the komaster is @code{GRAY} and | |
745 | ko recaptures are not allowed. | |
746 | ||
747 | @example | |
748 | @group | |
749 | ||
750 | 8 . . . . . . . . komaster: GRAY | |
751 | 7 . . O . . . . . kom_pos: B4 | |
752 | 6 . . O . . . . . | |
753 | 5 O O O . . . . . | |
754 | 4 O . O O . . . . | |
755 | 3 X O X O O O O . | |
756 | 2 . X X X O . . . | |
757 | 1 X O . . . . . . | |
758 | A B C D E F G H | |
759 | ||
760 | @end group | |
761 | @end example | |
762 | ||
763 | Since B is not allowed any ko recaptures, there is nothing | |
764 | he can do and he is found dead. Thus the komaster scheme | |
765 | produces the correct result. | |
766 | ||
767 | ||
768 | @node Another Ko Example | |
769 | @section Another Ko Example | |
770 | ||
771 | We now consider an example to show why the komaster is reset | |
772 | to @code{EMPTY} if the ko is resolved in the komaster's favor. This | |
773 | means that the ko is filled, or else that is becomes no longer | |
774 | a ko and it is illegal for the komaster's opponent to play | |
775 | there. | |
776 | ||
777 | The position resulting under consideration is in the file | |
778 | @file{regressions/games/ko5.sgf}. This is the position: | |
779 | ||
780 | @example | |
781 | @group | |
782 | . . . . . . O O 8 | |
783 | X X X . . . O . 7 | |
784 | X . X X . . O . 6 | |
785 | . X . X X X O O 5 | |
786 | X X . X . X O X 4 | |
787 | . O X O O O X . 3 | |
788 | O O X O . O X X 2 | |
789 | . O . X O X X . 1 | |
790 | F G H J K L M N | |
791 | @end group | |
792 | @end example | |
793 | ||
794 | We recommend studying this example by | |
795 | examining the variation file produced by the command: | |
796 | ||
797 | @example | |
798 | gnugo -l ko5.sgf --quiet --decide-string L1 -o vars.sgf | |
799 | @end example | |
800 | ||
801 | The correct resolution is that H1 attacks L1 unconditionally while K2 | |
802 | defends it with ko (code @code{KO_A}). | |
803 | ||
804 | After Black (X) takes the ko at K3, white can do nothing | |
805 | but retake the ko conditionally, becoming komaster. B cannot | |
806 | do much, but in one variation he plays at K4 and W takes | |
807 | at H1. The following position results: | |
808 | ||
809 | @example | |
810 | @group | |
811 | . . . . . . O O 8 | |
812 | X X X . . . O . 7 | |
813 | X . X X . . O . 6 | |
814 | . X . X X X O O 5 | |
815 | X X . X X X O X 4 | |
816 | . O X O O O X . 3 | |
817 | O O X O . O X X 2 | |
818 | . O O . O X X . 1 | |
819 | F G H J K L M N | |
820 | @end group | |
821 | @end example | |
822 | ||
823 | Now it is important the @samp{O} is no longer komaster. Were @samp{O} | |
824 | still komaster, he could capture the ko at N3 and there would be | |
825 | no way to finish off B. | |
826 | ||
827 | ||
828 | @node Alternate Komaster Schemes | |
829 | @section Alternate Komaster Schemes | |
830 | ||
831 | The following alternate schemes have been proposed. It is assumed | |
832 | that @samp{O} is the player about to move. | |
833 | ||
834 | @subsection Essentially the 2.7.232 scheme. | |
835 | ||
836 | @itemize @bullet | |
837 | @item Komaster is EMPTY. | |
838 | @itemize @minus | |
839 | @item Unconditional ko capture is allowed. Komaster remains EMPTY. | |
840 | @item Conditional ko capture is allowed. Komaster is set to O and | |
841 | @code{kom_pos} to the location of the ko, where a stone was | |
842 | just removed. | |
843 | @end itemize | |
844 | @item Komaster is O: | |
845 | @itemize @minus | |
846 | @item Conditional ko capture is not allowed. | |
847 | @item Unconditional ko capture is allowed. Komaster parameters unchanged. | |
848 | @end itemize | |
849 | @item Komaster is X: | |
850 | @itemize @minus | |
851 | @item Conditional ko capture is not allowed. | |
852 | @item Unconditional ko capture is allowed except for a move at | |
853 | @code{kom_pos}. Komaster parameters unchanged. | |
854 | @end itemize | |
855 | @end itemize | |
856 | ||
857 | @subsection Revised 2.7.232 version | |
858 | ||
859 | @itemize @bullet | |
860 | @item Komaster is EMPTY. | |
861 | @itemize @minus | |
862 | @item Unconditional ko capture is allowed. Komaster remains EMPTY. | |
863 | @item Conditional ko capture is allowed. Komaster is set to @samp{O} and | |
864 | @code{kom_pos} to the location of the ko, where a stone was | |
865 | just removed. | |
866 | @end itemize | |
867 | @item Komaster is @samp{O}: | |
868 | @itemize @minus | |
869 | @item Ko capture (both kinds) is allowed only if after playing the move, | |
870 | @code{is_ko(kom_pos, X)} returns false. In that case, | |
871 | @code{kom_pos} is updated to the new ko position, i.e. the stone | |
872 | captured by this move. | |
873 | @end itemize | |
874 | @item Komaster is @samp{X}: | |
875 | @itemize @minus | |
876 | @item Conditional ko capture is not allowed. | |
877 | @item Unconditional ko capture is allowed except for a move at | |
878 | @code{kom_pos}. Komaster parameters unchanged. | |
879 | @end itemize | |
880 | @end itemize | |
881 | ||
882 | @node Superstrings | |
883 | @section Superstrings | |
884 | ||
885 | A @emph{superstring} is an extended string, where the extensions are | |
886 | through the following kinds of connections: | |
887 | ||
888 | @enumerate | |
889 | @item Solid connections (just like ordinary string). | |
890 | @example | |
891 | OO | |
892 | @end example | |
893 | @item Diagonal connection or one space jump through an intersection | |
894 | where an opponent move would be suicide or self-atari. | |
895 | @example | |
896 | @group | |
897 | ... | |
898 | O.O | |
899 | XOX | |
900 | X.X | |
901 | @end group | |
902 | @end example | |
903 | @item Bamboo joint. | |
904 | @example | |
905 | @group | |
906 | OO | |
907 | .. | |
908 | OO | |
909 | @end group | |
910 | @end example | |
911 | @item Diagonal connection where both adjacent intersections are empty. | |
912 | @example | |
913 | @group | |
914 | .O | |
915 | O. | |
916 | @end group | |
917 | @end example | |
918 | @item Connection through adjacent or diagonal tactically captured stones. | |
919 | Connections of this type are omitted when the superstring code is | |
920 | called from @file{reading.c}, but included when the superstring code is | |
921 | called from @file{owl.c}. | |
922 | @end enumerate | |
923 | ||
924 | Like a dragon, a superstring is an amalgamation of strings, but it is | |
925 | a much tighter organization of stones than a dragon, and its purpose | |
926 | is different. Superstrings are encountered already in the tactical | |
927 | reading because sometimes attacking or defending an element of the | |
928 | superstring is the best way to attack or defend a string. This is | |
929 | in contrast with dragons, which are ignored during tactical reading. | |
930 | ||
931 | @node Debugging | |
932 | @section Debugging the reading code | |
933 | ||
934 | @cindex How to debug the reading code | |
935 | @cindex Debugging the reading code | |
936 | @cindex Reading code debugging tools | |
937 | ||
938 | The reading code searches for a path through the move tree to | |
939 | determine whether a string can be captured. We have a tool for | |
940 | investigating this with the @option{--decidestring} option. This may | |
941 | be run with or without an output file. | |
942 | ||
943 | Simply running | |
944 | ||
945 | @example | |
946 | ||
947 | @command{gnugo -t -l [input file name] -L [movenumber] --decidestring [location]} | |
948 | ||
949 | @end example | |
950 | ||
951 | @noindent | |
952 | will run @code{attack()} to determine whether the string can be captured. | |
953 | If it can, it will also run @code{find_defense()} to determine whether or | |
954 | not it can be defended. It will give a count of the number of | |
955 | variations read. The @option{-t} is necessary, or else GNU Go will not | |
956 | report its findings. | |
957 | ||
958 | If we add @option{-o @var{output file}} GNU Go will produce | |
959 | an output file with all variations considered. The variations are | |
960 | numbered in comments. | |
961 | ||
962 | This file of variations is not very useful without a way of | |
963 | navigating the source code. This is provided with the GDB | |
964 | source file, listed at the end. You can source this from GDB, | |
965 | or just make it your GDB init file. | |
966 | ||
967 | @cindex GDB | |
968 | ||
969 | If you are using GDB to debug GNU Go you may find it less | |
970 | confusing to compile without optimization. The optimization | |
971 | sometimes changes the order in which program steps are | |
972 | executed. For example, to compile @file{reading.c} without optimization, | |
973 | edit @file{engine/Makefile} to remove the string @code{-O2} from | |
974 | the file, touch @file{engine/reading.c} and make. Note that the | |
975 | Makefile is automatically generated and may get overwritten | |
976 | later. | |
977 | ||
978 | If in the course of reading you need to analyze a result where | |
979 | a function gets its value by returning a cached position from | |
980 | the hashing code, rerun the example with the hashing turned off | |
981 | by the command line option @option{--hash 0}. You should get the same | |
982 | result. (If you do not, please send us a bug report.) Don't | |
983 | run @option{--hash 0} unless you have a good reason to, since it | |
984 | increases the number of variations. | |
985 | ||
986 | With the source file given at the end of this document loaded, | |
987 | we can now navigate the variations. It is a good idea to use | |
988 | cgoban with a small @option{-fontHeight}, so that the | |
989 | variation window takes in a big picture. (You can resize the | |
990 | board.) | |
991 | ||
992 | Suppose after perusing this file, we find that variation 17 is | |
993 | interesting and we would like to find out exactly what is | |
994 | going on here. | |
995 | ||
996 | The macro 'jt n' will jump to the n-th variation. | |
997 | ||
998 | @example | |
999 | ||
1000 | (gdb) set args -l [filename] -L [move number] --decidestring [location] | |
1001 | (gdb) tbreak main | |
1002 | (gdb) run | |
1003 | (gdb) jt 17 | |
1004 | ||
1005 | @end example | |
1006 | ||
1007 | @noindent | |
1008 | will then jump to the location in question. | |
1009 | ||
1010 | Actually the attack variations and defense variations are numbered | |
1011 | separately. (But @code{find_defense()} is only run if @code{attack()} succeeds, | |
1012 | so the defense variations may or may not exist.) It is redundant to | |
1013 | have to tbreak main each time. So there are two macros avar and dvar. | |
1014 | ||
1015 | @example | |
1016 | ||
1017 | (gdb) avar 17 | |
1018 | ||
1019 | @end example | |
1020 | ||
1021 | @noindent | |
1022 | restarts the program, and jumps to the 17-th attack variation. | |
1023 | ||
1024 | @example | |
1025 | ||
1026 | (gdb) dvar 17 | |
1027 | ||
1028 | @end example | |
1029 | ||
1030 | @noindent | |
1031 | jumps to the 17-th defense variation. Both variation sets are | |
1032 | found in the same sgf file, though they are numbered separately. | |
1033 | ||
1034 | Other commands defined in this file: | |
1035 | ||
1036 | @example | |
1037 | ||
1038 | @cindex GNU Go's GDB commands | |
1039 | ||
1040 | @command{dump} will print the move stack. | |
1041 | @command{nv} moves to the next variation | |
1042 | @command{ascii i j} converts (i,j) to ascii | |
1043 | ||
1044 | ####################################################### | |
1045 | ############### .gdbinit file ############### | |
1046 | ####################################################### | |
1047 | ||
1048 | # this command displays the stack | |
1049 | ||
1050 | define dump | |
1051 | set dump_stack() | |
1052 | end | |
1053 | ||
1054 | # display the name of the move in ascii | |
1055 | ||
1056 | define ascii | |
1057 | set gprintf("%o%m\n",$arg0,$arg1) | |
1058 | end | |
1059 | ||
1060 | # display the all information about a dragon | |
1061 | ||
1062 | define dragon | |
1063 | set ascii_report_dragon("$arg0") | |
1064 | end | |
1065 | ||
1066 | define worm | |
1067 | set ascii_report_worm("$arg0") | |
1068 | end | |
1069 | ||
1070 | # move to the next variation | |
1071 | ||
1072 | define nv | |
1073 | tbreak trymove | |
1074 | continue | |
1075 | finish | |
1076 | next | |
1077 | end | |
1078 | ||
1079 | # move forward to a particular variation | |
1080 | ||
1081 | define jt | |
1082 | while (count_variations < $arg0) | |
1083 | nv | |
1084 | end | |
1085 | nv | |
1086 | dump | |
1087 | end | |
1088 | ||
1089 | # restart, jump to a particular attack variation | |
1090 | ||
1091 | define avar | |
1092 | delete | |
1093 | tbreak sgffile_decidestring | |
1094 | run | |
1095 | tbreak attack | |
1096 | continue | |
1097 | jt $arg0 | |
1098 | end | |
1099 | ||
1100 | # restart, jump to a particular defense variation | |
1101 | ||
1102 | define dvar | |
1103 | delete | |
1104 | tbreak sgffile_decidestring | |
1105 | run | |
1106 | tbreak attack | |
1107 | continue | |
1108 | finish | |
1109 | next 3 | |
1110 | jt $arg0 | |
1111 | end | |
1112 | ||
1113 | @end example | |
1114 | ||
1115 | @node Connection Reading | |
1116 | @section Connection Reading | |
1117 | ||
1118 | GNU Go does reading to determine if strings can be connected. The algorithms | |
1119 | for this are in @file{readconnect.c}. As with the reading code, the connection | |
1120 | code is not pattern based. | |
1121 | ||
1122 | The connection code is invoked by the engine through the functions: | |
1123 | ||
1124 | @itemize | |
1125 | @item @code{int string_connect(int str1, int str2, int *move)} | |
1126 | @findex string_connect | |
1127 | @quotation | |
1128 | Returns @code{WIN} if @code{str1} and @code{str2} can be connected. | |
1129 | @end quotation | |
1130 | @item @code{int disconnect(int str1, int str2, int *move)} | |
1131 | @findex disconnect | |
1132 | @quotation | |
1133 | Returns @code{WIN} if @code{str1} and @code{str2} can be disconnected. | |
1134 | @end quotation | |
1135 | @end itemize | |
1136 | ||
1137 | To see the connection code in action, you may try the | |
1138 | following example. | |
1139 | ||
1140 | @example | |
1141 | gnugo --quiet -l connection3.sgf --decide-connection M3/N7 -o vars.sgf | |
1142 | @end example | |
1143 | ||
1144 | (The file @file{connection3.sgf} is in @file{regression/games}.) | |
1145 | Examine the sgf file produced by this to see what kind of reading | |
1146 | is done by the functions @code{string_connect()} and | |
1147 | @code{string_disconnect()}, which are called by the function | |
1148 | @code{decide_connection}. | |
1149 | ||
1150 | One use of the connection code is used is through the autohelper macros | |
1151 | @code{oplay_connect}, @code{xplay_connect}, @code{oplay_disconnect} and | |
1152 | @code{xplay_disconnect} which are used in the connection databases. | |
1153 |