Updated README: Equal sign not required with `--mode` flag.

[sgk-go] / doc / board.texi

@menu
* Board Data Structures::      Board Data Structures
* The Board Array::	       One-dimensional board array
* Incremental Board::	  	Incremental board data structures
* Some Board Functions::      	Explanation of some board functions
@end menu

The foundation of the GNU Go engine is a library of very efficient
routines for handling go boards.  This board library, called
@file{libboard}, can be used for those programs that only need a
basic go board but no AI capability. One such program is
@file{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:

@itemize
@item @file{board.h}
@quotation
The public interface to the board library.
@end quotation

@item @file{board.c}
@quotation
The basic board code. It uses incremental algorithms for keeping track
of strings and liberties on the go board.
@end quotation

@item @file{boardlib.c}
@quotation
This contains all global variable of the board library.
@end quotation

@item @file{hash.c}
@quotation
Code for hashing go positions.
@end quotation

@item @file{sgffile.c}
@quotation
Implementation of output file in SGF format.
@end quotation

@item @file{printutils.c}
@quotation
Utilities for printing go boards and other things.
@end quotation

@end itemize

To use the board library, you must include @file{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 @code{libboard.a}.

@node Board Data Structures
@section Board Data structures

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

@example
@group

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

float         komi;
int           white_captured;
int           black_captured;

Hash_data     hashdata;
@end group
@end example

The description of the @code{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 
(@pxref{Incremental Board}). The variable @code{hashdata} contains information
about the hash value for the current position (@pxref{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. 

@node The Board Array
@section The Board Array

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

The @code{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.

@example
@group
  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
@end group
@end example

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

@example
#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)
@end example

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

@example
@group
  j  -1   0   1   2   3   4   5   6
i +----------------------------------
-1|   #   #   #   #   #   #   #   #
 0|   #   .   .   .   .   .   .   .
 1|   #   .   .   .   .   .   .   .
 2|   #   .   .   .   .   .   .   .
 3|   #   .   .   .   .   .   .   .
 4|   #   .   .   .   .   .   .   .
 5|   #   .   .   .   .   .   .   .
 6|   #   .   .   .   .   .   .   .
 7|   #   #   #   #   #   #   #   #   #
@end group
@end example

The indices marked @samp{#} have value @code{GRAY}.
If @code{MAX_BOARD} is 7 and @code{board_size} is only 5:

@example
@group
  j  -1   0   1   2   3   4   5   6
i +----------------------------------
-1|   #   #   #   #   #   #   #   #
 0|   #   .   .   .   .   .   #   #
 1|   #   .   .   .   .   .   #   #
 2|   #   .   .   .   .   .   #   #
 3|   #   .   .   .   .   .   #   #
 4|   #   .   .   .   .   .   #   #
 5|   #   #   #   #   #   #   #   #
 6|   #   #   #   #   #   #   #   #
 7|   #   #   #   #   #   #   #   #   #
@end group
@end example

Navigation on the board is done by the @code{SOUTH}, @code{WEST},
@code{NORTH}, and @code{EAST} macros,

@example
#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)
@end example

There are also shorthand macros @code{SW}, @code{NW}, @code{NE},
@code{SE}, @code{SS}, @code{WW}, @code{NN}, @code{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

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

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 @code{pos}, we can do this with
@code{NORTH(EAST(pos))} instead of @code{(i+1, j-1)}.

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

A loop over multiple directions is straightforwardly written:

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

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

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

@code{BOARDSIZE} is the actual size of the 1D board array,
@code{BOARDMIN} is the first index corresponding to a point on the
board, and @code{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:

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

Or:

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


@node Incremental Board
@section Incremental Board data structures

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

@itemize @bullet
@item The color of the string.
@item Number of stones in the string.
@item Origin of the string, i.e. a canonical reference point, defined
to be the stone with smallest 1D board coordinate.
@item A list of the stones in the string.
@item Number of liberties.
@item A list of the liberties. If there are too many liberties the list is
truncated.
@item The number of neighbor strings.
@item A list of the neighbor strings.
@end itemize

The basic data structure is

@example
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];
@end example

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

@example
static int string_number[BOARDMAX];
@end example

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

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

@example
static int next_stone[BOARDMAX];
@end example

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:

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

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

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

@code{next_string} gives the number of the next available entry in the
@code{string} array. Then @code{strings_initialized} is set to one when
all data structures are known to be up to date. Given an arbitrary board
position in the @samp{board} array, this is done by calling
@code{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:

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

struct change_stack_entry change_stack[STACK_SIZE];
int change_stack_index;
@end example

@noindent
and manipulated with the macros

@example
BEGIN_CHANGE_RECORD()
PUSH_VALUE(v)
POP_MOVE()
@end example

Calling @code{BEGIN_CHANGE_RECORD()} stores a null pointer in the address
field to indicate the start of changes for a new move. As mentioned
earlier @code{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 @code{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 @code{int} values and the other one stores
@code{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 @code{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:

@enumerate
@item The new stone is isolated, i.e. it has no friendly neighbor.
@item The new stone has exactly one friendly neighbor.
@item The new stone has at least two friendly neighbors.
@end enumerate

The first case is easiest. Then we create a new string by using the
number given by @code{next_string} and increasing this variable. The string
will have size one, @code{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

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

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

@node Some Board Functions
@section Some Board Functions

@strong{Reading}, often called @strong{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 @code{trymove}, or its
variant @code{tryko}. This function pushes the current board
on the stack and plays a move. The stack pointer @code{stackp},
which keeps track of the position, is incremented. The function
@code{popgo()} pops the move stack, decrementing @code{stackp} and
undoing the last move made.

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

@example
@group

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

@end group
@end example

@noindent

In case the move is a ko capture, the legality of the capture is subject to
the komaster scheme (@pxref{Ko}).

@itemize @bullet
@item @code{int trymove(int pos, int color, const char *message)}
@findex trymove
@quotation
Returns true if @code{(pos)} is a legal move for @code{color}. In that
case, it pushes the board on the stack and makes the move, incrementing
@code{stackp}. If the reading code is recording reading variations (as
with @option{--decide-string} or with @option{-o}), the string
@code{*message} will be inserted in the SGF file as a comment. The
comment will also refer to the string at @code{str} if this is not
@code{0}. The value of @code{str} can be NO_MOVE if it is not needed but
otherwise the location of @code{str} is included in the comment.
@end quotation
@item @code{int tryko(int pos, int color, const char *message)}
@findex tryko
@quotation
@code{tryko()} pushes the position onto the stack, and makes a move
@code{pos} of @code{color}. The move is allowed even if it is an
illegal ko capture. It is to be imagined that @code{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.
@end quotation

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

@strong{NOTE}: If @code{trymove/tryko} returns @code{0}, i.e. the tried
move was not legal, you must @strong{not} call @code{popgo}.
@end quotation

@item @code{int komaster_trymove(int pos, int color, const char *message, int str, int *is_conditional_ko, int consider_conditional_ko)}
@findex komaster_trymove
@quotation
Variation of @code{trymove}/@code{tryko} where ko captures (both
conditional and unconditional) must follow a komaster scheme
(@pxref{Ko}).
@end quotation

@end itemize

As you see, @code{trymove()} plays a move which can be easily
retracted (with @code{popgo()}) and it is call thousands of
times per actual game move as GNU Go analyzes the board position.
By contrast the function @code{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.

@itemize @bullet
@item @code{void play_move(int pos, int color)}
@findex play_move
@quotation
Play a move. If you want to test for legality you should first call
@code{is_legal()}. This function strictly follows the algorithm: 
@enumerate
@item Place a stone of given color on the board.
@item If there are any adjacent opponent strings without liberties,
remove them and increase the prisoner count. 
@item If the newly placed stone is part of a string without liberties,
remove it and increase the prisoner count.
@end enumerate
In spite of the name ``permanent move'', this move can (usually) be
unplayed by @code{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.
@end quotation
@item @code{int undo_move(int n)}
@findex undo_move
@quotation
Undo @samp{n} permanent moves. Returns 1 if successful and 0 if it fails.
If @samp{n} moves cannot be undone, no move is undone.
@end quotation
@end itemize

Other board functions are documented in @xref{Board Utilities}.