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

search

	Buy GNU books!

GNU Go Documentation

4.1 Definitions

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. (see section 10.1 Worms.)

A dragon is a union of strings of the same color which will be treated as a unit. If two strings are in the same dragon, it is the computer's working hypothesis that they will live or die together and are effectively connected. (see section 10.7 Dragons.)

A superstring is a less commonly used unit which is the union of several strings but generally smaller than a dragon. The superstring code is in `engine/utils.c'. The definition of a superstring is slightly different if the code is called from `owl.c' or from `reading.c'.

GNU Go represents the board in a one-dimensional array called board. For some purposes a two dimensional indexing of the board by parameters (i,j) might be used.

The board array includes out-of-board markers around the board. To make the relation to the old two-dimensional board representation clear, this figure shows how the 1D indices correspond to the 2D indices when MAX_BOARD is 7.

j -1 0 1 2 3 4 5 6 i +---------------------------------- -1| 0 1 2 3 4 5 6 7 0| 8 9 10 11 12 13 14 15 1| 16 17 18 19 20 21 22 23 2| 24 25 26 27 28 29 30 31 3| 32 33 34 35 36 37 38 39 4| 40 41 42 43 44 45 46 47 5| 48 49 50 51 52 53 54 55 6| 56 57 58 59 60 61 62 63 7| 64 65 66 67 68 69 70 71 72

To convert between a 1D index pos and a 2D index (i,j), the macros POS, I, and J are provided, defined as below:

#define POS(i, j) ((MAX_BOARD + 2) + (i) * (MAX_BOARD + 1) + (j)) #define I(pos) ((pos) / (MAX_BOARD + 1) - 1) #define J(pos) ((pos) % (MAX_BOARD + 1) - 1)

All 1D indices not corresponding to points on the board have the out of board marker value GRAY. Thus if board_size and MAX_BOARD both are 7, this looks like

j -1 0 1 2 3 4 5 6 i +---------------------------------- -1| # # # # # # # # 0| # . . . . . . . 1| # . . . . . . . 2| # . . . . . . . 3| # . . . . . . . 4| # . . . . . . . 5| # . . . . . . . 6| # . . . . . . . 7| # # # # # # # # #

The indices marked `#' have value GRAY. If MAX_BOARD is 7 and board_size is only 5:

j -1 0 1 2 3 4 5 6 i +---------------------------------- -1| # # # # # # # # 0| # . . . . . # # 1| # . . . . . # # 2| # . . . . . # # 3| # . . . . . # # 4| # . . . . . # # 5| # # # # # # # # 6| # # # # # # # # 7| # # # # # # # # #

Navigation on the board is done by the SOUTH, WEST, NORTH, and EAST macros,

#define NS (MAX_BOARD + 1) #define WE 1 #define SOUTH(pos) ((pos) + NS) #define WEST(pos) ((pos) - 1) #define NORTH(pos) ((pos) - NS) #define EAST(pos) ((pos) + 1)

There are also shorthand macros SW, NW, NE, SE, SS, WW, NN, EE for two step movements.

Any movement from a point on the board to an adjacent or diagonal vertex is guaranteed to produce a valid index into the board array, and the color found is GRAY if it is not on the board. To do explicit tests for out of board there are two macros

#define ON_BOARD(pos) (board[pos] != GRAY) #define ON_BOARD1(pos) (((unsigned) (pos) < BOARDSIZE) && board[pos] != GRAY)

where the first one should be used in the algorithms and the second one is useful for assertion tests.

Important: The 2D coordinate (-1,-1), which is used for pass and sometimes to indicate no point, maps to the 1D coordinate 0, not to -1. Instead of a plain 0, use one of the macros NO_MOVE or PASS_MOVE.

A loop over multiple directions is straightforwardly written:

for (k = 0; k < 4; k++) { int d = delta[k]; do_something(pos + d); }

The following constants are useful for loops over the entire board and allocation of arrays with a 1-1 mapping to the board.

#define BOARDSIZE ((MAX_BOARD + 2) * (MAX_BOARD + 1) + 1) #define BOARDMIN (MAX_BOARD + 2) #define BOARDMAX (MAX_BOARD + 1) * (MAX_BOARD + 1)

BOARDSIZE is the actual size of the 1D board array, BOARDMIN is the first index corresponding to a point on the board, and BOARDMAX is one larger than the last index corresponding to a point on the board.

Often one wants to traverse the board, carrying out some function at every vertex. Here are two possible ways of doing this:

int m, n; for (m = 0; m < board_size; m++) for (n = 0; n < board_size; n++) { do_something(POS(m, n)); }

Or:

int pos; for (pos = BOARDMIN; pos < BOARDMAX; pos++) { if (ON_BOARD(pos)) do_something(pos); }