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