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

7. Worms and Dragons

7.1 Worms  
7.2 Amalgamation   How two Worms are amalgamated.
7.3 Connection   Connections.
7.4 Half Eyes and False Eyes  
7.5 Dragons   Union of WORMS.
7.6 Colored Dragon Display   Colored display of DRAGONS.

Before considering its move, GNU Go collects some data in several arrays. Two of these arrays, called worm and dragon, are discussed in this document. Others are discussed in See section Eyes and Half Eyes.

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

A worm is a maximal set of stones on the board which are connected along the horizontal and vertical lines, and are of the same color. We often say string instead of worm.

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 involves simplifying assumptions which can be refined in later implementations.

7.1 Worms

The array struct worm_data worm[MAX_BOARD] 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;
  float effective_size;
  int origin;
  int liberties;
  int liberties2;
  int liberties3;
  int liberties4;
  int lunch;
  int cutstone;
  int cutstone2;
  int genus;
  int inessential;
  int invincible;
  int unconditional_status;
  int attack_points[MAX_TACTICAL_POINTS];
  int attack_codes[MAX_TACTICAL_POINTS];
  int defense_points[MAX_TACTICAL_POINTS];
  int defend_codes[MAX_TACTICAL_POINTS];
  int attack_threat_points[MAX_TACTICAL_POINTS];
  int attack_threat_codes[MAX_TACTICAL_POINTS]; 
  int defense_threat_points[MAX_TACTICAL_POINTS];
  int defense_threat_codes[MAX_TACTICAL_POINTS];
};

We have two distinct notions of cutting stone, which we keep track of in the separate fields worm.cutstone and worm.cutstone2. We use currently use both concepts in parallel.

The function makeworms() will generate data for all worms.

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

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

Amalgamation of worms in GNU Go proceeds as follows. First we amalgamate all boundary components of an eyeshape. 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_eye(), discussed further in EYES.

Next, we amalgamate strings which seem uncuttable. We 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

A database of connection patterns may be found in ‘patterns/conn.db’.

7.3 Connection

The fields black_eye.cut and white_eye.cut are set where the opponent can cut, and this is done by the B (break) class patterns in ‘conn.db’. There are two important uses for this field, which can be accessed by the autohelper functions xcut() and ocut(). The first use is to stop amalgamation in positions like

 
..X..
OO*OO
X.O.X
..O..

where X can play at * to cut off either branch. What happens here is that first connection pattern CB1 finds the double cut and marks * as a cutting point. Later the C (connection) class patterns in conn.db are searched to find secure connections over which to amalgamate dragons. Normally a diagonal connection would be deemed secure and amalgamated by connection pattern CC101, but there is a constraint requiring that neither of the empty intersections is a cutting point.

A weakness with this scheme is that X can only cut one connection, not both, so we should be allowed to amalgamate over one of the connections. This is performed by connection pattern CC401, which with the help of amalgamate_most_valuable_helper() decides which connection to prefer.

The other use is to simplify making alternative connection patterns to the solid connection. Positions where the diag_miai helper thinks a connection is necessary are marked as cutting points by connection pattern 12. Thus we can write a connection pattern like CC6:

 
?xxx?     straight extension to connect
XOO*?
O...?

:8,C,NULL

?xxx?
XOOb?
Oa..?

;xcut(a) && odefend_against(b,a)

where we verify that a move at * would stop the enemy from safely playing at the cutting point, thus defending against the cut.

7.4 Half Eyes and False Eyes

A half eye is a place where, if the defender plays first, an eye will materialize, but where if the attacker plays first, no eye will materialize. A false eye is a vertex which is surrounded by a dragon yet is not an eye. Here is a half eye:

 
XXXXX
OO..X
O.O.X
OOXXX

Here is a false eye:

 
XXXXX
XOO.X
O.O.X
OOXXX

The "topological" algorithm for determining half and false eyes is described elsewhere (see section Topology of Half Eyes and False Eyes).

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 field type is 0, or else HALF_EYE or FALSE_EYE depending on which type is found; the fields attack_point[] point to up to 4 points to attack the half eye, and similarly defense_point[] gives points to defend the half eye.

 
struct half_eye_data half_eye[MAX_BOARD];

struct half_eye_data {
  float value;          /* Topological eye value */
  int type;             /* HALF_EYE or FALSE_EYE */
  int num_attacks;      /* Number of attacking points */
  int attack_point[4];  /* The moves to attack a topological halfeye */
  int num_defends;      /* Number of defending points */
  int defense_point[4]; /* The moves to defend a topological halfeye */
};

The array struct half_eye_data half_eye[MAX_BOARD] contains information about half and false eyes. If the type is HALF_EYE then up to four moves are recorded which can either attack or defend the eye. In rare cases the attack points could be different from the defense points.

7.5 Dragons

The array struct dragon_data dragon[MAX_BOARD] collects information about the dragons. We will give definitions of the various fields. Each field has constant value at each vertex of the dragon. (Fields will be discussed below.)

 
struct dragon_data {
  int color;    /* its color                               */
  int id;       /* the index into the dragon2 array        */
  int origin;   /* the origin of the dragon. Two vertices  */
                /* are in the same dragon iff they have    */
                /* same origin.                            */
  int size;     /* size of the dragon                      */
  float effective_size; /* stones and surrounding spaces   */
  int crude_status;     /* (ALIVE, DEAD, UNKNOWN, CRITICAL)*/
  int status;           /* best trusted status             */
};

extern struct dragon_data dragon[BOARDMAX];

Other fields attached to the dragon are contained in the dragon_data2 struct array. (Fields will be discussed below.)

 
struct dragon_data2 {
  int origin;
  int adjacent[MAX_NEIGHBOR_DRAGONS];
  int neighbors;
  int hostile_neighbors;
  int moyo_size;
  float moyo_territorial_value;
  int safety;
  float weakness;
  float weakness_pre_owl;
  int escape_route;
  struct eyevalue genus;
  int heye;
  int lunch;
  int surround_status;
  int surround_size;
  int semeais;
  int semeai_margin_of_safety;
  int semeai_defense_point;
  int semeai_defense_certain;  
  int semeai_attack_point;
  int semeai_attack_certain;
  int owl_threat_status;
  int owl_status;
  int owl_attack_point;
  int owl_attack_code;
  int owl_attack_certain;
  int owl_second_attack_point;
  int owl_defense_point;
  int owl_defense_code;
  int owl_defense_certain;
  int owl_second_defense_point;
  int owl_attack_kworm;
  int owl_defense_kworm;
};

extern struct dragon_data2 *dragon2;

The difference between the two arrays is that the dragon array is indexed by the board, and there is a copy of the dragon data at every stone in the dragon, while there is only one copy of the dragon2 data. The dragons are numbered, and the id field of the dragon is a key into the dragon2 array. Two macros DRAGON and DRAGON2 are provided for gaining access to the two arrays.

 
#define DRAGON2(pos) dragon2[dragon[pos].id]
#define DRAGON(d) dragon[dragon2[d].origin]

Thus if you know the position pos of a stone in the dragon you can access the dragon array directly, for example accessing the origin with dragon[pos].origin. However if you need a field from the dragon2 array, you can access it using the DRAGON2 macro, for example you can access its neighor dragons by

 
for (k = 0; k < DRAGON2(pos).neighbors; k++) {
  int d = DRAGON2(pos).adjacent[k];
  int apos = dragon2[d].origin;
  do_something(apos);
}

Similarly if you know the dragon number (which is dragon[pos].id) then you can access the dragon2 array directly, or you can access the dragon array using the DRAGON macro.

Here are the definitions of each field in the dragon arrray.

Here are definitions of the fields in the dragon2 array.

7.6 Colored Dragon Display

You can get a colored ASCII display of the board in which each dragon is assigned a different letter; and the different values of dragon.status values (ALIVE, DEAD, UNKNOWN, CRITICAL) have different colors. This is very handy for debugging. A second diagram shows the values of owl.status. If this is UNCHECKED the dragon is displayed in White.

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

Open an xterm or rxvt window. You may also use the Linux console. Using the console, you may need to use “SHIFT-PAGE UP” to see the first diagram. Xterm will only work if it is compiled with color support—if you do not see the colors try rxvt. Make the background color black and the foreground color white.

Execute:

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

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

Other useful colored displays may be obtained by using instead:

The colored displays are documented elsewhere (see section Colored Display).

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

This document was generated by Daniel Bump on February, 19 2009 using texi2html 1.78.