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