www.delorie.com/gnu/docs/gnugo/gnugo_120.html

search

	Buy GNU books!

GNU Go Documentation

10.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]; };

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

• effective_size

  This is the number of stones in a worm plus the number of empty intersections that are at least as close to this worm as to any other worm. Intersections that are shared are counted with equal fractional values for each worm. This measures the direct territorial value of capturing a worm. effective_size is a floating point number. Only intersections at a distance of 4 or less are counted.

• origin

  Each worm has a distinguished member, called its origin. 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[pos].origin == pos.

• liberties
• liberties2
• liberties3
• liberties4

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

  The path may also not pass through a liberty at distance 1 if that liberty is flanked by two stones of the opposing color. This reflects the fact that the O stone is blocked from expansion to the left by the two X stones in the following situation:

  X. .O X.

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

• lunch

  If nonzero, lunch points to a boundary worm which can be easily captured. (It does not matter whether or not the string can be defended.)

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.

• cutstone

  This field is equal to 2 for cutting stones, 1 for potential cutting stones. Otherwise it is zero. Definitions for this field: a cutting stone is one adjacent to two enemy strings, which do not have a liberty in common. The most common type of cutting string is in this situation:

  XO OX

  A potential cutting stone is adjacent to two enemy strings which do share a liberty. For example, X in:

  XO O.

  For cutting strings we set worm[].cutstone=2. For potential cutting strings we set worm[].cutstone=1.

• cutstone2

  Cutting points are identified by the patterns in the connections database. Proper cuts are handled by the fact that attacking and defending moves also count as moves cutting or connecting the surrounding dragons. The cutstone2 field is set during find_cuts(), called from make_domains().

• genus

  There are two separate notions of genus for worms and dragons. The dragon notion is more important, so dragon[pos].genus is a far more useful field than worm[pos].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.

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

• invincible

  An invincible worm is one which GNU Go thinks cannot be captured. Invincible worms are computed by the function unconditional_life() which tries to find those worms of the given color that can never be captured, even if the opponent is allowed an arbitrary number of consecutive moves.

• unconditional_status

  Unconditional status is also set by the function unconditional_life. This is set ALIVE for stones which are invincible. Stones which can not be turned invincible even if the defender is allowed an arbitrary number of consecutive moves are given an unconditional status of DEAD. Empty points where the opponent cannot form an invincible worm are called unconditional territory. The unconditional status is set to WHITE_BORDER or BLACK_BORDER depending on who owns the territory. Finally, if a stone can be captured but is adjacent to unconditional territory of its own color, it is also given the unconditional status ALIVE. In all other cases the unconditional status is UNKNOWN.

  To make sense of these definitions it is important to notice that any stone which is alive in the ordinary sense (even if only in seki) can be transformed into an invincible group by some number of consecutive moves. Well, this is not entirely true because there is a rare class of seki groups not satisfying this condition. Exactly which these are is left as an exercise for the reader. Currently unconditional_life, which strictly follows the definitions above, calls such seki groups unconditionally dead, which of course is a misfeature. It is possible to avoid this problem by making the algorithm slightly more complex, but this is left for a later revision.

• int attack_points[MAX_TACTICAL_POINTS]
• attack_codes[MAX_TACTICAL_POINTS]
• int defense_points[MAX_TACTICAL_POINTS];
• int defend_codes[MAX_TACTICAL_POINTS];

  If the tactical reading code (see section 14. Tactical reading) finds that the worm can be attacked, attack_points[0] is a point of attack, and attack_codes[0] is the attack code, WIN, KO_A or KO_B. If multiple attacks are known, attack_points[k] and attack_codes[k] are used. Similarly with the defense codes and defense 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];

  These are points that threaten to attack or defend a worm.

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