[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9. The Pattern Code

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.
[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.1 Overview

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’.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.2 Pattern Attributes

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.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.2.1 Constraint Pattern Attributes

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.2.2 Action Attributes

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.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.3 Pattern Attributes

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.

The meaning of these values is documented in See section Move generation.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.4 Helper Functions

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().

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.5 Autohelpers and Constraints

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.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.6 Autohelper Actions

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’.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.7 Autohelper Functions

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.

 
lib(x)
lib2(x)
lib3(x)
lib4(x)

Number of first, second, third, and fourth order liberties of a worm respectively. See section Worms and Dragons, the documentation on worms for definitions.

 
xlib(x)
olib(x)

The number of liberties that an enemy or own stone, respectively, would obtain if played at the empty intersection ‘x’.

 
xcut(x)
ocut(x)

Calls cut_possible (see section General Utilities) to determine whether ‘X’ or ‘O’ can cut at the empty intersection ‘x’.

 
ko(x)

True if ‘x’ is either a stone or an empty point involved in a ko position.

 
status(x)

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).

 
alive(x)
unknown(x)
critical(x)
dead(x)

Each function true if the dragon has the corresponding matcher status and false otherwise (see section Worms and Dragons).

 
status(x)

Returns the status of the dragon at ‘x’ (see section Worms and Dragons).

 
genus(x)

The number of eyes of a dragon. It is only meaningful to compare this value against 0, 1, or 2.

 
xarea(x)
oarea(x)
xmoyo(x)
omoyo(x)
xterri(x)
oterri(x)

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.

 
weak(x)

True for a dragon that is perceived as weak.

 
attack(x)
defend(x)

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.

 
safe_xmove(x)
safe_omove(x)

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.

 
legal_xmove(x)
legal_omove(x)

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.

 
does_defend(x,y)
does_attack(x,y)

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.

 
xplay_defend(a,b,c,...,z)
oplay_defend(a,b,c,...,z)
xplay_attack(a,b,c,...,z)
oplay_attack(a,b,c,...,z)

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).

 
xplay_defend_both(a,b,c,...,y,z)
oplay_defend_both(a,b,c,...,y,z)
xplay_attack_either(a,b,c,...,y,z)
oplay_attack_either(a,b,c,...,y,z)

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.

 
xplay_connect(a,b,c,...,y,z)
oplay_connect(a,b,c,...,y,z)
xplay_disconnect(a,b,c,...,y,z)
oplay_disconnect(a,b,c,...,y,z)

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).

 
xplay_break_through(a,b,c,...,x,y,z)
oplay_break_through(a,b,c,...,x,y,z)

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’.

 
eye(x)
proper_eye(x)
marginal_eye(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.

 
antisuji(x)

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.

 
dragonsize(x)
wormsize(x)

Number of stones in the indicated dragon or worm.

 
add_connect_move(x,y)
add_cut_move(x,y)
add_attack_either_move(x,y)
add_defend_both_move(x,y)

Explicitly notify the move generation about move reasons for the move in the pattern.

 
halfeye(x)

Returns true if the empty intersection at ‘x’ is a half eye.

 
remove_attack(x)

Inform the tactical reading that a supposed attack does in fact not work.

 
potential_cutstone(x)

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.

 
not_lunch(x,y)

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)
 
vital_chain(x)

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(x,y)

Amalgamate (join) the dragons at ‘x’ and ‘y’ (see section Worms and Dragons).

 
amalgamate_most_valuable(x,y,z)

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.

 
owl_topological_eye(x,y)

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.

 
owl_escape_value(x)

Returns the escape value at ‘x’. This is only useful in owl attack and defense patterns.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.8 Attack and Defense Database

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.

‘D’

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 ‘*’.

‘A’

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.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.9 The Connections Database

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.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.10 Connections Functions

Here are the public functions in ‘connections.c’.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.11 Tuning the Pattern databases

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.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.12 Implementation

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)

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.13 Symmetry and transformations

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 ‘\’.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.14 Implementation Details

  1. An entry in the pattern header states whether the anchor is an ‘X’ or an ‘O’. This helps performance, since all transformations can be rejected at once if the anchor stone does not match. (Ideally, we could just define that the anchor is always ‘O’ or always ‘X’, but some patterns contain no ‘O’ and some contain no ‘X’.)
  2. The pattern header contains the size of the pattern (ie the co-ordinates of the top left and bottom right elements) relative to the anchor. This allows the pattern can be rejected quickly if there is not room for the pattern to fit around the anchor stone in a given orientation (ie it is too near the edge of the board). The bounding box information must first be transformed like the elements before it can be tested, and after transforming, we need to work out where the top-left and bottom-right corners are.
  3. The edge constraints are implemented by notionally padding the pattern with rows or columns of ‘?’ until it is exactly 19 (or whatever the current board size is) elements wide or high. Then the pattern is quickly rejected by (ii) above if it is not at the edge. So the example pattern above is compiled as if it was written
     
    "example"
.OO????????????????
*XX????????????????
o??????????????????
:8,80
  4. The elements in a pattern are sorted so that non-space elements are checked before space elements. It is hoped that, for most of the game, more squares are empty, and so the pattern can be more quickly rejected doing it this way.
  5. The actual tests are performed using an ’and-compare’ sequence. Each board position is a 2-bit quantity. %00 for empty, %01 for ‘O’, %10 for ‘X’. We can test for an exact match by and-ing with %11 (no-op), then comparing with 0, 1 or 2. The test for ‘o’ is the same as a test for ’not-X’, ie not %10. So and with %01 should give 0 if it matches. Similarly ‘x’ is a test that bit 0 is not set.
[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.15 The “Grid” Optimization

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.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.16 The Joseki Compiler

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:

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,*)
[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.17 Ladders in Joseki

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.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.18 Corner Matcher

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:

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 levelPositionColorNumber of stones
1R16“same”1
2P17“same”1
3Q16“other”2
4P16“other”4
5Q17“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().

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.19 Emacs Mode for Editing Patterns

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:

[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated by root on November 12, 2019 using texi2html 1.82.