/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
* http://www.gnu.org/software/gnugo/ for more information. *
* Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
* 2008 and 2009 by the Free Software Foundation. *
* This program is free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License as *
* published by the Free Software Foundation - version 3 or *
* (at your option) any later version. *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License in file COPYING for more details. *
* You should have received a copy of the GNU General Public *
* License along with this program; if not, write to the Free *
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor, *
* Boston, MA 02111, USA. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* The functions in this file implements a go board with incremental
* update of strings and liberties.
* See the Texinfo documentation (Utility Functions: Incremental Board)
/* This can be used for internal checks w/in board.c that should
* typically not be necessary (for speed).
#define PARANOID1(x, pos) ASSERT1(x, pos)
#define PARANOID1(x, pos)
/* ================================================================ */
/* ================================================================ */
/* Incremental 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 neighbors
; /* Number of neighbor strings */
int mark
; /* General purpose mark. */
struct string_liberties_data
{
int list
[MAX_LIBERTIES
]; /* Coordinates of liberties. */
struct string_neighbors_data
{
int list
[MAXCHAIN
]; /* List of neighbor string numbers. */
/* we keep the address and the old value */
struct change_stack_entry
{
/* we keep the address and the old value */
struct vertex_stack_entry
{
/* Experimental results show that the average number of change stack
* entries per move usually is in the 20-30 range and very seldom
* exceeds 40. But since we have no way to recover from running out of
* stack space, we allocate with a substantial safety margin.
#define STACK_SIZE 80 * MAXSTACK
#define CLEAR_STACKS() do { \
change_stack_pointer = change_stack; \
vertex_stack_pointer = vertex_stack; \
VALGRIND_MAKE_WRITABLE(change_stack, sizeof(change_stack)); \
VALGRIND_MAKE_WRITABLE(vertex_stack, sizeof(vertex_stack)); \
/* Begin a record : address == NULL */
#define BEGIN_CHANGE_RECORD()\
((change_stack_pointer++)->address = NULL,\
(vertex_stack_pointer++)->address = NULL)
/* Save a value : store the address and the value in the stack */
(change_stack_pointer->address = &(v),\
(change_stack_pointer++)->value = (v))
/* Save a board value : store the address and the value in the stack */
(vertex_stack_pointer->address = &(v),\
(vertex_stack_pointer++)->value = (v))
while ((--change_stack_pointer)->address)\
*(change_stack_pointer->address) =\
change_stack_pointer->value
while ((--vertex_stack_pointer)->address)\
*(vertex_stack_pointer->address) =\
vertex_stack_pointer->value
/* ================================================================ */
/* static data structures */
/* ================================================================ */
/* Main array of string information. */
static struct string_data string
[MAX_STRINGS
];
static struct string_liberties_data string_libs
[MAX_STRINGS
];
static struct string_neighbors_data string_neighbors
[MAX_STRINGS
];
/* Stacks and stack pointers. */
static struct change_stack_entry change_stack
[STACK_SIZE
];
static struct change_stack_entry
*change_stack_pointer
;
static struct vertex_stack_entry vertex_stack
[STACK_SIZE
];
static struct vertex_stack_entry
*vertex_stack_pointer
;
/* Index into list of strings. The index is only valid if there is a
static int string_number
[BOARDMAX
];
/* The stones in a string are linked together in a cyclic list.
* These are the coordinates to the next stone in the string.
static int next_stone
[BOARDMAX
];
/* ---------------------------------------------------------------- */
/* Macros to traverse the stones of a string.
* } while (!BACK_TO_FIRST_STONE(s, pos));
#define NEXT_STONE(pos) \
#define BACK_TO_FIRST_STONE(s, pos) \
((pos) == string[s].origin)
/* Assorted useful macros.
* Some of them could have been functions but are implemented as
#define UNMARKED_LIBERTY(pos) \
(board[pos] == EMPTY && ml[pos] != liberty_mark)
#define MARK_LIBERTY(pos) \
#define UNMARKED_STRING(pos) \
(string[string_number[pos]].mark != string_mark)
/* Note that these two macros are not complementary. Both return
* false if board[pos] != color.
#define UNMARKED_COLOR_STRING(pos, color)\
&& string[string_number[pos]].mark != string_mark)
#define MARKED_COLOR_STRING(pos, color)\
&& string[string_number[pos]].mark == string_mark)
#define MARK_STRING(pos) string[string_number[pos]].mark = string_mark
#define STRING_AT_VERTEX(pos, s, color)\
((board[pos] == color) && string_number[pos] == (s))
#define NEIGHBOR_OF_STRING(pos, s, color)\
(STRING_AT_VERTEX(SOUTH(pos), s, color)\
|| STRING_AT_VERTEX(WEST(pos), s, color)\
|| STRING_AT_VERTEX(NORTH(pos), s, color)\
|| STRING_AT_VERTEX(EAST(pos), s, color))
/* These four macros have rather confusing names. It should be read as:
* "(pos) is a neighbor of string (s) of (color) in any direction except
#define NON_SOUTH_NEIGHBOR_OF_STRING(pos, s, color)\
(STRING_AT_VERTEX(SOUTH(pos), s, color)\
|| STRING_AT_VERTEX(WEST(pos), s, color)\
|| STRING_AT_VERTEX(EAST(pos), s, color))
#define NON_WEST_NEIGHBOR_OF_STRING(pos, s, color)\
(STRING_AT_VERTEX(WEST(pos), s, color)\
|| STRING_AT_VERTEX(NORTH(pos), s, color)\
|| STRING_AT_VERTEX(SOUTH(pos), s, color))
#define NON_NORTH_NEIGHBOR_OF_STRING(pos, s, color)\
(STRING_AT_VERTEX(NORTH(pos), s, color)\
|| STRING_AT_VERTEX(EAST(pos), s, color)\
|| STRING_AT_VERTEX(WEST(pos), s, color))
#define NON_EAST_NEIGHBOR_OF_STRING(pos, s, color)\
(STRING_AT_VERTEX(EAST(pos), s, color)\
|| STRING_AT_VERTEX(SOUTH(pos), s, color)\
|| STRING_AT_VERTEX(NORTH(pos), s, color))
string[string_number[pos]].liberties
#define COUNTSTONES(pos) \
string[string_number[pos]].size
#define ADD_LIBERTY(s, pos)\
if (string[s].liberties < MAX_LIBERTIES)\
string_libs[s].list[string[s].liberties] = pos;\
#define ADD_AND_MARK_LIBERTY(s, pos)\
if (string[s].liberties < MAX_LIBERTIES)\
string_libs[s].list[string[s].liberties] = pos;\
#define ADD_NEIGHBOR(s, pos)\
string_neighbors[s].list[string[s].neighbors++] = string_number[pos]
#define DO_ADD_STONE(pos, color)\
PUSH_VERTEX(board[pos]);\
hashdata_invert_stone(&board_hash, pos, color);\
#define DO_REMOVE_STONE(pos)\
PUSH_VERTEX(board[pos]);\
hashdata_invert_stone(&board_hash, pos, board[pos]);\
/* ---------------------------------------------------------------- */
/* Number of the next free string. */
/* For marking purposes. */
/* Forward declarations. */
static void really_do_trymove(int pos
, int color
);
static int do_trymove(int pos
, int color
, int ignore_ko
);
static void undo_trymove(void);
static int do_approxlib(int pos
, int color
, int maxlib
, int *libs
);
static int slow_approxlib(int pos
, int color
, int maxlib
, int *libs
);
static int do_accuratelib(int pos
, int color
, int maxlib
, int *libs
);
static int is_superko_violation(int pos
, int color
, enum ko_rules type
);
static void new_position(void);
static int propagate_string(int stone
, int str
);
static void find_liberties_and_neighbors(int s
);
static int do_remove_string(int s
);
static void do_commit_suicide(int pos
, int color
);
static void do_play_move(int pos
, int color
);
static int komaster
, kom_pos
;
static int trymove_counter
= 0;
/* Coordinates for the eight directions, ordered
* south, west, north, east, southwest, northwest, northeast, southeast.
int deltai
[8] = { 1, 0, -1, 0, 1, -1, -1, 1};
int deltaj
[8] = { 0, -1, 0, 1, -1, -1, 1, 1};
int delta
[8] = { NS
, -1, -NS
, 1, NS
-1, -NS
-1, -NS
+1, NS
+1};
/* ================================================================ */
/* Board initialization */
/* ================================================================ */
store_board(struct board_state
*state
)
state
->board_size
= board_size
;
memcpy(state
->board
, board
, sizeof(board
));
memcpy(state
->initial_board
, initial_board
, sizeof(initial_board
));
state
->board_ko_pos
= board_ko_pos
;
state
->white_captured
= white_captured
;
state
->black_captured
= black_captured
;
state
->initial_board_ko_pos
= initial_board_ko_pos
;
state
->initial_white_captured
= initial_white_captured
;
state
->initial_black_captured
= initial_black_captured
;
state
->move_history_pointer
= move_history_pointer
;
for (k
= 0; k
< move_history_pointer
; k
++) {
state
->move_history_color
[k
] = move_history_color
[k
];
state
->move_history_pos
[k
] = move_history_pos
[k
];
state
->move_history_hash
[k
] = move_history_hash
[k
];
state
->handicap
= handicap
;
state
->move_number
= movenum
;
* Restore a saved board state.
restore_board(struct board_state
*state
)
board_size
= state
->board_size
;
memcpy(board
, state
->board
, sizeof(board
));
memcpy(initial_board
, state
->initial_board
, sizeof(initial_board
));
board_ko_pos
= state
->board_ko_pos
;
white_captured
= state
->white_captured
;
black_captured
= state
->black_captured
;
initial_board_ko_pos
= state
->initial_board_ko_pos
;
initial_white_captured
= state
->initial_white_captured
;
initial_black_captured
= state
->initial_black_captured
;
move_history_pointer
= state
->move_history_pointer
;
for (k
= 0; k
< move_history_pointer
; k
++) {
move_history_color
[k
] = state
->move_history_color
[k
];
move_history_pos
[k
] = state
->move_history_pos
[k
];
move_history_hash
[k
] = state
->move_history_hash
[k
];
handicap
= state
->handicap
;
movenum
= state
->move_number
;
hashdata_recalc(&board_hash
, board
, board_ko_pos
);
* Clear the internal board.
gg_assert(board_size
> 0 && board_size
<= MAX_BOARD
);
memset(board
, EMPTY
, sizeof(board
));
memset(initial_board
, EMPTY
, sizeof(initial_board
));
for (k
= 0; k
< BOARDSIZE
; k
++) {
if (!ON_BOARD2(I(k
), J(k
))) {
initial_board_ko_pos
= NO_MOVE
;
initial_white_captured
= 0;
initial_black_captured
= 0;
move_history_pointer
= 0;
hashdata_recalc(&board_hash
, board
, board_ko_pos
);
/* Test the integrity of the gray border. */
gg_assert(board_size
> 0 && board_size
<= MAX_BOARD
);
for (k
= 0; k
< BOARDSIZE
; k
++)
if (!ON_BOARD2(I(k
), J(k
)))
/* ================================================================ */
/* ================================================================ */
/* Stack of trial moves to get to current
* position and which color made them. Perhaps
* this should be one array of a structure
static int stack
[MAXSTACK
];
static int move_color
[MAXSTACK
];
static Hash_data board_hash_stack
[MAXSTACK
];
* trymove pushes the position onto the stack, and makes a move
* at pos of color. Returns one if the move is legal. The
* stack pointer is only incremented if the move is legal.
* The way to use this is:
* The message can be written as a comment to an sgf file using
* sgfdump(). str can be NO_MOVE if it is not needed but otherwise
* the location of str is included in the comment.
trymove(int pos
, int color
, const char *message
, int str
)
/* Do the real work elsewhere. */
if (!do_trymove(pos
, color
, 0))
/* Store the move in an sgf tree if one is available. */
gg_snprintf(buf
, 100, "%s (variation %d, hash %s, komaster %s:%s)",
message
, count_variations
, hashdata_to_string(&board_hash
),
color_to_string(komaster
), location_to_string(kom_pos
));
gg_snprintf(buf
, 100, "%s (variation %d, hash %s)", message
,
count_variations
, hashdata_to_string(&board_hash
));
"%s at %s (variation %d, hash %s, komaster %s:%s)",
message
, location_to_string(pos
), count_variations
,
hashdata_to_string(&board_hash
),
color_to_string(komaster
),
location_to_string(kom_pos
));
gg_snprintf(buf
, 100, "%s at %s (variation %d, hash %s)",
message
, location_to_string(pos
), count_variations
,
hashdata_to_string(&board_hash
));
sgftreeAddPlayLast(sgf_dumptree
, color
, I(pos
), J(pos
));
sgftreeAddComment(sgf_dumptree
, buf
);
* tryko pushes the position onto the stack, and makes a move
* at (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.
tryko(int pos
, int color
, const char *message
)
/* Do the real work elsewhere. */
if (!do_trymove(pos
, color
, 1))
gg_snprintf(buf
, 100, "tryko: %s (variation %d, %s, komaster %s:%s)",
message
, count_variations
, hashdata_to_string(&board_hash
),
color_to_string(komaster
), location_to_string(kom_pos
));
gg_snprintf(buf
, 100, "tryko: %s (variation %d, %s)", message
,
count_variations
, hashdata_to_string(&board_hash
));
/* Add two pass moves to the SGF output to simulate the ko threat
* The reason we add these is that certain SGF viewers, including
* Cgoban 1, won't properly display variations with illegal ko
* captures. SGF FF[4] compliant browsers should have no problem
sgftreeAddPlayLast(sgf_dumptree
, color
, -1, -1);
sgftreeAddComment(sgf_dumptree
, "tenuki (ko threat)");
sgftreeAddPlayLast(sgf_dumptree
, OTHER_COLOR(color
), -1, -1);
sgftreeAddComment(sgf_dumptree
, "tenuki (answers ko threat)");
sgftreeAddPlayLast(sgf_dumptree
, color
, I(pos
), J(pos
));
sgftreeAddComment(sgf_dumptree
, buf
);
/* Really, really make a temporary move. It is assumed that all
* necessary checks have already been made and likewise that various
* administrative bookkeeping outside of the actual board logic has
* either been done or is not needed.
really_do_trymove(int pos
, int color
)
PUSH_VALUE(board_ko_pos
);
* FIXME: Do we really have to store board_hash in a stack?
* Answer: No, we don't. But for every stone that we add
* or remove, we must call hashdata_invert_stone(). This is
* not difficult per se, but the whole board.c
* will have to be checked, and there is lots of room
* At the same time, profiling shows that storing the
* hashdata in a stack doesn't take a lot of time, so
* this is not an urgent FIXME.
memcpy(&board_hash_stack
[stackp
], &board_hash
, sizeof(board_hash
));
if (board_ko_pos
!= NO_MOVE
)
hashdata_invert_ko(&board_hash
, board_ko_pos
);
PUSH_VALUE(black_captured
);
PUSH_VALUE(white_captured
);
do_play_move(pos
, color
);
* Do the main work of trymove() and tryko(), i.e. the common parts.
* The ignore_ko flag tells whether an illegal ko capture may be done.
* Return 1 if the move was valid, otherwise 0.
do_trymove(int pos
, int color
, int ignore_ko
)
/* 1. The color must be BLACK or WHITE. */
gg_assert(color
== BLACK
|| color
== WHITE
);
/* 2. Unless pass, the move must be inside the board. */
/* Update the reading tree shadow. */
/* 3. The location must be empty. */
/* 4. The location must not be the ko point, unless ignore_ko == 1. */
if (!ignore_ko
&& pos
== board_ko_pos
) {
if (board
[WEST(pos
)] == OTHER_COLOR(color
)
|| board
[EAST(pos
)] == OTHER_COLOR(color
)) {
/* 5. Test for suicide. */
if (is_suicide(pos
, color
))
/* Check for stack overflow. */
if (stackp
>= MAXSTACK
-2) {
"gnugo: Truncating search. This is beyond my reading ability!\n");
/* FIXME: Perhaps it's best to just assert here and be done with it? */
ASSERT1(0 && "trymove stack overflow", pos
);
/* Only count trymove when we do create a new position. */
/* So far, so good. Now push the move on the move stack. These are
* needed for dump_stack().
move_color
[stackp
] = color
;
really_do_trymove(pos
, color
);
* popgo pops the position from the stack.
/* FIXME: Change the sgfGet*Property() interface so that either
* "C" instead of "C " works or the SGFXX symbols are used.
if (sgfGetCharProperty(sgf_dumptree
->lastnode
, "C ", &sgf_comment
)
&& strncmp(sgf_comment
, "tryko:", 6) == 0)
gg_snprintf(buf
, 100, "(next variation: %d)", count_variations
);
sgftreeAddComment(sgf_dumptree
, buf
);
sgf_dumptree
->lastnode
= sgf_dumptree
->lastnode
->parent
;
/* After tryko() we need to undo two pass nodes too. */
sgf_dumptree
->lastnode
= sgf_dumptree
->lastnode
->parent
->parent
;
/* Restore board state to the position before the last move. This is
* accomplished by popping everything that was stored on the stacks
* since the last BEGIN_CHANGE_RECORD(). Also stackp is decreased and
* board hash is restored from stack.
* This undoes the effects of do_trymove() or really_do_trymove() and
* is appropriate to call instead of popgo() if you have not passed
* through trymove() or tryko().
gg_assert(change_stack_pointer
- change_stack
<= STACK_SIZE
);
gprintf("Change stack size = %d\n", change_stack_pointer
- change_stack
);
gprintf("Vertex stack size = %d\n", vertex_stack_pointer
- vertex_stack
);
memcpy(&board_hash
, &(board_hash_stack
[stackp
]), sizeof(board_hash
));
* dump_stack() for use under gdb prints the move stack.
gprintf("%o (variation %d)", count_variations
-1);
gprintf("%o (%s)", hashdata_to_string(&board_hash
));
/* Bare bones of dump_stack(). */
for (n
= 0; n
< stackp
; n
++)
gprintf("%o%s:%1m ", move_color
[n
] == BLACK
? "B" : "W", stack
[n
]);
/* ================================================================ */
/* ================================================================ */
memcpy(initial_board
, board
, sizeof(board
));
initial_board_ko_pos
= board_ko_pos
;
initial_white_captured
= white_captured
;
initial_black_captured
= black_captured
;
move_history_pointer
= 0;
/* Place a stone on the board and update the board_hash. This operation
* destroys all move history.
add_stone(int pos
, int color
)
ASSERT1(stackp
== 0, pos
);
ASSERT1(board
[pos
] == EMPTY
, pos
);
hashdata_invert_stone(&board_hash
, pos
, color
);
/* Remove a stone from the board and update the board_hash. This
* operation destroys the move history.
ASSERT1(stackp
== 0, pos
);
ASSERT1(IS_STONE(board
[pos
]), pos
);
hashdata_invert_stone(&board_hash
, pos
, board
[pos
]);
/* Play a move. Basically the same as play_move() below, but doesn't store
* the move in history list.
* Set `update_internals' to zero if you want to play several moves in a
* row to avoid overhead caused by new_position(). Don't forget to call
* it yourself after all the moves have been played.
play_move_no_history(int pos
, int color
, int update_internals
)
/* Check the hash table to see if it corresponds to the cumulative one. */
hashdata_recalc(&oldkey
, board
, board_ko_pos
);
gg_assert(hashdata_is_equal(oldkey
, board_hash
));
if (board_ko_pos
!= NO_MOVE
)
hashdata_invert_ko(&board_hash
, board_ko_pos
);
/* If the move is a pass, we can skip some steps. */
ASSERT1(board
[pos
] == EMPTY
, pos
);
if (!is_suicide(pos
, color
))
do_play_move(pos
, color
);
do_commit_suicide(pos
, color
);
/* Check the hash table to see if it equals the previous one. */
hashdata_recalc(&oldkey
, board
, board_ko_pos
);
gg_assert(hashdata_is_equal(oldkey
, board_hash
));
if (update_internals
|| next_string
== MAX_STRINGS
)
/* Load the initial position and replay the first n moves. */
replay_move_history(int n
)
memcpy(board
, initial_board
, sizeof(board
));
board_ko_pos
= initial_board_ko_pos
;
white_captured
= initial_white_captured
;
black_captured
= initial_black_captured
;
play_move_no_history(move_history_pos
[k
], move_history_color
[k
], 0);
/* 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.
play_move(int pos
, int color
)
ASSERT1(stackp
== 0, pos
);
ASSERT1(color
== WHITE
|| color
== BLACK
, pos
);
ASSERT1(pos
== PASS_MOVE
|| ON_BOARD1(pos
), pos
);
ASSERT1(pos
== PASS_MOVE
|| board
[pos
] == EMPTY
, pos
);
ASSERT1(komaster
== EMPTY
&& kom_pos
== NO_MOVE
, pos
);
if (move_history_pointer
>= MAX_MOVE_HISTORY
) {
/* The move history is full. We resolve this by collapsing the
* first about 10% of the moves into the initial position.
int number_collapsed_moves
= 1 + MAX_MOVE_HISTORY
/ 10;
Intersection saved_board
[BOARDSIZE
];
int saved_board_ko_pos
= board_ko_pos
;
int saved_white_captured
= white_captured
;
int saved_black_captured
= black_captured
;
memcpy(saved_board
, board
, sizeof(board
));
replay_move_history(number_collapsed_moves
);
memcpy(initial_board
, board
, sizeof(board
));
initial_board_ko_pos
= board_ko_pos
;
initial_white_captured
= white_captured
;
initial_black_captured
= black_captured
;
for (k
= number_collapsed_moves
; k
< move_history_pointer
; k
++) {
move_history_color
[k
- number_collapsed_moves
] = move_history_color
[k
];
move_history_pos
[k
- number_collapsed_moves
] = move_history_pos
[k
];
move_history_hash
[k
- number_collapsed_moves
] = move_history_hash
[k
];
move_history_pointer
-= number_collapsed_moves
;
memcpy(board
, saved_board
, sizeof(board
));
board_ko_pos
= saved_board_ko_pos
;
white_captured
= saved_white_captured
;
black_captured
= saved_black_captured
;
move_history_color
[move_history_pointer
] = color
;
move_history_pos
[move_history_pointer
] = pos
;
move_history_hash
[move_history_pointer
] = board_hash
;
if (board_ko_pos
!= NO_MOVE
)
hashdata_invert_ko(&move_history_hash
[move_history_pointer
], board_ko_pos
);
play_move_no_history(pos
, color
, 1);
/* Undo n permanent moves. Returns 1 if successful and 0 if it fails.
* If n moves cannot be undone, no move is undone.
/* Fail if and only if the move history is too short. */
if (move_history_pointer
< n
)
replay_move_history(move_history_pointer
- n
);
move_history_pointer
-= n
;
/* Return the last move done by the opponent to color. Both if no move
* was found or if the last move was a pass, PASS_MOVE is returned.
get_last_opponent_move(int color
)
for (k
= move_history_pointer
- 1; k
>= 0; k
--)
if (move_history_color
[k
] == OTHER_COLOR(color
))
return move_history_pos
[k
];
/* Return the last move done by anyone. Both if no move was found or
* if the last move was a pass, PASS_MOVE is returned.
if (move_history_pointer
== 0)
return move_history_pos
[move_history_pointer
- 1];
/* Return the color of the player doing the last move. If no move was
* found, EMPTY is returned.
if (move_history_pointer
== 0)
return move_history_color
[move_history_pointer
- 1];
/* ================================================================ */
/* ================================================================ */
* Test if the move is a pass or not. Return 1 if it is.
* is_legal(pos, color) determines whether the move (color) at pos is
* legal. This is for internal use in the engine and always assumes
* that suicide is allowed and only simple ko restrictions, no
* superko, regardless of the rules actually used in the game.
* Use is_allowed_move() if you want to take alternative suicide and
is_legal(int pos
, int color
)
/* 0. A pass move is always legal. */
/* 1. The move must be inside the board. */
/* 2. The location must be empty. */
/* 3. The location must not be the ko point. */
if (pos
== board_ko_pos
) {
/* The ko position is guaranteed to have all neighbors of the
* same color, or off board. If that color is the same as the
* move the ko is being filled, which is always allowed. This
* could be tested with has_neighbor() but here a faster test
if (board
[WEST(pos
)] == OTHER_COLOR(color
)
|| board
[EAST(pos
)] == OTHER_COLOR(color
)) {
/* Check for stack overflow. */
if (stackp
>= MAXSTACK
-2) {
"gnugo: Truncating search. This is beyond my reading ability!\n");
/* FIXME: Perhaps it's best to just assert here and be done with it? */
ASSERT1(0 && "is_legal stack overflow", pos
);
if (is_suicide(pos
, color
))
* is_suicide(pos, color) determines whether the move (color) at
* (pos) would be a suicide.
* 1. There is no neighboring empty intersection.
* 2. There is no neighboring opponent string with exactly one liberty.
* 3. There is no neighboring friendly string with more than one liberty.
is_suicide(int pos
, int color
)
ASSERT1(board
[pos
] == EMPTY
, pos
);
&& ((board
[SOUTH(pos
)] == color
) ^ (LIBERTIES(SOUTH(pos
)) == 1))))
&& ((board
[WEST(pos
)] == color
) ^ (LIBERTIES(WEST(pos
)) == 1))))
&& ((board
[NORTH(pos
)] == color
) ^ (LIBERTIES(NORTH(pos
)) == 1))))
&& ((board
[EAST(pos
)] == color
) ^ (LIBERTIES(EAST(pos
)) == 1))))
* is_illegal_ko_capture(pos, color) determines whether the move
* (color) at (pos) would be an illegal ko capture.
is_illegal_ko_capture(int pos
, int color
)
ASSERT1(board
[pos
] == EMPTY
, pos
);
return (pos
== board_ko_pos
&& ((board
[WEST(pos
)] == OTHER_COLOR(color
))
|| (board
[EAST(pos
)] == OTHER_COLOR(color
))));
* is_allowed_move(int pos, int color) determines whether a move is
* legal with respect to the suicide and ko rules in play.
* This function is only valid when stackp == 0 since there is no
* tracking of superko for trymoves.
is_allowed_move(int pos
, int color
)
/* 1. A pass move is always legal, no matter what. */
/* 2. The move must be inside the board. */
/* 3. The location must be empty. */
/* 4. Simple ko repetition is only allowed if no ko rule is in use.
* For superko rules this check is redundant.
* The ko position is guaranteed to have all neighbors of the
* same color, or off board. If that color is the same as the
* move the ko is being filled, which is always allowed. This
* could be tested with has_neighbor() but here a faster test
&& (board
[WEST(pos
)] == OTHER_COLOR(color
)
|| board
[EAST(pos
)] == OTHER_COLOR(color
)))
/* 5. Check for suicide. Suicide rule options:
* FORBIDDEN - No suicides allowed.
* ALLOWED - Suicide of more than one stone allowed.
* ALL_ALLOWED - All suicides allowed.
if (is_suicide(pos
, color
))
if (suicide_rule
== FORBIDDEN
|| (suicide_rule
== ALLOWED
&& !has_neighbor(pos
, color
)))
/* 6. Check for whole board repetitions. The superko options are
* SIMPLE, NONE - No superko restrictions.
* PSK - Repetition of a previous position forbidden.
* SSK - Repetition of a previous position with the same
* player to move forbidden.
if (is_superko_violation(pos
, color
, ko_rule
))
/* Necessary work to set the new komaster state. */
set_new_komaster(int new_komaster
)
hashdata_invert_komaster(&board_hash
, komaster
);
hashdata_invert_komaster(&board_hash
, komaster
);
/* Necessary work to set the new komaster position. */
set_new_kom_pos(int new_kom_pos
)
hashdata_invert_kom_pos(&board_hash
, kom_pos
);
hashdata_invert_kom_pos(&board_hash
, kom_pos
);
/* Variation of trymove()/tryko() where ko captures (both conditional
* and unconditional) must follow a komaster scheme.
* Historical note: Up to GNU Go 3.4 five different komaster schemes
* were implemented and could easily be switched between. In GNU Go
* 3.5.1 four of them were removed to simplify the code and because it
* no longer seemed interesting to be able to switch. The remaining
* komaster scheme was previously known as komaster scheme 5 (or V).
* FIXME: This function could be optimized by integrating the
* trymove()/tryko() code.
/* V. Complex scheme, O to move.
* 1a) Unconditional ko capture is allowed.
* Komaster remains EMPTY if previous move was not a ko capture.
* Komaster is set to WEAK_KO if previous move was a ko capture
* and kom_pos is set to the old value of board_ko_pos.
* 1b) Conditional ko capture is allowed. Komaster is set to O and
* kom_pos to the location of the ko, where a stone was
* 2a) Only nested ko captures are allowed. Kom_pos is moved to the
* 2b) If komaster fills the ko at kom_pos then komaster reverts to
* Play at kom_pos is not allowed. Any other ko capture
* is allowed. If O takes another ko, komaster becomes GRAY_X.
* 4. Komaster is GRAY_O or GRAY_X:
* Ko captures are not allowed. If the ko at kom_pos is
* filled then the komaster reverts to EMPTY.
* 5. Komaster is WEAK_KO:
* 5a) After a non-ko move komaster reverts to EMPTY.
* 5b) Unconditional ko capture is only allowed if it is nested ko capture.
* Komaster is changed to WEAK_X and kom_pos to the old value of
* 5c) Conditional ko capture is allowed according to the rules of 1b.
komaster_trymove(int pos
, int color
, const char *message
, int str
,
int *is_conditional_ko
, int consider_conditional_ko
)
int other
= OTHER_COLOR(color
);
int previous_board_ko_pos
= board_ko_pos
;
ko_move
= is_ko(pos
, color
, &kpos
);
/* If opponent is komaster we may not capture his ko. */
if (komaster
== other
&& pos
== kom_pos
)
/* If komaster is gray we may not capture ko at all. */
if (komaster
== GRAY_WHITE
|| komaster
== GRAY_BLACK
)
/* If we are komaster, we may only do nested captures. */
if (komaster
== color
&& !DIAGONAL_NEIGHBORS(kpos
, kom_pos
))
/* If komaster is WEAK_KO, we may only do nested ko capture or
* conditional ko capture.
if (komaster
== WEAK_KO
) {
if (pos
!= board_ko_pos
&& !DIAGONAL_NEIGHBORS(kpos
, kom_pos
))
if (!trymove(pos
, color
, message
, str
)) {
if (!consider_conditional_ko
)
if (!tryko(pos
, color
, message
))
/* Conditional ko capture, set komaster parameters. */
if (komaster
== EMPTY
|| komaster
== WEAK_KO
) {
/* If we are komaster, check whether the ko was resolved by the
* current move. If that is the case, revert komaster to EMPTY.
* The ko has been resolved in favor of the komaster if it has
* been filled, or if it is no longer a ko and an opponent move
|| (komaster
== GRAY_WHITE
&& color
== WHITE
)
|| (komaster
== GRAY_BLACK
&& color
== BLACK
))
&& (IS_STONE(board
[kom_pos
])
|| (!is_ko(kom_pos
, other
, NULL
)
&& is_suicide(kom_pos
, other
))))) {
set_new_kom_pos(NO_MOVE
);
if (komaster
== WEAK_KO
) {
set_new_kom_pos(NO_MOVE
);
set_new_komaster(GRAY_BLACK
);
set_new_komaster(GRAY_WHITE
);
else if (komaster
== color
) {
/* This is where we update kom_pos after a nested capture. */
/* We can reach here when komaster is EMPTY or WEAK_KO. If previous
* move was also a ko capture, we now set komaster to WEAK_KO.
if (previous_board_ko_pos
!= NO_MOVE
) {
set_new_komaster(WEAK_KO
);
set_new_kom_pos(previous_board_ko_pos
);
/* Determine whether vertex is on the edge. */
/* Distance to the edge. */
return gg_min(gg_min(i
, board_size
-1 - i
), gg_min(j
, board_size
-1 - j
));
/* Determine whether vertex is a corner. */
is_corner_vertex(int pos
)
if ((!ON_BOARD(WEST(pos
)) || !ON_BOARD(EAST(pos
)))
&& (!ON_BOARD(SOUTH(pos
)) || !ON_BOARD(NORTH(pos
))))
/* Reorientation of point pos. This function could have been
* implemented using the rotate() function in utils/gg_utils.c but we
* don't want to make libboard dependent on utils.
rotate1(int pos
, int rot
)
gg_assert(rot
>= 0 && rot
< 8);
return pos
; /* identity map */
return POS(bs
- j
, i
); /* rotation over 90 degrees */
return POS(bs
- i
, bs
- j
); /* rotation over 180 degrees */
return POS(j
, bs
- i
); /* rotation over 270 degrees */
return POS(j
, i
); /* flip along diagonal */
return POS(bs
- i
, j
); /* flip */
return POS(bs
- j
, bs
- i
); /* flip along diagonal */
return POS(i
, bs
- j
); /* flip */
return PASS_MOVE
; /* unreachable */
/* Returns true if the empty vertex respectively the string at pos1 is
* adjacent to the empty vertex respectively the string at pos2.
are_neighbors(int pos1
, int pos2
)
if (board
[pos1
] == EMPTY
) {
if (board
[pos2
] == EMPTY
)
return (gg_abs(pos1
- pos2
) == NS
|| gg_abs(pos1
- pos2
) == WE
);
return neighbor_of_string(pos1
, pos2
);
if (board
[pos2
] == EMPTY
)
return neighbor_of_string(pos2
, pos1
);
return adjacent_strings(pos1
, pos2
);
/* Count the number of liberties of the string at pos. pos must not be
ASSERT1(IS_STONE(board
[str
]), str
);
/* We already know the number of liberties. Just look it up. */
return string
[string_number
[str
]].liberties
;
/* Find the liberties of the string at str. str must not be
* empty. The locations of up to maxlib liberties are written into
* libs[]. The full number of liberties is returned.
* If you want the locations of all liberties, whatever their number,
* you should pass MAXLIBS as the value for maxlib and allocate space
* for libs[] accordingly.
findlib(int str
, int maxlib
, int *libs
)
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(libs
!= NULL
, str
);
/* We already have the list of liberties and only need to copy it to
* However, if the string has more than MAX_LIBERTIES liberties the
* list is truncated and if maxlib is also larger than MAX_LIBERTIES
* we have to traverse the stones in the string in order to find
* where the liberties are.
liberties
= string
[s
].liberties
;
if (liberties
<= MAX_LIBERTIES
|| maxlib
<= MAX_LIBERTIES
) {
/* The easy case, it suffices to copy liberty locations from the
* incrementally updated list.
for (k
= 0; k
< maxlib
&& k
< liberties
; k
++)
libs
[k
] = string_libs
[s
].list
[k
];
/* The harder case, where we have to traverse the stones in the
* string. We don't have to check explicitly if we are back to
* the start of the chain since we will run out of liberties
for (k
= 0, pos
= FIRST_STONE(s
);
k
< maxlib
&& k
< liberties
;
if (UNMARKED_LIBERTY(SOUTH(pos
))) {
MARK_LIBERTY(SOUTH(pos
));
if (UNMARKED_LIBERTY(WEST(pos
))) {
if (UNMARKED_LIBERTY(NORTH(pos
))) {
MARK_LIBERTY(NORTH(pos
));
if (UNMARKED_LIBERTY(EAST(pos
))) {
/* Count the liberties a stone of the given color would get if played
* at (pos). The location (pos) must be empty.
* The intent of this function is to be as fast as possible, not
* necessarily complete. But if it returns a positive value (meaning
* it has succeeded), the value is guaranteed to be correct.
* Captures are ignored based on the ignore_capture flag. The function
* fails if there are more than two neighbor strings of the same
* color. In this case, the return value is -1. Captures are handled
* in a very limited way, so if ignore_capture is 0, and a capture is
* required, it will often return -1.
* Note well, that it relies on incremental data.
fastlib(int pos
, int color
, int ignore_captures
)
ASSERT1(board
[pos
] == EMPTY
, pos
);
ASSERT1(IS_STONE(color
), pos
);
/* Find neighboring strings of the same color. If there are more than two of
* them, we give up (it's too difficult to count their common liberties).
if (board
[SOUTH(pos
)] == color
) {
ally1
= string_number
[SOUTH(pos
)];
if (board
[WEST(pos
)] == color
&& string_number
[WEST(pos
)] != ally1
) {
ally2
= string_number
[WEST(pos
)];
if (board
[NORTH(pos
)] == color
&& string_number
[NORTH(pos
)] != ally1
&& string_number
[NORTH(pos
)] != ally2
)
else if (board
[NORTH(pos
)] == color
&& string_number
[NORTH(pos
)] != ally1
)
ally2
= string_number
[NORTH(pos
)];
if (board
[EAST(pos
)] == color
&& string_number
[EAST(pos
)] != ally1
) {
ally2
= string_number
[EAST(pos
)];
else if (string_number
[EAST(pos
)] != ally2
)
else if (board
[WEST(pos
)] == color
) {
ally1
= string_number
[WEST(pos
)];
if (board
[NORTH(pos
)] == color
&& string_number
[NORTH(pos
)] != ally1
) {
ally2
= string_number
[NORTH(pos
)];
if (board
[EAST(pos
)] == color
&& string_number
[EAST(pos
)] != ally1
&& string_number
[EAST(pos
)] != ally2
)
else if (board
[EAST(pos
)] == color
&& string_number
[EAST(pos
)] != ally1
)
ally2
= string_number
[EAST(pos
)];
else if (board
[NORTH(pos
)] == color
) {
ally1
= string_number
[NORTH(pos
)];
if (board
[EAST(pos
)] == color
&& string_number
[EAST(pos
)] != ally1
)
ally2
= string_number
[EAST(pos
)];
else if (board
[EAST(pos
)] == color
)
ally1
= string_number
[EAST(pos
)];
/* If we are to ignore captures, the things are very easy. */
if (ally1
< 0) { /* No allies */
else if (ally2
< 0) { /* One ally */
&& !NON_SOUTH_NEIGHBOR_OF_STRING(SOUTH(pos
), ally1
, color
))
&& !NON_WEST_NEIGHBOR_OF_STRING(WEST(pos
), ally1
, color
))
&& !NON_NORTH_NEIGHBOR_OF_STRING(NORTH(pos
), ally1
, color
))
&& !NON_EAST_NEIGHBOR_OF_STRING(EAST(pos
), ally1
, color
))
fast_liberties
+= string
[ally1
].liberties
- 1;
&& !NON_SOUTH_NEIGHBOR_OF_STRING(SOUTH(pos
), ally1
, color
)
&& !NON_SOUTH_NEIGHBOR_OF_STRING(SOUTH(pos
), ally2
, color
))
&& !NON_WEST_NEIGHBOR_OF_STRING(WEST(pos
), ally1
, color
)
&& !NON_WEST_NEIGHBOR_OF_STRING(WEST(pos
), ally2
, color
))
&& !NON_NORTH_NEIGHBOR_OF_STRING(NORTH(pos
), ally1
, color
)
&& !NON_NORTH_NEIGHBOR_OF_STRING(NORTH(pos
), ally2
, color
))
&& !NON_EAST_NEIGHBOR_OF_STRING(EAST(pos
), ally1
, color
)
&& !NON_EAST_NEIGHBOR_OF_STRING(EAST(pos
), ally2
, color
))
fast_liberties
+= string
[ally1
].liberties
+ string
[ally2
].liberties
- count_common_libs(string
[ally1
].origin
, string
[ally2
].origin
) - 1;
/* We are to take captures into account. This case is much more rare, so
* it is not optimized much.
for (k
= 0; k
< 4; k
++) {
int neighbor
= pos
+ delta
[k
];
&& (ally1
< 0 || !NEIGHBOR_OF_STRING(neighbor
, ally1
, color
))
&& (ally2
< 0 || !NEIGHBOR_OF_STRING(neighbor
, ally2
, color
)))
else if (board
[neighbor
] == OTHER_COLOR(color
) /* A capture */
&& LIBERTIES(neighbor
) == 1) {
int neighbor_size
= COUNTSTONES(neighbor
);
if (neighbor_size
== 1 || (neighbor_size
== 2 && ally1
< 0))
fast_liberties
+= string
[ally1
].liberties
- 1;
fast_liberties
+= string
[ally2
].liberties
- count_common_libs(string
[ally1
].origin
, string
[ally2
].origin
);
/* Effectively true unless we store full position in hash. */
#define USE_BOARD_CACHES (NUM_HASHVALUES <= 4)
struct board_cache_entry
{
static struct board_cache_entry approxlib_cache
[BOARDMAX
][2];
/* Clears approxlib() cache. This function should be called only once
* during engine initialization. Sets thresholds to zero.
clear_approxlib_cache(void)
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
approxlib_cache
[pos
][0].threshold
= 0;
approxlib_cache
[pos
][1].threshold
= 0;
/* Find the liberties a stone of the given color would get if played
* at (pos), ignoring possible captures of opponent stones. (pos)
* must be empty. If libs != NULL, the locations of up to maxlib
* liberties are written into libs[]. The counting of liberties may
* or may not be halted when maxlib is reached. The number of liberties
* If you want the number or the locations of all liberties, however
* many they are, you should pass MAXLIBS as the value for maxlib and
* allocate space for libs[] accordingly.
approxlib(int pos
, int color
, int maxlib
, int *libs
)
struct board_cache_entry
*entry
= &approxlib_cache
[pos
][color
- 1];
ASSERT1(board
[pos
] == EMPTY
, pos
);
ASSERT1(IS_STONE(color
), pos
);
/* First see if this result is cached. */
if (hashdata_is_equal(board_hash
, entry
->position_hash
)
&& maxlib
<= entry
->threshold
) {
liberties
= fastlib(pos
, color
, 1);
/* Since fastlib() always returns precise result and doesn't take
* `maxlib' into account, we set threshold to MAXLIBS so that this
* result is used regardless of any `maxlib' passed.
entry
->threshold
= MAXLIBS
;
entry
->liberties
= liberties
;
entry
->position_hash
= board_hash
;
/* We initialize the cache entry threshold to `maxlib'. If do_approxlib()
* or slow_approxlib() finds all the liberties (that is, they don't use
* `maxlib' value for an early return), they will set threshold to
entry
->threshold
= maxlib
;
if (maxlib
<= MAX_LIBERTIES
)
liberties
= do_approxlib(pos
, color
, maxlib
, libs
);
liberties
= slow_approxlib(pos
, color
, maxlib
, libs
);
entry
->liberties
= liberties
;
entry
->position_hash
= board_hash
;
#else /* not USE_BOARD_CACHES */
ASSERT1(board
[pos
] == EMPTY
, pos
);
ASSERT1(IS_STONE(color
), pos
);
liberties
= fastlib(pos
, color
, 1);
if (maxlib
<= MAX_LIBERTIES
)
liberties
= do_approxlib(pos
, color
, maxlib
, libs
);
liberties
= slow_approxlib(pos
, color
, maxlib
, libs
);
#endif /* not USE_BOARD_CACHES */
/* Does the real work of approxlib(). */
do_approxlib(int pos
, int color
, int maxlib
, int *libs
)
/* Look for empty neighbors and the liberties of the adjacent
* strings of the given color. The algorithm below won't work
* correctly if any of the adjacent strings have more than
* MAX_LIBERTIES liberties AND maxlib is larger than MAX_LIBERTIES.
* therefore approxlib() calls more robust slow_approxlib() if
* this might be the case.
/* Start by marking pos itself so it isn't counted among its own
if (UNMARKED_LIBERTY(SOUTH(pos
))) {
libs
[liberties
] = SOUTH(pos
);
/* Stop counting if we reach maxlib. */
MARK_LIBERTY(SOUTH(pos
));
else if (board
[SOUTH(pos
)] == color
) {
int s
= string_number
[SOUTH(pos
)];
for (k
= 0; k
< string
[s
].liberties
; k
++) {
int lib
= string_libs
[s
].list
[k
];
if (UNMARKED_LIBERTY(lib
)) {
if (UNMARKED_LIBERTY(WEST(pos
))) {
libs
[liberties
] = WEST(pos
);
/* Stop counting if we reach maxlib. */
else if (board
[WEST(pos
)] == color
) {
int s
= string_number
[WEST(pos
)];
for (k
= 0; k
< string
[s
].liberties
; k
++) {
int lib
= string_libs
[s
].list
[k
];
if (UNMARKED_LIBERTY(lib
)) {
if (UNMARKED_LIBERTY(NORTH(pos
))) {
libs
[liberties
] = NORTH(pos
);
/* Stop counting if we reach maxlib. */
MARK_LIBERTY(NORTH(pos
));
else if (board
[NORTH(pos
)] == color
) {
int s
= string_number
[NORTH(pos
)];
for (k
= 0; k
< string
[s
].liberties
; k
++) {
int lib
= string_libs
[s
].list
[k
];
if (UNMARKED_LIBERTY(lib
)) {
if (UNMARKED_LIBERTY(EAST(pos
))) {
libs
[liberties
] = EAST(pos
);
/* Unneeded since we're about to leave. */
else if (board
[EAST(pos
)] == color
) {
int s
= string_number
[EAST(pos
)];
for (k
= 0; k
< string
[s
].liberties
; k
++) {
int lib
= string_libs
[s
].list
[k
];
if (UNMARKED_LIBERTY(lib
)) {
/* If we reach here, then we have counted _all_ the liberties, so
* we set threshold to MAXLIBS (the result is the same regardless
approxlib_cache
[pos
][color
- 1].threshold
= MAXLIBS
;
/* Find the liberties a move of the given color at pos would have,
* excluding possible captures, by traversing all adjacent friendly
* strings. This is a fallback used by approxlib() when a faster
* algorithm can't be used.
slow_approxlib(int pos
, int color
, int maxlib
, int *libs
)
for (k
= 0; k
< 4; k
++) {
if (UNMARKED_LIBERTY(pos
+ d
)) {
libs
[liberties
] = pos
+ d
;
else if (board
[pos
+ d
] == color
&& UNMARKED_STRING(pos
+ d
)) {
int s
= string_number
[pos
+ d
];
for (l
= 0; l
< 4; l
++) {
if (UNMARKED_LIBERTY(pos2
+ d2
)) {
libs
[liberties
] = pos2
+ d2
;
} while (!BACK_TO_FIRST_STONE(s
, pos2
));
/* If we reach here, then we have counted _all_ the liberties, so
* we set threshold to MAXLIBS (the result is the same regardless
approxlib_cache
[pos
][color
- 1].threshold
= MAXLIBS
;
/* accuratelib() cache. */
static struct board_cache_entry accuratelib_cache
[BOARDMAX
][2];
/* Clears accuratelib() cache. This function should be called only once
* during engine initialization. Sets thresholds to zero.
clear_accuratelib_cache(void)
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
accuratelib_cache
[pos
][0].threshold
= 0;
accuratelib_cache
[pos
][1].threshold
= 0;
/* Find the liberties a stone of the given color would get if played
* at (pos). This function takes into consideration all captures. Its
* return value is exact in that sense it counts all the liberties,
* unless (maxlib) allows it to stop earlier. (pos) must be empty. If
* libs != NULL, the locations of up to maxlib liberties are written
* into libs[]. The counting of liberties may or may not be halted
* when maxlib is reached. The number of found liberties is returned.
* This function guarantees that liberties which are not results of
* captures come first in libs[] array. To find whether all the
* liberties starting from a given one are results of captures, one
* may use if (board[libs[k]] != EMPTY) construction.
* If you want the number or the locations of all liberties, however
* many they are, you should pass MAXLIBS as the value for maxlib and
* allocate space for libs[] accordingly.
accuratelib(int pos
, int color
, int maxlib
, int *libs
)
struct board_cache_entry
*entry
= &accuratelib_cache
[pos
][color
- 1];
ASSERT1(board
[pos
] == EMPTY
, pos
);
ASSERT1(IS_STONE(color
), pos
);
/* First see if this result is cached. */
if (hashdata_is_equal(board_hash
, entry
->position_hash
)
&& maxlib
<= entry
->threshold
) {
liberties
= fastlib(pos
, color
, 0);
/* Since fastlib() always returns precise result and doesn't take
* `maxlib' into account, we set threshold to MAXLIBS so that this
* result is used regardless of any `maxlib' passed.
entry
->threshold
= MAXLIBS
;
entry
->liberties
= liberties
;
entry
->position_hash
= board_hash
;
liberties
= do_accuratelib(pos
, color
, maxlib
, libs
);
/* If accuratelib() found less than `maxlib' liberties, then its
* result is certainly independent of `maxlib' and we set threshold
entry
->threshold
= liberties
< maxlib
? MAXLIBS
: maxlib
;
entry
->liberties
= liberties
;
entry
->position_hash
= board_hash
;
#else /* not USE_BOARD_CACHES */
ASSERT1(board
[pos
] == EMPTY
, pos
);
ASSERT1(IS_STONE(color
), pos
);
liberties
= fastlib(pos
, color
, 0);
liberties
= do_accuratelib(pos
, color
, maxlib
, libs
);
#endif /* not USE_BOARD_CACHES */
/* Does the real work of accuratelib(). */
do_accuratelib(int pos
, int color
, int maxlib
, int *libs
)
for (k
= 0; k
< 4; k
++) {
int pos2
= pos
+ delta
[k
];
if (UNMARKED_LIBERTY(pos2
)) {
else if (UNMARKED_COLOR_STRING(pos2
, color
)) {
/* An own neighbor string */
struct string_data
*s
= &string
[string_number
[pos2
]];
struct string_liberties_data
*sl
= &string_libs
[string_number
[pos2
]];
if (s
->liberties
<= MAX_LIBERTIES
|| maxlib
<= MAX_LIBERTIES
- 1) {
/* The easy case - we already have all (necessary) liberties of
for (l
= 0; l
< s
->liberties
; l
++) {
if (UNMARKED_LIBERTY(lib
)) {
/* The harder case - we need to find all the liberties of the
* string by traversing its stones. We stop as soon as we have
* traversed all the stones or have reached maxlib. Unfortunately,
* we cannot use the trick from findlib() since some of the
* liberties may already have been marked.
if (UNMARKED_LIBERTY(SOUTH(stone
))) {
libs
[liberties
] = SOUTH(stone
);
MARK_LIBERTY(SOUTH(stone
));
if (UNMARKED_LIBERTY(WEST(stone
))) {
libs
[liberties
] = WEST(stone
);
MARK_LIBERTY(WEST(stone
));
if (UNMARKED_LIBERTY(NORTH(stone
))) {
libs
[liberties
] = NORTH(stone
);
MARK_LIBERTY(NORTH(stone
));
if (UNMARKED_LIBERTY(EAST(stone
))) {
libs
[liberties
] = EAST(stone
);
MARK_LIBERTY(EAST(stone
));
stone
= NEXT_STONE(stone
);
else if (board
[pos2
] == OTHER_COLOR(color
)
&& string
[string_number
[pos2
]].liberties
== 1) {
captured
[captures
++] = pos2
;
/* Now we look at all the captures found in the previous step */
for (k
= 0; k
< captures
; k
++) {
/* Add the stone adjacent to (pos) to the list of liberties if
* it is not also adjacent to an own marked string (otherwise,
* it will be added later).
if (!MARKED_COLOR_STRING(SOUTH(lib
), color
)
&& !MARKED_COLOR_STRING(WEST(lib
), color
)
&& !MARKED_COLOR_STRING(NORTH(lib
), color
)
&& !MARKED_COLOR_STRING(EAST(lib
), color
)) {
/* Check if we already know of this capture. */
if (string_number
[captured
[l
]] == string_number
[lib
])
/* Traverse all the stones of the capture and add to the list
* of liberties those, which are adjacent to at least one own
if (MARKED_COLOR_STRING(SOUTH(lib
), color
)
|| MARKED_COLOR_STRING(WEST(lib
), color
)
|| MARKED_COLOR_STRING(NORTH(lib
), color
)
|| MARKED_COLOR_STRING(EAST(lib
), color
)) {
} while (lib
!= captured
[k
]);
/* Find the number of common liberties of the two strings at str1 and str2.
count_common_libs(int str1
, int str2
)
int all_libs1
[MAXLIBS
], *libs1
;
int liberties1
, liberties2
;
ASSERT1(IS_STONE(board
[str1
]), str1
);
ASSERT1(IS_STONE(board
[str2
]), str2
);
liberties1
= string
[n
].liberties
;
if (liberties1
> string
[string_number
[str2
]].liberties
) {
liberties1
= string
[n
].liberties
;
if (liberties1
<= MAX_LIBERTIES
) {
/* Speed optimization: don't copy liberties with findlib */
libs1
= string_libs
[n
].list
;
liberties2
= string
[n
].liberties
;
if (liberties2
<= MAX_LIBERTIES
) {
/* Speed optimization: NEIGHBOR_OF_STRING is quite expensive */
for (k
= 0; k
< liberties1
; k
++)
libs1
= string_libs
[n
].list
;
for (k
= 0; k
< liberties2
; k
++)
if (!UNMARKED_LIBERTY(libs1
[k
]))
findlib(str1
, MAXLIBS
, all_libs1
);
for (k
= 0; k
< liberties1
; k
++)
if (NEIGHBOR_OF_STRING(libs1
[k
], string_number
[str2
], board
[str2
]))
/* Find the common liberties of the two strings at str1 and str2. The
* locations of up to maxlib common liberties are written into libs[].
* The full number of common liberties is returned.
* If you want the locations of all common liberties, whatever their
* number, you should pass MAXLIBS as the value for maxlib and
* allocate space for libs[] accordingly.
find_common_libs(int str1
, int str2
, int maxlib
, int *libs
)
int all_libs1
[MAXLIBS
], *libs1
;
int liberties1
, liberties2
;
ASSERT1(IS_STONE(board
[str1
]), str1
);
ASSERT1(IS_STONE(board
[str2
]), str2
);
ASSERT1(libs
!= NULL
, str1
);
liberties1
= string
[n
].liberties
;
if (liberties1
> string
[string_number
[str2
]].liberties
) {
liberties1
= string
[n
].liberties
;
if (liberties1
<= MAX_LIBERTIES
) {
/* Speed optimization: don't copy liberties with findlib */
libs1
= string_libs
[n
].list
;
liberties2
= string
[n
].liberties
;
if (liberties2
<= MAX_LIBERTIES
) {
/* Speed optimization: NEIGHBOR_OF_STRING is quite expensive */
for (k
= 0; k
< liberties1
; k
++)
libs1
= string_libs
[n
].list
;
for (k
= 0; k
< liberties2
; k
++)
if (!UNMARKED_LIBERTY(libs1
[k
])) {
libs
[commonlibs
] = libs1
[k
];
findlib(str1
, MAXLIBS
, all_libs1
);
for (k
= 0; k
< liberties1
; k
++)
if (NEIGHBOR_OF_STRING(libs1
[k
], string_number
[str2
], board
[str2
])) {
libs
[commonlibs
] = libs1
[k
];
/* Determine whether two strings have at least one common liberty.
* If they do and lib != NULL, one common liberty is returned in *lib.
have_common_lib(int str1
, int str2
, int *lib
)
int all_libs1
[MAXLIBS
], *libs1
;
ASSERT1(IS_STONE(board
[str1
]), str1
);
ASSERT1(IS_STONE(board
[str2
]), str2
);
liberties1
= string
[n
].liberties
;
if (liberties1
> string
[string_number
[str2
]].liberties
) {
liberties1
= string
[n
].liberties
;
if (liberties1
<= MAX_LIBERTIES
)
/* Speed optimization: don't copy liberties with findlib */
libs1
= string_libs
[n
].list
;
findlib(str1
, MAXLIBS
, all_libs1
);
for (k
= 0; k
< liberties1
; k
++) {
if (NEIGHBOR_OF_STRING(libs1
[k
], string_number
[str2
], board
[str2
])) {
* Report the number of stones in a string.
ASSERT1(IS_STONE(board
[str
]), str
);
/* Find the stones of the string at str. str must not be
* empty. The locations of up to maxstones stones are written into
* stones[]. The full number of stones is returned.
findstones(int str
, int maxstones
, int *stones
)
ASSERT1(IS_STONE(board
[str
]), str
);
/* Traverse the stones of the string, by following the cyclic chain. */
for (k
= 0; k
< maxstones
&& k
< size
; k
++) {
/* Counts how many stones in str1 are directly adjacent to str2.
* A limit can be given in the maxstones parameter so that the
* function returns immediately. See fast_defense() in reading.c
count_adjacent_stones(int str1
, int str2
, int maxstones
)
ASSERT1(IS_STONE(board
[str1
]), str1
);
ASSERT1(IS_STONE(board
[str2
]), str2
);
s1
= string_number
[str1
];
s2
= string_number
[str2
];
/* Traverse the stones of the string, by following the cyclic chain. */
for (k
= 0; k
< size
&& count
< maxstones
; k
++) {
if (NEIGHBOR_OF_STRING(pos
, s2
, board
[str2
]))
/* chainlinks returns (in the (adj) array) the chains surrounding
* the string at (str). The number of chains is returned.
chainlinks(int str
, int adj
[MAXCHAIN
])
struct string_neighbors_data
*sn
;
ASSERT1(IS_STONE(board
[str
]), str
);
/* We already have the list ready, just copy it and fill in the
s
= &string
[string_number
[str
]];
sn
= &string_neighbors
[string_number
[str
]];
for (k
= 0; k
< s
->neighbors
; k
++)
adj
[k
] = string
[sn
->list
[k
]].origin
;
/* chainlinks2 returns (in adj array) those chains surrounding
* the string at str which have exactly lib liberties. The number
* of such chains is returned.
chainlinks2(int str
, int adj
[MAXCHAIN
], int lib
)
struct string_data
*s
, *t
;
struct string_neighbors_data
*sn
;
ASSERT1(IS_STONE(board
[str
]), str
);
/* We already have the list ready, just copy the strings with the
* right number of liberties.
s
= &string
[string_number
[str
]];
sn
= &string_neighbors
[string_number
[str
]];
for (k
= 0; k
< s
->neighbors
; k
++) {
t
= &string
[sn
->list
[k
]];
adj
[neighbors
++] = t
->origin
;
/* chainlinks3 returns (in adj array) those chains surrounding
* the string at str, which have less or equal lib liberties.
* The number of such chains is returned.
chainlinks3(int str
, int adj
[MAXCHAIN
], int lib
)
struct string_data
*s
, *t
;
struct string_neighbors_data
*sn
;
ASSERT1(IS_STONE(board
[str
]), str
);
/* We already have the list ready, just copy the strings with the
* right number of liberties.
s
= &string
[string_number
[str
]];
sn
= &string_neighbors
[string_number
[str
]];
for (k
= 0; k
< s
->neighbors
; k
++) {
t
= &string
[sn
->list
[k
]];
adj
[neighbors
++] = t
->origin
;
/* extended_chainlinks() returns (in the (adj) array) the opponent
* strings being directly adjacent to (str) or having a common liberty
* with (str). The number of such strings is returned.
* If the both_colors parameter is true, also own strings sharing a
extended_chainlinks(int str
, int adj
[MAXCHAIN
], int both_colors
)
struct string_neighbors_data
*sn
;
ASSERT1(IS_STONE(board
[str
]), str
);
/* We already have the list of directly adjacent strings ready, just
* copy it and mark the strings.
s
= &string
[string_number
[str
]];
sn
= &string_neighbors
[string_number
[str
]];
for (n
= 0; n
< s
->neighbors
; n
++) {
adj
[n
] = string
[sn
->list
[n
]].origin
;
liberties
= findlib(str
, MAXLIBS
, libs
);
/* Look for unmarked opponent strings next to a liberty and add the
* ones which are found to the output.
for (r
= 0; r
< liberties
; r
++) {
for (k
= 0; k
< 4; k
++) {
if ((board
[libs
[r
] + delta
[k
]] == OTHER_COLOR(board
[str
])
|| (both_colors
&& board
[libs
[r
] + delta
[k
]] == board
[str
]))
&& UNMARKED_STRING(libs
[r
] + delta
[k
])) {
adj
[n
] = string
[string_number
[libs
[r
] + delta
[k
]]].origin
;
/* Returns true if a move by (color) fits a shape like:
* More specifically the move should have the following properties:
* - The move is a self-atari
* - The move forms a string of exactly two stones
* - When the opponent captures, the capturing stone becomes a single
* - When capturing back the original position is repeated
send_two_return_one(int move
, int color
)
int other
= OTHER_COLOR(color
);
int friendly_neighbor
= NO_MOVE
;
ASSERT1(board
[move
] == EMPTY
, move
);
for (k
= 0; k
< 4; k
++) {
int pos
= move
+ delta
[k
];
if (board
[pos
] == color
) {
if (friendly_neighbor
!= NO_MOVE
)
if (string
[s
].size
!= 1 || string
[s
].liberties
!= 2)
lib
= string_libs
[s
].list
[0] + string_libs
[s
].list
[1] - move
;
else if (board
[pos
] == other
&& string
[string_number
[pos
]].liberties
== 1)
if (friendly_neighbor
== NO_MOVE
)
for (k
= 0; k
< 4; k
++) {
int pos
= lib
+ delta
[k
];
if (board
[pos
] == EMPTY
|| board
[pos
] == other
)
if (board
[pos
] == color
&&
string
[string_number
[pos
]].liberties
< 2)
* Find the origin of a worm, i.e. the point with the
* smallest 1D board coordinate. The idea is to have a canonical
* reference point for a string.
ASSERT1(IS_STONE(board
[str
]), str
);
return string
[string_number
[str
]].origin
;
/* Determine whether a move by color at (pos) would be a self atari,
* i.e. whether it would get more than one liberty. This function
* returns true also for the case of a suicide move.
is_self_atari(int pos
, int color
)
int other
= OTHER_COLOR(color
);
/* number of empty neighbors */
int trivial_liberties
= 0;
/* number of captured opponent strings */
/* Whether there is a friendly neighbor with a spare liberty. If it
* has more than one spare liberty we immediately return 0.
ASSERT1(board
[pos
] == EMPTY
, pos
);
ASSERT1(IS_STONE(color
), pos
);
/* 1. Try first to solve the problem without much work. */
else if (board
[SOUTH(pos
)] == color
) {
if (LIBERTIES(SOUTH(pos
)) > 2)
if (LIBERTIES(SOUTH(pos
)) == 2)
else if (board
[SOUTH(pos
)] == other
&& LIBERTIES(SOUTH(pos
)) == 1 && UNMARKED_STRING(SOUTH(pos
))) {
else if (board
[WEST(pos
)] == color
) {
if (LIBERTIES(WEST(pos
)) > 2)
if (LIBERTIES(WEST(pos
)) == 2)
else if (board
[WEST(pos
)] == other
&& LIBERTIES(WEST(pos
)) == 1 && UNMARKED_STRING(WEST(pos
))) {
else if (board
[NORTH(pos
)] == color
) {
if (LIBERTIES(NORTH(pos
)) > 2)
if (LIBERTIES(NORTH(pos
)) == 2)
else if (board
[NORTH(pos
)] == other
&& LIBERTIES(NORTH(pos
)) == 1 && UNMARKED_STRING(NORTH(pos
))) {
else if (board
[EAST(pos
)] == color
) {
if (LIBERTIES(EAST(pos
)) > 2)
if (LIBERTIES(EAST(pos
)) == 2)
else if (board
[EAST(pos
)] == other
&& LIBERTIES(EAST(pos
)) == 1 && UNMARKED_STRING(EAST(pos
))) {
/* Each captured string is guaranteed to produce at least one
* liberty. These are disjoint from both trivial liberties and far
* liberties. The two latter may however coincide.
if (trivial_liberties
+ captures
>= 2)
if ((far_liberties
> 0) + captures
>= 2)
if (captures
== 0 && far_liberties
+ trivial_liberties
<= 1)
/* 2. It was not so easy. We use accuratelib() in this case. */
return accuratelib(pos
, color
, 2, NULL
) <= 1;
* Returns true if pos is a liberty of the string at str.
liberty_of_string(int pos
, int str
)
if (IS_STONE(board
[pos
]))
return NEIGHBOR_OF_STRING(pos
, string_number
[str
], board
[str
]);
* Returns true if pos is a second order liberty of the string at str.
second_order_liberty_of_string(int pos
, int str
)
if (board
[pos
+ delta
[k
]] == EMPTY
&& NEIGHBOR_OF_STRING(pos
+ delta
[k
], string_number
[str
], board
[str
]))
* Returns true if pos is adjacent to the string at str.
neighbor_of_string(int pos
, int str
)
ASSERT1(IS_STONE(color
), str
);
return NEIGHBOR_OF_STRING(pos
, string_number
[str
], color
);
* Returns true if (pos) has a neighbor of color (color).
has_neighbor(int pos
, int color
)
ASSERT1(IS_STONE(color
), pos
);
return (board
[SOUTH(pos
)] == color
|| board
[WEST(pos
)] == color
|| board
[NORTH(pos
)] == color
|| board
[EAST(pos
)] == color
);
* Returns true if str1 and str2 belong to the same string.
same_string(int str1
, int str2
)
ASSERT1(IS_STONE(board
[str1
]), str1
);
ASSERT1(IS_STONE(board
[str2
]), str2
);
return string_number
[str1
] == string_number
[str2
];
* Returns true if the strings at str1 and str2 are adjacent.
adjacent_strings(int str1
, int str2
)
ASSERT1(IS_STONE(board
[str1
]), str1
);
ASSERT1(IS_STONE(board
[str2
]), str2
);
s1
= string_number
[str1
];
s2
= string_number
[str2
];
for (k
= 0; k
< string
[s1
].neighbors
; k
++)
if (string_neighbors
[s1
].list
[k
] == s2
)
* Return true if the move (pos) by (color) is a ko capture
* (whether capture is legal on this move or not). If so,
* and if ko_pos is not a NULL pointer, then
* *ko_pos returns the location of the captured ko stone.
* If the move is not a ko capture, *ko_pos is set to 0.
* A move is a ko capture if and only if
* 1. All neighbors are opponent stones.
* 2. The number of captured stones is exactly one.
is_ko(int pos
, int color
, int *ko_pos
)
int other
= OTHER_COLOR(color
);
ASSERT1(color
== WHITE
|| color
== BLACK
, pos
);
if (ON_BOARD(SOUTH(pos
))) {
if (board
[SOUTH(pos
)] != other
)
else if (LIBERTIES(SOUTH(pos
)) == 1) {
captures
+= string
[string_number
[SOUTH(pos
)]].size
;
if (ON_BOARD(WEST(pos
))) {
if (board
[WEST(pos
)] != other
)
else if (LIBERTIES(WEST(pos
)) == 1) {
captures
+= string
[string_number
[WEST(pos
)]].size
;
if (ON_BOARD(NORTH(pos
))) {
if (board
[NORTH(pos
)] != other
)
else if (LIBERTIES(NORTH(pos
)) == 1) {
captures
+= string
[string_number
[NORTH(pos
)]].size
;
if (ON_BOARD(EAST(pos
))) {
if (board
[EAST(pos
)] != other
)
else if (LIBERTIES(EAST(pos
)) == 1) {
captures
+= string
[string_number
[EAST(pos
)]].size
;
/* Return true if pos is either a stone, which if captured would give
* ko, or if pos is an empty intersection adjacent to a ko stone.
if (board
[pos
] == EMPTY
) {
if (ON_BOARD(SOUTH(pos
)))
color
= board
[SOUTH(pos
)];
color
= board
[NORTH(pos
)];
if (IS_STONE(color
) && is_ko(pos
, OTHER_COLOR(color
), NULL
))
struct string_data
*s
= &string
[string_number
[pos
]];
struct string_liberties_data
*sl
= &string_libs
[string_number
[pos
]];
if (s
->liberties
== 1 && s
->size
== 1
&& is_ko(sl
->list
[0], OTHER_COLOR(s
->color
), NULL
))
/* Return true if a move by color at pos is a superko violation
* according to the specified type of ko rules. This function does not
* detect simple ko unless it's also a superko violation.
* The superko detection is done by comparing board hashes from
* previous positions. For this to work correctly it's necessary to
* remove the contribution to the hash from the simple ko position.
* The move_history_hash array contains board hashes for previous
* positions, also without simple ko position contributions.
is_superko_violation(int pos
, int color
, enum ko_rules type
)
Hash_data this_board_hash
= board_hash
;
Hash_data new_board_hash
;
/* No superko violations if the ko rule is not a superko rule. */
if (type
== NONE
|| type
== SIMPLE
)
if (board_ko_pos
!= NO_MOVE
)
hashdata_invert_ko(&this_board_hash
, board_ko_pos
);
really_do_trymove(pos
, color
);
new_board_hash
= board_hash
;
if (board_ko_pos
!= NO_MOVE
)
hashdata_invert_ko(&new_board_hash
, board_ko_pos
);
/* The current position is only a problem with positional superko
* and a single stone suicide.
if (type
== PSK
&& hashdata_is_equal(this_board_hash
, new_board_hash
))
for (k
= move_history_pointer
- 1; k
>= 0; k
--)
if (hashdata_is_equal(move_history_hash
[k
], new_board_hash
)
|| move_history_color
[k
] == OTHER_COLOR(color
)))
/* Returns 1 if at least one string is captured when color plays at pos.
does_capture_something(int pos
, int color
)
int other
= OTHER_COLOR(color
);
ASSERT1(board
[pos
] == EMPTY
, pos
);
if (board
[SOUTH(pos
)] == other
&& LIBERTIES(SOUTH(pos
)) == 1)
if (board
[WEST(pos
)] == other
&& LIBERTIES(WEST(pos
)) == 1)
if (board
[NORTH(pos
)] == other
&& LIBERTIES(NORTH(pos
)) == 1)
if (board
[EAST(pos
)] == other
&& LIBERTIES(EAST(pos
)) == 1)
/* For each stone in the string at pos, set mx to value mark. */
mark_string(int str
, signed char mx
[BOARDMAX
], signed char mark
)
ASSERT1(IS_STONE(board
[str
]), str
);
/* Returns true if at least one move has been played at pos
* at deeper than level 'cutoff' in the reading tree.
move_in_stack(int pos
, int cutoff
)
for (k
= cutoff
; k
< stackp
; k
++)
/* Retrieve a move from the move stack. */
get_move_from_stack(int k
, int *move
, int *color
)
/* Return the number of stones of the indicated color(s) on the board.
* This only counts stones in the permanent position, not stones placed
* by trymove() or tryko(). Use stones_on_board(BLACK | WHITE) to get
* the total number of stones on the board.
* FIXME: This seems wrong, it uses the modified board, not the permanent
stones_on_board(int color
)
static int stone_count_for_position
= -1;
static int white_stones
= 0;
static int black_stones
= 0;
if (stone_count_for_position
!= position_number
) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
else if (board
[pos
] == BLACK
)
stone_count_for_position
= position_number
;
return ((color
& BLACK
? black_stones
: 0) +
(color
& WHITE
? white_stones
: 0));
/* ===================== Statistics ============================= */
/* Retrieve statistics. */
/* ================================================================ */
/* Lower level functions */
/* ================================================================ */
/* This function should be called if the board is modified by other
* means than do_play_move() or undo_trymove().
* We have reached a new position. Increase the position counter and
* re-initialize the incremental strings.
* Set up incremental board structures and populate them with the
* strings available in the position given by board[]. Clear the stacks
* and start the mark numbers from zero. All undo information is lost
* by calling this function.
memset(string
, 0, sizeof(string
));
memset(string_libs
, 0, sizeof(string_libs
));
memset(string_neighbors
, 0, sizeof(string_neighbors
));
memset(ml
, 0, sizeof(ml
));
VALGRIND_MAKE_WRITABLE(next_stone
, sizeof(next_stone
));
/* propagate_string relies on non-assigned stones to have
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
/* Find the existing strings. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (IS_STONE(board
[pos
]) && string_number
[pos
] == -1) {
string_number
[pos
] = next_string
;
string
[next_string
].size
= propagate_string(pos
, pos
);
string
[next_string
].color
= board
[pos
];
string
[next_string
].origin
= pos
;
string
[next_string
].mark
= 0;
PARANOID1(next_string
< MAX_STRINGS
, pos
);
/* Fill in liberty and neighbor info. */
for (s
= 0; s
< next_string
; s
++) {
find_liberties_and_neighbors(s
);
* Debug function. Dump all string information.
dump_incremental_board(void)
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
fprintf(stderr
, "%2d ", string_number
[pos
]);
for (s
= 0; s
< next_string
; s
++) {
if (board
[string
[s
].origin
] == EMPTY
)
gprintf("%o%d %s %1m size %d, %d liberties, %d neighbors\n", s
,
color_to_string(string
[s
].color
),
string
[s
].origin
, string
[s
].size
,
string
[s
].liberties
, string
[s
].neighbors
);
} while (!BACK_TO_FIRST_STONE(s
, pos
));
gprintf("%o\nliberties:");
for (i
= 0; i
< string
[s
].liberties
; i
++)
gprintf("%o %1m", string
[s
].libs
[i
]);
gprintf("%o\nneighbors:");
for (i
= 0; i
< string
[s
].neighbors
; i
++)
gprintf("%o %d(%1m)", string
[s
].neighborlist
[i
],
string
[string
[s
].neighborlist
[i
]].origin
);
/* Build a string and its cyclic list representation from scratch.
* propagate_string(stone, str) adds the stone (stone) to the string
* (str) and recursively continues with not already included friendly
* neighbors. To start a new string at (stone), use
* propagate_string(stone, stone). The size of the string is returned.
propagate_string(int stone
, int str
)
/* Start a new string. */
next_stone
[stone
] = stone
;
/* Link the stone at (stone) to the string including (str) */
string_number
[stone
] = string_number
[str
];
next_stone
[stone
] = next_stone
[str
];
/* Look in all four directions for more stones to add. */
for (k
= 0; k
< 4; k
++) {
&& board
[stone
+ d
] == board
[stone
]
&& string_number
[stone
+ d
] == -1)
size
+= propagate_string(stone
+ d
, str
);
/* Build the lists of liberties and neighbors of a string from
* scratch. No information is pushed onto the stack by this function.
find_liberties_and_neighbors(int s
)
int other
= OTHER_COLOR(string
[s
].color
);
/* Traverse the stones of the string, by following the cyclic chain. */
/* Look in each direction for new liberties or new neighbors. Mark
* already visited liberties and neighbors.
if (UNMARKED_LIBERTY(SOUTH(pos
))) {
ADD_AND_MARK_LIBERTY(s
, SOUTH(pos
));
else if (UNMARKED_COLOR_STRING(SOUTH(pos
), other
)) {
ADD_NEIGHBOR(s
, SOUTH(pos
));
if (UNMARKED_LIBERTY(WEST(pos
))) {
ADD_AND_MARK_LIBERTY(s
, WEST(pos
));
else if (UNMARKED_COLOR_STRING(WEST(pos
), other
)) {
ADD_NEIGHBOR(s
, WEST(pos
));
if (UNMARKED_LIBERTY(NORTH(pos
))) {
ADD_AND_MARK_LIBERTY(s
, NORTH(pos
));
else if (UNMARKED_COLOR_STRING(NORTH(pos
), other
)) {
ADD_NEIGHBOR(s
, NORTH(pos
));
if (UNMARKED_LIBERTY(EAST(pos
))) {
ADD_AND_MARK_LIBERTY(s
, EAST(pos
));
else if (UNMARKED_COLOR_STRING(EAST(pos
), other
)) {
ADD_NEIGHBOR(s
, EAST(pos
));
} while (!BACK_TO_FIRST_STONE(s
, pos
));
/* Update the liberties of a string from scratch, first pushing the
/* Push the old information. */
PUSH_VALUE(string
[s
].liberties
);
for (k
= 0; k
< string
[s
].liberties
&& k
< MAX_LIBERTIES
; k
++) {
PUSH_VALUE(string_libs
[s
].list
[k
]);
/* Clear the liberty mark. */
/* Traverse the stones of the string, by following the cyclic chain. */
/* Look in each direction for new liberties. Mark already visited
if (UNMARKED_LIBERTY(SOUTH(pos
))) {
ADD_AND_MARK_LIBERTY(s
, SOUTH(pos
));
if (UNMARKED_LIBERTY(WEST(pos
))) {
ADD_AND_MARK_LIBERTY(s
, WEST(pos
));
if (UNMARKED_LIBERTY(NORTH(pos
))) {
ADD_AND_MARK_LIBERTY(s
, NORTH(pos
));
if (UNMARKED_LIBERTY(EAST(pos
))) {
ADD_AND_MARK_LIBERTY(s
, EAST(pos
));
} while (!BACK_TO_FIRST_STONE(s
, pos
));
/* Remove a string from the list of neighbors and push the changed
remove_neighbor(int str_number
, int n
)
struct string_data
*s
= &string
[str_number
];
struct string_neighbors_data
*sn
= &string_neighbors
[str_number
];
for (k
= 0; k
< s
->neighbors
; k
++)
/* We need to push the last entry too because it may become
PUSH_VALUE(sn
->list
[s
->neighbors
- 1]);
PUSH_VALUE(s
->neighbors
);
sn
->list
[k
] = sn
->list
[s
->neighbors
- 1];
/* Remove one liberty from the list of liberties, pushing changed
* information. If the string had more liberties than the size of the
* list, rebuild the list from scratch.
remove_liberty(int str_number
, int pos
)
struct string_data
*s
= &string
[str_number
];
struct string_liberties_data
*sl
= &string_libs
[str_number
];
if (s
->liberties
> MAX_LIBERTIES
)
update_liberties(str_number
);
for (k
= 0; k
< s
->liberties
; k
++)
if (sl
->list
[k
] == pos
) {
/* We need to push the last entry too because it may become
PUSH_VALUE(sl
->list
[s
->liberties
- 1]);
PUSH_VALUE(s
->liberties
);
sl
->list
[k
] = sl
->list
[s
->liberties
- 1];
/* Remove a string from the board, pushing necessary information to
* restore it. Return the number of removed stones.
int size
= string
[s
].size
;
/* Traverse the stones of the string, by following the cyclic chain. */
/* Push color, string number and cyclic chain pointers. */
PUSH_VALUE(string_number
[pos
]);
PUSH_VALUE(next_stone
[pos
]);
} while (!BACK_TO_FIRST_STONE(s
, pos
));
/* The neighboring strings have obtained some new liberties and lost
* a neighbor. For speed reasons we handle two most common cases
* when string size is 1 or 2 stones here instead of calling
for (k
= 0; k
< string
[s
].neighbors
; k
++) {
int neighbor
= string_neighbors
[s
].list
[k
];
remove_neighbor(neighbor
, s
);
PUSH_VALUE(string
[neighbor
].liberties
);
if (string
[neighbor
].liberties
< MAX_LIBERTIES
)
string_libs
[neighbor
].list
[string
[neighbor
].liberties
] = pos
;
string
[neighbor
].liberties
++;
int other
= OTHER_COLOR(string
[s
].color
);
int pos2
= NEXT_STONE(pos
);
for (k
= 0; k
< string
[s
].neighbors
; k
++) {
int neighbor
= string_neighbors
[s
].list
[k
];
remove_neighbor(neighbor
, s
);
PUSH_VALUE(string
[neighbor
].liberties
);
if (NEIGHBOR_OF_STRING(pos
, neighbor
, other
)) {
if (string
[neighbor
].liberties
< MAX_LIBERTIES
)
string_libs
[neighbor
].list
[string
[neighbor
].liberties
] = pos
;
string
[neighbor
].liberties
++;
if (NEIGHBOR_OF_STRING(pos2
, neighbor
, other
)) {
if (string
[neighbor
].liberties
< MAX_LIBERTIES
)
string_libs
[neighbor
].list
[string
[neighbor
].liberties
] = pos2
;
string
[neighbor
].liberties
++;
for (k
= 0; k
< string
[s
].neighbors
; k
++) {
remove_neighbor(string_neighbors
[s
].list
[k
], s
);
update_liberties(string_neighbors
[s
].list
[k
]);
/* Update the number of captured stones. These are assumed to
* already have been pushed.
if (string
[s
].color
== WHITE
)
/* We have played an isolated new stone and need to create a new
create_new_string(int pos
)
int other
= OTHER_COLOR(color
);
/* Get the next free string number. */
PARANOID1(s
< MAX_STRINGS
, pos
);
/* Set up a size one cycle for the string. */
/* Set trivially known values and initialize the rest to zero. */
/* Clear the string mark. */
/* In each direction, look for a liberty or a nonmarked opponent
* neighbor. Mark visited neighbors. There is no need to mark the
* liberties since we can't find them twice. */
if (LIBERTY(SOUTH(pos
))) {
ADD_LIBERTY(s
, SOUTH(pos
));
else if (UNMARKED_COLOR_STRING(SOUTH(pos
), other
)) {
int s2
= string_number
[SOUTH(pos
)];
/* Add the neighbor to our list. */
ADD_NEIGHBOR(s
, SOUTH(pos
));
/* Add us to our neighbor's list. */
PUSH_VALUE(string
[s2
].neighbors
);
if (LIBERTY(WEST(pos
))) {
ADD_LIBERTY(s
, WEST(pos
));
else if (UNMARKED_COLOR_STRING(WEST(pos
), other
)) {
int s2
= string_number
[WEST(pos
)];
/* Add the neighbor to our list. */
ADD_NEIGHBOR(s
, WEST(pos
));
/* Add us to our neighbor's list. */
PUSH_VALUE(string
[s2
].neighbors
);
if (LIBERTY(NORTH(pos
))) {
ADD_LIBERTY(s
, NORTH(pos
));
else if (UNMARKED_COLOR_STRING(NORTH(pos
), other
)) {
int s2
= string_number
[NORTH(pos
)];
/* Add the neighbor to our list. */
ADD_NEIGHBOR(s
, NORTH(pos
));
/* Add us to our neighbor's list. */
PUSH_VALUE(string
[s2
].neighbors
);
if (LIBERTY(EAST(pos
))) {
ADD_LIBERTY(s
, EAST(pos
));
else if (UNMARKED_COLOR_STRING(EAST(pos
), other
)) {
int s2
= string_number
[EAST(pos
)];
/* Add the neighbor to our list. */
ADD_NEIGHBOR(s
, EAST(pos
));
/* Add us to our neighbor's list. */
PUSH_VALUE(string
[s2
].neighbors
);
/* No need to mark since no visits left. */
/* We have played a stone with exactly one friendly neighbor. Add the
* new stone to that string.
extend_neighbor_string(int pos
, int s
)
int liberties_updated
= 0;
int other
= OTHER_COLOR(color
);
/* Link in the stone in the cyclic list. */
int pos2
= string
[s
].origin
;
next_stone
[pos
] = next_stone
[pos2
];
PUSH_VALUE(next_stone
[pos2
]);
/* Do we need to update the origin? */
PUSH_VALUE(string
[s
].origin
);
/* The size of the string has increased by one. */
PUSH_VALUE(string
[s
].size
);
/* If s has too many liberties, we don't know where they all are and
* can't update the liberties with the algorithm we otherwise
* use. In that case we can only recompute the liberties from
if (string
[s
].liberties
> MAX_LIBERTIES
) {
/* The place of the new stone is no longer a liberty. */
/* Mark old neighbors of the string. */
for (k
= 0; k
< string
[s
].neighbors
; k
++)
string
[string_neighbors
[s
].list
[k
]].mark
= string_mark
;
/* Look at the neighbor locations of pos for new liberties and/or
/* If we find a liberty, look two steps away to determine whether
* this already is a liberty of s.
if (LIBERTY(SOUTH(pos
))) {
&& !NON_SOUTH_NEIGHBOR_OF_STRING(SOUTH(pos
), s
, color
))
ADD_LIBERTY(s
, SOUTH(pos
));
else if (UNMARKED_COLOR_STRING(SOUTH(pos
), other
)) {
int s2
= string_number
[SOUTH(pos
)];
PUSH_VALUE(string
[s
].neighbors
);
ADD_NEIGHBOR(s
, SOUTH(pos
));
PUSH_VALUE(string
[s2
].neighbors
);
if (LIBERTY(WEST(pos
))) {
&& !NON_WEST_NEIGHBOR_OF_STRING(WEST(pos
), s
, color
))
ADD_LIBERTY(s
, WEST(pos
));
else if (UNMARKED_COLOR_STRING(WEST(pos
), other
)) {
int s2
= string_number
[WEST(pos
)];
PUSH_VALUE(string
[s
].neighbors
);
ADD_NEIGHBOR(s
, WEST(pos
));
PUSH_VALUE(string
[s2
].neighbors
);
if (LIBERTY(NORTH(pos
))) {
&& !NON_NORTH_NEIGHBOR_OF_STRING(NORTH(pos
), s
, color
))
ADD_LIBERTY(s
, NORTH(pos
));
else if (UNMARKED_COLOR_STRING(NORTH(pos
), other
)) {
int s2
= string_number
[NORTH(pos
)];
PUSH_VALUE(string
[s
].neighbors
);
ADD_NEIGHBOR(s
, NORTH(pos
));
PUSH_VALUE(string
[s2
].neighbors
);
if (LIBERTY(EAST(pos
))) {
&& !NON_EAST_NEIGHBOR_OF_STRING(EAST(pos
), s
, color
))
ADD_LIBERTY(s
, EAST(pos
));
else if (UNMARKED_COLOR_STRING(EAST(pos
), other
)) {
int s2
= string_number
[EAST(pos
)];
PUSH_VALUE(string
[s
].neighbors
);
ADD_NEIGHBOR(s
, EAST(pos
));
PUSH_VALUE(string
[s2
].neighbors
);
/* Incorporate the string at pos with the string s.
assimilate_string(int s
, int pos
)
int s2
= string_number
[pos
];
string
[s
].size
+= string
[s2
].size
;
/* Walk through the s2 stones and change string number. Also pick up
* the last stone in the cycle for later use.
PUSH_VALUE(string_number
[pos
]);
} while (!BACK_TO_FIRST_STONE(s2
, pos
));
/* Link the two cycles together. */
int pos2
= string
[s
].origin
;
PUSH_VALUE(next_stone
[last
]);
PUSH_VALUE(next_stone
[pos2
]);
next_stone
[last
] = next_stone
[pos2
];
next_stone
[pos2
] = string
[s2
].origin
;
/* Do we need to update the origin? */
if (string
[s2
].origin
< pos2
)
string
[s
].origin
= string
[s2
].origin
;
/* Pick up the liberties of s2 that we don't already have.
* It is assumed that the liberties of s have been marked before
* this function is called.
if (string
[s2
].liberties
<= MAX_LIBERTIES
) {
for (k
= 0; k
< string
[s2
].liberties
; k
++) {
int pos2
= string_libs
[s2
].list
[k
];
if (UNMARKED_LIBERTY(pos2
)) {
ADD_AND_MARK_LIBERTY(s
, pos2
);
/* If s2 had too many liberties the above strategy wouldn't be
* effective, since not all liberties are listed in
* libs[] the chain of stones for s2 is no
* longer available (it has already been merged with s) so we
* can't reconstruct the s2 liberties. Instead we capitulate and
* rebuild the list of liberties for s (including the neighbor
* strings assimilated so far) from scratch.
liberty_mark
++; /* Reset the mark. */
string
[s
].liberties
= 0; /* To avoid pushing the current list. */
/* Remove s2 as neighbor to the neighbors of s2 and instead add s if
* they don't already have added it. Also add the neighbors of s2 as
* neighbors of s, unless they already have been added. The already
* known neighbors of s are assumed to have been marked before this
for (k
= 0; k
< string
[s2
].neighbors
; k
++) {
int t
= string_neighbors
[s2
].list
[k
];
if (string
[t
].mark
!= string_mark
) {
PUSH_VALUE(string
[t
].neighbors
);
string_neighbors
[t
].list
[string
[t
].neighbors
++] = s
;
string_neighbors
[s
].list
[string
[s
].neighbors
++] = t
;
string
[t
].mark
= string_mark
;
/* Create a new string for the stone at pos and assimilate all
* friendly neighbor strings.
assimilate_neighbor_strings(int pos
)
int other
= OTHER_COLOR(color
);
/* Get the next free string number. */
PARANOID1(s
< MAX_STRINGS
, pos
);
/* Set up a size one cycle for the string. */
/* Set trivially known values and initialize the rest to zero. */
string
[s
].mark
= string_mark
;
/* Look in each direction for
* 1. liberty: Add if not already visited.
* 2. opponent string: Add it among our neighbors and us among its
* neighbors, unless already visited.
* 3. friendly string: Assimilate.
if (UNMARKED_LIBERTY(SOUTH(pos
))) {
ADD_AND_MARK_LIBERTY(s
, SOUTH(pos
));
else if (UNMARKED_COLOR_STRING(SOUTH(pos
), other
)) {
ADD_NEIGHBOR(s
, SOUTH(pos
));
PUSH_VALUE(string
[string_number
[SOUTH(pos
)]].neighbors
);
ADD_NEIGHBOR(string_number
[SOUTH(pos
)], pos
);
else if (UNMARKED_COLOR_STRING(SOUTH(pos
), color
)) {
assimilate_string(s
, SOUTH(pos
));
if (UNMARKED_LIBERTY(WEST(pos
))) {
ADD_AND_MARK_LIBERTY(s
, WEST(pos
));
else if (UNMARKED_COLOR_STRING(WEST(pos
), other
)) {
ADD_NEIGHBOR(s
, WEST(pos
));
PUSH_VALUE(string
[string_number
[WEST(pos
)]].neighbors
);
ADD_NEIGHBOR(string_number
[WEST(pos
)], pos
);
else if (UNMARKED_COLOR_STRING(WEST(pos
), color
)) {
assimilate_string(s
, WEST(pos
));
if (UNMARKED_LIBERTY(NORTH(pos
))) {
ADD_AND_MARK_LIBERTY(s
, NORTH(pos
));
else if (UNMARKED_COLOR_STRING(NORTH(pos
), other
)) {
ADD_NEIGHBOR(s
, NORTH(pos
));
PUSH_VALUE(string
[string_number
[NORTH(pos
)]].neighbors
);
ADD_NEIGHBOR(string_number
[NORTH(pos
)], pos
);
else if (UNMARKED_COLOR_STRING(NORTH(pos
), color
)) {
assimilate_string(s
, NORTH(pos
));
if (UNMARKED_LIBERTY(EAST(pos
))) {
ADD_AND_MARK_LIBERTY(s
, EAST(pos
));
ADD_LIBERTY(s
, EAST(pos
));
else if (UNMARKED_COLOR_STRING(EAST(pos
), other
)) {
ADD_NEIGHBOR(s
, EAST(pos
));
PUSH_VALUE(string
[string_number
[EAST(pos
)]].neighbors
);
ADD_NEIGHBOR(string_number
[EAST(pos
)], pos
);
else if (UNMARKED_COLOR_STRING(EAST(pos
), color
)) {
assimilate_string(s
, EAST(pos
));
/* Suicide at `pos' (the function assumes that the move is indeed suicidal).
* Remove the neighboring friendly strings.
do_commit_suicide(int pos
, int color
)
if (board
[SOUTH(pos
)] == color
)
do_remove_string(string_number
[SOUTH(pos
)]);
if (board
[WEST(pos
)] == color
)
do_remove_string(string_number
[WEST(pos
)]);
if (board
[NORTH(pos
)] == color
)
do_remove_string(string_number
[NORTH(pos
)]);
if (board
[EAST(pos
)] == color
)
do_remove_string(string_number
[EAST(pos
)]);
/* Count the stone we "played" as captured. */
/* Play a move without legality checking. This is a low-level function,
* it assumes that the move is not a suicide. Such cases must be handled
* where the function is called.
do_play_move(int pos
, int color
)
int other
= OTHER_COLOR(color
);
/* Put down the stone. We also set its string number to -1 for a while
* so that NEIGHBOR_OF_STRING() and friends don't get confused with the
DO_ADD_STONE(pos
, color
);
/* Look in all directions. Count the number of neighbor strings of the same
* color, remove captured strings and remove `pos' as liberty for opponent
* strings that are not captured.
if (board
[SOUTH(pos
)] == color
) {
s
= string_number
[SOUTH(pos
)];
else if (board
[SOUTH(pos
)] == other
) {
if (LIBERTIES(SOUTH(pos
)) > 1) {
remove_liberty(string_number
[SOUTH(pos
)], pos
);
captured_stones
+= do_remove_string(string_number
[SOUTH(pos
)]);
if (UNMARKED_COLOR_STRING(WEST(pos
), color
)) {
s
= string_number
[WEST(pos
)];
else if (UNMARKED_COLOR_STRING(WEST(pos
), other
)) {
if (LIBERTIES(WEST(pos
)) > 1) {
remove_liberty(string_number
[WEST(pos
)], pos
);
captured_stones
+= do_remove_string(string_number
[WEST(pos
)]);
if (UNMARKED_COLOR_STRING(NORTH(pos
), color
)) {
s
= string_number
[NORTH(pos
)];
else if (UNMARKED_COLOR_STRING(NORTH(pos
), other
)) {
if (LIBERTIES(NORTH(pos
)) > 1) {
remove_liberty(string_number
[NORTH(pos
)], pos
);
captured_stones
+= do_remove_string(string_number
[NORTH(pos
)]);
if (UNMARKED_COLOR_STRING(EAST(pos
), color
)) {
s
= string_number
[EAST(pos
)];
else if (UNMARKED_COLOR_STRING(EAST(pos
), other
)) {
if (LIBERTIES(EAST(pos
)) > 1) {
remove_liberty(string_number
[EAST(pos
)], pos
);
captured_stones
+= do_remove_string(string_number
[EAST(pos
)]);
/* Choose strategy depending on the number of friendly neighbors. */
if (neighbor_allies
== 0)
else if (neighbor_allies
== 1) {
extend_neighbor_string(pos
, s
);
return; /* can't be a ko, we're done */
assimilate_neighbor_strings(pos
);
return; /* can't be a ko, we're done */
/* Check whether this move was a ko capture and if so set
* No need to push board_ko_pos on the stack,
* because this has been done earlier.
if (string
[s
].liberties
== 1
&& captured_stones
== 1) {
/* In case of a double ko: clear old ko position first. */
if (board_ko_pos
!= NO_MOVE
)
hashdata_invert_ko(&board_hash
, board_ko_pos
);
board_ko_pos
= string_libs
[s
].list
[0];
hashdata_invert_ko(&board_hash
, board_ko_pos
);
/* ================================================================ *
* The following functions don't actually belong here. They are
* only here because they are faster here where they have access to
* the incremental data structures.
* ================================================================ */
/* Help collect the data needed by order_moves() in reading.c.
* It's the caller's responsibility to initialize the result parameters.
incremental_order_moves(int move
, int color
, int str
,
int *number_edges
, int *number_same_string
,
int *number_own
, int *number_opponent
,
int *captured_stones
, int *threatened_stones
,
int *saved_stones
, int *number_open
)
/* Clear the string mark. */
for (k
= 0; k
< 4; k
++) {
else if (board
[pos
] == EMPTY
)
int s
= string_number
[pos
];
if (string_number
[str
] == s
)
if (board
[pos
] == color
) {
if (string
[s
].liberties
== 1)
(*saved_stones
) += string
[s
].size
;
if (string
[s
].liberties
== 1) {
(*captured_stones
) += string
[s
].size
;
for (r
= 0; r
< string
[s
].neighbors
; r
++) {
t
= &string
[string
[s
].neighborlist
[r
]];
(*saved_stones
) += t
->size
;
else if (string
[s
].liberties
== 2 && UNMARKED_STRING(pos
)) {
(*threatened_stones
) += string
[s
].size
;
else if (board[arg] == EMPTY) \
int s = string_number[arg]; \
if (string_number[str] == s) \
(*number_same_string)++; \
if (board[arg] == color) { \
if (string[s].liberties == 1) \
(*saved_stones) += string[s].size; \
if (string[s].liberties == 1) { \
(*captured_stones) += string[s].size; \
for (r = 0; r < string[s].neighbors; r++) { \
t = &string[string_neighbors[s].list[r]]; \
(*saved_stones) += t->size; \
else if (string[s].liberties == 2 && UNMARKED_STRING(arg)) { \
(*threatened_stones) += string[s].size; \
/* Clear the string mark. */
square_dist(int pos1
, int pos2
)
int idist
= I(pos1
) - I(pos2
);
int jdist
= J(pos1
) - J(pos2
);
return idist
*idist
+ jdist
*jdist
;