                   THE DRAGON CODE

Before considering its move, GNU Go collects some data
in two arrays, called worm and dragon. This information
is intended to help evaluate the connectedness, eye 
shape, escape potential and life status of each group.
Later routines called by genmove() will then have access to
this information. This document attempts to explain the
philosophy and algorithms of this preliminary analysis,
which is carried out by the two routines make_worm() and
make_dragon() in dragon.c.

In this document wherever we define a concept we use
CAPITAL LETTERS for the term being defined.

A WORM is a maximal set of vertices on the board which are
connected along the horizontal and vertical lines, and are
of the same color, which can be BLACK, WHITE or EMPTY. The
term EMPTY applied to a worm means that the worm consists of
empty (unoccupied) vertices. It does NOT mean that that the
worm is the empty set. A STRING is a nonempty worm. An empty
worm is called a CAVITY.  If a subset of vertices is
contained in a worm, there is a unique worm containing it;
this is its WORM CLOSURE.

A DRAGON is a union of strings of the same color which
will be treated as a unit. The dragons are generated anew
at each move. If two strings are in the dragon, it is the
computer's working hypothesis that they will live or die
together and are effectively connected.

The purpose of the dragon code is to allow the computer
to formulate meaningful statements about life and death.
To give one example, consider the following situation:

      OOOOO
     OOXXXOO
     OX...XO
     OXXXXXO
      OOOOO

The X's here should be considered a single group with one
three-space eye, but they consist of two separate strings.
Thus we must amalgamate these two strings into a single
dragon. Then the assertion makes sense, that playing at
the center will kill or save the dragon, and is a vital
point for both players. It would be difficult to formulate
this statement if the X's are not perceived as a unit.

The present implementation of the dragon code involve
simplifying assumptions which can be refined in later
implementations. 


                	WORMS

The array struct worm_data worm[19][19] collects information
about the worms. We will give definitions of the various
fields. Each field has constant value at each vertex of the
worm. We will define each field.

struct worm_data {
  int color;       
  int size;        
  int origini;     
  int originj;     
  int liberties;   
  int liberties2;  
  int liberties3;  
  int liberties4;  
  int attacki;     
  int attackj;     
  int cutstone;    
  int genus;       
  int inessential; 
};

COLOR: If the worm is BLACK or WHITE, that is its color.
Cavities (empty worms) have an additional attribute which
we call BORDERCOLOR. This will be one of BLACK_BORDER,
WHITE_BORDER or GRAY_BORDER. Specifically, if all the
worms adjacent to a given empty worm have the same color
(black or white) then we define that to be the
bordercolor. Otherwise the bordercolor is gray.

Rather than define a new field, we keep this data in the
field color. Thus for every worm, the color field will
have one of the following values: BLACK, WHITE,
GRAY_BORDER, BLACK_BORDER or WHITE_BORDER. The last three
categories are empty worms classified by bordercolor.


SIZE: This field contains the cardinality of the worm.


ORIGIN: Each worm has a distinguished member, called
its ORIGIN. Its coordinates are (origini, originj). The
purpose of this field is to make it easy to determine
when two vertices lie in the same worm: we compare 
their origin. Also if we wish to perform some test
once for each worm, we simply perform it at the origin
and ignore the other vertices. The origin is characterized
by the test:

(worm[m][n].origini == m) && (worm[m][n].originj == n).


LIBERTIES: For a nonempty worm the field liberties is the
number of liberties of the string. This is supplemented
by liberties2, liberties3 and liberties4, which are the
number of second order, third order and fourth order 
liberties, respectively.

The definition of liberties of order >1 is adapted to the
problem of detecting the shape of the surrounding
cavity. In particular we want to be able to see if a group
is loosely surrounded. A LIBERTY OF ORDER n is an empty
vertex which may be connected to the string by placing n
stones of the same color on the board, but no fewer. The
path of connection may pass through an intervening group
of the same color. The stones placed at distance >1 may
not touch a group of the opposite color. Connections through
ko are not permitted. Thus in the following configuration:

  .XX...    We label the     .XX.4.
  XO....    liberties of     XO1234
  XO....    order < 5 of     XO1234
  ......    the O group:     ..2.4.
  .X.X..                     .X.X..

The convention that liberties of order >1 may not touch a
group of the opposite color means that knight's moves and
one space jumps are perceived as impenetrable barriers.
This is useful in determining when the string is becoming
surrounded.

We say that n is the DISTANCE of the liberty of order
n from the dragon.

ATTACK: If it is determined that the string may be
easily captured, (attacki, attackj) points to an 
attacking move. In the present implementation, this
is only used for strings with <4 liberties. The
algorithm in reading.c is fairly reliable at finding
ladders but poor at finding nets (geta). This module
therefore needs rewriting. If no attacking move is
found, then attacki == -1.


WEAK: If weaki != -1 then (weaki, weakj) points
to a boundary worm which can be easily captured.


CUTSTONE: This field is equal to 2 for cutting stones,
1 for potential cutting stones. Otherwise it is zero.
We match the following patterns:

OX   If the two X stones lie in separate worms, O is
XO   a cutting stone;

OX   If the two X stones lie in separate worms, O is
X.   a potential cutting stone.


GENUS: There are two separate notions of genus for worms and
dragons. The dragon notion is more important, so
dragon[m][n].genus is a far more useful field than
worm[m][n].genus. Both fields are intended as approximations
to the number of eyes.  The GENUS of a string is the number
of connected components of its complement, minus one. It is
an approximation to the number of eyes of the string. If (i,
j) points to the origin of a string, genus(i, j) returns its
genus.


KO: For every ko, the flag ko is set =1 at the ko stone
which is in atari, and also at the ko cavity adjacent
to it. Thus in this situation:

     XO
    X.XO
     XO

the flag ko is set =1 at the rightmost X stone, and also
at the cavity to its left.


INESSENTIAL: An INESSENTIAL string is one which meets a
criterion designed to guarantee that it has no life
potential unless a particular surrounding string of the
opposite color can be killed. More precisely an INESSENTIAL
STRING is a string S of genus zero, not adjacent to any
opponent string which can be easily captured, and which has
no edge liberties or second order liberties, and which
satisfies the following further property: If the string is
removed from the board, then the empty worm E which is the
worm closure of the set of vertices which it occupied has
bordercolor the opposite of the removed string. The empty
worm E (empty, that is, as a worm of the board modified by
removal of S) consists of the union of support of S
together with certain other empty worms which we call the
BOUNDARY COMPONENTS of S.

The inessential strings are used in the amalgamation of
cavities in make_dragon.

Makeworms() will generate data for all worms. For empty
worms, the following fields are significant: color, size,
origini and originj. The liberty, attack, cutstone,
genus and inessential fields have significance only for
nonempty worms.


		AMALGAMATION

A DRAGON, we have said, is a group of stones which are
treated as a unit. It is a working hypothesis that these
stones will live or die together. Thus the program will
not expect to disconnect an opponent's strings if they
have been amalgamated into a single dragon.

Makedragons() will amalgamate worms into dragons by
maintaining separate arrays worms[] and dragons[] containing
similar data. Each dragon is a union of worms. Just as the
data maintained in worm[19][19] is constant on each worm,
the data in dragon[19][19] is constant on each dragon.

AMALGAMATION of two worms means means in practice replacing
the origin of one worm by the origin of the other. 
Amalgamation takes place in two stages: first, the
amalgamation of empty worms (cavities) into empty
dragons (caves); then, the amalgamation of colored
worm into dragons.


          AMALGAMATION OF CAVITIES

As we have already defined it, a CAVITY is an empty
worm. A CAVE is an empty dragon.

Under certain circumstances we want to amalgamate two or
more cavities into a single cave. This is done before we
amalgamate strings. An example where we wish to amalgamate
two empty strings is the following:

      OOOOO
     OOXXXOO
     OXaObXO
     OOXXXOO
      OOOOO

The two empty worms at a and b are to be amalgamated.

We have already defined a string to be INESSENTIAL if it
meets a criterion designed to guarantee that it has no life
potential unless a particular surrounding string of the
opposite color can be killed. An INESSENTIAL STRING is a
string S of genus zero which is not a cutting string or
potential cutting string, and which has no edge liberties or
second order liberties [the last condition should be
relaxed], and which satisfies the following further
property: If the string is removed from the board, then the
empty worm E which is the worm closure of the set of
vertices which it occupied has bordercolor the opposite of
the removed string.

Thus in the previous example, after removing the inessential
string at the center the worm closure of the center vertex
consists of an empty worm of size 3 including a and b. The
latter are the boundary components.

The last condition in the definition of inessential worms
excludes examples such as this:

        OOOO
       OXXOO
      OXX.XO 
      OX.XXO
      OOXXO
       OOO

Neither of the two X strings should be considered
inessential (together they form a live group!) and indeed
after removing one of them the resulting space has gray
bordercolor, so by this definition these worms are not
inessential.

Some strings which should by rights be considered
inessential will be missed by this criterion.

The algorithm for amalgamation of empty worms consists of
amalgamating the boundary components of any inessential
worm. The resulting dragon has bordercolor the opposite of
the removed string.

Any dragon consisting of a single cavity has bordercolor
equal to that of the cavity.



            AMALGAMATION OF STRINGS

Amalgamation of nonempty worms will proceed as follows. First
we amalgamate all boundary components of a cave with nongray
border. Thus in the following example:

.OOOO.       The four X strings are amalgamated into a 
OOXXO.       single dragon because they are the boundary
OX..XO       components of a blackbordered cave. The
OX..XO       cave could contain an inessential string
OOXXO.       with no effect on this amalgamation.
XXX...       

The code for this type of amalgamation is in the routine
dragon_ring().

Next, we amalgamate strings which seem uncuttable.
amalgamate dragons which either share two or more common
liberties, or share one liberty into the which the opponent
cannot play without being captured. (ignores ko rule).

   X.    X.X     XXXX.XXX         X.O
   .X    X.X     X......X         X.X
                 XXXXXX.X         OXX

The code for this amalgamation is in the routine dragon_pairs.


                    HALF EYES

A HALF EYE is a pattern where an eye may or may not materialize,
depending on who moves first. Here is a half eye for O:

   OOOX
   O..X
   OOOX

A FALSE EYE is a cave which cannot become an eye. Here is are
two examples of false eyes for O:

   OOX         OOX
   O.O         O.OO
   XOO         OOX

A database of half eye and false eye shapes is kept in the file
hey.db. 

The half eye data is collected in the dragon array. Before
this is done, however, an auxiliary array called half_eye_data
is filled with information. The type is 0, or else
HALF_EYE or FALSE_EYE depending on which type is found;
(di, dj) points to the dragon to which it is attached;
and (ki, kj) points to a move to kill the half eye.

struct half_eye_data half_eye[19][19];

struct half_eye_data {
  int type;         /* HALF_EYE or FALSE_EYE; */
  int di;           /* (di,dj) is the dragon */
  int dj;
  int ki;           /* (ki,kj) is the move to kill or live */
  int kj;
};



half_eye[19][19], half_eyei[19][19] and half_eyej[19][19]
are filled. First, half_eye[m][n] is zero unless a half
eye or false eye is found at the empty vertex (m,n); in
this case, it is assigned the value FALSE_EYE or HALF_EYE,
and (half_eyei[m][n], half_eyej[m][n]) points to the dragon
having the false or half eye.


             DISTANCE and STRATEGIC DISTANCE

The DISTANCE from an empty vertex to black is the length of the
shortest path from the vertex to any black stone, not passing through
a white stone. The STRATEGIC DISTANCE is defined similarly except
that the path may not pass through any liberty of any white stone,
except possibly at the beginning. The distance or strategic
distance is -1 (representating infinity) if no such path may be found.
Distance and strategic distance to white are defined similarly.

For example in the following diagram on the edge, the distance from the
vertex at `a' to the color X is six:

...........
..X.XXOOO...
...XOO.a.OO
...........
-----------

because we can find the following path of length 6 from a to X:

...........
..X.XXOOO...
...6OO1a.OO
...5432....
-----------

The strategic distance is infinite, however. The above path is
not admissible for strategic distance, because at 3 and 4 it
passes through O's liberties. The path at 1 also is an O 
liberty but this is admissible since it is at the very beginning
of the path.

We maintain these data in the integer arrays distance_to_black[19][19]
and distance_to_white[19][19], and simlarly for the
strategic_distance. They may also be accessed by the functions
distance_to() and strategic_distance_to() in count.c.



                  OPEN EYES

We consider an empty vertex to be an OPEN EYE of a dragon if
its border color is gray, and it is a liberty of the dragon
and of distance at least 4 from every dragon of the opposite
color, and is not a half eye or false eye.

In most cases an open eye is actually a true eye. For
example consider the following situations. The potential
eyes are marked `p' and in each case they correspond to true
eyes of the X dragon:




|XXXO 
|p...
+----



OXXXXXO
...p...
-------



.XXXO
OXpXO
OX.XO
.....
-----



In the last example, the eye is at distance 5 from the O
stones. 

In the following example we do not have an open eye at n:


OXXXO
OXnXO
..*..
-----

It is at distance 4 from the O strings, so satisfies the definition of
an open eye except for one point: it is a half eye, and will be marked
as such by the half eye code.


                     DRAGONS

The array struct dragon_data dragon[19][19] collects information
about the dragons. We will give definitions of the various
fields. Each field has constant value at each vertex of the
dragon. We will define each field.


struct dragon_data {
  int color;   
  int origini; 
  int originj; 
  int borderi; 
  int borderj; 
  int size;    
  int heyes;
  int heyei;
  int heyej;
  int genus;
  int escape_route;
  int weaki;       
  int weakj;       
  int status;    
};


COLOR: For strings, this is BLACK or WHITE. For caves, it is
BLACK_BORDER, WHITE_BORDER or GRAY_BORDER. The meaning of
these concepts is the same as for worms.


ORIGIN: The origin of the dragon is a unique particular vertex
of the dragon, useful for determining when two vertices belong
to the same dragon. Before amalgamation the worm origins are
copied to the dragon origins. Amalgamation of two dragons
amounts to changing the origin of one.
	

BORDER: This field is relevant for caves. If the color of the
cave is BLACK_BORDER or WHITE_BORDER then the surrounding worms
all have the same color BLACK or WHITE and these have been
amalgamated into a dragon with origin (borderi, borderj).


SIZE: This is the cardinality of the dragon.


HEYES: This is the number of half eyes the dragon has. A
HALF EYE is a pattern where an eye may or may not materialize,
depending on who moves first. If any half eyes are found,
(heyi,heyj) points to a move which will create an eye.


GENUS: The GENUS of a nonempty dragon consists of the number
of distinct adjacent caves whose bordercolor is the color of
the dragon, minus the number of false eyes found. The genus
is a computable approximation to the number of eyes a dragon
has.


OPENEYES: In this implementation of GNU go, the open eyes
field is either 1 or 0, depending on whether or not open
eyes exist. This can cause undercounting of eyes --- a
similar undercounting exists for the eyes coming from
cavities, since some cavities (such as 4 spaces in a row)
actually amount to two eyes. This undercounting will
eventually have to be fixed.


ESCAPE ROUTE: The field dragon[m][n].escape_route is the maximum
of worm[i][j].liberties4 over the worms of the dragon. This is
a measure of the escape potential of the string.


WEAK: If weaki != -1, then (weaki,weakj) points to a boundary
worm which can be captured easily. In contrast with the
worm version of this parameter, we exclude strings
which cannot be saved.

STATUS: An attempt is made to classify the dragons as ALIVE,
DEAD, CRITICAL or UNKNOWN. The CRITICAL classification 
means that the fate of the dragon depends on who moves
first in the area. 


In the current algorithm, the dragon is classed ALIVE if the
2*dragon[i][j].genus+dragon[i][j].heyes > 3; it is classed
DEAD if 2*dragon[i][j].genus+dragon[i][j].heyes <3 and
its escape_route equals zero. It is also assumed that there
is no adjacent worm which can be easily captured, except
perhaps an inessential one. My current view is that such a
vulnerable boundary worm worm should be considered a half
eye if indeed capturing it creates an eye, and that this
should not be a part of the test. However I have not
implemented this change. Finally, the dragon is classed
CRITICAL if 2*dragon[i][j].genus+dragon[i][j].heyes == 3,
its escape_route equals zero and there is no essential
adjacent worm which can be easily captured. In this case,
it has an eye and a half eye (or three half eyes) and it
can be killed or saved by playing at (heyi,heyj).  If the
dragon does not fit any of these descriptions it is classed
UNKNOWN.

It is of the utmost importance accomplish this classification
as accurately as possible. Unfortunately this is not easy.
A problem is that the algorithm described is that it
sometimes classifies dragons as DEAD which can actually form
two eyes. 


                 COLORED DISPLAY

You can display the dragons as follows. Compile the program
with the options:

COLOR=-DCURSES
COLORLIB=-lncurses

With these options, you can get a colored ASCII display of
the board in which each dragon is assigned a different 
letter; and the different statuses (ALIVE, DEAD, UNKNOWN,
CRITICAL) have different colors. This is very handy for
debugging.

Save a game in sgf format using CGoban, or using the -o
option with GNU Go itself.

Open an rxvt window. (Xterm will not work.) Now execute

freedom -l [filename] -L [movenum] -T to get the colored display.

The color scheme: Green = ALIVE; Yellow = UNKNOWN; White = DEAD
and Red = CRITICAL. Worms which have been amalgamated into
the same dragon are labelled with the same letter.