| 1 | In the tactical reading code in @file{reading.c}, the |
| 2 | code generating the moves which are tried are all hand |
| 3 | coded in C, for efficiency. There is much to be said for |
| 4 | another type of reading, in which the moves to be tried are |
| 5 | generated from a pattern database. |
| 6 | |
| 7 | GNU Go does three main types of pattern based reading. First, |
| 8 | there is the OWL code (Optics with Limit Negotiation) which |
| 9 | attempts to read out to a point where the code in |
| 10 | @file{engine/optics.c} (@pxref{Eyes}) can be used to evaluate |
| 11 | it. Like the tactical reading code, a persistent cache is |
| 12 | employed to maintain some of the owl data from move to |
| 13 | move. This is an essential speedup without which GNU Go would |
| 14 | play too slowly. |
| 15 | |
| 16 | Secondly, there is the @file{engine/combination.c} which |
| 17 | attempts to find combinations---situations where a series |
| 18 | of threats eventually culminates in one that cannot be |
| 19 | parried. |
| 20 | |
| 21 | Finally there is the semeai module. A @strong{semeai} is |
| 22 | a capturing race between two adjacent DEAD or CRITICAL |
| 23 | dragons of opposite colors. The principal function, |
| 24 | @code{owl_analyze_semeai()} is contained in @file{owl.c}. |
| 25 | Due to the complex nature of semeais, the results of |
| 26 | this function are more frequently wrong than the usual |
| 27 | owl code. |
| 28 | |
| 29 | @menu |
| 30 | * The Owl Code:: Life and death reading |
| 31 | * Combinations:: Combinations |
| 32 | @end menu |
| 33 | |
| 34 | @node The Owl Code |
| 35 | @section The Owl Code |
| 36 | |
| 37 | The life and death code in @file{optics.c}, described elsewhere |
| 38 | (@pxref{Eyes}), works reasonably well as long as the position is in a |
| 39 | @dfn{terminal position}, which we define to be one where there are no |
| 40 | moves left which can expand the eye space, or limit it. In situations |
| 41 | where the dragon is surrounded, yet has room to thrash around a bit |
| 42 | making eyes, a simple application of the graph-based analysis will not |
| 43 | work. Instead, a bit of reading is needed to reach a terminal position. |
| 44 | |
| 45 | The defender tries to expand his eyespace, the attacker to limit |
| 46 | it, and when neither finds an effective move, the position is |
| 47 | evaluated. We call this type of life and death reading |
| 48 | @dfn{Optics With Limit-negotiation} (OWL). The module which |
| 49 | implements it is in @file{engine/owl.c}. |
| 50 | |
| 51 | There are two reasonably small databases |
| 52 | @file{patterns/owl_defendpats.db} and @file{patterns/owl_attackpats.db} |
| 53 | of expanding and limiting moves. The code in @file{owl.c} generates a |
| 54 | small move tree, allowing the attacker only moves from |
| 55 | @file{owl_attackpats.db}, and the defender only moves from |
| 56 | @file{owl_defendpats.db}. In addition to the moves suggested by |
| 57 | patterns, vital moves from the eye space analysis are also tested. |
| 58 | |
| 59 | A third database, @file{owl_vital_apats.db} includes patterns which |
| 60 | override the eyespace analysis done by the optics code. Since the |
| 61 | eyeshape graphs ignore the complications of shortage of liberties and |
| 62 | cutting points in the surrounding chains, the static analysis of |
| 63 | eyespace is sometimes wrong. The problem is when the optics code says |
| 64 | that a dragon definitely has 2 eyes, but it isn't true due to |
| 65 | shortage of liberties, so the ordinary owl patterns never get into play. |
| 66 | In such situations @file{owl_vital_apats.db} is the only available measure |
| 67 | to correct mistakes by the optics. Currently the patterns in |
| 68 | @file{owl_vital_apats.db} are only matched when the level is 9 or |
| 69 | greater. |
| 70 | |
| 71 | The owl code is tuned by editing these three pattern databases, |
| 72 | principally the first two. |
| 73 | |
| 74 | @findex owl_attack |
| 75 | @findex owl_defend |
| 76 | @findex compute_eyes_pessimistic |
| 77 | A node of the move tree is considered @code{terminal} if no further moves |
| 78 | are found from @file{owl_attackpats.db} or @file{owl_defendpats.db}, or if |
| 79 | the function @code{compute_eyes_pessimistic()} reports that the group is |
| 80 | definitely alive. At this point, the status of the group is evaluated. |
| 81 | The functions @code{owl_attack()} and @code{owl_defend()}, with |
| 82 | usage similar to @code{attack()} and @code{find_defense()}, make |
| 83 | use of the owl pattern databases to generate the move tree and decide |
| 84 | the status of the group. |
| 85 | |
| 86 | The function @code{compute_eyes_pessimistic()} used by the owl |
| 87 | code is very conservative and only feels certain about eyes if the |
| 88 | eyespace is completely closed (i.e. no marginal vertices). |
| 89 | |
| 90 | The maximum number of moves tried at each node is limited by |
| 91 | the parameter @code{MAX_MOVES} defined at the beginning of |
| 92 | @file{engine/owl.c}. The most most valuable moves are |
| 93 | tried first, with the following restrictions: |
| 94 | |
| 95 | @itemize @bullet |
| 96 | @item |
| 97 | If @code{stackp > owl_branch_depth} then only one move is tried per |
| 98 | variation. |
| 99 | @item |
| 100 | If @code{stackp > owl_reading_depth} then the reading terminates, |
| 101 | and the situation is declared a win for the defender (since |
| 102 | deep reading may be a sign of escape). |
| 103 | @item |
| 104 | If the node count exceeds @code{owl_node_limit}, the reading also |
| 105 | terminates with a win for the defender. |
| 106 | @item |
| 107 | Any pattern with value 99 is considered a forced move: no |
| 108 | other move is tried, and if two such moves are found, the function |
| 109 | returns false. This is only relevant for the attacker. |
| 110 | @item |
| 111 | Any pattern in @file{patterns/owl_attackpats.db} and |
| 112 | @file{patterns/owl_defendpats.db} with value 100 is considered a win: if |
| 113 | such a pattern is found by @code{owl_attack} or @code{owl_defend}, the |
| 114 | function returns true. This feature must be used most carefully. |
| 115 | @end itemize |
| 116 | |
| 117 | The functions @code{owl_attack()} and @code{owl_defend()} may, like |
| 118 | @code{attack()} and @code{find_defense()}, return an attacking or |
| 119 | defending move through their pointer arguments. If the position is |
| 120 | already won, @code{owl_attack()} may or may not return an attacking |
| 121 | move. If it finds no move of interest, it will return @code{PASS}, that |
| 122 | is, @code{0}. The same goes for @code{owl_defend()}. |
| 123 | |
| 124 | When @code{owl_attack()} or @code{owl_defend()} is called, |
| 125 | the dragon under attack is marked in the array @code{goal}. |
| 126 | The stones of the dragon originally on the board are marked |
| 127 | with goal=1; those added by @code{owl_defend()} are marked |
| 128 | with goal=2. If all the original strings of the original dragon |
| 129 | are captured, @code{owl_attack()} considers the dragon to be defeated, |
| 130 | even if some stones added later can make a live group. |
| 131 | |
| 132 | Only dragons with small escape route are studied when the |
| 133 | functions are called from @code{make_dragons()}. |
| 134 | |
| 135 | The owl code can be conveniently tested using the |
| 136 | @option{--decide-owl @var{location}} option. This should be used with |
| 137 | @option{-t} to produce a useful trace, @option{-o} to produce |
| 138 | an SGF file of variations produced when the life and death of |
| 139 | the dragon at @var{location} is checked, or both. |
| 140 | @option{--decide-position} performs the same analysis for all |
| 141 | dragons with small escape route. |
| 142 | |
| 143 | @node Combinations |
| 144 | @section Combination reading |
| 145 | |
| 146 | It may happen that no single one of a set of worms can be killed, |
| 147 | yet there is a move that guarantees that at least one can be captured. |
| 148 | The simplest example is a double atari. The purpose of the code in |
| 149 | @file{combination.c} is to find such moves. |
| 150 | |
| 151 | For example, consider the following situation: |
| 152 | |
| 153 | @example |
| 154 | |
| 155 | +--------- |
| 156 | |....OOOOX |
| 157 | |....OOXXX |
| 158 | |..O.OXX.. |
| 159 | |.OXO.OX.. |
| 160 | |.OX..OO.. |
| 161 | |.XXOOOXO. |
| 162 | |..*XXOX.. |
| 163 | |....XOX.. |
| 164 | |.XX..X... |
| 165 | |X........ |
| 166 | |
| 167 | @end example |
| 168 | |
| 169 | Every @samp{X} stone in this position is alive. However the move |
| 170 | at @samp{*} produces a position in which at least one of four |
| 171 | strings will get captured. This is a @emph{combination}. |
| 172 | |
| 173 | The driving function is called @code{atari_atari} because typically |
| 174 | a combination involves a sequence of ataris culminating in a capture, |
| 175 | though sometimes the moves involved are not ataris. For example in |
| 176 | the above example, the first move at @samp{*} is @emph{not} an |
| 177 | atari, though after @samp{O} defends the four stones above, a |
| 178 | sequence of ataris ensues resulting in the capture of some |
| 179 | string. |
| 180 | |
| 181 | Like the owl functions @code{atari_atari} does pattern-based |
| 182 | reading. The database generating the attacking moves is |
| 183 | @file{aa_attackpats.db}. One danger with this function is |
| 184 | that the first atari tried might be irrelevant to the actual |
| 185 | combination. To detect this possibility, once we've found a |
| 186 | combination, we mark that first move as forbidden, then try |
| 187 | again. If no combination of the same size or larger turns |
| 188 | up, then the first move was indeed essential. |
| 189 | |
| 190 | @itemize @bullet |
| 191 | @item @code{void combinations(int color)} |
| 192 | @findex combinations |
| 193 | @quotation |
| 194 | Generate move reasons for combination attacks and defenses against |
| 195 | them. This is one of the move generators called from genmove(). |
| 196 | @end quotation |
| 197 | @item @code{int atari_atari(int color, int *attack_move, char defense_moves[BOARDMAX], int save_verbose)} |
| 198 | @findex atari_atari |
| 199 | @quotation |
| 200 | Look for a combination for @code{color}. For the purpose of |
| 201 | the move generation, returns the size of the smallest of the |
| 202 | worms under attack. |
| 203 | @end quotation |
| 204 | @item @code{int atari_atari_confirm_safety(int color, int move, int *defense, int minsize, const char saved_dragons[BOARDMAX], const char saved_worms[BOARDMAX])} |
| 205 | @findex atari_atari_confirm_safety |
| 206 | @quotation |
| 207 | Tries to determine whether a move is a blunder. Wrapper |
| 208 | around atari_atari_blunder_size. Check whether a combination |
| 209 | attack of size at least @code{minsize} appears after move at |
| 210 | @code{move} has been made. The arrays @code{saved_dragons[]} and |
| 211 | @code{saved_worms[]} should be one for stones belonging to dragons |
| 212 | or worms respectively, which are supposedly saved by @code{move}. |
| 213 | @end quotation |
| 214 | @item @code{int atari_atari_blunder_size(int color, int move, int *defense, const char safe_stones[BOARDMAX])} |
| 215 | @findex atari_atari_blunder_size |
| 216 | @quotation |
| 217 | This function checks whether any new combination attack appears after |
| 218 | move at (move) has been made, and returns its size (in points). |
| 219 | @code{safe_stones} marks which of our stones are supposedly safe |
| 220 | after this move. |
| 221 | @end quotation |
| 222 | @end itemize |
| 223 | |
| 224 | |
| 225 | |