| [ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
6.1 Introduction 6.2 Generation of move reasons 6.3 Detailed Descriptions of various Move Reasons Detailed Descriptions of Move Reasons 6.4 Valuation of suggested moves Valuating the moves 6.5 End Game Endgame move generation
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:
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
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_THREAT_MOVE
DEFEND_THREAT_MOVE
EITHER_MOVE
ALL_MOVE
CONNECT_MOVE
CUT_MOVE
ANTISUJI_MOVE
SEMEAI_MOVE
SEMEAI_THREAT
EXPAND_TERRITORY_MOVE
EXPAND_MOYO_MOVE
VITAL_EYE_MOVE
STRATEGIC_ATTACK_MOVE
STRATEGIC_DEFEND_MOVE
OWL_ATTACK_MOVE
OWL_DEFEND_MOVE
OWL_ATTACK_THREAT
OWL_DEFEND_THREAT
OWL_PREVENT_THREAT
UNCERTAIN_OWL_ATTACK
UNCERTAIN_OWL_DEFENSE
MY_ATARI_ATARI_MOVE
YOUR_ATARI_ATARI_MOVE
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 11.4 Ko Handling.
See `engine/move_reasons.h' for the full of move reasons.
NOTE: 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.1 Attacking and defending moves Worm Attack and Defense 6.3.2 Threats to Attack or Defend Worm Threats 6.3.3 Multiple attack or defense moves Combined Attacks and Defenses 6.3.4 Cutting and connecting moves Cutting and Connecting moves 6.3.5 Semeai winning moves 6.3.6 Making or destroying eyes Vital eye moves 6.3.7 Antisuji moves Never play these! 6.3.8 Territorial moves Block or expand territory 6.3.9 Attacking and Defending Dragons Owl Attack and Defense 6.3.10 Combination Attacks Coordinated threats such as double ataris
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.)
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.
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.
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.
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.
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.)
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.
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.
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.
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.
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
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 13.4 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 How much territory does a move gain 6.4.2 Strategical Value Strategical gains from a move 6.4.3 Shape Factor Local shape 6.4.4 Minimum Value Minimum value 6.4.5 Secondary Value Other, more indirect, gains from a move 6.4.6 Threats and Followup Value Valuation of attack and defense threats
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.
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.
In the value field of a pattern (see section 9.3 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.
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.
Secondary move reasons are weighed very slightly. Such a move can tip the scales if all other factors are equal.
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.
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.
| [ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |