| 1 | |
| 2 | @menu |
| 3 | * Move generation Intro:: Introduction. |
| 4 | * Move Reasons:: Generation of move reasons. |
| 5 | * Move Reason Details:: Detailed Descriptions of Move Reasons |
| 6 | * Valuation:: Valuating the moves |
| 7 | * End Game:: Endgame move generation |
| 8 | @end menu |
| 9 | |
| 10 | @node Move generation Intro |
| 11 | @section Introduction |
| 12 | |
| 13 | GNU Go 3.0 introduced a move generation scheme substantially different |
| 14 | from earlier versions. In particular, it was different from the method of move |
| 15 | generation in GNU Go 2.6. |
| 16 | |
| 17 | In the old scheme, various move generators suggested different moves with |
| 18 | attached values. The highest such value then decided the move. There were two |
| 19 | important drawbacks with this scheme: |
| 20 | |
| 21 | @itemize @bullet |
| 22 | @item |
| 23 | Efficient multipurpose moves could only be found by patterns which |
| 24 | explicitly looked for certain combinations, such as a simultaneous |
| 25 | connection and cut. There was also no good way to e.g. choose among |
| 26 | several attacking moves. |
| 27 | |
| 28 | @item |
| 29 | The absolute move values were increasingly becoming harder to tune with |
| 30 | the increasing number of patterns. They were also fairly subjective and |
| 31 | the tuning could easily break in unexpected ways when something changed, |
| 32 | e.g. the worm valuation. |
| 33 | @end itemize |
| 34 | |
| 35 | The basic idea of the new move generation scheme is that the various |
| 36 | move generators suggest reasons for moves, e.g. that a move captures |
| 37 | something or connects two strings, and so on. When all reasons for the |
| 38 | different moves have been found, the valuation starts. The primary |
| 39 | advantages are |
| 40 | |
| 41 | @itemize @bullet |
| 42 | @item |
| 43 | The move reasons are objective, in contrast to the move values in |
| 44 | the old scheme. Anyone can verify whether a suggested move reason is |
| 45 | correct. |
| 46 | |
| 47 | @item |
| 48 | The centralized move valuation makes tuning easier. It also allows |
| 49 | for style dependent tuning, e.g. how much to value influence |
| 50 | compared to territory. Another possibility is to increase the value |
| 51 | of safe moves in a winning position. |
| 52 | @end itemize |
| 53 | |
| 54 | |
| 55 | @node Move Reasons |
| 56 | @section Generation of move reasons |
| 57 | @cindex move reasons |
| 58 | |
| 59 | Each move generator suggests a number of moves. It justifies each move |
| 60 | suggestion with one or move @dfn{move reasons}. These move reasons |
| 61 | are collected at each intersection where the moves are suggested for |
| 62 | later valuation. Here is a partial list of of move reasons considered by GNU |
| 63 | Go. (The complete list may be found in @file{move_reasons.h}.) |
| 64 | |
| 65 | @table @code |
| 66 | @item ATTACK_MOVE |
| 67 | @itemx DEFEND_MOVE |
| 68 | Attack or defend a worm. |
| 69 | @item ATTACK_THREAT_MOVE |
| 70 | @itemx DEFEND_THREAT_MOVE |
| 71 | Threaten to attack or defend a worm. |
| 72 | @item EITHER_MOVE |
| 73 | A move that either achieves one goal or another (at the moment this only |
| 74 | used for attacks on worms). |
| 75 | @item ALL_MOVE |
| 76 | At the moment this is used for a move that defends two worms threatened |
| 77 | by a double attack. |
| 78 | @item CONNECT_MOVE |
| 79 | @itemx CUT_MOVE |
| 80 | Connect or cut two worms. |
| 81 | @item ANTISUJI_MOVE |
| 82 | Declare an antisuji or forbidden move. |
| 83 | @item SEMEAI_MOVE |
| 84 | @itemx SEMEAI_THREAT |
| 85 | Win or threaten to win a semeai. |
| 86 | @item EXPAND_TERRITORY_MOVE |
| 87 | @item EXPAND_MOYO_MOVE |
| 88 | Move expanding our territory/moyo. These reasons are at the moment |
| 89 | treated identically. |
| 90 | @item VITAL_EYE_MOVE |
| 91 | A vital point for life and death. |
| 92 | @item STRATEGIC_ATTACK_MOVE |
| 93 | @itemx STRATEGIC_DEFEND_MOVE |
| 94 | Moves added by 'a' and 'd' class patterns (@pxref{Pattern Classification}) |
| 95 | which (perhaps intangibly) attack or defend a dragon. |
| 96 | @item OWL_ATTACK_MOVE |
| 97 | @itemx OWL_DEFEND_MOVE |
| 98 | An owl attack or defense move. |
| 99 | @item OWL_ATTACK_THREAT |
| 100 | @itemx OWL_DEFEND_THREAT |
| 101 | A threat to owl attack or defend a group. |
| 102 | @item OWL_PREVENT_THREAT |
| 103 | A move to remove an owl threat. |
| 104 | @item UNCERTAIN_OWL_ATTACK |
| 105 | @itemx UNCERTAIN_OWL_DEFENSE |
| 106 | An uncertain owl attack or defense. This means that the owl code could |
| 107 | not decide the outcome, because the owl node limit was reached. |
| 108 | @item MY_ATARI_ATARI_MOVE |
| 109 | A move that starts a chain of ataris, eventually leading to a |
| 110 | capture. |
| 111 | @item YOUR_ATARI_ATARI_MOVE |
| 112 | A move that if played by the opponent starts a chain of ataris for the |
| 113 | opponent, leading to capture, which is also a safe move for us. Preemptively |
| 114 | playing such a move almost always defends the threat. |
| 115 | @end table |
| 116 | |
| 117 | The attack and defend move types can have a suffix to denote moves whose |
| 118 | result depends on a ko, e.g. @code{OWL_ATTACK_MOVE_GOOD_KO}. Here |
| 119 | @code{..._GOOD_KO} and @code{..._BAD_KO} correspond to @code{KO_A} and |
| 120 | @code{KO_B} as explained in @ref{Ko}. |
| 121 | See @file{engine/move_reasons.h} for the full of move reasons. |
| 122 | |
| 123 | @strong{NOTICE:} Some of these are reasons for @strong{not} playing a move. |
| 124 | |
| 125 | More detailed discussion of these move reasons will be found in the |
| 126 | next section. |
| 127 | |
| 128 | @node Move Reason Details |
| 129 | @section Detailed Descriptions of various Move Reasons |
| 130 | |
| 131 | @menu |
| 132 | * Attack and Defense:: Worm Attack and Defense |
| 133 | * Threats to Attack or Defend:: Worm Threats |
| 134 | * Multi Attack or Defense:: Combined Attacks and Defenses |
| 135 | * Cutting and Connecting:: Cutting and Connecting moves |
| 136 | * Semeai:: Semeai winning moves |
| 137 | * Making eyes:: Vital eye moves |
| 138 | * Antisuji moves:: Never play these! |
| 139 | * Territorial moves:: Block or expand territory |
| 140 | * Owl attack and defense:: Owl Attack and Defense |
| 141 | * Combination Attacks:: Coordinated threats such as double ataris |
| 142 | @end menu |
| 143 | |
| 144 | @node Attack and Defense |
| 145 | @subsection Attacking and defending moves |
| 146 | |
| 147 | A move which tactically captures a worm is called an @dfn{attack move} and a |
| 148 | move which saves a worm from being tactically captured is called a |
| 149 | @dfn{defense move}. It is understood that a defense move can only exist if |
| 150 | the worm can be captured, and that a worm without defense only is |
| 151 | attacked by moves that decrease the liberty count or perform necessary |
| 152 | backfilling. |
| 153 | |
| 154 | It is important that all moves which attack or defend a certain string |
| 155 | are found, so that the move generation can make an informed choice |
| 156 | about how to perform a capture, or find moves which capture and/or |
| 157 | defend several worms. |
| 158 | |
| 159 | Attacking and defending moves are first found in @code{make_worms} while it |
| 160 | evaluates the tactical status of all worms, although this step only |
| 161 | gives one attack and defense (if any) move per worm. Immediately |
| 162 | after, still in @code{make_worms}, all liberties of the attacked worms are |
| 163 | tested for additional attack and defense moves. More indirect moves |
| 164 | are found by @code{find_attack_patterns} and @code{find_defense_patterns}, |
| 165 | which match the A (attack) and D (defense) class patterns in |
| 166 | @file{patterns/attack.db} and @file{patterns/defense.db} As a final step, all |
| 167 | moves which fill some purpose at all are tested whether they additionally |
| 168 | attacks or defends some worm. (Only unstable worms are analyzed.) |
| 169 | |
| 170 | @node Threats to Attack or Defend |
| 171 | @subsection Threats to Attack or Defend |
| 172 | |
| 173 | A threat to attack a worm, but where the worm can be defended is used as |
| 174 | a secondary move reason. This move reason can enhance the value of a |
| 175 | move so that it becomes sente. A threatening move without any other |
| 176 | justification can also be used as a ko threat. The same is true for a |
| 177 | move that threatens defense of a worm, but where the worm can still be |
| 178 | captured if the attacker doesn't tenuki. |
| 179 | |
| 180 | Threats found by the owl code are called @strong{owl threats} and they |
| 181 | have their own owl reasons. |
| 182 | |
| 183 | @node Multi Attack or Defense |
| 184 | @subsection Multiple attack or defense moves |
| 185 | |
| 186 | Sometimes a move attacks at least one of a number of worms or |
| 187 | simultaneously defends all of several worms. These moves are noted |
| 188 | by their own move reasons. |
| 189 | |
| 190 | @node Cutting and Connecting |
| 191 | @subsection Cutting and connecting moves |
| 192 | |
| 193 | Moves which connect two distinct dragons are called @code{connecting moves}. |
| 194 | Moves which prevent such connections are called @dfn{cutting moves}. Cutting |
| 195 | and connecting moves are primarily found by pattern matching, the @code{C} |
| 196 | and @code{B} class patterns. |
| 197 | |
| 198 | A second source of cutting and connecting moves comes from the attack |
| 199 | and defense of cutting stones. A move which attacks a worm |
| 200 | automatically counts as a connecting move if there are multiple |
| 201 | dragons adjacent to the attacked worm. Similarly a defending move |
| 202 | counts as a cutting move. The action taken when a pattern of |
| 203 | this type is found is to induce a connect or cut move reason. |
| 204 | |
| 205 | When a cut or connect move reason is registered, the involved dragons |
| 206 | are of course stored. Thus the same move may cut and/or connect |
| 207 | several pairs of dragons. |
| 208 | |
| 209 | @node Semeai |
| 210 | @subsection Semeai winning moves |
| 211 | |
| 212 | A move which is necessary to win a capturing race is called a @dfn{semeai |
| 213 | move}. These are similar to attacking moves, except that they involve |
| 214 | the simultaneous attack of one worm and the defense of another. As for |
| 215 | attack and defense moves, it's important that all moves which win a |
| 216 | semeai are found, so an informed choice can be made between them. |
| 217 | |
| 218 | Semeai move reasons should be set by the semeai module. However this |
| 219 | has not been implemented yet. One might also wish to list moves |
| 220 | which increase the lead in a semeai race (removes ko threats) for use |
| 221 | as secondary move reasons. Analogously if we are behind in the race. |
| 222 | |
| 223 | @node Making eyes |
| 224 | @subsection Making or destroying eyes |
| 225 | |
| 226 | A move which makes a difference in the number of eyes produced from an |
| 227 | eye space is called an @dfn{eye move}. It's not necessary that the eye is |
| 228 | critical for the life and death of the dragon in question, although it |
| 229 | will be valued substantially higher if this is the case. As usual it's |
| 230 | important to find all moves that change the eye count. |
| 231 | |
| 232 | (This is part of what eye_finder was doing. Currently it only finds |
| 233 | one vital point for each unstable eye space.) |
| 234 | |
| 235 | @node Antisuji moves |
| 236 | @subsection Antisuji moves |
| 237 | |
| 238 | Moves which are locally inferior or for some other reason must not be |
| 239 | played are called @dfn{antisuji moves}. These moves are generated by pattern |
| 240 | matching. Care must be taken with this move reason as the move under |
| 241 | no circumstances will be played. |
| 242 | |
| 243 | @node Territorial moves |
| 244 | @subsection Territorial moves |
| 245 | |
| 246 | Any move that increases territory gets a move reason. This is the expand |
| 247 | territory move reason. That move reason is added by the @samp{e} |
| 248 | patterns in @file{patterns/patterns.db}. Similarly the @samp{E} patterns |
| 249 | attempt to generate or mitigate a moyo, which is a region of influence |
| 250 | not yet secure territory, yet valuable. Such a pattern sets the ``expand |
| 251 | moyo'' move reason. |
| 252 | |
| 253 | @node Owl attack and defense |
| 254 | @subsection Attacking and Defending Dragons |
| 255 | @findex owl_reasons |
| 256 | |
| 257 | Just as the tactical reading code tries to determine when a worm |
| 258 | can be attacked or defended, the owl code tries to determine |
| 259 | when a dragon can get two eyes and live. The function @code{owl_reasons()} |
| 260 | generates the corresponding move reasons. |
| 261 | |
| 262 | The owl attack and owl defense move reasons are self explanatory. |
| 263 | |
| 264 | The owl attack threat reason is generated if owl attack on an |
| 265 | opponent's dragon fails but the owl code determines that the |
| 266 | dragon can be killed with two consecutive moves. The killing |
| 267 | moves are stored in @code{dragon[pos].owl_attack_point} |
| 268 | and @code{dragon[pos].owl_second_attack_point}. |
| 269 | |
| 270 | Similarly if a friendly dragon is dead but two moves can revive it, |
| 271 | an owl defense threat move reason is generated. |
| 272 | |
| 273 | The prevent threat reasons are similar but with the colors |
| 274 | reversed: if the opponent has an attack threat move then a |
| 275 | move which removes the threat gets a prevent threat move |
| 276 | reason. |
| 277 | |
| 278 | The owl uncertain move reasons are generated when the owl |
| 279 | code runs out of nodes. In order to prevent the owl code from |
| 280 | running too long, a cap is put on the number of nodes one owl |
| 281 | read can generate. If this is exceeded, the reading is cut |
| 282 | short and the result is cached as usual, but marked uncertain. |
| 283 | In this case an owl uncertain move reason may be generated. |
| 284 | For example, if the owl code finds the dragon alive but is |
| 285 | unsure, a move to defend may still be generated. |
| 286 | |
| 287 | @node Combination Attacks |
| 288 | @subsection Combination Attacks |
| 289 | @findex atari_atari |
| 290 | |
| 291 | The function @code{atari_atari} tries to find a sequence of ataris |
| 292 | culminating in an unexpected change of status of any opponent string, |
| 293 | from @code{ALIVE} to @code{CRITICAL}. Once such a sequence of ataris |
| 294 | is found, it tries to shorten it by rejecting irrelevant moves. |
| 295 | |
| 296 | @node Valuation |
| 297 | @section Valuation of suggested moves |
| 298 | @findex value_move_reasons() |
| 299 | |
| 300 | At the end of the move generation process, the function |
| 301 | @code{value_move_reasons()} tries to assign values to the |
| 302 | moves for the purpose of selecting the best move. The |
| 303 | single purpose of the move valuation is to try to rank |
| 304 | the moves so that the best move gets the highest |
| 305 | score. In principle these values could be arbitrary, |
| 306 | but in order to make it easier to evaluate how well the |
| 307 | valuation performs, not to mention simplify the tuning, |
| 308 | we try to assign values which are consistent with the |
| 309 | usual methods of counting used by human Go players, |
| 310 | as explained for example in @emph{The Endgame} by Ogawa |
| 311 | and Davies. |
| 312 | |
| 313 | Moves are valued with respect to four different criteria. These are |
| 314 | |
| 315 | @itemize @bullet |
| 316 | @item territorial value |
| 317 | @item strategical value |
| 318 | @item shape value, |
| 319 | @item secondary value. |
| 320 | @end itemize |
| 321 | |
| 322 | All of these are floats and should be measured in terms of actual |
| 323 | points. |
| 324 | |
| 325 | The territorial value is the total change of expected territory caused |
| 326 | by this move. This includes changes in the status of groups if the move |
| 327 | is an attack or a defense move. |
| 328 | |
| 329 | Beginning with GNU Go 3.0, the influence function plays an important role |
| 330 | in estimating territory (@pxref{Influence and Territory}). It is used |
| 331 | to make a guess at each intersection how likely it is that it will become |
| 332 | black or white territory. The territorial value sums up the changes |
| 333 | in these valuations. |
| 334 | |
| 335 | Strategical value is a measure of the effect the move has on the |
| 336 | safety of all groups on the board. Typically cutting and connecting |
| 337 | moves have their main value here. Also edge extensions, enclosing |
| 338 | moves and moves towards the center have high strategical value. The |
| 339 | strategical value should be the sum of a fraction of the territorial |
| 340 | value of the involved dragons. The fraction is determined by the |
| 341 | change in safety of the dragon. |
| 342 | |
| 343 | Shape value is a purely local shape analysis. An |
| 344 | important role of this measure is to offset mistakes made by the |
| 345 | estimation of territorial values. In open positions it's |
| 346 | often worth sacrificing a few points of (apparent) immediate profit to |
| 347 | make good shape. Shape value is implemented by pattern matching, the |
| 348 | Shape patterns. |
| 349 | |
| 350 | Secondary value is given for move reasons which by themselves are not |
| 351 | sufficient to play the move. One example is to reduce the number of |
| 352 | eyes for a dragon that has several or to attack a defenseless worm. |
| 353 | |
| 354 | When all these values have been computed, they are summed, possibly |
| 355 | weighted (secondary value should definitely have a small weight), into |
| 356 | a final move value. This value is used to decide the move. |
| 357 | |
| 358 | @menu |
| 359 | * Territorial value:: How much territory does a move gain |
| 360 | * Strategical value:: Strategical gains from a move |
| 361 | * Shape factor:: Local shape |
| 362 | * Minimum Value:: Minimum value |
| 363 | * Secondary Value:: Other, more indirect, gains from a move |
| 364 | * Threats and Followup Value:: Valuation of attack and defense threats |
| 365 | @end menu |
| 366 | |
| 367 | @node Territorial value |
| 368 | @subsection Territorial Value |
| 369 | @findex estimate_territorial_value |
| 370 | |
| 371 | The algorithm for computing territorial value is in the function |
| 372 | @code{estimate_territorial_value}. As the name suggests, it seeks |
| 373 | to estimate the change in territory. |
| 374 | |
| 375 | It considers all groups that are changed from alive to death or vice-versa |
| 376 | due to this move. Also, it makes an assumption whether the move should be |
| 377 | considered safe. If so, the influence module is called: The function |
| 378 | @code{influence_delta_territory} estimates the territorial effect of |
| 379 | both the stone played and of the changes of group status'. |
| 380 | |
| 381 | The result returned by the influence module is subject to a number of |
| 382 | corrections. This is because some move reasons cannot be evaluated by a |
| 383 | single call to the influence function, such as moves depending on a ko. |
| 384 | |
| 385 | @node Strategical value |
| 386 | @subsection Strategical Value |
| 387 | |
| 388 | Strategical defense or attack reasons are assigned to any move |
| 389 | which matches a pattern of type @samp{a} or @samp{d}. These are |
| 390 | moves which in some (often intangible) way tend to help |
| 391 | strengthen or weaken a dragon. Of course strengthening a |
| 392 | dragon which is already alive should not be given much value, |
| 393 | but when the move reason is generated it is not necessary |
| 394 | to check its status or safety. This is done later, during |
| 395 | the valuation phase. |
| 396 | |
| 397 | @node Shape factor |
| 398 | @subsection Shape Factor |
| 399 | |
| 400 | In the value field of a pattern (@pxref{Pattern Values}) one may |
| 401 | specify a shape value. |
| 402 | |
| 403 | This is used to compute the shape factor, which multiplies the |
| 404 | score of a move. We take the largest positive contribution to |
| 405 | shape and add 1 for each additional positive contribution |
| 406 | found. Then we take the largest negative contribution to |
| 407 | shape, and add 1 for each additional negative contribution. The |
| 408 | resulting number is raised to the power 1.05 to obtain the |
| 409 | shape factor. |
| 410 | |
| 411 | The rationale behind this complicated scheme is that every |
| 412 | shape point is very significant. If two shape contributions |
| 413 | with values (say) 5 and 3 are found, the second contribution |
| 414 | should be devalued to 1. Otherwise the engine is too difficult |
| 415 | to tune since finding multiple contributions to shape can cause |
| 416 | significant overvaluing of a move. |
| 417 | |
| 418 | @node Minimum Value |
| 419 | @subsection Minimum Value |
| 420 | |
| 421 | A pattern may assign a minimum (and sometimes also a maximum) |
| 422 | value. For example the Joseki patterns have values which are |
| 423 | prescribed in this way, or ones with a @code{value} field. |
| 424 | One prefers not to use this approach but in practice it is |
| 425 | sometimes needed. |
| 426 | |
| 427 | In the fuseki, there are often several moves with identical minimum |
| 428 | value. GNU Go chooses randomly between such moves, which ensures |
| 429 | some indeterminacy of GNU Go's play. Later in the game, GNU Go's |
| 430 | genuine valuation of such a move is used as a secondary criterion. |
| 431 | |
| 432 | @node Secondary Value |
| 433 | @subsection Secondary Value |
| 434 | |
| 435 | Secondary move reasons are weighed very slightly. Such a move |
| 436 | can tip the scales if all other factors are equal. |
| 437 | |
| 438 | @node Threats and Followup Value |
| 439 | @subsection Threats and Followup Value |
| 440 | |
| 441 | Followup value refers to value which may acrue if we get two |
| 442 | moves in a row in a local area. It is assigned for moves that threaten |
| 443 | to attack or defend a worm or dragon. Also, since GNU Go 3.2 the influence |
| 444 | module makes an assessment of the possible purely territorial followup |
| 445 | moves. In cases where these two heuristics are not sufficient we |
| 446 | add patterns with a @code{followup_value} autohelper macro. |
| 447 | |
| 448 | Usually, the followup value gives only a small contribution; e.g. if |
| 449 | it the followup value is very large, then GNU Go treats the move as sente by |
| 450 | doubling its value. However, if the largest move on the board is a ko |
| 451 | which we cannot legally take, then such a move becomes attractive as a ko |
| 452 | threat and the full followup value is taken into account. |
| 453 | |
| 454 | @node End Game |
| 455 | @section End Game |
| 456 | |
| 457 | Endgame moves are generated just like any other move by GNU Go. In fact, |
| 458 | the concept of endgame does not exist explicitly, but if the largest |
| 459 | move initially found is worth 6 points or less, an extra set of patterns |
| 460 | in @file{endgame.db} is matched and the move valuation is redone. |