                          THE PATTERN CODE


Overview
--------

A database of patterns is supplied in patterns.db These are ascii
representations, of the form:

# pattern 552

??o|          sente hane
?Oo|
XX*|
...|
?.?|

:8,70,0,0,0,0,O,0,sente_hane_helper


where 'O' marks a friendly stone, 'X' marks enemy stones, '.' 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 right in this example is the edge of the
board itself---this is an edge pattern. Corners can also be
indicated. So this pattern describes a hane on the first line. The 'o'
makes sure that it would not be in atari immediately, though the
matcher can check for this automatically (see class).  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 importance.  Optionally, a function called a
``helper'' can be provided to assist the matcher in deciding the worth
of the move, and a simple measure of the influence of nearby stones
can be factored in. In this case, there is a helper, the
sente_hane_helper, which may be found in helpers.c. Most patterns do
not require a helper, and this field is filled with NULL.

The matcher searches the board for places where this layout appears on
the board, and chooses the highest scoring pattern.


Pattern Attributes
------- ----------

After the pattern, some supplementary information in the format:

  :trfno, patwt, ucutoff, uvalue, mycutoff, myvalue, classification, 
       bonus, 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.)  patwt is the numerical
pattern value - if there is a helper function (see below), it is the
maximum weight it can return.

The parameters ucutoff, uvalue, mycutoff and myvalue reflect the fact
that a pattern may have different values depending on external
circumstances. For example, a pattern to connect is less important
where I am powerful, but more important where my opponent is
powerful. My power (mypower) and your power (upower) are measured by
the function testwind(). The actual value of the move is given by the
formula:

  patwt+uvalue*min(upower,abs(ucutoff))+myvalue*min(mypower,abs(mycutoff)).

upower and ucutoff must have the same sign, as must mypower and
mycutoff.  In practice we have only used positive values for these
parameters. We have always given uvalue and myvalue the value 1 or
in rare instances 2. 

The classification scheme is as follows : a sequence of
zero or more of the following characters, each with a
different meaning.

s  :  no checking is done. This is appropriate for sacrifice patterns.
      Otherwise, the matcher requires that the stone played cannot
      be trivially captured.

n  :  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.

O  :  it is checked that every friendly ('O') stone of the pattern
      belongs to a dragon which is classified as ALIVE or UNKNOWN.

o  :  it is checked that every friendly ('O') stone of the pattern
      belongs to a dragon which is classified as DEAD or UNKNOWN.

X  :  it is checked that every opponent ('X') stone of the pattern
      belongs to a dragon which is classified as ALIVE or UNKNOWN.

x  :  it is checked that every opponent ('X') stone of the pattern
      belongs to a dragon which is classified as DEAD or UNKNOWN

D  :  if it is found that an O stone at (m,n) of the pattern can be 
      captured (worm[m][n].attacki != 0) then the move at * is tried.
      If it is found to defend the stone, worm[m][n].defend is set
      to equal *. This means that defender will later use this
      move to defend the stone.

C  :  if two distinct O dragons occur in the pattern, the pattern
      is given the connection_value.

B  :  if two distinct X dragons occur in the pattern, the pattern
      is given the connection_value.

Most likely class to use is OX (which rejects pattern if either sides
stones are dead). The string '-' may be used as a placeholder. (In
fact any characters other than the above and ',' are ignored.)

o and O could conceivably appear in a class, meaning it applies only
to UNKNOWN. X and x could be used together.

The bonus is an additional award which can be offered to patterns
which are becoming surrounded. This should be an even number. The
parameter dragon[m][n].escape_route (documented in (DRAGON) measures
the potential of a dragon to escape into open space. When this becomes
less than bonus/2, the bonus is allocated, two points at a time, for
each decrease in the escape_route.  This gives us a method of
rewarding patterns whose purpose is to secure life or to expand a
group which is becoming surrounded.  The bonus is awarded when the
escape route of ANY string in the pattern (of either color) begins to
become surrounded.

helper_fn is the name of a c function which will be invoked
to assist in the evaluation of the pattern. It will be passed
the co-ordinates on the board of the pattern element marked '*',
the rotation of the pattern which has been matched,
and the color of the piece for whom the move is being considered.
('O' in the key above). Facilities are provided for navigating
around the pattern taking the rotation into account.

`make renum' at the command line will correct the numbering
of the patterns in case you insert, delete or move patterns
around. The old file is renamed patterns.db.bak in case 
this fails for any reason.


Tuning the Pattern Database
---------------------------

Since the pattern database GNU Go's personality to a very great
extent, much time can be devoted to ``tuning'' it.  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 if its maximum possible contribution is smaller than a pattern
already found. This makes the program less efficient, but then you can
see how much you must increase a pattern value in order to `promote' a
better move over the move actually chosen.

You can obtain a Smart Go 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 Go 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 sgf
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 pattern matcher. If bad moves are being proposed, one
may modify a pattern to exclude it, or reduce the value of the
pattern.  If important moves are not proposed at all, you may have
found a gap in the pattern database, and you can add a pattern. If the
right move is proposed but with too low a score, this may be a sign
that you should adjust its weight upwards. It is almost always best
to make the *minimum* adjustment needed to correct the bad behavior.

If you decide to add a pattern, give some thought to adding the
pattern in exactly the right generality by putting ? at irrelevant
locations, and by using the o and x options.

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.

Pattern weights exceeding 99 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 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.

Alternatively, you can use the CGoban tools to delete all moves after
and including the one you want to study, and then load without the -L
option.

If a pattern is contributing a bad move, you can adjust its weight
downward, or you you can adjust the weight of a pattern which is
contributing a good move up. If no pattern is contributing the move
that you think should be made, then you may add a pattern.

You can also get a visual display of the dragons by compiling with a
color option and displaying in an rxvt window, using the -T
option. (Xterm will probably not display the colors so use rxvt or
GNU/Linux console.)  Be sure that you have uncommented either of the
color options in the make file, and from the rxvt window, try:

         gnugo -l [filename] -L [move number] -T

This is very handy in recognizing at a glance which strings GNU Go has
amalgamated into a single dragon, and the status of the dragon. Live
dragons are flagged green, dead dragons white, dragons of unknown
status yellow, and dragons of critical status red. See DRAGON for
definitions of these terms.

If you want to get the same game over and over again, you can
eliminate the randomness in GNU Go's play by changing the value of
seed in main.c to a fixed nonzero integer. If seed==0, then GNU Go
will play a different game each time.



Defensive Patterns
--------- --------

Usually a pattern will only contribute a move if its value is
large enough to outweigh all other moves which have been
found. There is an exception to this, however. If the
pattern classification string contains a `D', the pattern
is a defensive one. If an O string is found in the pattern
which can be captured, and if the move at * defends it,
then the point of defense (worm[m][n].defendi, worm[m][n].defendj)
is moved to *. This means that even if the pattern has small
value, the defensive move will be remembered later when 
defender() is run.



Helper functions
----------------

Helper functions can be provided to assist the matcher in weighing up
the importance of a move. 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, a
transformation number is supplied.  This number can be passed to a
utility function offset() with the relative co-ordinates in the
original, untransformed pattern. This function will return the actual
board co-ordinates to use for the indicated stone.

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
defend_bamboo_helper. This begins with a comment:

/*

?X?        ?X?         
O.O        ObO 
O.*        Oat

*/

The image on the left is the actual pattern. On the right we've
taken this image and added letters to label (ti, tj), (ai, aj)
and (bi, bj). Of course t is always at *, the point where GNU
Go will move if the pattern is adopted.


int
defend_bamboo_helper (struct pattern *pat, int transformation, int ti, int tj, int color)
{
  int ai, aj, bi, bj, ci, cj;
  int tval=0;
  int other=OTHER_COLOR(color);

  offset(0, -1, ti, tj, &ai, &aj, transformation);
  offset(-1, -1, ti, tj, &bi, &bj, transformation);

  if (strategic_distance_to(other, ti, tj)>10)
    return (0);                                   /* solid connection is better */
  if (trymove(bi, bj, other)) {
    if (trymove(ai, aj, color)) {
      if (safe_move(ti, tj, other))
	  tval=compute_score(ti, tj, color, pat);
      popgo();
    }
    popgo();
  }
  return (tval);
}


The offsets tell GNU Go the positions of the two stones at a=(ai,aj)
and b=(bi,bj). The pattern is subjected to two tests. First, the
strategic_distance to X (see DRAGONS) 





"Wind Assistance" 
-----------------

Each pattern can take additional numbers in the : line. For example

"connect if invaded"

OX..
.*.O
.?.?

:8,55,20,1,0,0,-,0,NULL

These represent additional biases to the score for the influence of
nearby stones. The first pair are a multiplier and a cutoff for enemy
stones, and the second for friendly stones. The actual weight
(computed in the function compute_score()) is given by the formula:

patwt+uvalue*min(upower,abs(ucutoff))+myvalue*min(mypower,abs(mycutoff)).

Typically uvalue (if nonzero) would have the value 1, meaning that the
score increases by 1 for each increase in upower, up to a maximum of
ucutoff, after which it does not increase. Thus in this example, the
value of the pattern can increase up to 75, becoming more valuable
when the opponent becomes strong in the area. This is a good feature
for patterns which help the safety of our group.



Implementation
--------------

The pattern code in GNU Go 2.0 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 2.0, the ascii patterns.db file is precompiled into tables
(see patterns.h) by a standalone program mkpat.c, and the resulting
file patterns.c is 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)

There are two modes of operation:

i) Each pattern can be compiled to one entry in patterns.c,
   describing the number of permutations in which it
   must be tested on the board. These transformations
   are calculated by the matcher at GNU Go runtime.

ii) All the transformations of each pattern are calculated
   by mkpat, and each is written out as a separate
   pattern. This results in larger executable size
   and longer compile time, but much faster performance
   at run time.


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.


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, f=e, h=g
\  e=a, g=c, f=b, h=d
/  h=a, f=c, g=b, e=d
X  a=d=e=h, b=c=f=g


To keep the implementation simple, we currrently
support only |, \, X

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,f,d,g,....
and choose first 2 for X, the first 4 for both | and \,
and all 8 for non-symmetrical patterns.

[With hindsight, I'm sure there must have been
 an obvious geometrical justifaction for why
 we have chosen the rotations...
 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 \.
]



Implementation Details
----------------------

i) 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's and some contain no X's.)

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

iii) The edge constraints are implemented by notionally padding the
pattern with rows or columns of '?' until it is exactly 19 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


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

v) The patterns themselves are sorted by decreasing
maximum-weight, which is the maximum value the pattern can
take, taking weight and wind assistance into account.  For
this to work, the weight stored for patterns with helpers
must be the maximum which the helper can return. As a hint,
to simplify maintenance, the helper can access the stored
weight from the pattern structure passed in.

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



The "grid" optimisation
-----------------------

This is a compile time option. By editing the makefile,
you can use this faster code to match patterns. The only 
disadvantage to using this code is that it might be harder 
to understand and debug.

As described in (vi), the comparisons between pattern and
board are performed as 2-bit bitwise operations. Therefore they
can be performed in paralled, 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 (vi) above, but for 32-bits
at a time.



