The foundation of the GNU Go engine is a library of very efficient routines for handling go boards.  This board library, called libboard, can be used for those programs that only need a basic go board but no AI capability. One such program is patterns/joseki.c, which compiles joseki pattern databases from SGF files.

If you want to use the board library in your own program, you need all the .c-files listed under libboard_SOURCES in engine/Makefile.am, and the files in the directories sgf/ and utils/. Then you should include engine/board.h in your code.

The library consists of the following files:

  * board.h

          The public interface to the board library.

  * board.c

          The basic board code. It uses incremental algorithms for keeping track of strings and liberties on the go board.

  * boardlib.c

          This contains all global variable of the board library.

  * hash.c

          Code for hashing go positions.

  * sgffile.c

          Implementation of output file in SGF format.

  * printutils.c

          Utilities for printing go boards and other things.

To use the board library, you must include liberty.h just like when you use the whole engine, but of course you cannot use all the functions declared in it, i.e. the functions that are part of the engine, but not part of the board library.  You must link your application with libboard.a.

Board Data structures
=====================

The basic data structures of the board correspond tightly to the board_state struct described in see The Board State. They are all stored in global variables for efficiency reasons, the most important of which are:

     int           board_size;
     Intersection  board[MAXSIZE];
     int           board_ko_pos;

     float         komi;
     int           white_captured;
     int           black_captured;

     Hash_data     hashdata;

The description of the Position struct is applicable to these variables also, so we won't duplicate it here.  All these variables are globals for performance reasons.  Behind these variables, there are a number of other private data structures.  These implement incremental handling of strings, liberties and other properties (see Incremental Board). The variable hashdata contains information about the hash value for the current position (see Hashing).

These variables should never be manipulated directly, since they are only the front end for the incremental machinery. They can be read, but should only be written by using the functions described in the next section. If you write directly to them, the incremental data structures will become out of sync with each other, and a crash is the likely result.

The Board Array
===============

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.

The advantage of a one-dimensional board array is that it gives a significant performance advantage. We need only one variable to determine a board position, which means that many functions need less arguments. Also, often one computation is sufficient for 1D-coordinate where we would need two with two 2D-coordinates: If we, for example, want to have the coordinate of the upper right of pos, we can do this with NORTH(EAST(pos)) instead of (i+1, j-1).

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

Incremental Board data structures
=================================

In addition to the global board state, the algorithms in board.c implement a method of incremental updates that keeps track of the following information for each string:

  * The color of the string.

  * Number of stones in the string.

  * Origin of the string, i.e. a canonical reference point, defined to be the stone with smallest 1D board coordinate.

  * A list of the stones in the string.

  * Number of liberties.

  * A list of the liberties. If there are too many liberties the list is truncated.

  * The number of neighbor strings.

  * A list of the neighbor strings.

The basic data structure is

     struct string_data {
       int color;                       /* Color of string, BLACK or WHITE */
       int size;                        /* Number of stones in string. */
       int origin;                      /* Coordinates of "origin", i.e. */
                                        /* "upper left" stone. */
       int liberties;                   /* Number of liberties. */
       int libs[MAX_LIBERTIES];         /* Coordinates of liberties. */
       int neighbors;                   /* Number of neighbor strings */
       int neighborlist[MAXCHAIN];      /* List of neighbor string numbers. */
       int mark;                        /* General purpose mark. */
     };

     struct string_data string[MAX_STRINGS];

It should be clear that almost all information is stored in the string array. To get a mapping from the board coordinates to the string array we have

     static int string_number[BOARDMAX];

which contains indices into the string array. This information is only valid at nonempty vertices, however, so it is necessary to first verify that board[pos] != EMPTY.

The string_data structure does not include an array of the stone coordinates. This information is stored in a separate array:

     static int next_stone[BOARDMAX];

This array implements cyclic linked lists of stones. Each vertex contains a pointer to another (possibly the same) vertex. Starting at an arbitrary stone on the board, following these pointers should traverse the entire string in an arbitrary order before coming back to the starting point. As for the 'string_number' array, this information is invalid at empty points on the board. This data structure has the good properties of requiring fixed space (regardless of the number of strings) and making it easy to add a new stone or join two strings.

Additionally the code makes use of some work variables:

     static int ml[BOARDMAX];
     static int liberty_mark;
     static int string_mark;
     static int next_string;
     static int strings_initialized = 0;

The ml array and liberty_mark are used to "mark" liberties on the board, e.g. to avoid counting the same liberty twice. The convention is that if ml[pos] has the same value as liberty_mark, then pos is marked. To clear all marks it suffices to increase the value of liberty_mark, since it is never allowed to decrease.

The same relation holds between the mark field of the string_data structure and string_mark. Of course these are used for marking individual strings.

next_string gives the number of the next available entry in the string array. Then strings_initialized is set to one when all data structures are known to be up to date. Given an arbitrary board position in the board array, this is done by calling incremental_board_init(). It is not necessary to call this function explicitly since any other function that needs the information does this if it has not been done.

The interesting part of the code is the incremental update of the data structures when a stone is played and subsequently removed. To understand the strategies involved in adding a stone it is necessary to first know how undoing a move works. The idea is that as soon as some piece of information is about to be changed, the old value is pushed onto a stack which stores the value and its address. The stack is built from the following structures:

     struct change_stack_entry {
       int *address;
       int value;
     };

     struct change_stack_entry change_stack[STACK_SIZE];
     int change_stack_index;

and manipulated with the macros

     BEGIN_CHANGE_RECORD()
     PUSH_VALUE(v)
     POP_MOVE()

Calling BEGIN_CHANGE_RECORD() stores a null pointer in the address field to indicate the start of changes for a new move. As mentioned earlier PUSH_VALUE() stores a value and its corresponding address. Assuming that all changed information has been duly pushed onto the stack, undoing the move is only a matter of calling POP_MOVE(), which simply assigns the values to the addresses in the reverse order until the null pointer is reached. This description is slightly simplified because this stack can only store 'int' values and we need to also store changes to the board. Thus we have two parallel stacks where one stores int values and the other one stores Intersection values.

When a new stone is played on the board, first captured opponent strings, if any, are removed. In this step we have to push the board values and the next_stone pointers for the removed stones, and update the liberties and neighbor lists for the neighbors of the removed strings. We do not have to push all information in the 'string' entries of the removed strings however. As we do not reuse the entries they will remain intact until the move is pushed and they are back in use.

After this we put down the new stone and get three distinct cases:

 1. The new stone is isolated, i.e. it has no friendly neighbor.

 2. The new stone has exactly one friendly neighbor.

 3. The new stone has at least two friendly neighbors.

The first case is easiest. Then we create a new string by using the number given by next_string and increasing this variable. The string will have size one, next_stone points directly back on itself, the liberties can be found by looking for empty points in the four directions, possible neighbor strings are found in the same way, and those need also to remove one liberty and add one neighbor.

In the second case we do not create a new string but extend the neighbor with the new stone. This involves linking the new stone into the cyclic chain, if needed moving the origin, and updating liberties and neighbors. Liberty and neighbor information also needs updating for the neighbors of the new stone.

In the third case finally, we need to join already existing strings. In order not to have to store excessive amounts of information, we create a new string for the new stone and let it assimilate the neighbor strings. Thus all information about those can simply be left around in the 'string' array, exactly as for removed strings. Here it becomes a little more complex to keep track of liberties and neighbors since those may have been shared by more than one of the joined strings. Making good use of marks it all becomes rather straightforward anyway.

The often used construction

         pos = FIRST_STONE(s);
         do {
             ...
             pos = NEXT_STONE(pos);
         } while (!BACK_TO_FIRST_STONE(s, pos));

traverses the stones of the string with number s exactly once, with pos holding the coordinates. In general pos is used as board coordinate and s as an index into the string array or sometimes a pointer to an entry in the string array.

Some Board Functions
====================

Reading, often called search in computer game theory, is a fundamental process in GNU Go. This is the process of generating hypothetical future boards in order to determine the answer to some question, for example "can these stones live." Since these are hypothetical future positions, it is important to be able to undo them, ultimately returning to the present board. Thus a move stack is maintained during reading. When a move is tried, by the function trymove, or its variant tryko. This function pushes the current board on the stack and plays a move. The stack pointer stackp, which keeps track of the position, is incremented. The function popgo() pops the move stack, decrementing stackp and undoing the last move made.

Every successful trymove() must be matched with a popgo(). Thus the correct way of using this function is:

       if (trymove(pos, color, ... )) {
            ...    [potentially lots of code here]
            popgo();
       }

In case the move is a ko capture, the legality of the capture is subject to the komaster scheme (see Ko).

  * int trymove(int pos, int color, const char *message)

          Returns true if (pos) is a legal move for color. In that case, it pushes the board on the stack and makes the move, incrementing stackp. If the reading code is recording reading variations (as with --decide-string or with -o), the string *message will be inserted in the SGF file as a comment. The comment will also refer to the string at str if this is not 0. The value of str can be NO_MOVE if it is not needed but otherwise the location of str is included in the comment.

  * int tryko(int pos, int color, const char *message)

          tryko() pushes the position onto the stack, and makes a move pos of color. The move is allowed even if it is an illegal ko capture. It is to be imagined that color has made an intervening ko threat which was answered and now the continuation is to be explored. Return 1 if the move is legal with the above caveat. Returns zero if it is not legal because of suicide.

  * void popgo()

          Pops the move stack. This function must (eventually) be called after a succesful trymove or tryko to restore the board position. It undoes all the changes done by the call to trymove/tryko and leaves the board in the same state as it was before the call.

          NOTE: If trymove/tryko returns 0, i.e. the tried move was not legal, you must not call popgo.

  * int komaster_trymove(int pos, int color, const char *message, int str, int *is_conditional_ko, int consider_conditional_ko)

          Variation of trymove/tryko where ko captures (both conditional and unconditional) must follow a komaster scheme (see Ko).

As you see, trymove() plays a move which can be easily retracted (with popgo()) and it is call thousands of times per actual game move as GNU Go analyzes the board position. By contrast the function play_move() plays a move which is intended to be permanent, though it is still possible to undo it if, for example, the opponent retracts a move.

  * void play_move(int pos, int color)

          Play a move. If you want to test for legality you should first call is_legal(). This function strictly follows the algorithm:

           1. Place a stone of given color on the board.

           2. If there are any adjacent opponent strings without liberties, remove them and increase the prisoner count.

           3. If the newly placed stone is part of a string without liberties, remove it and increase the prisoner count.

          In spite of the name ``permanent move'', this move can (usually) be unplayed by undo_move(), but it is significantly more costly than unplaying a temporary move. There are limitations on the available move history, so under certain circumstances the move may not be possible to unplay at a later time.

  * int undo_move(int n)

          Undo n permanent moves. Returns 1 if successful and 0 if it fails. If n moves cannot be undone, no move is undone.

Other board functions are documented in see Board Utilities.