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