[ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
9.1 Overview | Overview of the pattern database. | |
9.2 Pattern Attributes | The classification field | |
9.3 Pattern Attributes | The value field | |
9.4 Helper Functions | ||
9.5 Autohelpers and Constraints | Automatic generation of helper functions. | |
9.6 Autohelper Actions | ||
9.7 Autohelper Functions | ||
9.8 Attack and Defense Database | The Attack and defense moves database. | |
9.9 The Connections Database | The connection database. | |
9.10 Connections Functions | Functions in ‘connections.c’ | |
9.11 Tuning the Pattern databases | Tuning the pattern database. | |
9.12 Implementation | ||
9.13 Symmetry and transformations | ||
9.14 Implementation Details | Details of implementation. | |
9.15 The “Grid” Optimization | The “grid” optimization. | |
9.16 The Joseki Compiler | The joseki compiler. | |
9.17 Ladders in Joseki | Example: ladders in joseki. | |
9.18 Corner Matcher | A special matcher for joseki patterns. | |
9.19 Emacs Mode for Editing Patterns | Emacs major mode for pattern files. |
Several pattern databases are in the patterns directory. This chapter
primarily discusses the patterns in ‘patterns.db’, ‘patterns2.db’,
and the pattern files ‘hoshi.db’ etc. which are compiled from the SGF
files ‘hoshi.sgf’ (see section The Joseki Compiler). There is no essential
difference between these files, except that the ones in ‘patterns.db’ and
‘patterns2.db’ are hand written. They are concatenated before being
compiled by mkpat
into ‘patterns.c’. The purpose of the separate
file ‘patterns2.db’ is that it is handy to move patterns into a new
directory in the course of organizing them. The patterns in ‘patterns.db’
are more disorganized, and are slowly being moved to ‘patterns2.db’.
During the execution of genmove()
, the patterns are matched in
‘shapes.c’ in order to find move reasons.
The same basic pattern format is used by ‘attack.db’, ‘defense.db’, ‘conn.db’, ‘apats.db’ and ‘dpats.db’. However these patterns are used for different purposes. These databases are discussed in other parts of this documentation. The patterns in ‘eyes.db’ are entirely different and are documented elsewhere (see section Eyes and Half Eyes).
The patterns described in the databases are ascii representations, of the form:
Pattern EB112
?X?.? jump under O.*oo O.... o.... ----- :8,ed,NULL |
Here ‘O’ marks a friendly stone, ‘X’ marks an enemy stone, ‘.’ marks an empty vertex, ‘*’ marks O's next move, ‘o’ marks a square either containing ‘O’ or empty but not ‘X’. (The symbol ‘x’, which does not appear in this pattern, means ‘X’ or ‘.’.) Finally ‘?’ Indicates a location where we don't care what is there, except that it cannot be off the edge of the board.
The line of ‘-’'s along the bottom in this example is the edge of the board itself—this is an edge pattern. Corners can also be indicated. Elements are not generated for ‘?’ markers, but they are not completely ignored - see below.
The line beginning ‘:’ describes various attributes of the pattern, such as its symmetry and its class. Optionally, a function called a “helper” can be provided to assist the matcher in deciding whether to accept move. Most patterns do not require a helper, and this field is filled with NULL.
The matcher in ‘matchpat.c’ searches the board for places where this
layout appears on the board, and the callback function
shapes_callback()
in ‘shapes.c’ registers the appropriate move
reasons.
After the pattern, there is some supplementary information in the format:
:trfno, classification, [values], helper_function |
Here trfno represents the number of transformations of the pattern to consider, usually ‘8’ (no symmetry, for historical reasons), or one of ‘|’, ‘\’, ‘/’, ‘-’, ‘+’, ‘X’, where the line represents the axis of symmetry. (E.g. ‘|’ means symmetrical about a vertical axis.)
The above pattern could equally well be written on the left edge:
|oOO? |...X |..*? |..o. |..o? :8,ed,NULL |
The program mkpat
is capable of parsing patterns written this
way, or for that matter, on the top or right edges, or in any
of the four corners. As a matter of convention all the edge patterns
in ‘patterns.db’ are written on the bottom edge or in the lower left
corners. In the ‘patterns/’ directory there is a program called
transpat
which can rotate or otherwise transpose patterns.
This program is not built by default—if you think you need it,
make transpat
in the ‘patterns/’ directory and
consult the usage remarks at the beginning of ‘patterns/transpat.c’.
The attribute field in the ‘:’ line of a pattern consists of a sequence of zero or more of the following characters, each with a different meaning. The attributes may be roughly classified as constraints, which determine whether or not the pattern is matched, and actions, which describe what is to be done when the pattern is matched, typically to add a move reason.
Safety of the move is not checked. This is appropriate for sacrifice patterns. If this classification is omitted, the matcher requires that the stone played cannot be trivially captured. Even with s classification, a check for legality is made, though.
In addition to usual check that the stone played cannot be trivially captured, it is also confirmed that an opponent move here could not be captured.
It is checked that every friendly (‘O’) stone of the pattern belongs to a dragon which has status (see section Dragons)
ALIVE
orUNKNOWN
. TheCRITICAL
matcher status is excluded. It is possible for a string to haveALIVE
status and still be tactically critical, since it might be amalgamated into an ALIVE dragon, and the matcher status is constant on the dragon. Therefore, an additional test is performed: if the pattern contains a string which is tactically critical, and if ‘*’ does not rescue it, the pattern is rejected.
It is checked that every friendly (‘O’) stone of the pattern belongs to a dragon which is classified as
DEAD
orUNKNOWN
.
It is checked that every opponent (‘X’) stone of the pattern belongs to a dragon with status
ALIVE
,UNKNOWN
orCRITICAL
. Note that there is an asymmetry with ‘O’ patterns, whereCRITICAL
dragons are rejected.
It is checked that every opponent (‘X’) stone of the pattern belongs to a dragon which is classified as
DEAD
orUNKNOWN
If two or more distinct O dragons occur in the pattern, the move is given the move reasons that it connects each pair of dragons. An exception is made for dragons where the underlying worm can be tactically captured and is not defended by the considered move.
Add strategical defense move reason for all our dragons and a small shape bonus. This classification is appropriate for weak connection patterns.
If two or more distinct ‘X’ dragons occur in the pattern, the move is given the move reasons that it cuts each pair of dragons.
The move makes or secures territory.
The move attempts increase influence and create/expand a moyo.
The move strategically defends all O dragons in the pattern, except those that can be tactically captured and are not tactically defended by this move. If any O dragon should happen to be perfectly safe already, this only reflects in the move reason being valued to zero.
The move strategically attacks all ‘X’ dragons in the pattern.
Standard joseki move. Unless there is an urgent move on the board these moves are made as soon as they can be. This is equivalent to adding the ‘d’ and ‘a’ classifications together with a minimum accepted value of 27.
This indicates a fuseki pattern. This is only effective together with either the ‘j’ or ‘t’ classification, and is used to ensure indeterministic play during fuseki.
Slightly less urgent joseki move. These moves will be made after those with the ‘J’ classification. This adds the ‘e’ and ‘E’ classifications. If the move has the ‘F’ classification, it also gets a fixed value of 20.1, otherwise it gets a minimum accepted value of 20. (This makes sure that GNU Go chooses randomly between different moves that have ‘jF’ as classification.)
Minor joseki move (tenuki OK). This is equivalent to adding the ‘e’ and ‘E’ classifications together with either a fixed value of 15.07 (if the move has ‘F’ classification) or a minimum value of 15 (otherwise).
Urgent joseki move (never tenuki). This is equivalent to the ‘d’ and ‘a’ classifications together with a shape bonus of 15 and a minimum accepted value of 40.
A commonly used class is OX
(which rejects pattern if either side
has dead stones). The string ‘-’ may be used as a placeholder. (In
fact any characters other than the above and ‘,’ are ignored.)
The types ‘o’ and ‘O’ could conceivably appear in a class, meaning it
applies only to UNKNOWN
. ‘X’ and ‘x’ could similarly be used together.
All classes can be combined arbitrarily.
The second and following fields in the ‘:’ line of a pattern
are optional and of the form value1(x),value2(y),...
. The available set
of values are as follows.
terri(x)
Forces the territorial value of the move to be at least x.
minterri(x)
Forces the territorial value of the move to be at least x.
maxterri(x)
Forces the territorial value of the move to be at most x.
value(x)
Forces the final value of the move to be at least x.
minvalue(x)
, maxvalue(x)
Forces the final value of the move to be at least/most x.
shape(x)
Adds x to the move's shape value.
followup(x)
Adds x to the move's followup value.
The meaning of these values is documented in See section Move generation.
Helper functions can be provided to assist the matcher in deciding whether to accept a pattern, register move reasons, and setting various move values. The helper is supplied with the compiled pattern entry in the table, and the (absolute) position on the board of the ‘*’ point.
One difficulty is that the helper must be able to cope with all the possible transformations of the pattern. To help with this, the OFFSET macro is used to transform relative pattern coordinates to absolute board locations.
The actual helper functions are in ‘helpers.c’. They are declared in ‘patterns.h’.
As an example to show how to write a helper function, we consider
a hypothetical helper called wedge_helper
. Such a helper
used to exist, but has been replaced by a constraint. Due to
its simplicity it's still a good example. The helper begins with a
comment:
/* ?O. ?Ob .X* aX* ?O. ?Oc :8,C,wedge_helper */ |
The image on the left is the actual pattern. On the right we've taken
this image and added letters to label apos
, bpos
, and
cpos
. The position of *, the point where GNU Go will move if the
pattern is adopted, is passed through the parameter move
.
int wedge_helper(ARGS) { int apos, bpos, cpos; int other = OTHER_COLOR(color); int success = 0; apos = OFFSET(0, -2); bpos = OFFSET(-1, 0); cpos = OFFSET(1, 0); if (TRYMOVE(move, color)) { if (TRYMOVE(apos, other)) { if (board[apos] == EMPTY || attack(apos, NULL)) success = 1; else if (TRYMOVE(bpos, color)) { if (!safe_move(cpos, other)) success = 1; popgo(); } popgo(); } popgo(); } return success; } |
The OFFSET
lines tell GNU Go the positions of the three stones at
‘a’, ‘b’, and ‘c’. To decide whether the pattern
guarantees a connection, we do some reading. First we use the
TRYMOVE
macro to place an ‘O’ at ‘move’ and let
‘X’ draw back to ‘a’. Then we ask whether ‘O’ can capture
these stones by calling attack()
. The test if there is a stone at
‘a’ before calling attack()
is in this position not really
necessary but it's good practice to do so, because if the attacked stone
should happen to already have been captured while placing stones, GNU Go
would crash with an assertion failure.
If this attack fails we let ‘O’ connect at ‘b’ and use the
safe_move()
function to examine whether a cut by ‘X’ at
‘c’ could be immediately captured. Before we return the result we
need to remove the stones we placed from the reading stack. This is done
with the function popgo()
.
In addition to the hand-written helper functions in ‘helpers.c’, GNU Go can automatically generate helper functions from a diagram with labels and an expression describing a constraint. The constraint diagram, specifying the labels, is placed below the ‘:’ line and the constraint expression is placed below the diagram on line starting with a ‘;’. Constraints can only be used to accept or reject a pattern. If the constraint evaluates to zero (false) the pattern is rejected, otherwise it's accepted (still conditioned on passing all other tests of course). To give a simple example we consider a connection pattern.
Pattern Conn311 O*. ?XO :8,C,NULL O*a ?BO ;oplay_attack_either(*,a,a,B) |
Here we have given the label ‘a’ to the empty spot to the right of
the considered move and the label ‘B’ to the ‘X’ stone in the
pattern. In addition to these, ‘*’ can also be used as a label. A
label may be any lowercase or uppercase ascii letter except OoXxt
. By
convention we use uppercase letters for ‘X’ stones and lowercase for ‘O’
stones and empty intersections. When labeling a stone that's part of a
larger string in the pattern, all stones of the string should be marked
with the label. (These conventions are not enforced by the pattern
compiler, but to make the database consistent and easy to read they
should be followed.)
The labels can now be used in the constraint expression. In this example we have a reading constraint which should be interpreted as "Play an ‘O’ stone at ‘*’ followed by an ‘X’ stone at ‘a’. Accept the pattern if ‘O’ now can capture either at ‘a’ or at ‘B’ (or both strings)."
The functions that are available for use in the constraints are listed in the section `Autohelpers Functions' below. Technically the constraint expression is transformed by mkpat into an automatically generated helper function in ‘patterns.c’. The functions in the constraint are replaced by C expressions, often functions calls. In principle any valid C code can be used in the constraints, but there is in practice no reason to use anything more than boolean and arithmetic operators in addition to the autohelper functions. Constraints can span multiple lines, which are then concatenated.
As a complement to the constraints, which only can accept or reject a pattern, one can also specify an action to perform when the pattern has passed all tests and finally has been accepted.
Example:
Pattern EJ4 ...*. continuation .OOX. ..XOX ..... ----- :8,Ed,NULL ...*. never play a here .OOX. .aXOX ..... ----- >antisuji(a) |
The line starting with ‘>’ is the action line. In this case it tells the move generation that the move at a should not be considered, whatever move reasons are found by other patterns. The action line uses the labels from the constraint diagram. Both constraint and action can be used in the same pattern. If the action only needs to refer to ‘*’, no constraint diagram is required. Like constraints, actions can span multiple lines.
Here is a partial list of the autohelper macros which are typically called from action lines. This list is not complete. If you cannot find an autohelper macro in an action line in this list, consult ‘mkpat.c’ to find out what function in the engine is actually called. If no macro exists which does what you want, you can add macros by editing the list in ‘mkpat.c’.
antisuji(a);
Mark ‘a’ as an antisuji, that is, a move that must never be played.
replace(a,*)
This is appropriate if the move at ‘*’ is definitely better than the move at ‘a’. The macro adds a point redistribution rule. Any points which are assigned to ‘a’ during the move generation by any move reason are redistributed to ‘*’.
prevent_attack_threat(a)
Add a reverse followup value because the opponent's move here would threaten to capture ‘a’.
threaten_to_save(a)
Add a followup value because the move at ‘*’ threatens to rescue the dead string at ‘a’.
defend_against_atari(a)
Estimate the value of defending the string ‘a’ which can be put into atari and add this as a reverse followup value.
add_defend_both_move(a,b);
add_cut_move(c,d);
Add to the move reasons that the move at ‘*’ threatens to cut ‘c’ and ‘d’.
The autohelper functions are translated into C code by the program in ‘mkpat.c’. To see exactly how the functions are implemented, consult the autohelper function definitions in that file. Autohelper functions can be used in both constraint and action lines.
|
Number of first, second, third, and fourth order liberties of a worm respectively. See section Worms and Dragons, the documentation on worms for definitions.
|
The number of liberties that an enemy or own stone, respectively, would obtain if played at the empty intersection ‘x’.
|
Calls cut_possible
(see section General Utilities) to determine
whether ‘X’ or ‘O’ can cut at the empty intersection ‘x’.
|
True if ‘x’ is either a stone or an empty point involved in a ko position.
|
The matcher status of a dragon. status(x) returns an integer that can have the
values ALIVE
, UNKNOWN
, CRITICAL
, or DEAD
(see section Worms and Dragons).
|
Each function true if the dragon has the corresponding matcher status and false otherwise (see section Worms and Dragons).
|
Returns the status of the dragon at ‘x’ (see section Worms and Dragons).
|
The number of eyes of a dragon. It is only meaningful to compare this value against 0, 1, or 2.
|
These functions call whose_territory()
, whose_moyo()
and whose_area()
(see section Territory, Moyo and Area). For example
xarea(x)
evaluates to true if ‘x’ is either a living enemy stone
or an empty point within the opponent's “area”. The function oarea(x)
is analogous but with respect to our stones and area. The main difference
between area, moyo, and terri is that area is a very far reaching kind of
influence, moyo gives a more realistic estimate of what may turn in to
territory, and terri gives the points that already are believed to be secure
territory.
|
True for a dragon that is perceived as weak.
|
Results of tactical reading. attack(x)
is true if the worm can be
captured, defend(x)
is true if there also is a defending move. Please
notice that defend(x)
will return false if there is no attack on the
worm.
|
True if an enemy or friendly stone, respectively, can safely be played at ‘x’. By safe it is understood that the move is legal and that it cannot be captured right away.
|
True if an enemy or friendly stone, respectively, can legally be played at x.
o_somewhere(x,y,z, ...) x_somewhere(x,y,z, ...) |
True if O (respectively X) has a stone at one of the labelled vertices. In the diagram, these vertices should be marked with a ‘?’.
odefend_against(x,y) xdefend_against(x,y) |
True if an own stone at ‘x’ would stop the enemy from safely playing at ‘y’, and conversely for the second function.
|
True if a move at ‘x’ defends/attacks the worm at ‘y’. For defense a move of the same color as ‘y’ is tried and for attack a move of the opposite color.
|
These functions make it possible to do more complex reading experiments in the constraints. All of them work so that first the sequence of moves ‘a’,‘b’,‘c’,... is played through with alternating colors, starting with ‘X’ or ‘O’ as indicated by the name. Then it is tested whether the worm at ‘z’ can be attacked or defended, respectively. It doesn't matter who would be in turn to move, a worm of either color may be attacked or defended. For attacks the opposite color of the string being attacked starts moving and for defense the same color starts. The defend functions return true if the worm cannot be attacked in the position or if it can be attacked but also defended. The attack functions return true if there is a way to capture the worm, whether or not it can also be defended. If there is no stone present at ‘z’ after the moves have been played, it is assumed that an attack has already been successful or a defense has already failed. If some of the moves should happen to be illegal, typically because it would have been suicide, the following moves are played as if nothing has happened and the attack or defense is tested as usual. It is assumed that this convention will give the relevant result without requiring a lot of special cases.
The special label ‘?’ can be used to represent a tenuki.
Thus oplay_defend(a,?,b,c)
tries moves by ‘O’ at ‘a’ and
‘b’, as if ‘X’ plays the second move in another part of
the board, then asks if ‘c’ can be defended. The tenuki cannot
be the first move of the sequence, nor does it need to be:
instead of oplay_defend(?,a,b,c)
you can use
xplay_defend(a,b,c)
.
|
These functions are similar to the previous ones. The difference is that the last *two* arguments denote worms to be attacked or defended simultaneously. Obviously ‘y’ and ‘z’ must have the same color. If either location is empty, it is assumed that an attack has been successful or a defense has failed. The typical use for these functions is in cutting patterns, where it usually suffices to capture either cutstone.
The function xplay_defend_both
plays alternate moves
beginning with an ‘X’ at ‘a’. Then it passes the last
two arguments to defend_both
in
‘engine/utils.c’. This function checks to determine
whether the two strings can be simultaneously defended.
The function xplay_attack_either
plays alternate
moves beginning with an ‘X’ move at ‘a’. Then it passes
the last two arguments to attack_either
in
‘engine/utils.c’. This function looks for a move
which captures at least one of the two strings. In its
current implementation attack_either
only looks
for uncoordinated attacks and would thus miss a double
atari.
|
The function xplay_connect(a,b,c,...,y,z)
begins
with an ‘X’ move at ‘a’, then an ‘O’
move at ‘b’, and so forth, then finally calls
string_connect()
to determine whether
‘x’ and ‘y’ can be connected. The other
functions are similar (see section Connection Reading).
|
These functions are used to set up a position like
.O. .y. OXO xXz |
and ‘X’ aims at capturing at least one of ‘x’, ‘y’, and ‘z’. If this succeeds ‘1’ is returned. If it doesn't, ‘X’ tries instead to cut through on either side and if this succeeds, ‘2’ is returned. Of course the same shape with opposite colors can also be used.
Important notice: ‘x’, ‘y’, and ‘z’ must be given in the order they have in the diagram above, or any reflection and/or rotation of it.
seki_helper(x) |
Checks whether the string at ‘x’ can attack any surrounding string. If so, return false as the move to create a seki (probably) wouldn't work.
threaten_to_save(x) |
Calls add_followup_value
to add as a move reason a conservative
estimate of the value of saving the string ‘x’ by capturing one opponent
stone.
area_stone(x) |
Returns the number of stones in the area around ‘x’.
area_space(x) |
Returns the amount of space in the area around ‘x’.
|
True if ‘x’ is an eye space for either color, a non-marginal eye space for either color, or a marginal eye space for either color, respectively.
|
Tell the move generation that ‘x’ is a substandard move that never should be played.
same_dragon(x,y) same_worm(x,y) |
Return true if ‘x’ and ‘y’ are the same dragon or worm respectively.
|
Number of stones in the indicated dragon or worm.
|
Explicitly notify the move generation about move reasons for the move in the pattern.
|
Returns true if the empty intersection at ‘x’ is a half eye.
|
Inform the tactical reading that a supposed attack does in fact not work.
|
True if cutstone2
field from worm data is larger than one. This
indicates that saving the worm would introduce at least two new
cutting points.
|
Prevents the misreporting of ‘x’ as lunch for ‘y’. For example, the following pattern tells GNU Go that even though the stone at ‘a’ can be captured, it should not be considered “lunch” for the dragon at ‘b’, because capturing it does not produce an eye:
XO| ba| O*| O*| oo| oo| ?o| ?o| > not_lunch(a,b) |
|
Calls vital_chain
to determine whether capturing
the stone at ‘x’ will result in one eye for an adjacent
dragon. The current implementation just checks that the stone
is not a singleton on the first line.
|
Amalgamate (join) the dragons at ‘x’ and ‘y’ (see section Worms and Dragons).
|
Called when ‘x’, ‘y’, ‘z’ point to three (preferably distinct) dragons, in situations such as this:
.O.X X*OX .O.X |
In this situation, the opponent can play at ‘*’, preventing the three dragons from becoming connected. However ‘O’ can decide which cut to allow. The helper amalgamates the dragon at ‘y’ with either ‘x’ or ‘z’, whichever is largest.
make_proper_eye(x) |
This autohelper should be called when ‘x’ is an eyespace which is misidentified as marginal. It is reclassified as a proper eyespace (see section Eye spaces).
remove_halfeye(x) |
Remove a half eye from the eyespace. This helper should not be run after
make_dragons
is finished, since by that time the eyespaces have
already been analyzed.
remove_eyepoint(x) |
Remove an eye point. This function can only be used before the segmentation into eyespaces.
|
Here ‘x’ is an empty intersection which may be an eye or half eye for some dragon, and ‘y’ is a stone of the dragon, used only to determine the color of the eyespace in question. Returns the sum of the values of the diagonal intersections, relative to ‘x’, as explained in See section Topology of Half Eyes and False Eyes, equal to 4 or more if the eye at ‘x’ is false, 3 if it is a half eye, and 2 if it is a true eye.
|
Returns the escape value at ‘x’. This is only useful in owl attack and defense patterns.
The patterns in ‘attack.db’ and ‘defense.db’ are used to assist the
tactical reading in finding moves that attacks or defends worms. The
matching is performed during make_worms()
, at the time when the
tactical status of all worms is decided. None of the classes described
above are useful in these databases, instead we have two other
classes.
For each ‘O’ worm in the pattern that can be tactically captured
(worm[m][n].attack_code != 0
), the move at ‘*’ is
tried. If it is found to defend the stone, this is registered as a
reason for the move ‘*’ and the defense point of the worm is set to
‘*’.
For each ‘X’ worm in the pattern, it's tested whether the move at ‘*’ captures the worm. If that is the case, this is registered as a reason for the move at ‘*’. The attack point of the worm is set to ‘*’ and if it wasn't attacked before, a defense is searched for.
Furthermore, ‘A’ patterns can only be used in ‘attack.db’ and ‘D’ patterns only in ‘defense.db’. Unclassified patterns may appear in these databases, but then they must work through actions to be effective.
The patterns in ‘conn.db’ are used for helping make_dragons()
amalgamate worms into dragons and to some extent for modifying eye spaces.
The patterns in this database use the classifications ‘B’,
‘C’, and ‘e’. ‘B’ patterns are used for finding cutting points,
where amalgamation should not be performed, ‘C’ patterns are used for
finding existing connections, over which amalgamation is to be done, and
‘e’ patterns are used for modifying eye spaces and reevaluating lunches.
There are also some patterns without classification, which use action lines to
have an impact. These are matched together with the ‘C’ patterns. Further
details and examples can be found in See section Worms and Dragons.
We will illustrate these databases by example. In this situation:
XOO O.O ... |
‘X’ cannot play safely at the cutting point, so the ‘O’ dragons are to be amalgamated. Two patterns are matched here:
Pattern CC204 O . O :+,C O A O ;!safe_xmove(A) && !ko(A) && !xcut(A) Pattern CC205 XO O. :\,C AO OB ;attack(A) || (!safe_xmove(B) && !ko(B) && !xcut(B)) |
The constraints are mostly clear. For example the second
pattern should not be matched if the ‘X’ stone cannot
be attacked and ‘X’ can play safely at ‘B’, or
if ‘B’ is a ko. The constraint !xcut(B)
means
that connection has not previously been inhibited by
find_cuts
. For example consider this situation:
OOXX O.OX X..O X.OO |
The previous pattern is matched here twice, yet ‘X’ can push in and break one of the connections. To fix this, we include a pattern:
Pattern CB11 ?OX? O!OX ?*!O ??O? :8,B ?OA? OaOB ?*bO ??O? ; !attack(A) && !attack(B) && !xplay_attack(*,a,b,*) && !xplay_attack(*,b,a,*) |
After this pattern is found, the xcut
autohelper macro will return
true at any of the points ‘*’, ‘a’ and ‘b’. Thus the
patterns CB204
and CB205
will not be matched, and the dragons will
not be amalgamated.
Here are the public functions in ‘connections.c’.
static void cut_connect_callback(int m, int n, int color,
struct pattern *pattern, int ll, void *data)
Try to match all (permutations of) connection patterns at
(m,n)
. For each match, if it is a B pattern, set cutting point in worm data structure and make eye space marginal for the connection inhibiting entries of the pattern. If it is a ‘C’ pattern, amalgamate the dragons in the pattern.
void find_cuts(void)
Find cutting points which should inhibit amalgamations and sever the adjacent eye space. This goes through the connection database consulting only patterns of type B. When such a function is found, the function
cut_connect_callback
is invoked.
void find_connections(void)
Find explicit connection patterns and amalgamate the involved dragons. This goes through the connection database consulting patterns except those of type B, E or e. When such a function is found, the function
cut_connect_callback
is invoked.
Find explicit connection patterns and amalgamate the involved dragons. This goes through the connection database consulting only patterns of type E (see section The Connections Database). When such a function is found, the function
cut_connect_callback
is invoked.
Find explicit connection patterns and amalgamate the involved dragons. This goes through the connection database consulting only patterns of type e (see section The Connections Database). When such a function is found, the function
cut_connect_callback
is invoked.
Since the pattern databases, together with the valuation of move reasons, decide GNU Go's personality, much time can be devoted to “tuning” them. Here are some suggestions.
If you want to experiment with modifying the pattern database, invoke with the ‘-a’ option. This will cause every pattern to be evaluated, even when some of them may be skipped due to various optimizations.
You can obtain a Smart Game Format (SGF) record of your game in at least two different ways. One is to use CGoban to record the game. You can also have GNU Go record the game in Smart Game Format, using the ‘-o’ option. It is best to combine this with ‘-a’. Do not try to read the SGF file until the game is finished and you have closed the game window. This does not mean that you have to play the game out to its conclusion. You may close the CGoban window on the game and GNU Go will close the SGF file so that you can read it.
If you record a game in SGF form using the ‘-o’ option, GNU Go will add labels to the board to show all the moves it considered, with their values. This is an extremely useful feature, since one can see at a glance whether the right moves with appropriate weights are being proposed by the move generation.
First, due to a bug of unknown nature, it occasionally happens
that GNU Go will not receive the SIGTERM
signal from CGoban that it
needs to know that the game is over. When this happens, the SGF file
ends without a closing parenthesis, and CGoban will not open the
file. You can fix the file by typing:
echo ")" >>[filename] |
at the command line to add this closing parenthesis. Or you could add the ) using an editor.
Move values exceeding 99 (these should be rare) can be displayed by CGoban but you may have to resize the window in order to see all three digits. Grab the lower right margin of the CGoban window and pull it until the window is large. All three digits should be visible.
If you are playing a game without the ‘-o’ option and you wish to analyze a move, you may still use CGoban's “Save Game” button to get an SGF file. It will not have the values of the moves labelled, of course.
Once you have a game saved in SGF format, you can analyze any particular move by running:
gnugo -l [filename] -L [move number] -t -a -w |
to see why GNU Go made that move, and if you make changes to the pattern database and recompile the program, you may ask GNU Go to repeat the move to see how the behavior changes. If you're using emacs, it's a good idea to run GNU Go in a shell in a buffer (M-x shell) since this gives good navigation and search facilities.
Instead of a move number, you can also give a board coordinate to ‘-L’ in order to stop at the first move played at this location. If you omit the ‘-L’ option, the move after those in the file will be considered.
If a bad move is proposed, this can have several reasons. To begin with, each move should be valued in terms of actual points on the board, as accurately as can be expected by the program. If it's not, something is wrong. This may have two reasons. One possibility is that there are reasons missing for the move or that bogus reasons have been found. The other possibility is that the move reasons have been misevaluated by the move valuation functions. Tuning of patterns is with a few exceptions a question of fixing the first kind of problems.
If there are bogus move reasons found, search through the trace output for the pattern that is responsible. (Some move reasons, e.g. most tactical attack and defense, do not originate from patterns. If no pattern produced the bogus move reason, it is not a tuning problem.) Probably this pattern was too general or had a faulty constraint. Try to make it more specific or correct bugs if there were any. If the pattern and the constraint looks right, verify that the tactical reading evaluates the constraint correctly. If not, this is either a reading bug or a case where the reading is too complicated for GNU Go.
If a connecting move reason is found, but the strings are already effectively connected, there may be missing patterns in ‘conn.db’. Similarly, worms may be incorrectly amalgamated due to some too general or faulty pattern in ‘conn.db’. To get trace output from the matching of patterns in ‘conn.db’ you need to add a second ‘-t’ option.
If a move reason is missing, there may be a hole in the database. It could also be caused by some existing pattern being needlessly specific, having a faulty constraint, or being rejected due to a reading mistake. Unless you are familiar with the pattern databases, it may be hard to verify that there really is a pattern missing. Look around the databases to try to get a feeling for how they are organized. (This is admittedly a weak point of the pattern databases, but the goal is to make them more organized with time.) If you decide that a new pattern is needed, try to make it as general as possible, without allowing incorrect matches, by using proper classification from among snOoXx and constraints. The reading functions can be put to good use. The reason for making the patterns as general as they can be is that we need a smaller number of them then, which makes the database much easier to maintain. Of course, if you need too complicated constraints, it's usually better to split the pattern.
If a move has the correct set of reasons but still is misevaluated,
this is usually not a tuning problem. There are, however, some
possibilities to work around these mistakes with the use of patterns.
In particular, if the territorial value is off because delta_terri()
give strange results, the (min)terri and maxterri values can be set by
patterns as a workaround. This is typically done by the endgame
patterns, where we can know the (minimum) value fairly well from the
pattern. If it should be needed, (min)value and maxvalue can be used
similarly. These possibilities should be used conservatively though,
since such patterns are likely to become obsolete when better (or at
least different) functions for e.g. territory estimation are being
developed.
In order to choose between moves with the same move reasons, e.g. moves that connect two dragons in different ways, patterns with a nonzero shape value should be used. These should give positive shape values for moves that give good shape or good aji and negative values for bad shape and bad aji. Notice that these values are additive, so it's important that the matches are unique.
Sente moves are indicated by the use of the pattern followup value. This can usually not be estimated very accurately, but a good rule is to be rather conservative. As usual it should be measured in terms of actual points on the board. These values are also additive so the same care must be taken to avoid unintended multiple matches.
You can also get a visual display of the dragons using the ‘-T’ option. The default GNU Go configuration tries to build a version with color support using either curses or the ansi escape sequences. You are more likely to find color support in rxvt than xterm, at least on many systems, so we recommend running:
gnugo -l [filename] -L [move number] -T |
in an rxvt window. If you do not see a color display, and if your host is a GNU/Linux machine, try this again in the Linux console.
Worms belonging to the same dragon are labelled with the same letters.
The colors indicate the value of the field dragon.safety
, which
is set in ‘moyo.c’.
Green: GNU Go thinks the dragon is alive Yellow: Status unknown Blue: GNU Go thinks the dragon is dead Red: Status critical (1.5 eyes) or weak by the algorithm in ‘moyo.c’ |
If you want to get the same game over and over again, you can eliminate the randomness in GNU Go's play by providing a fixed random seed with the ‘-r’ option.
The pattern code in GNU Go is fairly straightforward conceptually, but because the matcher consumes a significant part of the time in choosing a move, the code is optimized for speed. Because of this there are implementation details which obscure things slightly.
In GNU Go, the ascii ‘.db’ files are precompiled into tables (see ‘patterns.h’) by a standalone program ‘mkpat.c’, and the resulting ‘.c’ files are compiled and linked into the main GNU Go executable.
Each pattern is compiled to a header, and a sequence of elements,
which are (notionally) checked sequentially at every position and
orientation of the board. These elements are relative to the pattern
'anchor' (or origin). One ‘X’ or ‘O’ stone is (arbitrarily) chosen to
represent the origin of the pattern. (We cannot dictate one or the
other since some patterns contain only one colour or the other.) All
the elements are in co-ordinates relative to this position. So a
pattern matches "at" board position (m,n,o)
if the the pattern anchor
stone is on (m,n)
, and the other elements match the board when the
pattern is transformed by transformation number ‘o’. (See below for
the details of the transformations, though these should not be
necessary)
In general, each pattern must be tried in each of 8 different permutations, to reflect the symmetry of the board. But some patterns have symmetries which mean that it is unnecessary (and therefore inefficient) to try all eight. The first character after the ‘:’ can be one of ‘8’,‘|’,‘\’,‘/’, ‘X’, ‘-’, ‘+’, representing the axes of symmetry. It can also be ‘O’, representing symmetry under 180 degrees rotation.
transformation I - | . \ l r / ABC GHI CBA IHG ADG CFI GDA IFC DEF DEF FED FED BEH BEH HEB HEB GHI ABC IHG CBA CFI ADG IFC GDA a b c d e f g h |
Then if the pattern has the following symmetries, the following are true:
| c=a, d=b, g=e, h=f - b=a, c=d, e=f, g=h \ e=a, g=b, f=c, h=d / h=a, f=b, g=c, e=d O a=d, b=c, e=h, f=g X a=d=e=h, b=c=f=g + a=b=c=d, e=f=g=h |
We can choose to use transformations a,d,f,g as the unique transformations for patterns with either ‘|’, ‘-’, ‘\’, or ‘/’ symmetry.
Thus we choose to order the transformations a,g,d,f,h,b,e,c and choose first 2 for ‘X’ and ‘+’, the first 4 for ‘|’, ‘-’, ‘/’, and ‘\’, the middle 4 for ‘O’, and all 8 for non-symmetrical patterns.
Each of the reflection operations (e-h) is equivalent to reflection about one arbitrary axis followed by one of the rotations (a-d). We can choose to reflect about the axis of symmetry (which causes no net change) and can therefore conclude that each of e-h is equivalent to the reflection (no-op) followed by a-d. This argument therefore extends to include ‘-’ and ‘/’ as well as ‘|’ and ‘\’.
"example" .OO???????????????? *XX???????????????? o?????????????????? :8,80 |
The comparisons between pattern and board are performed as 2-bit bitwise operations. Therefore they can be performed in parallel, 16-at-a-time on a 32-bit machine.
Suppose the board is layed out as follows :
.X.O....OO XXXXO..... .X..OOOOOO X.X....... ....X...O. |
which is internally stored internally in a 2d array (binary)
00 10 00 01 00 00 00 00 01 01 10 10 10 10 01 00 00 00 00 00 00 10 00 00 01 01 01 01 01 01 10 00 10 00 00 00 00 00 00 00 00 00 00 00 10 00 00 00 01 00 |
we can compile this to a composite array in which each element stores the state of a 4x4 grid of squares :
???????? ???????? ???????? ... ??001000 00100001 10000100 ??101010 10101010 10101001 ??001000 00100000 10000001 ??001000 00100001 ... ??101010 10101010 ??001000 00100000 ??001000 10001000 ... ??100010 ... ??000000 ???????? ???????? |
Where '??' is off the board.
We can store these 32-bit composites in a 2d merged-board array, substituting the illegal value %11 for '??'.
Similarly, for each pattern, mkpat produces appropriate 32-bit and-value masks for the pattern elements near the anchor. It is a simple matter to test the pattern with a similar test to (5) above, but for 32-bits at a time.
GNU Go includes a joseki compiler in ‘patterns/joseki.c’. This processes an SGF file (with variations) and produces a sequence of patterns which can then be fed back into mkpat. The joseki database is currently in files in ‘patterns/’ called ‘hoshi.sgf’, ‘komoku.sgf’, ‘sansan.sgf’, ‘mokuhazushi.sgf’ and ‘takamoku.sgf’. This division can be revised whenever need arises.
The SGF files are transformed into the pattern database ‘.db’ format by the program in ‘joseki.c’. These files are in turn transformed into C code by the program in ‘mkpat.c’ and the C files are compiled and linked into the GNU Go binary.
Not every node in the SGF file contributes a pattern. The nodes which contribute patterns have the joseki in the upper right corner, with the boundary marked with a square mark and other information to determine the resulting pattern marked in the comments.
The intention is that the move valuation should be able to choose between the available variations by normal valuation. When this fails the primary workaround is to use shape values to increase or decrease the value. It is also possible to add antisuji variations to forbid popular suboptimal moves. As usual constraints can be used, e.g. to condition a variation on a working ladder.
The joseki format has the following components for each SGF node:
SQ
or MA
property) to decide how large part of the
board should be included in the pattern.
LB
property), which must be a single letter each.
If there is at least one label, a constraint diagram will be
produced with these labels.
The rest of the line is ignored, as is the case of the letter. If neither of these is found, it's assumed to be a standard joseki move.
In addition to this, rows starting with the following characters are recognized:
Example: If the comment in the SGF file looks like
F :C,shape(3) ;xplay_attack(A,B,C,D,*) |
the generated pattern will have a colon line
:8,sjC,shape(3) |
and a constraint
;xplay_attack(A,B,C,D,*) |
As an example of how to use autohelpers with the Joseki compiler, we consider an example where a Joseki is bad if a ladder fails. Assume we have the taisha and are considering connecting on the outside with the pattern
--------+ ........| ........| ...XX...| ...OXO..| ...*O...| ....X...| ........| ........| |
But this is bad unless we have a ladder in our favor. To check this we add a constraint which may look like
--------+ ........| ........| ...XX...| ...OXO..| ...*OAC.| ....DB..| ........| ........| ;oplay_attack(*,A,B,C,D) |
In order to accept the pattern we require that the constraint on the semicolon line evaluates to true. This particular constraint has the interpretation "Play with alternating colors, starting with ‘O’, on the intersections ‘*’, ‘A’, ‘B’, and ‘C’. Then check whether the stone at ‘D’ can be captured." I.e. play to this position
--------+ ........| ........| ...XX...| ...OXO..| ...OOXX.| ....XO..| ........| ........| |
and call attack()
to see whether the lower ‘X’ stone can be
captured. This is not limited to ladders, but in this particular case the
reading will of course involve a ladder.
The constraint diagram above with letters is how it looks in the ‘.db’ file. The joseki compiler knows how to create these from labels in the SGF node. ‘Cgoban’ has an option to create one letter labels, but this ought to be a common feature for SGF editors.
Thus in order to implement this example in SGF, one would add labels to the four intersections and a comment:
;oplay_attack(*,A,B,C,D) |
The appropriate constraint (autohelper macro) will then be added to the Joseki ‘.db’ file.
GNU Go uses a special matcher for joseki patterns. It has certain constraints on the patterns it can match, but is much faster and takes far less space to store patterns than the standard matcher.
Patterns used with corner matcher have to qualify the following conditions:
shape(x)
. This is not because the matcher cannot handle other
values in principle, just they are currently not used in joseki databases.
Corner matcher was specifically designed for joseki patterns and they of course satisfy all the conditions above. With some modifications corner matcher could be used for fuseki patterns as well, but fullboard matcher does its work just fine.
The main idea of the matcher is very same to the one of DFA matcher (see section Pattern matching with DFA): check all available patterns at once, not a single pattern at a time. A modified version of DFA matcher could be used for joseki pattern matching, but its database would be very large. Corner matcher capitalizes on the fact that there are relatively few stones in each such pattern.
Corner pattern database is organized into a tree. Nodes of the tree are called “variations”. Variations represent certain sets of stones in a corner of the board. Root variation corresponds to an empty corner and a step down the tree is equivalent to adding a stone to the corner. Each variation has several properties:
By corner area we define a rectangle which corners are the current corner of the board and the position of the stone (inclusive). For instance, if the current board corner is A19 then corner area of a stone at C18 consists of A18, A19, B18, B19, C18 and C19.
Variation which is a direct child of the root variation matches if there is any stone at the variation position and the stone is alone in its corner area.
Variation at a deeper level of the tree matches if there is a stone of specified color in variation position and the number of stones in its corner area is equal to the number specified in variation structure.
When a certain variation matches, all its children has to be checked recursively for a match.
All leaf variations and some inner ones have patterns attached to them. For a pattern to match, it is required that its parent variation matches. In addition, it is checked that pattern is being matched for the appropriate color (using its variation “stone color” field) and that the number of stones in the area where the pattern is being matched is indeed equal to the number of stones in the pattern. The “stone position” property of the pattern variation determines the move suggested by the pattern.
Consider this joseki pattern which has four stones:
------+ ......| ......| .O*...| .XXO..| ......| ......| |
To encode it for the corner matcher, we have to use five variations, each next being a child of previous:
Tree level | Position | Color | Number of stones |
1 | R16 | “same” | 1 |
2 | P17 | “same” | 1 |
3 | Q16 | “other” | 2 |
4 | P16 | “other” | 4 |
5 | Q17 | “same” | 1 |
The fifth variation should have an attached pattern. Note that the stone color for the fifth variation is “same” because the first matched stone for this pattern is ‘O’ which stands for the stones of the player to whom moves are being suggested with ‘*’.
The tree consists of all variations for all patterns combined together. Variations for each patterns are sorted to allow very quick tree branch rejection and at the same time keep the database small enough. More details can be found in comments in file ‘mkpat.c’
Corner matcher resides in ‘matchpat.c’ in two functions:
corner_matchpat()
and do_corner_matchpat()
. The former computes
num_stones[]
array which holds number of stones in corner areas of
different intersections of the board for all possible transformations.
corner_matchpat()
also matches top-level variations.
do_corner_matchpat()
is responsible for recursive matching on the
variation tree and calling callback function upon pattern match.
Tree-like database for corner matcher is generated by mkpat
program.
Database generator consists of several functions, most important are:
corner_best_element()
, corner_variation_new()
,
corner_follow_variation()
and corner_add_pattern()
.
If you use GNU Emacs (XEmacs might work too), you can try a special mode for editing GNU Go pattern databases. The mode resides in ‘patterns/gnugo-db.el’.
Copy the file to ‘emacs/site-lisp’ directory. You can then load
the mode with (require 'gnugo-db)
. It makes sense to put this
line into your configuration file (‘~/.emacs’). You can either
use gnugo-db-mode
command to switch to pattern editing mode,
or use the following code snippet to make Emacs do this automatically
upon opening a file with ‘.db’ suffix:
(setq auto-mode-alist (append auto-mode-alist '(("\\.db\\'" . gnugo-db-mode)))) |
Pattern editing mode provides the following features:
Pattern
, goal_elements
and
callback_data
) and comments,
[ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This document was generated by Daniel Bump on February, 19 2009 using texi2html 1.78.