www.delorie.com/gnu/docs/gnugo/gnugo_42.html search
GNU Go Documentation

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

## 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); } ```

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

 webmaster delorie software   privacy Copyright © 2003   by The Free Software Foundation Updated Jun 2003