Updated README: Equal sign not required with `--mode` flag.

[sgk-go] / doc / patterns.texi

@menu
* Patterns Overview::             Overview of the pattern database.
* Pattern Classification::        The classification field
* Pattern Values::                The value field
* Helper Functions::              Helper Functions
* Autohelpers and Constraints::   Automatic generation of helper functions.
* Autohelper Actions::            Autohelper Actions
* Autohelper Functions::          Autohelper Functions
* Attack and Defense DB::         The Attack and defense moves database.
* Connections Database::          The connection database.
* Connection Functions::          Functions in @file{connections.c}
* Tuning::                        Tuning the pattern database.
* PM Implementation::             Implementation.
* Symmetry & transformations::    Symmetry and transformations.
* Details::                       Details of implementation.
* Grid optimization::             The ``grid'' optimization.
* Joseki Compiler::               The joseki compiler.
* Ladders in Joseki::             Example: ladders in joseki.
* Corner Matcher::                A special matcher for joseki patterns.
* Editing Patterns::              Emacs major mode for pattern files.
@end menu

@node Patterns Overview
@section Overview

@cindex pattern overview
@cindex pattern matching
@cindex pattern database
@cindex eye shapes database
@cindex defence shapes database
@cindex attack shapes database
@cindex connection shapes database
@cindex pattern.h
@cindex pattern.c

Several pattern databases are in the patterns directory.  This chapter
primarily discusses the patterns in @file{patterns.db}, @file{patterns2.db},
and the pattern files @file{hoshi.db} etc.  which are compiled from the SGF
files @file{hoshi.sgf} (@pxref{Joseki Compiler}). There is no essential
difference between these files, except that the ones in @file{patterns.db} and
@file{patterns2.db} are hand written. They are concatenated before being
compiled by @code{mkpat} into @file{patterns.c}. The purpose of the separate
file @file{patterns2.db} is that it is handy to move patterns into a new
directory in the course of organizing them. The patterns in @file{patterns.db}
are more disorganized, and are slowly being moved to @file{patterns2.db}.

During the execution of @code{genmove()}, the patterns are matched in
@file{shapes.c} in order to find move reasons.

The same basic pattern format is used by @file{attack.db}, @file{defense.db},
@file{conn.db}, @file{apats.db} and @file{dpats.db}.  However these patterns
are used for different purposes. These databases are discussed in other parts
of this documentation. The patterns in @file{eyes.db} are entirely different
and are documented elsewhere (@pxref{Eyes}).

@cindex format of the pattern database
@cindex description of shapes
@cindex ascii description of shapes

The patterns described in the databases are ascii representations, of
the form:

Pattern EB112

@example

  ?X?.?       jump under
  O.*oo
  O....
  o....
  -----
  
  :8,ed,NULL
@end example

Here @samp{O} marks a friendly stone, @samp{X} marks an enemy stone, @samp{.} marks
an empty vertex, @samp{*} marks O's next move, @samp{o} marks a square either
containing @samp{O} or empty but not @samp{X}. (The symbol @samp{x}, which does not
appear in this pattern, means @samp{X} or @samp{.}.) Finally @samp{?} 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 @samp{-}'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 @samp{?} markers, but they are not
completely ignored - see below.
        
The line beginning @samp{:} 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.

@findex shapes_callback
The matcher in @file{matchpat.c} searches the board for places where this
layout appears on the board, and the callback function
@code{shapes_callback()} in @file{shapes.c} registers the appropriate move
reasons.

After the pattern, there is some supplementary information in the format:
@example

  :trfno, classification, [values], helper_function

@end example

Here trfno represents the number of transformations of the pattern to
consider, usually @samp{8} (no symmetry, for historical reasons), or one of 
@samp{|}, @samp{\}, @samp{/}, @samp{-}, @samp{+}, @samp{X}, where the line 
represents the axis of symmetry. (E.g. @samp{|} means symmetrical about a
vertical axis.)

The above pattern could equally well be written on the left edge:

@example

  |oOO?
  |...X
  |..*?
  |..o.
  |..o?

  :8,ed,NULL
@end example

The program @code{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 @file{patterns.db} are written on the bottom edge or in the lower left
corners. In the @file{patterns/} directory there is a program called
@code{transpat} which can rotate or otherwise transpose patterns.
This program is not built by default---if you think you need it,
@code{make transpat} in the @file{patterns/} directory and
consult the usage remarks at the beginning of @file{patterns/transpat.c}.

@node  Pattern Classification
@section Pattern Attributes

@cindex pattern attributes
@cindex shape attributes

The attribute field in the @samp{:} 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 @dfn{constraints},
which determine whether or not the pattern is matched, and @dfn{actions},
which describe what is to be done when the pattern is matched, typically
to add a move reason.

@subsection Constraint Pattern Attributes

@itemize
@item @samp{s}
@quotation
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.
@end quotation
@item @samp{n}
@quotation
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.
@end quotation
@item @samp{O}
@quotation
It is checked that every friendly (@samp{O}) stone of the pattern belongs to a
dragon which has status (@pxref{Dragons}) @code{ALIVE} or
@code{UNKNOWN}. The @code{CRITICAL} matcher status is excluded. It is possible
for a string to have @code{ALIVE} 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 @samp{*}
does not rescue it, the pattern is rejected.
@end quotation
@item @samp{o}
@quotation
It is checked that every friendly (@samp{O}) stone of the pattern
belongs to a dragon which is classified as @code{DEAD} or @code{UNKNOWN}.
@end quotation
@item @samp{X}
@quotation
It is checked that every opponent (@samp{X}) stone of the pattern
belongs to a dragon with status @code{ALIVE}, @code{UNKNOWN} or 
@code{CRITICAL}. Note that there is an asymmetry with @samp{O} patterns, where
@code{CRITICAL} dragons are rejected.
@end quotation
@item @samp{x}
@quotation
It is checked that every opponent (@samp{X}) stone of the pattern
belongs to a dragon which is classified as @code{DEAD} or @code{UNKNOWN}
@end quotation
@end itemize

@subsection Action Attributes

@itemize
@item @samp{C}
@quotation
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.
@end quotation
@item @samp{c}
@quotation
Add strategical defense move reason for all our
dragons and a small shape bonus. This classification is
appropriate for weak connection patterns.
@end quotation
@item @samp{B}
@quotation
If two or more distinct @samp{X} dragons occur in the pattern, the
move is given the move reasons that it cuts each pair of
dragons.
@end quotation
@item @samp{e}
@quotation
The move makes or secures territory.
@end quotation
@item @samp{E}
@quotation
The move attempts increase influence and create/expand a moyo.
@end quotation
@item @samp{d}
@quotation
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.
@end quotation
@item @samp{a}
@quotation
The move strategically attacks all @samp{X} dragons in the pattern.
@end quotation
@item @samp{J}
@quotation
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 @samp{d}
and @samp{a} classifications together with a minimum accepted value of 27.
@end quotation
@item @samp{F}
@quotation
This indicates a fuseki pattern. This is only effective together with
either the @samp{j} or @samp{t} classification, and is used to ensure
indeterministic play during fuseki.
@end quotation
@item @samp{j}
@quotation
Slightly less urgent joseki move. These moves will be made after those
with the @samp{J} classification. This adds the
@samp{e} and @samp{E} classifications. If the move has the @samp{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 @samp{jF} as classification.)
@end quotation
@item @samp{t}
@quotation
Minor joseki move (tenuki OK). This is equivalent to adding the @samp{e} and
@samp{E} classifications together with either a fixed value of 15.07 (if
the move has @samp{F} classification) or a minimum value of 15 (otherwise).
@end quotation
@item @samp{U}
@quotation
Urgent joseki move (never tenuki). This is equivalent to the @samp{d} and
@samp{a} classifications together with a shape bonus of 15 and a minimum
accepted value of 40.  
@end quotation
@end itemize

A commonly used class is @code{OX} (which rejects pattern if either side
has dead stones). The string @samp{-} may be used as a placeholder. (In
fact any characters other than the above and @samp{,} are ignored.)

The types @samp{o} and @samp{O} could conceivably appear in a class, meaning it 
applies only to @code{UNKNOWN}. @samp{X} and @samp{x} could similarly be used together.
All classes can be combined arbitrarily.

@node  Pattern Values
@section Pattern Attributes

The second and following fields in the @samp{:} line of a pattern
are optional and of the form @code{value1(x),value2(y),...}. The available set
of values are as follows.

@itemize @bullet
@item @code{terri(x)}
@findex terri
@quotation
Forces the territorial value of the move to be at least x.
@end quotation
@item @code{minterri(x)}
@findex minterri
@quotation
Forces the territorial value of the move to be at least x.
@end quotation
@item @code{maxterri(x)}
@findex maxterri
@quotation
Forces the territorial value of the move to be at most x.
@end quotation
@item @code{value(x)}
@findex value
@quotation
Forces the final value of the move to be at least x.
@end quotation
@item @code{minvalue(x)}, @code{maxvalue(x)}
@findex minvalue
@findex maxvalue
@quotation
Forces the final value of the move to be at least/most x.
@end quotation
@item @code{shape(x)}
@findex shape
@quotation
Adds x to the move's shape value.
@end quotation
@item @code{followup(x)}
@findex followup
@quotation
Adds x to the move's followup value.
@end quotation
@end itemize

The meaning of these values is documented in @xref{Move Generation}.

@node  Helper Functions
@section Helper Functions

@cindex helper functions in pattern matching

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
@samp{*} 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 @file{helpers.c}. They are declared
in @file{patterns.h}.

As an example to show how to write a helper function, we consider
a hypothetical helper called @code{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:

@example
/*

?O.           ?Ob
.X*           aX*
?O.           ?Oc

:8,C,wedge_helper
*/
@end example

The image on the left is the actual pattern. On the right we've taken
this image and added letters to label @code{apos}, @code{bpos}, and
@code{cpos}. The position of *, the point where GNU Go will move if the
pattern is adopted, is passed through the parameter @code{move}.

@example
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;
@}

@end example

The @code{OFFSET} lines tell GNU Go the positions of the three stones at
@samp{a}, @samp{b}, and @samp{c}. To decide whether the pattern
guarantees a connection, we do some reading. First we use the
@code{TRYMOVE} macro to place an @samp{O} at @samp{move} and let
@samp{X} draw back to @samp{a}. Then we ask whether @samp{O} can capture
these stones by calling @code{attack()}. The test if there is a stone at
@samp{a} before calling @code{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 @samp{O} connect at @samp{b} and use the
@code{safe_move()} function to examine whether a cut by @samp{X} at
@samp{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 @code{popgo()}.

@node  Autohelpers and Constraints
@section Autohelpers and Constraints

@cindex generation of helper functions
@cindex Autohelpers

In addition to the hand-written helper functions in @file{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 @samp{:} line and the constraint
expression is placed below the diagram on line starting with a @samp{;}.
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.

@example

Pattern Conn311

O*.
?XO

:8,C,NULL

O*a
?BO

;oplay_attack_either(*,a,a,B)

@end example

Here we have given the label @samp{a} to the empty spot to the right of
the considered move and the label @samp{B} to the @samp{X} stone in the
pattern. In addition to these, @samp{*} can also be used as a label. A
label may be any lowercase or uppercase ascii letter except @code{OoXxt}. By
convention we use uppercase letters for @samp{X} stones and lowercase for @samp{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
@samp{O} stone at @samp{*} followed by an @samp{X} stone at
@samp{a}. Accept the pattern if @samp{O} now can capture either at
@samp{a} or at @samp{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 @file{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.

@node  Autohelper Actions
@section Autohelper Actions

@cindex 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:

@example

Pattern EJ4

...*.     continuation
.OOX.
..XOX
.....
-----

:8,Ed,NULL

...*.     never play a here
.OOX.
.aXOX
.....
-----

>antisuji(a)

@end example

The line starting with @samp{>} 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 @samp{*}, 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 @file{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 @file{mkpat.c}.

@itemize
@item @code{antisuji(a);}
@quotation
Mark @samp{a} as an antisuji, that is, a move that must never
be played.
@end quotation
@item @code{replace(a,*)}
@quotation
This is appropriate if the move at @samp{*} is definitely better
than the move at @samp{a}. The macro adds a point redistribution rule. Any 
points which are assigned to @samp{a} during the move generation
by any move reason are redistributed to @samp{*}.
@end quotation
@item @code{prevent_attack_threat(a)}
@quotation
Add a reverse followup value because the opponent's move here
would threaten to capture @samp{a}.
@end quotation
@item @code{threaten_to_save(a)}
@quotation
Add a followup value because the move at @samp{*} threatens to
rescue the dead string at @samp{a}.
@end quotation
@item @code{defend_against_atari(a)}
@quotation
Estimate the value of defending the string @samp{a} which can be put into
atari and add this as a reverse followup value.
@end quotation
@item @code{add_defend_both_move(a,b);}
@quotation
@end quotation
@item @code{add_cut_move(c,d);}
@quotation
Add to the move reasons that the move at @samp{*} threatens to cut
@samp{c} and @samp{d}.
@end quotation
@end itemize

@node  Autohelper Functions
@section Autohelper Functions

The autohelper functions are translated into C code by the program in
@file{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.

@example

@code{lib(x)}
@code{lib2(x)}
@code{lib3(x)}
@code{lib4(x)}

@end example

Number of first, second, third, and fourth order liberties of a worm
respectively. @xref{Worms and Dragons}, the documentation on worms for
definitions.

@example

@code{xlib(x)}
@code{olib(x)}

@end example

The number of liberties that an enemy or own stone, respectively,
would obtain if played at the empty intersection @samp{x}.

@example
@code{xcut(x)}
@code{ocut(x)}
@end example

Calls @code{cut_possible} (@pxref{General Utilities}) to determine
whether @samp{X} or @samp{O} can cut at the empty intersection @samp{x}. 

@example
@code{ko(x)}
@end example

True if @samp{x} is either a stone or an empty point involved in a ko
position.

@example
@code{status(x)}
@end example 

The matcher status of a dragon. status(x) returns an integer that can have the
values @code{ALIVE}, @code{UNKNOWN}, @code{CRITICAL}, or @code{DEAD}
(@pxref{Worms and Dragons}).

@example
@code{alive(x)}
@code{unknown(x)}
@code{critical(x)}
@code{dead(x)}
@end example

Each function true if the dragon has the corresponding matcher status and
false otherwise (@pxref{Worms and Dragons}).

@example
@code{status(x)}
@end example

Returns the status of the dragon at @samp{x} (@pxref{Worms and Dragons}).

@example
@code{genus(x)}
@end example

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

@example

@code{xarea(x)}
@code{oarea(x)}
@code{xmoyo(x)}
@code{omoyo(x)}
@code{xterri(x)}
@code{oterri(x)}

@end example

These functions call @code{whose_territory()}, @code{whose_moyo()}
and @code{whose_area()} (@pxref{Territory and Moyo}). For example
@code{xarea(x)} evaluates to true if @samp{x} is either a living enemy stone
or an empty point within the opponent's ``area''. The function @code{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.

@example
@code{weak(x)}
@end example

True for a dragon that is perceived as weak.

@example

@code{attack(x)}
@code{defend(x)}

@end example

Results of tactical reading. @code{attack(x)} is true if the worm can be
captured, @code{defend(x)} is true if there also is a defending move. Please
notice that @code{defend(x)} will return false if there is no attack on the
worm.

@example

@code{safe_xmove(x)}
@code{safe_omove(x)}

@end example

True if an enemy or friendly stone, respectively, can safely be played at
@samp{x}. By safe it is understood that the move is legal and that it cannot
be captured right away.

@example

@code{legal_xmove(x)}
@code{legal_omove(x)}

@end example

True if an enemy or friendly stone, respectively, can legally be played at x.

@example

o_somewhere(x,y,z, ...)
x_somewhere(x,y,z, ...)

@end example

True if O (respectively X) has a stone at one of the labelled vertices.
In the diagram, these vertices should be marked with a @samp{?}.

@example

odefend_against(x,y)
xdefend_against(x,y)

@end example

True if an own stone at @samp{x} would stop the enemy from safely playing at
@samp{y}, and conversely for the second function.

@example

@code{does_defend(x,y)}
@code{does_attack(x,y)}

@end example

True if a move at @samp{x} defends/attacks the worm at @samp{y}. For 
defense a move of the same color as @samp{y} is tried and for attack a move of
the opposite color.

@example

@code{xplay_defend(a,b,c,...,z)}
@code{oplay_defend(a,b,c,...,z)}
@code{xplay_attack(a,b,c,...,z)}
@code{oplay_attack(a,b,c,...,z)}

@end example

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 @samp{a},@samp{b},@samp{c},... is played through with
alternating colors, starting with @samp{X} or @samp{O} as indicated by
the name. Then it is tested whether the worm at @samp{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 @samp{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 @samp{?} can be used to represent a tenuki.
Thus @code{oplay_defend(a,?,b,c)} tries moves by @samp{O} at @samp{a} and
@samp{b}, as if @samp{X} plays the second move in another part of
the board, then asks if @samp{c} can be defended. The tenuki cannot
be the first move of the sequence, nor does it need to be:
instead of @code{oplay_defend(?,a,b,c)} you can use
@code{xplay_defend(a,b,c)}.

@example
@code{xplay_defend_both(a,b,c,...,y,z)}
@code{oplay_defend_both(a,b,c,...,y,z)}
@code{xplay_attack_either(a,b,c,...,y,z)}
@code{oplay_attack_either(a,b,c,...,y,z)}

@end example

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 @samp{y} and @samp{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 @code{xplay_defend_both} plays alternate moves
beginning with an @samp{X} at @samp{a}. Then it passes the last
two arguments to @code{defend_both} in
@file{engine/utils.c}. This function checks to determine
whether the two strings can be simultaneously defended.

The function @code{xplay_attack_either} plays alternate
moves beginning with an @samp{X} move at @samp{a}. Then it passes
the last two arguments to @code{attack_either} in
@file{engine/utils.c}. This function looks for a move
which captures at least one of the two strings. In its
current implementation @code{attack_either} only looks
for uncoordinated attacks and would thus miss a double
atari.

@example
@code{xplay_connect(a,b,c,...,y,z)}
@code{oplay_connect(a,b,c,...,y,z)}
@code{xplay_disconnect(a,b,c,...,y,z)}
@code{oplay_disconnect(a,b,c,...,y,z)}

@end example

The function @code{xplay_connect(a,b,c,...,y,z)} begins
with an @samp{X} move at @samp{a}, then an @samp{O}
move at @samp{b}, and so forth, then finally calls
@code{string_connect()} to determine whether
@samp{x} and @samp{y} can be connected. The other
functions are similar (@pxref{Connection Reading}).

@example

@code{xplay_break_through(a,b,c,...,x,y,z)}
@code{oplay_break_through(a,b,c,...,x,y,z)}

@end example

These functions are used to set up a position like

@example

.O.    .y.
OXO    xXz

@end example

@noindent
and @samp{X} aims at capturing at least one of @samp{x}, @samp{y}, and
@samp{z}. If this succeeds @samp{1} is returned. If it doesn't, @samp{X}
tries instead to cut through on either side and if this succeeds,
@samp{2} is returned. Of course the same shape with opposite colors can
also be used.

Important notice: @samp{x}, @samp{y}, and @samp{z} must be given in the
order they have in the diagram above, or any reflection and/or rotation
of it.

@example
seki_helper(x)
@end example

Checks whether the string at @samp{x} can attack any surrounding
string. If so, return false as the move to create a seki (probably)
wouldn't work.

@example
threaten_to_save(x)
@end example

Calls @code{add_followup_value} to add as a move reason a conservative
estimate of the value of saving the string @samp{x} by capturing one opponent
stone.

@example
area_stone(x)
@end example

Returns the number of stones in the area around @samp{x}.

@example
area_space(x)
@end example

Returns the amount of space in the area around @samp{x}.

@example
@code{eye(x)}
@code{proper_eye(x)}
@code{marginal_eye(x)}
@end example

True if @samp{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.

@example
@code{antisuji(x)}
@end example

Tell the move generation that @samp{x} is a substandard move that never should
be played.

@example
same_dragon(x,y)
same_worm(x,y)
@end example

Return true if @samp{x} and @samp{y} are the same dragon or worm respectively.

@example
@code{dragonsize(x)}
@code{wormsize(x)}
@end example

Number of stones in the indicated dragon or worm.

@example
@code{add_connect_move(x,y)}
@code{add_cut_move(x,y)}
@code{add_attack_either_move(x,y)}
@code{add_defend_both_move(x,y)}
@end example

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

@example
@code{halfeye(x)}
@end example

Returns true if the empty intersection at @samp{x} is a half eye.

@example
@code{remove_attack(x)}
@end example

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

@example
@code{potential_cutstone(x)}
@end example

True if @code{cutstone2} field from worm data is larger than one. This
indicates that saving the worm would introduce at least two new
cutting points.

@example
@code{not_lunch(x,y)}
@end example

Prevents the misreporting of @samp{x} as lunch for @samp{y}.
For example, the following pattern tells GNU Go that even
though the stone at @samp{a} can be captured, it should not
be considered ``lunch'' for the dragon at @samp{b}, because
capturing it does not produce an eye:

@example
XO|          ba|
O*|          O*|
oo|          oo|
?o|          ?o|

> not_lunch(a,b)
@end example

@example
@code{vital_chain(x)}
@end example

Calls @code{vital_chain} to determine whether capturing
the stone at @samp{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.

@example
@code{amalgamate(x,y)}
@end example

Amalgamate (join) the dragons at @samp{x} and @samp{y} (@pxref{Worms and Dragons}).

@example
@code{amalgamate_most_valuable(x,y,z)}
@end example

Called when @samp{x}, @samp{y}, @samp{z} point to three (preferably distinct)
dragons, in situations such as this:

@example

.O.X
X*OX
.O.X

@end example

In this situation, the opponent can play at @samp{*}, preventing
the three dragons from becoming connected. However @samp{O}
can decide which cut to allow. The helper amalgamates the
dragon at @samp{y} with either @samp{x} or @samp{z}, 
whichever is largest.

@example
make_proper_eye(x)
@end example

This autohelper should be called when @samp{x} is an eyespace
which is misidentified as marginal. It is reclassified as
a proper eyespace (@pxref{Eye Space}).

@example
remove_halfeye(x)
@end example

Remove a half eye from the eyespace. This helper should not be run after
@code{make_dragons} is finished, since by that time the eyespaces have
already been analyzed.

@example
remove_eyepoint(x)
@end example

Remove an eye point. This function can only be used before the
segmentation into eyespaces.

@example
@code{owl_topological_eye(x,y)}
@end example

Here @samp{x} is an empty intersection which may be an
eye or half eye for some dragon, and @samp{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 @samp{x}, as
explained in @xref{Eye Topology}, equal to 4 or more if the
eye at @samp{x} is false, 3 if it is a half eye, and 2 if it
is a true eye. 

@example
@code{owl_escape_value(x)}
@end example

Returns the escape value at @samp{x}. This is only useful in owl
attack and defense patterns.

@node  Attack and Defense DB
@section Attack and Defense Database

The patterns in @file{attack.db} and @file{defense.db} are used to assist the
tactical reading in finding moves that attacks or defends worms. The
matching is performed during @code{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.

@table @samp
@item D
For each @samp{O} worm in the pattern that can be tactically captured
(@code{worm[m][n].attack_code != 0}), the move at @samp{*} is
tried. If it is found to defend the stone, this is registered as a
reason for the move @samp{*} and the defense point of the worm is set to
@samp{*}.
@item A
For each @samp{X} worm in the pattern, it's tested whether the move
at @samp{*} captures the worm. If that is the case, this is
registered as a reason for the move at @samp{*}. The attack point of
the worm is set to @samp{*} and if it wasn't attacked before, a
defense is searched for.
@end table

Furthermore, @samp{A} patterns can only be used in @file{attack.db} and
@samp{D} patterns only in @file{defense.db}. Unclassified patterns may
appear in these databases, but then they must work through actions to be
effective.

@node  Connections Database
@section The Connections Database

@cindex connections database
@cindex connection shapes database

The patterns in @file{conn.db} are used for helping @code{make_dragons()}
amalgamate worms into dragons and to some extent for modifying eye spaces.
The patterns in this database use the classifications @samp{B}, 
@samp{C}, and @samp{e}. @samp{B} patterns are used for finding cutting points,
where amalgamation should not be performed, @samp{C} patterns are used for
finding existing connections, over which amalgamation is to be done, and 
@samp{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 @samp{C} patterns. Further
details and examples can be found in @xref{Worms and Dragons}.

We will illustrate these databases by example. In this situation:

@example
XOO
O.O
...
@end example
@noindent
@samp{X} cannot play safely at the cutting point, so the @samp{O} dragons
are to be amalgamated. Two patterns are matched here:

@example
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))
@end example

The constraints are mostly clear. For example the second
pattern should not be matched if the @samp{X} stone cannot
be attacked and @samp{X} can play safely at @samp{B}, or
if @samp{B} is a ko. The constraint @code{!xcut(B)} means
that connection has not previously been inhibited by 
@code{find_cuts}. For example consider this situation:

@example

OOXX
O.OX
X..O
X.OO
@end example
@noindent
The previous pattern is matched here twice, yet @samp{X} can push
in and break one of the connections. To fix this, we include
a pattern:

@example
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,*)
@end example

After this pattern is found, the @code{xcut} autohelper macro will return
true at any of the points @samp{*}, @samp{a} and @samp{b}. Thus the
patterns @code{CB204} and @code{CB205} will not be matched, and the dragons will
not be amalgamated.

@node Connection Functions
@section Connections Functions

Here are the public functions in @file{connections.c}.

@itemize @bullet
@item @code{static void cut_connect_callback(int m, int n, int color, 
        struct pattern *pattern, int ll, void *data)}
@findex cut_connect_callback
@quotation
Try to match all (permutations of) connection patterns at @code{(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 @samp{C} pattern, amalgamate
the dragons in the pattern.
@end quotation
@item @code{void find_cuts(void)}
@findex find_cuts
@quotation
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 @code{cut_connect_callback} is invoked.
@end quotation
@item @code{void find_connections(void)}
@findex find_connections
@quotation 
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
@code{cut_connect_callback} is invoked.
@end quotation
@item void modify_eye_spaces1(void)
@findex modify_eye_spaces1
@quotation 
Find explicit connection patterns and amalgamate the involved dragons.
This goes through the connection database consulting only patterns
of type E (@pxref{Connections Database}). When such a function is found, the
function @code{cut_connect_callback} is invoked.  
@end quotation
@item void modify_eye_spaces1(void)
@findex modify_eye_spaces1
@quotation 
Find explicit connection patterns and amalgamate the involved dragons.
This goes through the connection database consulting only patterns
of type e (@pxref{Connections Database}). When such a function is found, the
function @code{cut_connect_callback} is invoked.  
@end quotation
@end itemize

@node  Tuning
@section Tuning the Pattern databases

@cindex tuning the pattern database
@cindex tuning the shapes database

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 @option{-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 @option{-o}
option. It is best to combine this with @option{-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 @option{-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 @code{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:

@example

 echo ")" >>[filename]  

@end example

@noindent
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 @option{-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:

@example

  gnugo -l [filename] -L [move number] -t -a -w

@end example

@noindent
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 @option{-L}
in order to stop at the first move played at this location. If you
omit the @option{-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 @file{conn.db}.
Similarly, worms may be incorrectly amalgamated due to some too
general or faulty pattern in @file{conn.db}. To get trace output from the
matching of patterns in @file{conn.db} you need to add a second
@option{-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 @code{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 @option{-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:

@example
  gnugo -l [filename] -L [move number] -T
@end example

@noindent
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 @code{dragon.safety}, which
is set in @file{moyo.c}.

@format
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 @file{moyo.c}
@end format

@cindex eliminate the randomness

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 @option{-r} option.


@node PM Implementation
@section Implementation

@cindex implementation of pattern matching

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 @file{.db} files are precompiled into tables (see
@file{patterns.h}) by a standalone program @file{mkpat.c}, and the resulting 
@file{.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 @samp{X} or @samp{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 @code{(m,n,o)} if the the pattern anchor
stone is on @code{(m,n)}, and the other elements match the board when the
pattern is transformed by transformation number @samp{o}. (See below for
the details of the transformations, though these should not be
necessary)


@node  Symmetry & transformations, Details, PM Implementation, Patterns
@section Symmetry and transformations

@cindex symmetry and transformations
@cindex symmetry and transformations of shapes

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 @samp{:} can be one of @samp{8},@samp{|},@samp{\},@samp{/},
@samp{X}, @samp{-}, @samp{+}, representing the axes of symmetry. It can also
be @samp{O}, representing symmetry under 180 degrees rotation.

@format
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
@end format

Then if the pattern has the following symmetries, the
following are true:

@example

|  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

@end example

We can choose to use transformations a,d,f,g as the unique
transformations for patterns with either @samp{|}, @samp{-}, @samp{\}, or
@samp{/} symmetry.

Thus we choose to order the transformations a,g,d,f,h,b,e,c and choose
first 2 for @samp{X} and @samp{+}, the first 4 for @samp{|}, @samp{-},
@samp{/}, and @samp{\}, the middle 4 for @samp{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 @samp{-} and @samp{/} as well as @samp{|}
and @samp{\}.

@node  Details
@section Implementation Details

@cindex pattern matching optimization
@cindex grid optimization

@enumerate
@item An entry in the pattern header states whether the anchor is an @samp{X} or
an @samp{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 @samp{O} or always @samp{X}, but some
patterns contain no @samp{O} and some contain no @samp{X}.)

@item 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.

@item The edge constraints are implemented by notionally padding the
pattern with rows or columns of @samp{?} 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

"example"
.OO????????????????
*XX????????????????
o??????????????????
:8,80

@end example

@item 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.

@item The actual tests are performed using an 'and-compare'
sequence. Each board position is a 2-bit quantity.
%00 for empty, %01 for @samp{O}, %10 for @samp{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 @samp{o} is the
same as a test for 'not-X', ie not %10. So and with %01
should give 0 if it matches. Similarly @samp{x} is a test that
bit 0 is not set.

@end enumerate

@node Grid optimization
@section 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 :

@example

 .X.O....OO
 XXXXO.....
 .X..OOOOOO
 X.X.......
 ....X...O.

@end example

@noindent
which is internally stored internally in a 2d array (binary)

@example

 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

@end example

@noindent
we can compile this to a composite array in which each element
stores the state of a 4x4 grid of squares :

@example

 ????????  ????????  ???????? ...
 ??001000  00100001  10000100
 ??101010  10101010  10101001
 ??001000  00100000  10000001

 ??001000  00100001  ...
 ??101010  10101010
 ??001000  00100000
 ??001000  10001000 

...

 ??100010  ...
 ??000000
 ????????
 ????????

@end example

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.

@node  Joseki Compiler
@section The Joseki Compiler

@cindex joseki
@cindex how GNU Go learns new joseki
@cindex the joseki compiler
@cindex teaching josekis to GNU Go

GNU Go includes a joseki compiler in @file{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 @file{patterns/} called @file{hoshi.sgf}, @file{komoku.sgf}, @file{sansan.sgf}, 
@file{mokuhazushi.sgf} and @file{takamoku.sgf}.  This division can be revised
whenever need arises.

The SGF files are transformed into the pattern database @file{.db} format by
the program in @file{joseki.c}. These files are in turn transformed into C
code by the program in @file{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:

@itemize @bullet
@item
A square mark (@code{SQ} or @code{MA} property) to decide how large part of the
board should be included in the pattern.
@item A move (@samp{W} or @samp{B} property) with the natural interpretation.
If the square mark is missing or the move is a pass, no pattern is
produced for the node.
@item Optional labels (@code{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.
@item A comment (@samp{C} property). As the first character it should have one of the
following characters to decide its classification:
@itemize @minus
@item @samp{U} - urgent move
@item @samp{S} or @samp{J} - standard move
@item @samp{s} or @samp{j} - lesser joseki
@item @samp{T} - trick move
@item @samp{t} - minor joseki move (tenuki OK)
@item @samp{0} - antisuji (@samp{A} can also be used)
@end itemize
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:
@itemize @minus
@item @samp{#} - Comments. These are copied into the patterns file, above the diagram.
@item @samp{;} - Constraints. These are copied into the patterns file, below the
constraint diagram.
@item  @samp{>} - Actions. These are copied into the patterns file, below the
constraint diagram.
@item @samp{:} - Colon line. This is a little more complicated, but the colon
line of the produced patterns always start out with ":8,s" for
transformation number and sacrifice pattern class (it usually
isn't a sacrifice, but it's pointless spending time checking for
tactical safety). Then a joseki pattern class character is
appended and finally what is included on the colon line in the
comment for the SGF node.
@end itemize
@end itemize

Example: If the comment in the SGF file looks like

@example
F
:C,shape(3)
;xplay_attack(A,B,C,D,*)
@end example

@noindent
the generated pattern will have a colon line

@example
:8,sjC,shape(3)
@end example

@noindent
and a constraint

@example
;xplay_attack(A,B,C,D,*)
@end example

@node Ladders in Joseki
@section 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

@example
--------+
........|
........|
...XX...|
...OXO..|
...*O...|
....X...|
........|
........|
@end example

But this is bad unless we have a ladder in our favor. To check this we
add a constraint which may look like

@example
--------+
........|
........|
...XX...|
...OXO..|
...*OAC.|
....DB..|
........|
........|

;oplay_attack(*,A,B,C,D)
@end example

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 @samp{O}, 
on the intersections @samp{*}, @samp{A}, @samp{B}, and @samp{C}. Then check
whether the stone at @samp{D} can be captured." I.e. play to this position

@example
--------+
........|
........|
...XX...|
...OXO..|
...OOXX.|
....XO..|
........|
........|
@end example

@noindent
and call @code{attack()} to see whether the lower @samp{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 @file{.db}
file. The joseki compiler knows how to create these from labels in
the SGF node. @file{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:

@example
;oplay_attack(*,A,B,C,D)
@end example

The appropriate constraint (autohelper macro) will then be added
to the Joseki @file{.db} file.

@node Corner Matcher
@section Corner Matcher

@cindex implementation of pattern matching
@cindex joseki
@cindex 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:

@itemize @bullet
@item They must be matchable only at a corner of the board (hence the name of
the matcher).
@item They can consist only of @samp{O}, @samp{X} and @samp{.} elements.
@item Of all pattern values (@pxref{Pattern Values}), corner matcher only
support @code{shape(x)}.  This is not because the matcher cannot handle other
values in principle, just they are currently not used in joseki databases.
@end itemize

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
(@pxref{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:

@itemize @minus
@item stone position relative to the corner,
@item a flag determining whether the stone color must be equal to the first
matched stone color,
@item number of stones in the corner area (see below) of the variation stone.
@end itemize

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 @emph{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:

@example
------+
......|
......|
.O*...|
.XXO..|
......|
......|
@end example

To encode it for the corner matcher, we have to use five variations,
each next being a child of previous:

@multitable {Tree level} {Position} {``other''} {Number of stones}
@item Tree level @tab Position @tab Color @tab Number of stones
@item 1 @tab R16 @tab ``same'' @tab 1
@item 2 @tab P17 @tab ``same'' @tab 1
@item 3 @tab Q16 @tab ``other'' @tab 2
@item 4 @tab P16 @tab ``other'' @tab 4
@item 5 @tab Q17 @tab ``same'' @tab 1
@end multitable

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 @samp{O} which stands for the stones of the player
to whom moves are being suggested with @samp{*}.

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 @file{mkpat.c}

Corner matcher resides in @file{matchpat.c} in two functions:
@code{corner_matchpat()} and @code{do_corner_matchpat()}.  The former computes
@code{num_stones[]} array which holds number of stones in corner areas of
different intersections of the board for all possible transformations.
@code{corner_matchpat()} also matches top-level variations.
@code{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 @code{mkpat} program.
Database generator consists of several functions, most important are:
@code{corner_best_element()}, @code{corner_variation_new()},
@code{corner_follow_variation()} and @code{corner_add_pattern()}.

@node Editing Patterns
@section Emacs Mode for Editing Patterns

@cindex editing patterns
@cindex editing pattern database

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
@file{patterns/gnugo-db.el}.

Copy the file to @file{emacs/site-lisp} directory.  You can then load
the mode with @code{(require 'gnugo-db)}.  It makes sense to put this
line into your configuration file (@file{~/.emacs}).  You can either
use @command{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 @file{.db} suffix:

@example
	(setq auto-mode-alist
	      (append
	       auto-mode-alist
	       '(("\\.db\\'" . gnugo-db-mode))))
@end example

Pattern editing mode provides the following features:

@itemize @minus
@item
highlighting of keywords (@code{Pattern}, @code{goal_elements} and
@code{callback_data}) and comments,

@item
making paragraphs equal to patterns (@kbd{M-h}, @kbd{M-@{}, @kbd{M-@}}
and others operate on patterns),

@item
commands for pattern creation with automatic name selection (@kbd{C-c
C-p}) and copying main diagram to constraint diagram (@kbd{C-c C-c}),

@item
automated indentation of constraints and side comments (pattern
descriptions).
@end itemize