This is gnugo.info, produced by makeinfo version 4.11 from gnugo.texi.
INFO-DIR-SECTION GNU games
* GNU Go: (gnugo). The GNU Go program
File: gnugo.info, Node: The Owl Code, Next: Combinations, Up: Pattern Based Reading
The life and death code in `optics.c', described elsewhere (*note
Eyes::), works reasonably well as long as the position is in a
"terminal position", which we define to be one where there are no moves
left which can expand the eye space, or limit it. In situations where
the dragon is surrounded, yet has room to thrash around a bit making
eyes, a simple application of the graph-based analysis will not work.
Instead, a bit of reading is needed to reach a terminal position.
The defender tries to expand his eyespace, the attacker to limit it,
and when neither finds an effective move, the position is evaluated. We
call this type of life and death reading "Optics With
Limit-negotiation" (OWL). The module which implements it is in
There are two reasonably small databases
`patterns/owl_defendpats.db' and `patterns/owl_attackpats.db' of
expanding and limiting moves. The code in `owl.c' generates a small
move tree, allowing the attacker only moves from `owl_attackpats.db',
and the defender only moves from `owl_defendpats.db'. In addition to
the moves suggested by patterns, vital moves from the eye space
analysis are also tested.
A third database, `owl_vital_apats.db' includes patterns which
override the eyespace analysis done by the optics code. Since the
eyeshape graphs ignore the complications of shortage of liberties and
cutting points in the surrounding chains, the static analysis of
eyespace is sometimes wrong. The problem is when the optics code says
that a dragon definitely has 2 eyes, but it isn't true due to shortage
of liberties, so the ordinary owl patterns never get into play. In
such situations `owl_vital_apats.db' is the only available measure to
correct mistakes by the optics. Currently the patterns in
`owl_vital_apats.db' are only matched when the level is 9 or greater.
The owl code is tuned by editing these three pattern databases,
principally the first two.
A node of the move tree is considered `terminal' if no further moves
are found from `owl_attackpats.db' or `owl_defendpats.db', or if the
function `compute_eyes_pessimistic()' reports that the group is
definitely alive. At this point, the status of the group is evaluated.
The functions `owl_attack()' and `owl_defend()', with usage similar to
`attack()' and `find_defense()', make use of the owl pattern databases
to generate the move tree and decide the status of the group.
The function `compute_eyes_pessimistic()' used by the owl code is
very conservative and only feels certain about eyes if the eyespace is
completely closed (i.e. no marginal vertices).
The maximum number of moves tried at each node is limited by the
parameter `MAX_MOVES' defined at the beginning of `engine/owl.c'. The
most most valuable moves are tried first, with the following
* If `stackp > owl_branch_depth' then only one move is tried per
* If `stackp > owl_reading_depth' then the reading terminates, and
the situation is declared a win for the defender (since deep
reading may be a sign of escape).
* If the node count exceeds `owl_node_limit', the reading also
terminates with a win for the defender.
* Any pattern with value 99 is considered a forced move: no other
move is tried, and if two such moves are found, the function
returns false. This is only relevant for the attacker.
* Any pattern in `patterns/owl_attackpats.db' and
`patterns/owl_defendpats.db' with value 100 is considered a win: if
such a pattern is found by `owl_attack' or `owl_defend', the
function returns true. This feature must be used most carefully.
The functions `owl_attack()' and `owl_defend()' may, like `attack()'
and `find_defense()', return an attacking or defending move through
their pointer arguments. If the position is already won, `owl_attack()'
may or may not return an attacking move. If it finds no move of
interest, it will return `PASS', that is, `0'. The same goes for
When `owl_attack()' or `owl_defend()' is called, the dragon under
attack is marked in the array `goal'. The stones of the dragon
originally on the board are marked with goal=1; those added by
`owl_defend()' are marked with goal=2. If all the original strings of
the original dragon are captured, `owl_attack()' considers the dragon
to be defeated, even if some stones added later can make a live group.
Only dragons with small escape route are studied when the functions
are called from `make_dragons()'.
The owl code can be conveniently tested using the `--decide-owl
LOCATION' option. This should be used with `-t' to produce a useful
trace, `-o' to produce an SGF file of variations produced when the life
and death of the dragon at LOCATION is checked, or both.
`--decide-position' performs the same analysis for all dragons with
File: gnugo.info, Node: Combinations, Prev: The Owl Code, Up: Pattern Based Reading
It may happen that no single one of a set of worms can be killed, yet
there is a move that guarantees that at least one can be captured. The
simplest example is a double atari. The purpose of the code in
`combination.c' is to find such moves.
For example, consider the following situation:
Every `X' stone in this position is alive. However the move at `*'
produces a position in which at least one of four strings will get
captured. This is a _combination_.
The driving function is called `atari_atari' because typically a
combination involves a sequence of ataris culminating in a capture,
though sometimes the moves involved are not ataris. For example in the
above example, the first move at `*' is _not_ an atari, though after
`O' defends the four stones above, a sequence of ataris ensues
resulting in the capture of some string.
Like the owl functions `atari_atari' does pattern-based reading. The
database generating the attacking moves is `aa_attackpats.db'. One
danger with this function is that the first atari tried might be
irrelevant to the actual combination. To detect this possibility, once
we've found a combination, we mark that first move as forbidden, then
try again. If no combination of the same size or larger turns up, then
the first move was indeed essential.
* `void combinations(int color)'
Generate move reasons for combination attacks and defenses
against them. This is one of the move generators called from
* `int atari_atari(int color, int *attack_move, char
defense_moves[BOARDMAX], int save_verbose)'
Look for a combination for `color'. For the purpose of the
move generation, returns the size of the smallest of the
* `int atari_atari_confirm_safety(int color, int move, int *defense,
int minsize, const char saved_dragons[BOARDMAX], const char
Tries to determine whether a move is a blunder. Wrapper
around atari_atari_blunder_size. Check whether a combination
attack of size at least `minsize' appears after move at
`move' has been made. The arrays `saved_dragons[]' and
`saved_worms[]' should be one for stones belonging to dragons
or worms respectively, which are supposedly saved by `move'.
* `int atari_atari_blunder_size(int color, int move, int *defense,
const char safe_stones[BOARDMAX])'
This function checks whether any new combination attack
appears after move at (move) has been made, and returns its
size (in points). `safe_stones' marks which of our stones
are supposedly safe after this move.
File: gnugo.info, Node: Influence, Next: Monte Carlo Go, Prev: Pattern Based Reading, Up: Top
* Influential Concepts:: Conceptual Outline of Influence
* Territory and Moyo:: Territory, Moyo and Area
* Influence Usage:: Where influence gets used in the engine
* Influence and Territory:: Influence and Territory
* Territorial Details:: Details of the Territory Valuation
* The Influence Core:: The Core of the Influence Function
* The Influence Algorithm:: The algorithm of `accumlate_influence()'
* Permeability:: Permeability
* Surrounded Dragons:: Surrounded Dragons
* Influential Patterns:: Patterns used by the Influence module
* Influential Display:: Colored display and debugging of influence
* Influence Tuning:: Influence tuning with view.pike
File: gnugo.info, Node: Influential Concepts, Next: Territory and Moyo, Up: Influence
13.1 Conceptual Outline of Influence
====================================
We define call stones "lively" if they cannot be tactically attacked,
or if they have a tactical defense and belong to the player whose turn
it is. Similarly, stones that cannot be strategically attacked (in the
sense of the life-and-death analysis), or that have a strategical
defense and belong to the player to move, are called "alive". If we
want to use the influence function before deciding the strategical
status, all lively stones count as alive.
Every alive stone on the board works as an influence source, with
influence of its color radiating outwards in all directions. The
strength of the influence declines exponentially with the distance from
Influence can only flow unhindered if the board is empty, however.
All lively stones (regardless of color) act as influence barriers, as do
connections between enemy stones that can't be broken through. For
example the one space jump counts as a barrier unless either of the
stones can be captured. Notice that it doesn't matter much if the
connection between the two stones can be broken, since in that case
there would come influence from both directions anyway.
From the influence of both colors we compute a territorial value
between -1.0 and +1.0 for each intersection, which can be seen as the
likely hood of it becoming territory for either color.
In order to avoid finding bogus territory, we add extra influence
sources at places where an invasion can be launched, e.g. at 3-3 under
a handicap stone, in the middle of wide edge extensions and in the
center of large open spaces anywhere. Similarly we add extra influence
sources where intrusions can be made into what otherwise looks as solid
territory, e.g. monkey jumps. These intrusions depend on whose turn we
All these extra influence sources, as well as connections, are
controlled by a pattern database, which consists of the two files
patterns/influence.db and patterns/barriers.db. The details are
explained in *note Influential Patterns::.
File: gnugo.info, Node: Territory and Moyo, Next: Influence Usage, Prev: Influential Concepts, Up: Influence
13.2 Territory, Moyo and Area
=============================
Using the influence code, empty regions of the board are partitioned in
three ways. A vertex may be described as White or Black's "territory",
"moyo" or "area". The functions `whose_territory()', `whose_moyo()' and
`whose_area()' will return a color, or EMPTY if it belongs to one
player or the other in one of these classifications.
Those parts of the board which are expected to materialize as
actual points for one player or the other at the end of the
game are considered "territory".
Those parts of the board which are either already territory
or more generally places where a territory can easily
materialize if the opponent neglects to reduce are considered
Those parts of the board where one player or the other has a
stronger influence than his opponent are considered "area".
Generally territory is moyo and moyo is area. To get a feeling for
these concepts, load an sgf file in a middle game position with the
option `-m 0x0180' and examine the resulting diagrams (*note
File: gnugo.info, Node: Influence Usage, Next: Influence and Territory, Prev: Territory and Moyo, Up: Influence
13.3 Where influence gets used in the engine
============================================
The information obtained from the influence computation is used in a
variety of places in the engine, and the influence module is called
several times in the process of the move generation. The details of the
influence computation vary according to the needs of the calling
After GNU Go has decided about the tactical stability of strings, the
influence module gets called the first time. Here all lively stones act
as an influence source of default strength 100. The result is stored in
the variables `initial_influence' and `initial_opposite_influence', and
it is used as an important information for guessing the strength of
dragons. For example, a dragon that is part of a moyo of size 25 is
immediately considered alive. For dragons with a smaller moyo size, a
life-and-death analysis will be done by the owl code (see *note Pattern
Based Reading::). A dragon with a moyo size of only 5 will be
considered weak, even if the owl code has decided that it cannot be
As a tool for both the owl code and the strength estimate of dragons,
an "escape" influence gets computed for each dragon (*note Escape::).
Once all dragons have been evaluated, the influence module is called
again and the variables `initial_influence' and
`initial_opposite_influence' get overwritten. Of course, the dragon
status', which are available now, are taken into account. Stones
belonging to a dead dragon will not serve as an influence source, and
the strengths of other stones get adjusted according to the strength of
The result of this run is the most important tool for move
evaluation. All helper functions of patterns as explained in *note
Patterns:: that refer to influence results (e. g. `olib(*)' etc.)
actually use these results. Further, `initial_influence' serves as the
reference for computing the territorial value of a move. That is, from
the influence strengths stored in `initial_influence', a territory
value is assigned to each intersection. This value is supposed to
estimate the likelyhood that this intersection will become white or
Then, for each move that gets considered in the function
`value_moves', the influence module is called again via the function
`compute_move_influence' to assess the likely territorial balance after
this move, and the result is compared with the state before that move.
An additional influence computation is done in order to compute the
followup value of a move. Some explainations are in *note Territorial
Some of the public functions from `influence.c' which are used
throughout the engine are listed in *note Influence Utilities::.
File: gnugo.info, Node: Influence and Territory, Next: Territorial Details, Prev: Influence Usage, Up: Influence
13.4 Influence and Territory
============================
In this section we consider how the influence function is used to
estimate territory in the function `estimate_territorial_value()'.
A move like `*' by `O' below is worth one point:
This is evaluated by the influence function in the following way: We
first assign territory under the assumption that X moves first in all
local positions in the original position; then we reassing territory,
again under the assumption that `X' moves first in all local positions,
but after we let `O' make the move at `*'. These two territory
assignments are compared and the difference gives the territorial value
Technically, the assumption that `X' plays first everywhere is
implemented via an asymmetric pattern database in `barriers.db'. What
exactly is a safe connection that stops hostile influence from passing
through is different for `O' and `X'; of course such a connection has
to be tighter for stones with color `O'. Also, additional intrusion
influence sources are added for `X' in places where `X' stones have
In this specific example above, the asymmetry (before any move has
been made) would turn out as follows: If `X' is in turn to move, the
white influence would get stopped by a barrier at `*', leaving 4 points
of territory for `X'. However, if `O' was next to move, then a
followup move for the white stones at the left would be assumed in the
form of an extra ("intrusion") influence source at `*'. This would get
stopped at `a', leaving three points of territory.
Returning to the valuation of a move by `O' at `*', we get a value
of 1 for the move at `*'. However, of course this move is sente once
it is worth playing, and should therefore (in miai counting) be awarded
an effective value of 2. Hence we need to recognize the followup value
of a move. GNU Go 3.0 took care of this by using patterns in
`patterns.db' that enforced an explicit followup value. Versions from
3.2 on instead compute a seperate followup influence to each move
considered. In the above example, an intrusion source will be added at
`a' as a followup move to `*'. This destroys all of Black's territory
and hence gives a followup value of 3.
The pattern based followup value are still needed at some places,
To give another example, consider this position where we want to
estimate the value of an `O' move at `*':
Before the move we assume `X' moves first in the local position (and
that `O' has to connect), which gives territory like this (lower case
letter identify territory for each player):
Then we let `O' make the move at `*' and assume `X' moves first
again next. The territory then becomes (`X' is also assumed to have to
We see that this makes a difference in territory of 4, which is what
influence_delta_territory() should report. Then again, we have followup
value, and here also a reverse followup value. The reverse followup
value, which in this case will be so high that the move is treated as
reverse sente, is added by an explicit pattern. Other sources for
followup or reverse followup values are threats to capture a rescue a
string of stones. See the code and comments in the function
`value_move_reaons' for how followup and reverse followup values are
used to adjust the effective move value.
To give an example of territorial value where something is captured,
consider the `O' move at `*' here,
As before we first let the influence function determine territory
assuming X moves first, i.e. with a captured group:
Here `y' indicates `X' territory + captured stone, i.e. these count
for two points. After the `O' move at `*' we instead get
and we see that `X' has 16 territory fewer and `O' has two territory
more, for a total difference of 18 points.
That the influence function counts the value of captured stones was
introduced in GNU Go 3.2. Previously this was instead done using the
effective_size heuristic. The effective size is the number of stones
plus the surrounding empty spaces which are closer to this string or
dragon than to any other stones. Here the `O' string would thus have
effective size 6 (number of stones) + 2 (interior eye) + 2*0.5 (the two
empty vertices to the left of the string, split half each with the
surrounding X string) + 1*0.33 (the connection point, split between
three strings) = 9.33. As noted this value was doubled, giving 18.67
which is reasonably close to the correct value of 18. The effective size
heuristic is still used in certain parts of the move valuation where we
can't easily get a more accurate value from the influence function (e.
g. attacks depending on a ko, attack threats).
Note that this section only describes the territorial valuation of a
move. Apart from that, GNU Go uses various heuristics in assigning a
strategical value (weakening and strengthening of other stones on the
board) to a move. Also, the influence function isn't quite as well
tuned as the examples above may seem to claim. But it should give a
fairly good idea of how the design is intended.
Another matter is that so far we have only considered the change in
secure territory. GNU Go 3.2 and later versions use a revised
heuristic, which is explained in the next section, to assign probable
territory to each player.
projects / sgk-go / blob