Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | @menu |
2 | * Influential Concepts:: Conceptual Outline of Influence | |
3 | * Territory and Moyo:: Territory, Moyo and Area | |
4 | * Influence Usage:: Where influence gets used in the engine | |
5 | * Influence and Territory:: Influence and Territory | |
6 | * Territorial Details:: Details of the Territory Valuation | |
7 | * The Influence Core:: The Core of the Influence Function | |
8 | * The Influence Algorithm:: The algorithm of @code{accumlate_influence()} | |
9 | * Permeability:: Permeability | |
10 | * Escape:: Escape | |
11 | * Break Ins:: Break Ins | |
12 | * Surrounded Dragons:: Surrounded Dragons | |
13 | * Influential Patterns:: Patterns used by the Influence module | |
14 | * Influential Display:: Colored display and debugging of influence | |
15 | * Influence Tuning:: Influence tuning with view.pike | |
16 | @end menu | |
17 | ||
18 | @node Influential Concepts | |
19 | @section Conceptual Outline of Influence | |
20 | ||
21 | We define call stones @dfn{lively} if they cannot be tactically | |
22 | attacked, or if they have a tactical defense and belong to the player | |
23 | whose turn it is. Similarly, stones that cannot be strategically attacked | |
24 | (in the sense of the life-and-death analysis), or that have a strategical | |
25 | defense and belong to the player to move, are called @dfn{alive}. | |
26 | If we want to use the influence function before deciding the strategical | |
27 | status, all lively stones count as alive. | |
28 | ||
29 | Every alive stone on the board works as an influence source, with | |
30 | influence of its color radiating outwards in all directions. The | |
31 | strength of the influence declines exponentially with the distance | |
32 | from the source. | |
33 | ||
34 | Influence can only flow unhindered if the board is empty, however. All | |
35 | lively stones (regardless of color) act as influence barriers, as do | |
36 | connections between enemy stones that can't be broken through. For | |
37 | example the one space jump counts as a barrier unless either of the | |
38 | stones can be captured. Notice that it doesn't matter much if the | |
39 | connection between the two stones can be broken, since in that case | |
40 | there would come influence from both directions anyway. | |
41 | ||
42 | From the influence of both colors we compute a territorial value between | |
43 | -1.0 and +1.0 for each intersection, which can be seen as the likely hood | |
44 | of it becoming territory for either color. | |
45 | ||
46 | In order to avoid finding bogus territory, we add extra influence | |
47 | sources at places where an invasion can be launched, e.g. at 3-3 under | |
48 | a handicap stone, in the middle of wide edge extensions and in the | |
49 | center of large open spaces anywhere. Similarly we add extra influence | |
50 | sources where intrusions can be made into what otherwise looks as | |
51 | solid territory, e.g. monkey jumps. These intrusions depend on whose | |
52 | turn we assume it to be. | |
53 | ||
54 | All these extra influence sources, as well as connections, are controlled | |
55 | by a pattern database, which consists of the two files patterns/influence.db | |
56 | and patterns/barriers.db. The details are explained in | |
57 | @ref{Influential Patterns}. | |
58 | ||
59 | @node Territory and Moyo | |
60 | @section Territory, Moyo and Area | |
61 | @cindex territory | |
62 | @cindex moyo | |
63 | @cindex area | |
64 | ||
65 | Using the influence code, empty regions of the board are partitioned | |
66 | in three ways. A vertex may be described as White or Black's | |
67 | @dfn{territory}, @dfn{moyo} or @dfn{area}. The functions | |
68 | @code{whose_territory()}, @code{whose_moyo()} and @code{whose_area()} | |
69 | will return a color, or EMPTY if it belongs to one player or the | |
70 | other in one of these classifications. | |
71 | ||
72 | @itemize @bullet | |
73 | @item Territory | |
74 | @quotation | |
75 | Those parts of the board which are expected to materialize | |
76 | as actual points for one player or the other at the end of | |
77 | the game are considered @dfn{territory}. | |
78 | @end quotation | |
79 | @item Moyo | |
80 | @quotation | |
81 | Those parts of the board which are either already territory or more generally | |
82 | places where a territory can easily materialize if the opponent neglects to | |
83 | reduce are considered @dfn{moyo}. | |
84 | @dfn{moyo}. | |
85 | @end quotation | |
86 | @item Area | |
87 | @quotation | |
88 | Those parts of the board where one player or the other has a | |
89 | stronger influence than his opponent are considered @dfn{area}. | |
90 | @end quotation | |
91 | @end itemize | |
92 | ||
93 | Generally territory is moyo and moyo is area. To get a feeling | |
94 | for these concepts, load an sgf file in a middle game position | |
95 | with the option @option{-m 0x0180} and examine the resulting | |
96 | diagrams (@pxref{Influential Display}). | |
97 | ||
98 | @node Influence Usage | |
99 | @section Where influence gets used in the engine | |
100 | ||
101 | The information obtained from the influence computation is used in a variety | |
102 | of places in the engine, and the influence module is called several times | |
103 | in the process of the move generation. The details of the influence | |
104 | computation vary according to the needs of the calling function. | |
105 | ||
106 | After GNU Go has decided about the tactical stability of strings, the | |
107 | influence module gets called the first time. Here all lively stones act | |
108 | as an influence source of default strength 100. The result is stored in | |
109 | the variables @code{initial_influence} and @code{initial_opposite_influence}, | |
110 | and it is used as an important information for guessing the strength of | |
111 | dragons. For example, a dragon that is part of a moyo of size 25 is | |
112 | immediately considered alive. For dragons with a smaller moyo size, a | |
113 | life-and-death analysis will be done by the owl code (see @ref{Pattern Based | |
114 | Reading}). A dragon with a moyo size of only 5 will be considered weak, even | |
115 | if the owl code has decided that it cannot be killed. | |
116 | ||
117 | As a tool for both the owl code and the strength estimate of dragons, | |
118 | an "escape" influence gets computed for each dragon (@pxref{Escape}). | |
119 | ||
120 | Once all dragons have been evaluated, the influence module is called again | |
121 | and the variables @code{initial_influence} and | |
122 | @code{initial_opposite_influence} get overwritten. Of course, the dragon | |
123 | status', which are available now, are taken into account. Stones belonging | |
124 | to a dead dragon will not serve as an influence source, and the strengths of | |
125 | other stones get adjusted according to the strength of their respective | |
126 | dragon. | |
127 | ||
128 | The result of this run is the most important tool for move evaluation. All | |
129 | helper functions of patterns as explained in @ref{Patterns} that | |
130 | refer to influence results (e. g. @code{olib(*)} etc.) actually use these | |
131 | results. Further, @code{initial_influence} serves as the reference for | |
132 | computing the territorial value of a move. That is, from the influence | |
133 | strengths stored in @code{initial_influence}, a territory value is | |
134 | assigned to each intersection. This value is supposed to estimate the | |
135 | likelyhood that this intersection will become white or black territory. | |
136 | ||
137 | Then, for each move that gets considered in the function @code{value_moves}, | |
138 | the influence module is called again via the function | |
139 | @code{compute_move_influence} to assess the likely territorial balance after | |
140 | this move, and the result is compared with the state before that move. | |
141 | ||
142 | An additional influence computation is done in order to compute the followup | |
143 | value of a move. Some explainations are in @ref{Territorial Details}. | |
144 | ||
145 | Some of the public functions from @file{influence.c} which are used | |
146 | throughout the engine are listed in @ref{Influence Utilities}. | |
147 | ||
148 | @node Influence and Territory | |
149 | @section Influence and Territory | |
150 | ||
151 | In this section we consider how the influence function is used to | |
152 | estimate territory in the function @code{estimate_territorial_value()}. | |
153 | ||
154 | A move like @samp{*} by @samp{O} below is worth one point: | |
155 | ||
156 | @example | |
157 | OXXX. | |
158 | OX.XX | |
159 | O*a.X | |
160 | OX.XX | |
161 | OXXX. | |
162 | @end example | |
163 | ||
164 | This is evaluated by the influence function in the following way: | |
165 | We first assign territory under the assumption that X moves first in all | |
166 | local positions in the original position; then we reassing territory, | |
167 | again under the assumption that @samp{X} moves first in all local positions, | |
168 | but after we let @samp{O} make the move at @samp{*}. These two | |
169 | territory assignments are compared and the difference gives the | |
170 | territorial value of the move. | |
171 | ||
172 | Technically, the assumption that @samp{X} plays first everywhere is | |
173 | implemented via an asymmetric pattern database in @code{barriers.db}. | |
174 | What exactly is a safe connection that stops hostile influence from | |
175 | passing through is different for @samp{O} and @samp{X}; of course such a | |
176 | connection has to be tighter for stones with color @samp{O}. Also, | |
177 | additional intrusion influence sources are added for @samp{X} in places | |
178 | where @samp{X} stones have natural followup moves. | |
179 | ||
180 | In this specific example above, the asymmetry (before any move has been made) | |
181 | would turn out as follows: If @samp{X} is in turn to move, the white influence | |
182 | would get stopped by a barrier at @samp{*}, leaving 4 points of territory | |
183 | for @samp{X}. However, if @samp{O} was next to move, then a followup move | |
184 | for the white stones at the left would be assumed in the form of an extra | |
185 | ("intrusion") influence source at @samp{*}. This would get stopped at | |
186 | @samp{a}, leaving three points of territory. | |
187 | ||
188 | Returning to the valuation of a move by @samp{O} at @samp{*}, we get a | |
189 | value of 1 for the move at @samp{*}. | |
190 | However, of course this move is sente once it is worth playing, and should | |
191 | therefore (in miai counting) be awarded an effective value of 2. Hence we | |
192 | need to recognize the followup value of a move. GNU Go 3.0 took care of | |
193 | this by using patterns in @code{patterns.db} that enforced an explicit | |
194 | followup value. Versions from 3.2 on instead compute a seperate followup | |
195 | influence to each move considered. In the above example, an intrusion source | |
196 | will be added at @samp{a} as a followup move to @samp{*}. This destroys all of | |
197 | Black's territory and hence gives a followup value of 3. | |
198 | ||
199 | The pattern based followup value are still needed at some places, however. | |
200 | ||
201 | To give another example, consider this position where we want to | |
202 | estimate the value of an @samp{O} move at @samp{*}: | |
203 | ||
204 | @example | |
205 | OOOXXX | |
206 | ..OX.. | |
207 | ..OX.. | |
208 | ...*.. | |
209 | ------ | |
210 | @end example | |
211 | ||
212 | Before the move we assume @samp{X} moves first in the local position (and | |
213 | that @samp{O} has to connect), which gives territory like this (lower case | |
214 | letter identify territory for each player): | |
215 | ||
216 | @example | |
217 | OOOXXX | |
218 | ooOXxx | |
219 | o.OXxx | |
220 | o...xx | |
221 | ------ | |
222 | @end example | |
223 | ||
224 | Then we let @samp{O} make the move at @samp{*} and assume | |
225 | @samp{X} moves first again next. The territory then becomes (@samp{X} | |
226 | is also assumed to have to connect): | |
227 | ||
228 | @example | |
229 | OOOXXX | |
230 | ooOXxx | |
231 | ooOX.x | |
232 | oo.O.x | |
233 | ------ | |
234 | @end example | |
235 | ||
236 | We see that this makes a difference in territory of 4, which is what | |
237 | influence_delta_territory() should report. Then again, we have followup | |
238 | value, and here also a reverse followup value. The reverse followup value, | |
239 | which in this case will be so high that the move is treated as reverse | |
240 | sente, is added by an explicit pattern. Other sources for followup or | |
241 | reverse followup values are threats to capture a rescue a string of stones. | |
242 | See the code and comments in the function @code{value_move_reaons} for how | |
243 | followup and reverse followup values are used to adjust the effective | |
244 | move value. | |
245 | ||
246 | To give an example of territorial value where something is captured, | |
247 | consider the @samp{O} move at @samp{*} here, | |
248 | ||
249 | @example | |
250 | XXXXXXXO | |
251 | X.OOOOXO | |
252 | X.O..O*O | |
253 | -------- | |
254 | @end example | |
255 | ||
256 | As before we first let the influence function determine territory | |
257 | assuming X moves first, i.e. with a captured group: | |
258 | ||
259 | @example | |
260 | XXXXXXXO | |
261 | XxyyyyXO | |
262 | Xxyxxy.O | |
263 | -------- | |
264 | @end example | |
265 | ||
266 | Here @samp{y} indicates @samp{X} territory + captured stone, | |
267 | i.e. these count for two points. After the @samp{O} move at @samp{*} we | |
268 | instead get | |
269 | ||
270 | @example | |
271 | XXXXXXXO | |
272 | X.OOOOXO | |
273 | X.OooOOO | |
274 | -------- | |
275 | @end example | |
276 | ||
277 | and we see that @samp{X} has 16 territory fewer and @samp{O} | |
278 | has two territory more, for a total difference of 18 points. | |
279 | ||
280 | That the influence function counts the value of captured stones was | |
281 | introduced in GNU Go 3.2. Previously this was instead done using the | |
282 | effective_size heuristic. The effective size is the number of | |
283 | stones plus the surrounding empty spaces which are closer to | |
284 | this string or dragon than to any other stones. Here the @samp{O} | |
285 | string would thus have effective size 6 (number of stones) + 2 | |
286 | (interior eye) + 2*0.5 (the two empty vertices to the left of | |
287 | the string, split half each with the surrounding X string) + | |
288 | 1*0.33 (the connection point, split between three strings) = | |
289 | 9.33. As noted this value was doubled, giving 18.67 which is | |
290 | reasonably close to the correct value of 18. The effective size | |
291 | heuristic is still used in certain parts of the move valuation | |
292 | where we can't easily get a more accurate value from the | |
293 | influence function (e. g. attacks depending on a ko, attack threats). | |
294 | ||
295 | Note that this section only describes the territorial valuation of a move. | |
296 | Apart from that, GNU Go uses various heuristics in assigning a strategical | |
297 | value (weakening and strengthening of other stones on the board) to a move. | |
298 | Also, the influence function isn't quite as well tuned as the examples above | |
299 | may seem to claim. But it should give a fairly good idea of how the design | |
300 | is intended. | |
301 | ||
302 | Another matter is that so far we have only considered the change in secure | |
303 | territory. GNU Go 3.2 and later versions use a revised heuristic, which | |
304 | is explained in the next section, to assign probable territory to each | |
305 | player. | |
306 | ||
307 | @node Territorial Details | |
308 | @section Details of the Territory Valuation | |
309 | ||
310 | This section explains how GNU Go assigns a territorial value to an | |
311 | intersection once the white and black influence have been computed. | |
312 | The intention is that an intersection that has a chance of xx% of | |
313 | becoming white territory is counted as 0.xx points of territory for | |
314 | white, and similar for black. | |
315 | ||
316 | The algorithm in the function @code{new_value_territory} goes roughly | |
317 | as follows: | |
318 | ||
319 | If @code{wi} is the white influence at a point, and @code{bi} the black | |
320 | influence, then @code{ value = ( (wi-bi)/ (wi+bi) )^3} (positive values | |
321 | indicates likley white territory, negative stand for black territory) | |
322 | turns out to be very simple first guess that is still far off, but | |
323 | reasonable enough to be useful. | |
324 | ||
325 | This value is then suspect a number of corrections. Assume that this first | |
326 | guess resulted in a positive value. | |
327 | ||
328 | If both @code{bi} and @code{wi} are small, it gets reduced. What exactly is | |
329 | "small" depends on whether the intersection is close to a corner or an edge | |
330 | of the board, since it is easier to claim territory in the corner than in | |
331 | the center. | |
332 | ||
333 | Then the value at each intersection is degraded to the minimum value of | |
334 | its neighbors. This can be seen as a second implementation of the proverb | |
335 | saying that there is no territory in the center of the board. This step | |
336 | substantially reduces the size of spheres of territory that are open at | |
337 | several sides. | |
338 | ||
339 | Finally, there are a number of patterns that explicitly forbid GNU Go to | |
340 | count territory at some intersections. This is used e. g. for false eyes that | |
341 | will eventually have to be filled in. Also, points for prisoners are added. | |
342 | ||
343 | To fine tune this scheme, some revisions have been made to the influence | |
344 | computations that are relevant for territorial evaluation. This includes | |
345 | a reduced default attenuation and some revised pattern handling. | |
346 | ||
347 | @node The Influence Core | |
348 | @section The Core of the Influence Function | |
349 | ||
350 | The basic influence radiation process can efficiently be implemented | |
351 | as a breadth first search for adjacent and more distant points, using | |
352 | a queue structure. | |
353 | ||
354 | Influence barriers can be found by pattern matching, assisted by | |
355 | reading through constraints and/or helpers. Wall structures, invasion | |
356 | points and intrusion points can be found by pattern matching as well. | |
357 | ||
358 | When influence is computed, the basic idea is that there are a number | |
359 | of influence sources on the board, whose contributions are summed to | |
360 | produce the influence values. For the time being we can assume that | |
361 | the living stones on the board are the influence sources, although | |
362 | this is not the whole story. | |
363 | ||
364 | The function @code{compute_influence()} contains a loop over the | |
365 | board, and for each influence source on the board, the function | |
366 | @code{accumulate_influence()} is called. This is the core of the | |
367 | influence function. Before we get into the details, this is how | |
368 | the influence field from a single isolated influence source of | |
369 | strength 100 turns out (with an attenuation of 3.0): | |
370 | ||
371 | @example | |
372 | 0 0 0 0 0 0 0 0 0 0 0 | |
373 | 0 0 0 0 1 1 1 0 0 0 0 | |
374 | 0 0 0 1 2 3 2 1 0 0 0 | |
375 | 0 0 1 3 5 11 5 3 1 0 0 | |
376 | 0 1 2 5 16 33 16 5 2 1 0 | |
377 | 0 1 3 11 33 X 33 11 3 1 0 | |
378 | 0 1 2 5 16 33 16 5 2 1 0 | |
379 | 0 0 1 3 5 11 5 3 1 0 0 | |
380 | 0 0 0 1 2 3 2 1 0 0 0 | |
381 | 0 0 0 0 1 1 1 0 0 0 0 | |
382 | 0 0 0 0 0 0 0 0 0 0 0 | |
383 | @end example | |
384 | ||
385 | These values are in reality floating point numbers but have been | |
386 | rounded down to the nearest integer for presentation. This means that | |
387 | the influence field does not stop when the numbers become zeroes. | |
388 | ||
389 | Internally @code{accumulate_influence()} starts at the influence source and | |
390 | spreads influence outwards by means of a breadth first propagation, | |
391 | implemented in the form of a queue. The order of propagation and the | |
392 | condition that influence only is spread outwards guarantee that no | |
393 | intersection is visited more than once and that the process | |
394 | terminates. In the example above, the intersections are visited in the | |
395 | following order: | |
396 | ||
397 | @example | |
398 | + + + + + + + + + + + | |
399 | + 78 68 66 64 63 65 67 69 79 + | |
400 | + 62 46 38 36 35 37 39 47 75 + | |
401 | + 60 34 22 16 15 17 23 43 73 + | |
402 | + 58 32 14 6 3 7 19 41 71 + | |
403 | + 56 30 12 2 0 4 18 40 70 + | |
404 | + 57 31 13 5 1 8 20 42 72 + | |
405 | + 59 33 21 10 9 11 24 44 74 + | |
406 | + 61 45 28 26 25 27 29 48 76 + | |
407 | + 77 54 52 50 49 51 53 55 80 + | |
408 | + + + + + + + + + + + | |
409 | @end example | |
410 | ||
411 | The visitation of intersections continues in the same way on the | |
412 | intersections marked '@samp{+} and further outwards. In a real | |
413 | position there will be stones and tight connections stopping the | |
414 | influence from spreading to certain intersections. This will | |
415 | disrupt the diagram above, but the main property of the | |
416 | propagation still remains, i.e. no intersection is visited more | |
417 | than once and after being visited no more influence will be | |
418 | propagated to the intersection. | |
419 | ||
420 | @node The Influence Algorithm | |
421 | @section The Influence Algorithm | |
422 | ||
423 | Let @code{(m, n)} be the coordinates of the influence source and | |
424 | @code{(i, j)} the coordinates of a an intersection being visited | |
425 | during propagation, using the same notation as in the | |
426 | @code{accumulate_influence()} function. Influence is now propagated to | |
427 | its eight closest neighbors, including the diagonal ones, | |
428 | according to the follow scheme: | |
429 | ||
430 | For each of the eight directions @code{(di, dj)}, do: | |
431 | ||
432 | @enumerate | |
433 | @item | |
434 | Compute the scalar product @code{di*(i-m) + dj*(j-n)} | |
435 | between the vectors @code{(di,dj)} and @code{(i,j) - (m,n)} | |
436 | @item If this is negative or zero, the direction is not outwards and | |
437 | we continue with the next direction. The exception is when we | |
438 | are visiting the influence source, i.e. the first intersection, | |
439 | when we spread influence in all directions anyway. | |
440 | @item If @code{(i+di, j+dj)} is outside the board or occupied we | |
441 | also continue with the next direction. | |
442 | @item Let S be the strength of the influence at @code{(i, j)}. The influence | |
443 | propagated to @code{(i+di, j+dj)} from this intersection is given by | |
444 | @code{P*(1/A)*D*S}, where the three different kinds of damping are: | |
445 | ||
446 | @itemize @bullet | |
447 | @item The permeability @samp{P}, which is a property of the board | |
448 | intersections. Normally this is one, i.e. unrestricted | |
449 | propagation, but to stop propagation through e.g. one step | |
450 | jumps, the permeability is set to zero at such intersections | |
451 | through pattern matching. This is further discussed below. | |
452 | @item The attenuation @samp{A}, which is a property of the influence | |
453 | source and different in different directions. By default this has the | |
454 | value 3 except diagonally where the number is twice as much. By | |
455 | modifying the attenuation value it is possible to obtain influence | |
456 | sources with a larger or a smaller effective range. | |
457 | @item The directional damping @samp{D}, which is the squared cosine of the | |
458 | angle between @code{(di,dj)} and @code{(i,j) - (m,n)}. The idea is to | |
459 | stop influence from "bending" around an interfering stone and | |
460 | get a continuous behavior at the right angle cutoff. The | |
461 | choice of the squared cosine for this purpose is rather | |
462 | arbitrary, but has the advantage that it can be expressed as a | |
463 | rational function of @samp{m}, @samp{n}, @samp{i}, @samp{j}, | |
464 | @samp{di}, and @samp{dj}, without involving any trigonometric or | |
465 | square root computations. When we are visiting the influence | |
466 | source we let by convention this factor be one. | |
467 | @end itemize | |
468 | @end enumerate | |
469 | ||
470 | Influence is typically contributed from up to three neighbors | |
471 | "between" this intersection and the influence source. These values are | |
472 | simply added together. As pointed out before, all contributions will | |
473 | automatically have been made before the intersection itself is | |
474 | visited. | |
475 | ||
476 | When the total influence for the whole board is computed by | |
477 | @code{compute_influence()}, @code{accumulate_influence()} is | |
478 | called once for each influence source. These invocations are | |
479 | totally independent and the influence contributions from the | |
480 | different sources are added together. | |
481 | ||
482 | @node Permeability | |
483 | @section Permeability | |
484 | ||
485 | The permeability at the different points is initially one at all empty | |
486 | intersections and zero at occupied intersections. To get a useful | |
487 | influence function we need to modify this, however. Consider the | |
488 | following position: | |
489 | ||
490 | @example | |
491 | |...... | |
492 | |OOOO.. | |
493 | |...O.. | |
494 | |...a.X ('a' empty intersection) | |
495 | |...O.. | |
496 | |...OOO | |
497 | |.....O | |
498 | +------ | |
499 | @end example | |
500 | ||
501 | The corner is of course secure territory for @samp{O} and clearly | |
502 | the @samp{X} stone has negligible effect inside this position. To | |
503 | stop @samp{X} influence from leaking into the corner we use pattern | |
504 | matching (pattern Barrier1/Barrier2 in @file{barriers.db}) to modify the | |
505 | permeability for @samp{X} at this intersection to zero. @samp{O} can still | |
506 | spread influence through this connection. | |
507 | ||
508 | Another case that needs to be mentioned is how the permeability | |
509 | damping is computed for diagonal influence radiation. For horizontal | |
510 | and vertical radiation we just use the permeability (for the relevant | |
511 | color) at the intersection we are radiating from. In the diagonal case | |
512 | we additionally multiply with the maximum permeability at the two | |
513 | intersections we are trying to squeeze between. The reason for this | |
514 | can be found in the diagram below: | |
515 | ||
516 | @example | |
517 | |...X |...X | |
518 | |OO.. |Oda. | |
519 | |..O. |.bc. | |
520 | |..O. |..O. | |
521 | +---- +---- | |
522 | @end example | |
523 | ||
524 | We don't want @samp{X} influence to be spread from @samp{a} to | |
525 | @samp{b}, and since the permeability at both c and d is zero, the | |
526 | rule above stops this. | |
527 | ||
528 | @node Escape | |
529 | @section Escape | |
530 | ||
531 | One application of the influence code is in computing the | |
532 | @code{dragon.escape_route} field. This is computed by the function | |
533 | @code{compute_escape()} as follows. First, every intersection is | |
534 | assigned an escape value, ranging between 0 and 4, depending on | |
535 | the influence value of the opposite color. | |
536 | ||
537 | The @code{escape_route} field is modified by the code in @file{surround.c} | |
538 | (@pxref{Surrounded Dragons}). It is divided by two for weakly surrounded | |
539 | dragons, and set to zero for surrounded ones. | |
540 | ||
541 | In addition to assiging an escape value to empty vertices, | |
542 | we also assign an escape value to friendly dragons. This | |
543 | value can range from 0 to 6 depending on the status of | |
544 | the dragon, with live dragons having value 6. | |
545 | ||
546 | Then we sum the values of the resulting influence escape values | |
547 | over the intersections (including friendly dragons) at distance 4, | |
548 | that is, over those intersections which can be joined to the | |
549 | dragon by a path of length 4 (and no shorter path) not passing | |
550 | adjacent to any unfriendly dragon. In the following example, we | |
551 | sum the influence escape value over the four vertices labelled | |
552 | '4'. | |
553 | ||
554 | @example | |
555 | ||
556 | . . . . . . . . . . . . . . . . . . | |
557 | . . . . . X . . O . . . . . X . . O | |
558 | . . X . . . . . O . . X . 2 . 4 . O | |
559 | X . . . . . . . . X . . 1 1 2 3 4 . | |
560 | X O . O . . . . O X O 1 O 1 2 3 4 O | |
561 | X O . O . . . . . X O 1 O 1 . 4 . . | |
562 | X O . . . X . O O X O 1 . . X . . O | |
563 | . . . X . . . . . . 1 . X . . . . . | |
564 | X . . . . X . . . X . . . . X . . . | |
565 | . . . . . . . . . . . . . . . . . . | |
566 | ||
567 | @end example | |
568 | ||
569 | Since the dragon is trying to reach safety, the reader might | |
570 | wonder why @code{compute_influence()} is called with the opposite | |
571 | color of the dragon contemplating escape. To explain this point, | |
572 | we first remind the reader why there is a color parameter to | |
573 | @code{compute_influence()}. Consider the following example position: | |
574 | @example | |
575 | ||
576 | ...XX... | |
577 | OOO..OOO | |
578 | O......O | |
579 | O......O | |
580 | -------- | |
581 | ||
582 | @end example | |
583 | ||
584 | Whether the bottom will become O territory depends on who is in turn | |
585 | to play. This is implemented with the help of patterns in barriers.db, | |
586 | so that X influence is allowed to leak into the bottom if X is in turn | |
587 | to move but not if O is. There are also ``invade'' patterns which add | |
588 | influence sources in sufficiently open parts of the board which are | |
589 | handled differently depending on who is in turn to move. | |
590 | ||
591 | In order to decide the territorial value of an O move in the third | |
592 | line gap above, influence is first computed in the original position | |
593 | with the opponent (i.e. X) in turn to move. Then the O stone is played | |
594 | to give: | |
595 | ||
596 | @example | |
597 | ||
598 | ...XX... | |
599 | OOO.OOOO | |
600 | O......O | |
601 | O......O | |
602 | -------- | |
603 | ||
604 | @end example | |
605 | ||
606 | Now influence is computed once more, also this time with X in turn to | |
607 | move. The difference in territory (as computed from the influence | |
608 | values) gives the territorial value of the move. | |
609 | ||
610 | Exactly how influence is computed for use in the escape route | |
611 | estimation is all ad hoc. But it makes sense to assume the opponent | |
612 | color in turn to move so that the escape possibilities aren't | |
613 | overestimated. After we have made a move in the escape direction | |
614 | it is after all the opponent's turn. | |
615 | ||
616 | The current escape route mechanism seems good enough to be useful | |
617 | but is not completely reliable. Mostly it seems to err on the side of | |
618 | being too optimistic. | |
619 | ||
620 | @node Break Ins | |
621 | @section Break Ins | |
622 | ||
623 | The code in @file{breakin.c} break-ins into territories that require | |
624 | deeper tactical reading and are thus impossible to detect for the | |
625 | influence module. It gets run after the influence module and revises | |
626 | its territory valuations. | |
627 | ||
628 | The break-in code makes use of two public functions in @file{readconnect.c}, | |
629 | ||
630 | @itemize @bullet | |
631 | @item int break_in(int str, const char goal[BOARDMAX], int *move) | |
632 | @findex break_in | |
633 | @quotation | |
634 | Returns WIN if @code{str} can connect to the area @code{goal[]} (which may or | |
635 | may not contain stones), if the string's owner gets the first move. | |
636 | @end quotation | |
637 | @item int block_off(int str, const char goal[BOARDMAX], int *move) | |
638 | @findex block_off | |
639 | @quotation | |
640 | Returns WIN if @code{str} cannot connect to the area @code{goal[]} (which may | |
641 | or may not contain stones), if the other color moves first. | |
642 | @end quotation | |
643 | @end itemize | |
644 | ||
645 | These functions are public front ends to their counterparts | |
646 | @code{recursive_break_in} and @code{recursive_block_off}, which | |
647 | call each other recursively. | |
648 | ||
649 | The procedure is as follows: We look at all big (>= 10) territory regions | |
650 | as detected by the influence code. Using the computation of | |
651 | connection distances from readconnect.c, we compute all nearby vertices | |
652 | of this territory. We look for the closest safe stones belonging to | |
653 | the opponent. | |
654 | ||
655 | For each such string @code{str} we call | |
656 | ||
657 | @itemize @bullet | |
658 | @item @code{break_in(str, territory)} if the opponent is assumed to be next to move, | |
659 | @item @code{block_off(str, territory)} if the territory owner is next. | |
660 | @end itemize | |
661 | ||
662 | If the break in is successful resp. the blocking unsuccessful, we | |
663 | shrink the territory, and see whether the opponent can still break in. | |
664 | We repeat this until the territory is shrunk so much that the opponent | |
665 | can no longer reach it. | |
666 | ||
667 | To see the break in code in action run GNU Go on the file | |
668 | @file{regression/games/break_in.sgf} with the option @code{-d0x102000}. Among | |
669 | the traces you will find: | |
670 | ||
671 | @example | |
672 | Trying to break in from D7 to: | |
673 | E9 (1) F9 (1) G9 (1) E8 (1) F8 (1) G8 (1) | |
674 | H8 (1) G7 (1) H7 (1) J7 (1) H6 (1) J6 (1) | |
675 | H5 (1) J5 (1) H4 (1) J4 (1) H3 (1) J3 (1) | |
676 | H2 (1) J2 (1) | |
677 | block_off D7, result 0 PASS (355, 41952 nodes, 0.73 seconds) | |
678 | E9 (1) F9 (1) G9 (1) E8 (1) F8 (1) G8 (1) | |
679 | H8 (1) G7 (1) H7 (1) J7 (1) H6 (1) J6 (1) | |
680 | H5 (1) J5 (1) H4 (1) J4 (1) H3 (1) J3 (1) | |
681 | H2 (1) J2 (1) | |
682 | B:F4 | |
683 | Erasing territory at E8 -b. | |
684 | Erasing territory at G3 -b. | |
685 | Now trying to break to smaller goal: | |
686 | F9 (1) G9 (1) F8 (1) G8 (1) H8 (1) G7 (1) | |
687 | H7 (1) J7 (1) H6 (1) J6 (1) H5 (1) J5 (1) | |
688 | H4 (1) J4 (1) H3 (1) J3 (1) H2 (1) J2 (1) | |
689 | @end example | |
690 | ||
691 | This means that the function @code{break_in} is called with the goal | |
692 | marked 'a' in the following diagram. The code attempts to find out | |
693 | whether it is possible to connect into this area from the string | |
694 | at @code{D7}. | |
695 | ||
696 | @example | |
697 | A B C D E F G H J | |
698 | 9 . . . . a a a . . 9 | |
699 | 8 . . . . a a a a . 8 | |
700 | 7 . . . X O O a a a 7 | |
701 | 6 . . . X X X O a a 6 | |
702 | 5 . . . . + . . a a 5 | |
703 | 4 . . . X . . O a a 4 | |
704 | 3 . . . . X . . a a 3 | |
705 | 2 . . . . . . O a a 2 | |
706 | 1 . . . . . . . . . 1 | |
707 | A B C D E F G H J | |
708 | @end example | |
709 | ||
710 | A breakin is found, so the goal is shrunk by removing | |
711 | @code{E9} and @code{J2}, then break_in is called again. | |
712 | ||
713 | In order to see what reading is actually done in order to | |
714 | do this break in, you may load GNU Go in gtp mode, then | |
715 | issue the commands: | |
716 | ||
717 | @example | |
718 | loadsgf break_in.sgf | |
719 | = black | |
720 | ||
721 | start_sgftrace | |
722 | = | |
723 | ||
724 | break_in D7 E9 F9 G9 E8 F8 G8 H8 G7 H7 J7 H6 J6 H5 J5 H4 J4 H3 J3 H2 J2 | |
725 | = 1 E8 | |
726 | ||
727 | finish_sgftrace vars.sgf | |
728 | = | |
729 | ||
730 | start_sgftrace | |
731 | = | |
732 | ||
733 | break_in D7 F9 G9 F8 G8 H8 G7 H7 J7 H6 J6 H5 J5 H4 J4 H3 J3 H2 J2 | |
734 | = 1 G7 | |
735 | ||
736 | finish_sgftrace vars1.sgf | |
737 | @end example | |
738 | ||
739 | This will produce two sgf files containing the variations caused | |
740 | by these calls to the breakin code. The second file, @file{vars1.sgf} | |
741 | will contain quite a few variations. | |
742 | ||
743 | The break in code makes a list of break ins which are found. | |
744 | When it is finished, the function @code{add_expand_territory_move} | |
745 | is called for each break in, adding a move reason. | |
746 | ||
747 | The break in code is slow, and only changes a few moves by the engine | |
748 | per game. Nevertheless we believe that it contributes substantially | |
749 | to the strength of the program. The break in code is enabled by default | |
750 | in GNU Go 3.6 at level 10, and disabled at level 9. In fact, this is the | |
751 | @strong{only} difference between levels 9 and 10 in GNU Go 3.6. | |
752 | ||
753 | @node Surrounded Dragons | |
754 | @section Surrounded Dragons | |
755 | ||
756 | When is a dragon surrounded? | |
757 | ||
758 | As has been pointed out by Bruce Wilcox, the geometric lines connecting groups | |
759 | of the opposite color are often important. It is very hard to prevent the | |
760 | escape of this @samp{O} dragon: | |
761 | ||
762 | @example | |
763 | .......... | |
764 | .....O.... | |
765 | .X.......X | |
766 | .X...O...X | |
767 | .......... | |
768 | .......... | |
769 | ---------- | |
770 | @end example | |
771 | ||
772 | On the other hand, this dragon is in grave danger: | |
773 | ||
774 | @example | |
775 | .......... | |
776 | .......... | |
777 | .X.......X | |
778 | .....O.... | |
779 | .X.......X | |
780 | .X...O...X | |
781 | .......... | |
782 | .......... | |
783 | ---------- | |
784 | @end example | |
785 | ||
786 | The difference between these two positions is that in the first, the @samp{O} | |
787 | dragon crosses the line connecting the top two @samp{X} stones. | |
788 | ||
789 | Code in @file{surround.c} implements a test for when a dragon is surrounded. | |
790 | The idea is to compute the convex hull of the @emph{surround set}, that is, | |
791 | the set stones belonging to unfriendly neighbor dragons. If the dragon is | |
792 | contained within that hull. If it is, it is said to be @emph{surrounded}. | |
793 | ||
794 | In practice this scheme is modified slightly. The implementation uses various | |
795 | algorithms to compute distances and hostile stones are discarded from the | |
796 | surround set when a pair other hostile ones can be found which makes the | |
797 | considered one useless. For example, in the following position | |
798 | the bottom @samp{O} stone would get discarded. | |
799 | ||
800 | @example | |
801 | O.X.O | |
802 | ..... | |
803 | .O.O. | |
804 | ..... | |
805 | ..O.. | |
806 | @end example | |
807 | ||
808 | Also, points are added to the surround set below stones on the | |
809 | second and third lines. This should account for the edge being a | |
810 | natural barrier. | |
811 | ||
812 | In order to compute distances between corners of the convex hull | |
813 | a sorting by angle algorithm has been implemented. If the distance | |
814 | between a pair enclosing stones is large, the surround status gets | |
815 | decreased to @code{WEAKLY_SURROUNDED}, or even 0 for very large ones. | |
816 | ||
817 | The sorting by angle must be explained. A small diagram will probably help : | |
818 | ||
819 | @example | |
820 | .O.O. | |
821 | O...O | |
822 | ..X.. | |
823 | O...O | |
824 | .O.O. | |
825 | @end example | |
826 | ||
827 | The sorting algorithm will generate this: | |
828 | ||
829 | @example | |
830 | .4.5. | |
831 | 3...6 | |
832 | ..X.. | |
833 | 2...7 | |
834 | .1.8. | |
835 | @end example | |
836 | ||
837 | That is, the points are sorted by ascending order of the measure of the | |
838 | angle S-G-O, where S is SOUTH, G the (approximated) gravity center of | |
839 | the goal, and O the position of the considered hostile stones. | |
840 | ||
841 | The necessity of such sorting appears when one tries to measure distances | |
842 | between enclosing stones without sorting them, just by using directly the | |
843 | existing left and right corners arrays. In some positions, the results will | |
844 | be inconsistent. Imagine, for example a position where for instance the points | |
845 | 1,2,3,4,6 and 7 were in the left arrary, leaving only 5 and 8 in the right | |
846 | array. Because of the large distance between 5 and 8, the dragon would have | |
847 | declared weak surrounded or not surrounded at all. Such cases are rare but | |
848 | frequent enough to require the angle sorting. | |
849 | ||
850 | The following position: | |
851 | ||
852 | @example | |
853 | O.X.O | |
854 | ..... | |
855 | .O.O. | |
856 | @end example | |
857 | ||
858 | This is "more" surrounded than the following position: | |
859 | ||
860 | @example | |
861 | O.XXXXXX.O | |
862 | .......... | |
863 | .O......O. | |
864 | @end example | |
865 | ||
866 | In the second case, the surround status would be lowered to | |
867 | @code{WEAKLY_SURROUNDED}. | |
868 | ||
869 | The surround code is used to modify the escape_route field | |
870 | in the dragon2 data array. When a dragon is WEAKLY_SURROUNDED, | |
871 | the escape_route is divided by 2. If the dragon is SURROUNDED, | |
872 | escape_route is simply set to 0. | |
873 | ||
874 | ||
875 | @node Influential Patterns | |
876 | @section Patterns used by the Influence module | |
877 | ||
878 | This section explains the details of the pattern databases used for | |
879 | the influence computation. | |
880 | ||
881 | First, we have the patterns in @file{influence.db}, which get matched | |
882 | symmetrically for both colors. | |
883 | ||
884 | @itemize | |
885 | @item @samp{E} | |
886 | @quotation | |
887 | These patterns add extra influence sources close to some shapes like walls. | |
888 | This tries to reflect their extra strength. These patterns are not used | |
889 | in the influence computations relevant for territory valuations, but they | |
890 | are useful for getting a better estimate of strengths of groups. | |
891 | @end quotation | |
892 | @item @samp{I} | |
893 | @quotation | |
894 | These patterns add extra influence sources at typical invasion points. | |
895 | Usually they are of small strength. If they additionally have the class | |
896 | @samp{s}, the extra influence source is added for both colors. Otherwise, | |
897 | only the player assumed to be next to move gets the benefit. | |
898 | @end quotation | |
899 | @end itemize | |
900 | ||
901 | The patterns in @file{barriers.db} get matched only for @samp{O} | |
902 | being the player next to move. | |
903 | ||
904 | @itemize | |
905 | @item @samp{A} | |
906 | @quotation | |
907 | Connections between @samp{X} stones that stop influence of @samp{O}. They | |
908 | have to be tight enough that @samp{O} cannot break through, even though | |
909 | he is allowed to move first. | |
910 | @end quotation | |
911 | @item @samp{D} | |
912 | @quotation | |
913 | Connections between @samp{O} stones that stop influence of @samp{X}. The | |
914 | stones involved can be more loosely connected than those in @samp{A} | |
915 | patterns. | |
916 | @end quotation | |
917 | @item @samp{B} | |
918 | @quotation | |
919 | These indicate positions of followup moves for the @samp{O} stone marked | |
920 | with @samp{Q} in the pattern. They are used to reduce the territory e. g. | |
921 | where a monkey jump is possible. Also, they are used in the computation | |
922 | of the followup influence, if the @samp{Q} stone was the move played | |
923 | (or a stone saved by the move played). | |
924 | @end quotation | |
925 | @item @samp{t} | |
926 | @quotation | |
927 | These patterns indicate intersections where one color will not be able | |
928 | to get territory, for example in a false eye. The points are set with | |
929 | a call to the helper non_oterritory or non_xterritory in the action of | |
930 | the pattern. | |
931 | @end quotation | |
932 | @end itemize | |
933 | ||
934 | The intrusion patterns (@samp{B}) are more powerful than the description | |
935 | above might suggest. They can be very helpful in identifying weak shapes | |
936 | (by adding an intrusion source for the opponent where he can break through). | |
937 | A negative inference for this is that a single bad @samp{B} pattern, e. g. | |
938 | one that has a wrong constraint, typically causes 5 to 10 @code{FAIL}s in | |
939 | the regression test suite. | |
940 | ||
941 | Influence Patterns can have autohelper constraints as usual. As for | |
942 | the constraint attributes, there are (additionally to the usual | |
943 | ones @samp{O}, @samp{o}, @samp{X} and @samp{x}), | |
944 | attributes @samp{Y} and @samp{FY}. A pattern marked with @samp{Y} will | |
945 | only be used in the influence computations relevant for the territory | |
946 | valuation, while @samp{FY} patterns only get used in the other influence | |
947 | computations. | |
948 | ||
949 | The action of an influence pattern is at the moment only used for | |
950 | non-territory patterns as mentioned above, and as a workaround for a | |
951 | problem with @samp{B} patterns in the followup influence. | |
952 | ||
953 | To see why this workaround is necessary, consider the follwoing situation: | |
954 | ||
955 | @example | |
956 | ||
957 | ..XXX | |
958 | .a*.O | |
959 | .X.O. | |
960 | ..XXO | |
961 | ||
962 | @end example | |
963 | ||
964 | (Imagine that there is @samp{X} territory on the left.) | |
965 | ||
966 | The move by @samp{O} at @samp{*} has a natural followup move at @samp{a}. | |
967 | So, in the computation of the followup influence for @samp{*}, there would | |
968 | be an extra influence source for @samp{O} at @samp{a} which would destroy | |
969 | a lot of black territory on the left. This would give a big followup value, | |
970 | and in effect the move @samp{*} would be treated as sente. | |
971 | ||
972 | But of course it is gote, since @samp{X} will answer at @samp{a}, which | |
973 | both stops the possible intrusion and threatens to capture @samp{*}. This | |
974 | situation is in fact quite common. | |
975 | ||
976 | Hence we need an additional constraint that can tell when an intrusion | |
977 | pattern can be used in followup influence. This is done by misusing the | |
978 | action line: An additional line | |
979 | ||
980 | @example | |
981 | >return <condition>; | |
982 | @end example | |
983 | ||
984 | gets added to the pattern. The @code{condition} should be true if the | |
985 | intrusion cannot be stopped in sente. In the above example, the relevant | |
986 | intrusion pattern will have an action line of the form | |
987 | ||
988 | @example | |
989 | >return (!xplay_attack(a,b)); | |
990 | @end example | |
991 | ||
992 | where @samp{b} refers to the stone at @samp{*}. In fact, almost all | |
993 | followup-specific constraints look similar to this. | |
994 | ||
995 | ||
996 | @node Influential Display | |
997 | @section Colored display and debugging of influence | |
998 | ||
999 | There are various ways to obtain detailed information about the influence | |
1000 | computations. Colored diagrams showing influence are possible from | |
1001 | a colored xterm or rxvt window. | |
1002 | ||
1003 | There are two options controlling when to generate diagrams: | |
1004 | ||
1005 | @itemize @bullet | |
1006 | @item @option{-m 0x08} or @option{-m 8} | |
1007 | @quotation | |
1008 | Show diagrams for the initial influence computation. This is done | |
1009 | twice, the first time before @code{make_dragons()} is run and the second time | |
1010 | after. The difference is that dead dragons are taken into account the | |
1011 | second time. Tactically captured worms are taken into account both | |
1012 | times. | |
1013 | @end quotation | |
1014 | @item @option{--debug-influence @var{location}} | |
1015 | @quotation | |
1016 | Show influence diagrams after the move at the given location. An | |
1017 | important limitation of this option is that it's only effective for | |
1018 | moves that the move generation is considering. | |
1019 | @end quotation | |
1020 | @end itemize | |
1021 | ||
1022 | The other options control which diagrams should be generated in these | |
1023 | situations. You have to specify at least one of the options above and | |
1024 | at least one of the options below to generate any output. | |
1025 | ||
1026 | @strong{ | |
1027 | The options below must be combined with one of the two previous | |
1028 | ones, or the diagram will not be printed. For example to print | |
1029 | the influence diagram, you may combine 0x08 and 0x010, and use | |
1030 | the option @option{-m 0x018}.} | |
1031 | ||
1032 | @itemize @bullet | |
1033 | @item @option{-m 0x010} or @option{-m 16} | |
1034 | @quotation | |
1035 | Show colored display of territory/moyo/area regions. | |
1036 | @itemize @minus | |
1037 | @item territory: cyan | |
1038 | @item moyo: yellow | |
1039 | @item area: red | |
1040 | @end itemize | |
1041 | This feature is very useful to get an immediate impression of the influence | |
1042 | regions as GNU Go sees them. | |
1043 | @end quotation | |
1044 | @item @option{-m 0x20} or @option{-m 32} | |
1045 | @quotation | |
1046 | Show numerical influence values for white and black. These come in | |
1047 | two separate diagrams, the first one for white, the second one for | |
1048 | black. Notice that the influence values are represented by floats and | |
1049 | thus have been rounded in these diagrams. | |
1050 | @end quotation | |
1051 | @item @option{-m 0x40} or @option{-m 64} | |
1052 | @quotation | |
1053 | This generates two diagrams showing the permeability for black and white | |
1054 | influence on the board. | |
1055 | @end quotation | |
1056 | @item @option{-m 0x80} or @option{-m 128} | |
1057 | @quotation | |
1058 | This shows the strength of the influence sources for black and white | |
1059 | across the board. You will see sources at each lively stone (with strength | |
1060 | depending on the strength of this stone), and sources contributed by | |
1061 | patterns. | |
1062 | @end quotation | |
1063 | @item @option{-m 0x100} or @option{-m 256} | |
1064 | @quotation | |
1065 | This shows the attenuation with which the influence sources spread | |
1066 | influence across the board. Low attenuation indicates far-reaching | |
1067 | influence sources. | |
1068 | @end quotation | |
1069 | @item @option{-m 0x200} or @option{-m 512} | |
1070 | @quotation | |
1071 | This shows the territory valuation of GNU Go. Each intersection is | |
1072 | shown with a value between -1.0 and +1.0 (or -2 resp. +2 if there is | |
1073 | a dead stone on this intersection). Positive values indicate territory | |
1074 | for white. A value of -0.5 thus indicates a point where black has a | |
1075 | 50% chance of getting territory. | |
1076 | @end quotation | |
1077 | @end itemize | |
1078 | ||
1079 | Finally, there is the debug option @option{-d 0x1} which turns on | |
1080 | on @code{DEBUG_INFLUENCE}. This gives a message for each influence pattern | |
1081 | that gets matched. Unfortunately, these are way too many messages making | |
1082 | it tedious to navigate the output. However, if you discover an influence | |
1083 | source with @option{-m 0x80} that looks wrong, the debug output can | |
1084 | help you to quickly find out the responsible pattern. | |
1085 | ||
1086 | @node Influence Tuning | |
1087 | @section Influence Tuning with @code{view.pike} | |
1088 | ||
1089 | A useful program in the regression directory is @code{view.pike}. | |
1090 | To run it, you need Pike, which you may download from | |
1091 | @url{http://pike.ida.liu.se/}. | |
1092 | ||
1093 | The test case @file{endgame:920} fails in GNU Go 3.6. We will | |
1094 | explain how to fix it. | |
1095 | ||
1096 | Start by firing up view.pike on testcase endgame:920, e.g. by running | |
1097 | @command{pike view.pike endgame:920} in the regression directory. | |
1098 | ||
1099 | We see from the first view of move values that filling dame at P15 is | |
1100 | valued highest with 0.17 points while the correct move at C4 is valued | |
1101 | slightly lower with 0.16. The real problem is of course that C4 is | |
1102 | worth a full point and thus should be valued about 1.0. | |
1103 | ||
1104 | Now click on C4 to get a list of move reasons and move valuation | |
1105 | information. Everything looks okay except that change in territory is | |
1106 | 0.00 rather than 1.00 as it ought to be. | |
1107 | ||
1108 | We can confirm this by choosing the ``delta territory for...'' button | |
1109 | and again clicking C4. Now B5 should have been marked as one point of | |
1110 | change in territory, but it's not. | |
1111 | ||
1112 | Next step is to enter the influence debug tool. Press the ``influence'' | |
1113 | button, followed by ``black influence, dragons known,'' and ``territory | |
1114 | value.'' This shows the expected territory if black locally moves first | |
1115 | everywhere (thus ``black influence''). Here we can see that B5 is | |
1116 | incorrectly considered as 1.0 points of white territory. | |
1117 | ||
1118 | We can compare this with the territory after a white move at C4 (still | |
1119 | assuming that black locally moves first everywhere after that) by | |
1120 | pressing ``after move influence for...'' and clicking C4. This looks | |
1121 | identical, as expected since delta territory was 0, but here it is | |
1122 | correct that B5 is 1.0 points of territory for white. | |
1123 | ||
1124 | The most straightforward solution to this problem is to add a | |
1125 | non-territory pattern, saying that white can't get territory on B5 if | |
1126 | black moves first. The nonterritory patterns are in @file{barriers.db}. | |
1127 | ||
1128 | @example | |
1129 | Pattern Nonterritory56 | |
1130 | ||
1131 | ... | |
1132 | X.O | |
1133 | ?O. | |
1134 | ||
1135 | :8,t | |
1136 | ||
1137 | eac | |
1138 | XbO | |
1139 | ?Od | |
1140 | ||
1141 | ;oplay_attack(a,b,c,d,d) | |
1142 | ||
1143 | >non_xterritory(e); | |
1144 | @end example | |
1145 | ||
1146 | In these patterns it's always assumed that @samp{O} moves first and thus it | |
1147 | says that @samp{X} can't get territory at @code{B5} (@samp{e} in the | |
1148 | pattern). Now we need to be a bit careful however since after @samp{O} plays | |
1149 | at @samp{a} and @samp{X} cuts in at @samp{b}, it may well happen that @samp{O} | |
1150 | needs to defend around @samp{d}, allowing @samp{X} to cut at @samp{c}, possibly | |
1151 | making the nonterritory assumption invalid. It's difficult to do this entirely | |
1152 | accurate, but the constraint above is fairly conservative and should guarantee | |
1153 | that @samp{a} is safe in most, although not all, cases. |