| 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. |