6. Move generation

6.1 Introduction

GNU Go 3.0 introduced a move generation scheme substantially different from earlier versions. In particular, it was different from the method of move generation in GNU Go 2.6.

In the old scheme, various move generators suggested different moves with attached values. The highest such value then decided the move. There were two important drawbacks with this scheme:

• Efficient multipurpose moves could only be found by patterns which explicitly looked for certain combinations, such as a simultaneous connection and cut. There was also no good way to e.g. choose among several attacking moves.
• The absolute move values were increasingly becoming harder to tune with the increasing number of patterns. They were also fairly subjective and the tuning could easily break in unexpected ways when something changed, e.g. the worm valuation.

The basic idea of the new move generation scheme is that the various move generators suggest reasons for moves, e.g. that a move captures something or connects two strings, and so on. When all reasons for the different moves have been found, the valuation starts. The primary advantages are

• The move reasons are objective, in contrast to the move values in the old scheme. Anyone can verify whether a suggested move reason is correct.
• The centralized move valuation makes tuning easier. It also allows for style dependent tuning, e.g. how much to value influence compared to territory. Another possibility is to increase the value of safe moves in a winning position.

6.2 Generation of move reasons

Each move generator suggests a number of moves. It justifies each move suggestion with one or move move reasons. These move reasons are collected at each intersection where the moves are suggested for later valuation. Here is a partial list of of move reasons considered by GNU Go. (The complete list may be found in ‘move_reasons.h’.)

ATTACK_MOVE

DEFEND_MOVE

Attack or defend a worm.

ATTACK_THREAT_MOVE

DEFEND_THREAT_MOVE

Threaten to attack or defend a worm.

EITHER_MOVE

A move that either achieves one goal or another (at the moment this only used for attacks on worms).

ALL_MOVE

At the moment this is used for a move that defends two worms threatened by a double attack.

CONNECT_MOVE

CUT_MOVE

Connect or cut two worms.

ANTISUJI_MOVE

Declare an antisuji or forbidden move.

SEMEAI_MOVE

SEMEAI_THREAT

Win or threaten to win a semeai.

EXPAND_TERRITORY_MOVE

EXPAND_MOYO_MOVE

Move expanding our territory/moyo. These reasons are at the moment treated identically.

VITAL_EYE_MOVE

A vital point for life and death.

STRATEGIC_ATTACK_MOVE

STRATEGIC_DEFEND_MOVE

Moves added by 'a' and 'd' class patterns (see section Pattern Attributes) which (perhaps intangibly) attack or defend a dragon.

OWL_ATTACK_MOVE

OWL_DEFEND_MOVE

An owl attack or defense move.

OWL_ATTACK_THREAT

OWL_DEFEND_THREAT

A threat to owl attack or defend a group.

OWL_PREVENT_THREAT

A move to remove an owl threat.

UNCERTAIN_OWL_ATTACK

UNCERTAIN_OWL_DEFENSE

An uncertain owl attack or defense. This means that the owl code could not decide the outcome, because the owl node limit was reached.

MY_ATARI_ATARI_MOVE

A move that starts a chain of ataris, eventually leading to a capture.

YOUR_ATARI_ATARI_MOVE

A move that if played by the opponent starts a chain of ataris for the opponent, leading to capture, which is also a safe move for us. Preemptively playing such a move almost always defends the threat.

The attack and defend move types can have a suffix to denote moves whose result depends on a ko, e.g. OWL_ATTACK_MOVE_GOOD_KO. Here ..._GOOD_KO and ..._BAD_KO correspond to KO_A and KO_B as explained in Ko Handling. See ‘engine/move_reasons.h’ for the full of move reasons.

NOTICE: Some of these are reasons for not playing a move.

More detailed discussion of these move reasons will be found in the next section.

6.3 Detailed Descriptions of various Move Reasons

6.3.1 Attacking and defending moves

A move which tactically captures a worm is called an attack move and a move which saves a worm from being tactically captured is called a defense move. It is understood that a defense move can only exist if the worm can be captured, and that a worm without defense only is attacked by moves that decrease the liberty count or perform necessary backfilling.

It is important that all moves which attack or defend a certain string are found, so that the move generation can make an informed choice about how to perform a capture, or find moves which capture and/or defend several worms.

Attacking and defending moves are first found in make_worms while it evaluates the tactical status of all worms, although this step only gives one attack and defense (if any) move per worm. Immediately after, still in make_worms, all liberties of the attacked worms are tested for additional attack and defense moves. More indirect moves are found by find_attack_patterns and find_defense_patterns, which match the A (attack) and D (defense) class patterns in ‘patterns/attack.db’ and ‘patterns/defense.db’ As a final step, all moves which fill some purpose at all are tested whether they additionally attacks or defends some worm. (Only unstable worms are analyzed.)

6.3.2 Threats to Attack or Defend

A threat to attack a worm, but where the worm can be defended is used as a secondary move reason. This move reason can enhance the value of a move so that it becomes sente. A threatening move without any other justification can also be used as a ko threat. The same is true for a move that threatens defense of a worm, but where the worm can still be captured if the attacker doesn't tenuki.

Threats found by the owl code are called owl threats and they have their own owl reasons.

6.3.3 Multiple attack or defense moves

Sometimes a move attacks at least one of a number of worms or simultaneously defends all of several worms. These moves are noted by their own move reasons.

6.3.4 Cutting and connecting moves

Moves which connect two distinct dragons are called connecting moves. Moves which prevent such connections are called cutting moves. Cutting and connecting moves are primarily found by pattern matching, the C and B class patterns.

A second source of cutting and connecting moves comes from the attack and defense of cutting stones. A move which attacks a worm automatically counts as a connecting move if there are multiple dragons adjacent to the attacked worm. Similarly a defending move counts as a cutting move. The action taken when a pattern of this type is found is to induce a connect or cut move reason.

When a cut or connect move reason is registered, the involved dragons are of course stored. Thus the same move may cut and/or connect several pairs of dragons.

6.3.5 Semeai winning moves

A move which is necessary to win a capturing race is called a semeai move. These are similar to attacking moves, except that they involve the simultaneous attack of one worm and the defense of another. As for attack and defense moves, it's important that all moves which win a semeai are found, so an informed choice can be made between them.

Semeai move reasons should be set by the semeai module. However this has not been implemented yet. One might also wish to list moves which increase the lead in a semeai race (removes ko threats) for use as secondary move reasons. Analogously if we are behind in the race.

6.3.6 Making or destroying eyes

A move which makes a difference in the number of eyes produced from an eye space is called an eye move. It's not necessary that the eye is critical for the life and death of the dragon in question, although it will be valued substantially higher if this is the case. As usual it's important to find all moves that change the eye count.

(This is part of what eye_finder was doing. Currently it only finds one vital point for each unstable eye space.)

6.3.7 Antisuji moves

Moves which are locally inferior or for some other reason must not be played are called antisuji moves. These moves are generated by pattern matching. Care must be taken with this move reason as the move under no circumstances will be played.

6.3.8 Territorial moves

Any move that increases territory gets a move reason. This is the expand territory move reason. That move reason is added by the ‘e’ patterns in ‘patterns/patterns.db’. Similarly the ‘E’ patterns attempt to generate or mitigate a moyo, which is a region of influence not yet secure territory, yet valuable. Such a pattern sets the “expand moyo” move reason.

6.3.9 Attacking and Defending Dragons

Just as the tactical reading code tries to determine when a worm can be attacked or defended, the owl code tries to determine when a dragon can get two eyes and live. The function owl_reasons() generates the corresponding move reasons.

The owl attack and owl defense move reasons are self explanatory.

The owl attack threat reason is generated if owl attack on an opponent's dragon fails but the owl code determines that the dragon can be killed with two consecutive moves. The killing moves are stored in dragon[pos].owl_attack_point and dragon[pos].owl_second_attack_point.

Similarly if a friendly dragon is dead but two moves can revive it, an owl defense threat move reason is generated.

The prevent threat reasons are similar but with the colors reversed: if the opponent has an attack threat move then a move which removes the threat gets a prevent threat move reason.

The owl uncertain move reasons are generated when the owl code runs out of nodes. In order to prevent the owl code from running too long, a cap is put on the number of nodes one owl read can generate. If this is exceeded, the reading is cut short and the result is cached as usual, but marked uncertain. In this case an owl uncertain move reason may be generated. For example, if the owl code finds the dragon alive but is unsure, a move to defend may still be generated.

6.3.10 Combination Attacks

The function atari_atari tries to find a sequence of ataris culminating in an unexpected change of status of any opponent string, from ALIVE to CRITICAL. Once such a sequence of ataris is found, it tries to shorten it by rejecting irrelevant moves.

6.4 Valuation of suggested moves

At the end of the move generation process, the function value_move_reasons() tries to assign values to the moves for the purpose of selecting the best move. The single purpose of the move valuation is to try to rank the moves so that the best move gets the highest score. In principle these values could be arbitrary, but in order to make it easier to evaluate how well the valuation performs, not to mention simplify the tuning, we try to assign values which are consistent with the usual methods of counting used by human Go players, as explained for example in The Endgame by Ogawa and Davies.

Moves are valued with respect to four different criteria. These are

• territorial value
• strategical value
• shape value,
• secondary value.

All of these are floats and should be measured in terms of actual points.

The territorial value is the total change of expected territory caused by this move. This includes changes in the status of groups if the move is an attack or a defense move.

Beginning with GNU Go 3.0, the influence function plays an important role in estimating territory (see section Influence and Territory). It is used to make a guess at each intersection how likely it is that it will become black or white territory. The territorial value sums up the changes in these valuations.

Strategical value is a measure of the effect the move has on the safety of all groups on the board. Typically cutting and connecting moves have their main value here. Also edge extensions, enclosing moves and moves towards the center have high strategical value. The strategical value should be the sum of a fraction of the territorial value of the involved dragons. The fraction is determined by the change in safety of the dragon.

Shape value is a purely local shape analysis. An important role of this measure is to offset mistakes made by the estimation of territorial values. In open positions it's often worth sacrificing a few points of (apparent) immediate profit to make good shape. Shape value is implemented by pattern matching, the Shape patterns.

Secondary value is given for move reasons which by themselves are not sufficient to play the move. One example is to reduce the number of eyes for a dragon that has several or to attack a defenseless worm.

When all these values have been computed, they are summed, possibly weighted (secondary value should definitely have a small weight), into a final move value. This value is used to decide the move.

6.4.1 Territorial Value

The algorithm for computing territorial value is in the function estimate_territorial_value. As the name suggests, it seeks to estimate the change in territory.

It considers all groups that are changed from alive to death or vice-versa due to this move. Also, it makes an assumption whether the move should be considered safe. If so, the influence module is called: The function influence_delta_territory estimates the territorial effect of both the stone played and of the changes of group status'.

The result returned by the influence module is subject to a number of corrections. This is because some move reasons cannot be evaluated by a single call to the influence function, such as moves depending on a ko.

6.4.2 Strategical Value

Strategical defense or attack reasons are assigned to any move which matches a pattern of type ‘a’ or ‘d’. These are moves which in some (often intangible) way tend to help strengthen or weaken a dragon. Of course strengthening a dragon which is already alive should not be given much value, but when the move reason is generated it is not necessary to check its status or safety. This is done later, during the valuation phase.

6.4.3 Shape Factor

In the value field of a pattern (see section Pattern Attributes) one may specify a shape value.

This is used to compute the shape factor, which multiplies the score of a move. We take the largest positive contribution to shape and add 1 for each additional positive contribution found. Then we take the largest negative contribution to shape, and add 1 for each additional negative contribution. The resulting number is raised to the power 1.05 to obtain the shape factor.

The rationale behind this complicated scheme is that every shape point is very significant. If two shape contributions with values (say) 5 and 3 are found, the second contribution should be devalued to 1. Otherwise the engine is too difficult to tune since finding multiple contributions to shape can cause significant overvaluing of a move.

6.4.4 Minimum Value

A pattern may assign a minimum (and sometimes also a maximum) value. For example the Joseki patterns have values which are prescribed in this way, or ones with a value field. One prefers not to use this approach but in practice it is sometimes needed.

In the fuseki, there are often several moves with identical minimum value. GNU Go chooses randomly between such moves, which ensures some indeterminacy of GNU Go's play. Later in the game, GNU Go's genuine valuation of such a move is used as a secondary criterion.

6.4.5 Secondary Value

Secondary move reasons are weighed very slightly. Such a move can tip the scales if all other factors are equal.

6.4.6 Threats and Followup Value

Followup value refers to value which may acrue if we get two moves in a row in a local area. It is assigned for moves that threaten to attack or defend a worm or dragon. Also, since GNU Go 3.2 the influence module makes an assessment of the possible purely territorial followup moves. In cases where these two heuristics are not sufficient we add patterns with a followup_value autohelper macro.

Usually, the followup value gives only a small contribution; e.g. if it the followup value is very large, then GNU Go treats the move as sente by doubling its value. However, if the largest move on the board is a ko which we cannot legally take, then such a move becomes attractive as a ko threat and the full followup value is taken into account.

6.5 End Game

Endgame moves are generated just like any other move by GNU Go. In fact, the concept of endgame does not exist explicitly, but if the largest move initially found is worth 6 points or less, an extra set of patterns in ‘endgame.db’ is matched and the move valuation is redone.

This document was generated by Daniel Bump on February, 19 2009 using texi2html 1.78.