| 1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
| 2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * |
| 3 | * http://www.gnu.org/software/gnugo/ for more information. * |
| 4 | * * |
| 5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * |
| 6 | * 2008 and 2009 by the Free Software Foundation. * |
| 7 | * * |
| 8 | * This program is free software; you can redistribute it and/or * |
| 9 | * modify it under the terms of the GNU General Public License as * |
| 10 | * published by the Free Software Foundation - version 3 or * |
| 11 | * (at your option) any later version. * |
| 12 | * * |
| 13 | * This program is distributed in the hope that it will be useful, * |
| 14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * |
| 15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * |
| 16 | * GNU General Public License in file COPYING for more details. * |
| 17 | * * |
| 18 | * You should have received a copy of the GNU General Public * |
| 19 | * License along with this program; if not, write to the Free * |
| 20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * |
| 21 | * Boston, MA 02111, USA. * |
| 22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |
| 23 | |
| 24 | #ifndef _BOARD_H_ |
| 25 | #define _BOARD_H_ |
| 26 | |
| 27 | #include <stdarg.h> |
| 28 | #include "config.h" |
| 29 | #include "sgftree.h" |
| 30 | #include "winsocket.h" |
| 31 | |
| 32 | /* This type is used to store each intersection on the board. |
| 33 | * |
| 34 | * On a 486, char is best, since the time taken to push and pop |
| 35 | * becomes significant otherwise. On other platforms, an int may |
| 36 | * be better, e.g. if memcpy() is particularly fast, or if |
| 37 | * character access is very slow. |
| 38 | */ |
| 39 | |
| 40 | typedef unsigned char Intersection; |
| 41 | |
| 42 | /* FIXME: This is very ugly but we can't include hash.h until we have |
| 43 | * defined Intersection. And we do need to include it before using |
| 44 | * Hash_data. |
| 45 | */ |
| 46 | #include "hash.h" |
| 47 | |
| 48 | /* local versions of absolute value, min and max */ |
| 49 | |
| 50 | #define gg_abs(x) ((x) < 0 ? -(x) : (x)) |
| 51 | #define gg_min(a, b) ((a)<(b) ? (a) : (b)) |
| 52 | #define gg_max(a, b) ((a)<(b) ? (b) : (a)) |
| 53 | |
| 54 | /* Avoid compiler warnings with unused parameters */ |
| 55 | #define UNUSED(x) (void)x |
| 56 | |
| 57 | |
| 58 | /* A string with n stones can have at most 2(n+1) liberties. From this |
| 59 | * follows that an upper bound on the number of liberties of a string |
| 60 | * on a board of size N^2 is 2/3 (N^2+1). |
| 61 | */ |
| 62 | #define MAXLIBS (2*(MAX_BOARD*MAX_BOARD + 1)/3) |
| 63 | /* This is a smaller, practical number of liberties that we care to keep track of. */ |
| 64 | #define MAX_LIBERTIES 8 |
| 65 | |
| 66 | |
| 67 | /* This is an upper bound on the number of strings that can exist on |
| 68 | * the board simultaneously. Since each string must have at least one |
| 69 | * liberty and each empty point can provide a liberty to at most four |
| 70 | * strings, at least one out of five board points must be empty. |
| 71 | * |
| 72 | * FIXME: This is not sufficiently large. Above stackp==0, the |
| 73 | * incremental board code doesn't re-use the entries for |
| 74 | * removed or merged strings, while new strings require new |
| 75 | * entries. This is a problem only in very pathological cases, |
| 76 | * and is extremely unlikely to occur in practice. |
| 77 | * |
| 78 | * Actually, in the not all that pathological case of a |
| 79 | * repeated triple ko cycle, each move creates a new string and |
| 80 | * thus makes use of one more string, which relatively quickly |
| 81 | * will exhaust the available strings. For a safe upper bound |
| 82 | * MAX_STRINGS should be set to |
| 83 | * MAX_STACK + 4 * MAX_BOARD * MAX_BOARD / 5. |
| 84 | * It's not clear that it's worth the extra memory, however. |
| 85 | */ |
| 86 | #define MAX_STRINGS (4 * MAX_BOARD * MAX_BOARD / 5) |
| 87 | |
| 88 | /* Per gf: Unconditional_life() can get very close to filling the |
| 89 | * entire board under certain circumstances. This was discussed in |
| 90 | * the list around August 21, 2001, in a thread with the subject |
| 91 | * "gnugo bug logs". |
| 92 | */ |
| 93 | #define MAXSTACK MAX_BOARD * MAX_BOARD |
| 94 | #define MAXCHAIN 160 |
| 95 | |
| 96 | #define HASH_RANDOM_SEED 12345 |
| 97 | |
| 98 | /* ================================================================ * |
| 99 | * One-dimensional board * |
| 100 | * ================================================================ */ |
| 101 | |
| 102 | /* Board sizes */ |
| 103 | |
| 104 | |
| 105 | #define MIN_BOARD 1 /* Minimum supported board size. */ |
| 106 | #define MAX_BOARD 19 /* Maximum supported board size. */ |
| 107 | #define MAX_HANDICAP 9 /* Maximum supported handicap. */ |
| 108 | #define MAX_MOVE_HISTORY 500 /* Max number of moves remembered. */ |
| 109 | |
| 110 | #define DEFAULT_BOARD_SIZE MAX_BOARD |
| 111 | |
| 112 | /* Colors and komaster states. */ |
| 113 | enum colors { |
| 114 | EMPTY, |
| 115 | WHITE, |
| 116 | BLACK, |
| 117 | GRAY, |
| 118 | GRAY_WHITE, |
| 119 | GRAY_BLACK, |
| 120 | WEAK_KO, |
| 121 | NUM_KOMASTER_STATES |
| 122 | }; |
| 123 | |
| 124 | #define COLOR_NAMES \ |
| 125 | "empty", \ |
| 126 | "white", \ |
| 127 | "black", \ |
| 128 | "gray", \ |
| 129 | "gray_white", \ |
| 130 | "gray_black", \ |
| 131 | "weak_ko" |
| 132 | |
| 133 | const char *color_to_string(int color); |
| 134 | |
| 135 | #define OTHER_COLOR(color) (WHITE+BLACK-(color)) |
| 136 | #define IS_STONE(arg) ((arg) == WHITE || (arg) == BLACK) |
| 137 | |
| 138 | /* Note that POS(-1, -1) == 0 |
| 139 | * DELTA() is defined so that POS(i+di, j+dj) = POS(i, j) + DELTA(di, dj). |
| 140 | */ |
| 141 | #define BOARDSIZE ((MAX_BOARD + 2) * (MAX_BOARD + 1) + 1) |
| 142 | #define BOARDMIN (MAX_BOARD + 2) |
| 143 | #define BOARDMAX (MAX_BOARD + 1) * (MAX_BOARD + 1) |
| 144 | #define POS(i, j) ((MAX_BOARD + 2) + (i) * (MAX_BOARD + 1) + (j)) |
| 145 | #define DELTA(di, dj) ((di) * (MAX_BOARD + 1) + (dj)) |
| 146 | #define I(pos) ((pos) / (MAX_BOARD + 1) - 1) |
| 147 | #define J(pos) ((pos) % (MAX_BOARD + 1) - 1) |
| 148 | #define PASS_MOVE 0 |
| 149 | #define NO_MOVE PASS_MOVE |
| 150 | #define NS (MAX_BOARD + 1) |
| 151 | #define WE 1 |
| 152 | #define SOUTH(pos) ((pos) + NS) |
| 153 | #define WEST(pos) ((pos) - 1) |
| 154 | #define NORTH(pos) ((pos) - NS) |
| 155 | #define EAST(pos) ((pos) + 1) |
| 156 | #define SW(pos) ((pos) + NS - 1) |
| 157 | #define NW(pos) ((pos) - NS - 1) |
| 158 | #define NE(pos) ((pos) - NS + 1) |
| 159 | #define SE(pos) ((pos) + NS + 1) |
| 160 | #define SS(pos) ((pos) + 2 * NS) |
| 161 | #define WW(pos) ((pos) - 2) |
| 162 | #define NN(pos) ((pos) - 2 * NS) |
| 163 | #define EE(pos) ((pos) + 2) |
| 164 | |
| 165 | #define DIRECT_NEIGHBORS(pos1, pos2) \ |
| 166 | ((pos1) == SOUTH(pos2) \ |
| 167 | || (pos1) == WEST(pos2) \ |
| 168 | || (pos1) == NORTH(pos2) \ |
| 169 | || (pos1) == EAST(pos2)) |
| 170 | |
| 171 | #define DIAGONAL_NEIGHBORS(pos1, pos2) \ |
| 172 | ((pos1) == SW(pos2) \ |
| 173 | || (pos1) == NW(pos2) \ |
| 174 | || (pos1) == NE(pos2) \ |
| 175 | || (pos1) == SE(pos2)) |
| 176 | |
| 177 | #define BOARD(i, j) board[POS(i, j)] |
| 178 | |
| 179 | |
| 180 | #define MIRROR_MOVE(pos) POS(board_size - 1 - I(pos), board_size - 1 - J(pos)) |
| 181 | |
| 182 | /* ================================================================ */ |
| 183 | /* global variables */ |
| 184 | /* ================================================================ */ |
| 185 | |
| 186 | /* The board and the other parameters deciding the current position. */ |
| 187 | extern int board_size; /* board size (usually 19) */ |
| 188 | extern Intersection board[BOARDSIZE]; /* go board */ |
| 189 | extern int board_ko_pos; |
| 190 | extern int black_captured; /* num. of black stones captured */ |
| 191 | extern int white_captured; |
| 192 | |
| 193 | extern Intersection initial_board[BOARDSIZE]; |
| 194 | extern int initial_board_ko_pos; |
| 195 | extern int initial_white_captured; |
| 196 | extern int initial_black_captured; |
| 197 | extern int move_history_color[MAX_MOVE_HISTORY]; |
| 198 | extern int move_history_pos[MAX_MOVE_HISTORY]; |
| 199 | extern Hash_data move_history_hash[MAX_MOVE_HISTORY]; |
| 200 | extern int move_history_pointer; |
| 201 | |
| 202 | extern float komi; |
| 203 | extern int handicap; /* used internally in chinese scoring */ |
| 204 | extern int movenum; /* movenumber - used for debug output */ |
| 205 | |
| 206 | extern signed char shadow[BOARDMAX]; /* reading tree shadow */ |
| 207 | |
| 208 | enum suicide_rules { |
| 209 | FORBIDDEN, |
| 210 | ALLOWED, |
| 211 | ALL_ALLOWED |
| 212 | }; |
| 213 | extern enum suicide_rules suicide_rule; |
| 214 | |
| 215 | enum ko_rules { |
| 216 | SIMPLE, |
| 217 | NONE, |
| 218 | PSK, |
| 219 | SSK |
| 220 | }; |
| 221 | extern enum ko_rules ko_rule; |
| 222 | |
| 223 | |
| 224 | extern int stackp; /* stack pointer */ |
| 225 | extern int count_variations; /* count (decidestring) */ |
| 226 | extern SGFTree *sgf_dumptree; |
| 227 | |
| 228 | |
| 229 | /* This struct holds the internal board state. */ |
| 230 | struct board_state { |
| 231 | int board_size; |
| 232 | |
| 233 | Intersection board[BOARDSIZE]; |
| 234 | int board_ko_pos; |
| 235 | int black_captured; |
| 236 | int white_captured; |
| 237 | |
| 238 | Intersection initial_board[BOARDSIZE]; |
| 239 | int initial_board_ko_pos; |
| 240 | int initial_white_captured; |
| 241 | int initial_black_captured; |
| 242 | int move_history_color[MAX_MOVE_HISTORY]; |
| 243 | int move_history_pos[MAX_MOVE_HISTORY]; |
| 244 | Hash_data move_history_hash[MAX_MOVE_HISTORY]; |
| 245 | int move_history_pointer; |
| 246 | |
| 247 | float komi; |
| 248 | int handicap; |
| 249 | int move_number; |
| 250 | }; |
| 251 | |
| 252 | /* This is increased by one anytime a move is (permanently) played or |
| 253 | * the board is cleared. |
| 254 | */ |
| 255 | extern int position_number; |
| 256 | |
| 257 | /* ================================================================ */ |
| 258 | /* board.c functions */ |
| 259 | /* ================================================================ */ |
| 260 | |
| 261 | |
| 262 | /* Functions handling the permanent board state. */ |
| 263 | void clear_board(void); |
| 264 | int test_gray_border(void); |
| 265 | void setup_board(Intersection new_board[MAX_BOARD][MAX_BOARD], int ko_pos, |
| 266 | int *last, float new_komi, int w_captured, int b_captured); |
| 267 | void add_stone(int pos, int color); |
| 268 | void remove_stone(int pos); |
| 269 | void play_move(int pos, int color); |
| 270 | int undo_move(int n); |
| 271 | |
| 272 | void store_board(struct board_state *state); |
| 273 | void restore_board(struct board_state *state); |
| 274 | |
| 275 | /* Information about the permanent board. */ |
| 276 | int get_last_move(void); |
| 277 | int get_last_player(void); |
| 278 | int get_last_opponent_move(int color); |
| 279 | int stones_on_board(int color); |
| 280 | |
| 281 | /* Functions handling the variable board state. */ |
| 282 | int trymove(int pos, int color, const char *message, int str); |
| 283 | int tryko(int pos, int color, const char *message); |
| 284 | void popgo(void); |
| 285 | int komaster_trymove(int pos, int color, |
| 286 | const char *message, int str, |
| 287 | int *is_conditional_ko, int consider_conditional_ko); |
| 288 | int get_komaster(void); |
| 289 | int get_kom_pos(void); |
| 290 | |
| 291 | int move_in_stack(int pos, int cutoff); |
| 292 | void get_move_from_stack(int k, int *move, int *color); |
| 293 | void dump_stack(void); |
| 294 | void do_dump_stack(void); |
| 295 | |
| 296 | void reset_trymove_counter(void); |
| 297 | int get_trymove_counter(void); |
| 298 | |
| 299 | /* move properties */ |
| 300 | int is_pass(int pos); |
| 301 | int is_legal(int pos, int color); |
| 302 | int is_suicide(int pos, int color); |
| 303 | int is_illegal_ko_capture(int pos, int color); |
| 304 | int is_allowed_move(int pos, int color); |
| 305 | int is_ko(int pos, int color, int *ko_pos); |
| 306 | int is_ko_point(int pos); |
| 307 | int does_capture_something(int pos, int color); |
| 308 | int is_self_atari(int pos, int color); |
| 309 | |
| 310 | /* Purely geometric functions. */ |
| 311 | int is_edge_vertex(int pos); |
| 312 | int is_corner_vertex(int pos); |
| 313 | int edge_distance(int pos); |
| 314 | int square_dist(int pos1, int pos2); |
| 315 | int rotate1(int pos, int rot); |
| 316 | |
| 317 | /* Basic string information. */ |
| 318 | int find_origin(int str); |
| 319 | int chainlinks(int str, int adj[MAXCHAIN]); |
| 320 | int chainlinks2(int str, int adj[MAXCHAIN], int lib); |
| 321 | int chainlinks3(int str, int adj[MAXCHAIN], int lib); |
| 322 | int extended_chainlinks(int str, int adj[MAXCHAIN], int both_colors); |
| 323 | |
| 324 | int liberty_of_string(int pos, int str); |
| 325 | int second_order_liberty_of_string(int pos, int str); |
| 326 | int neighbor_of_string(int pos, int str); |
| 327 | int has_neighbor(int pos, int color); |
| 328 | int same_string(int str1, int str2); |
| 329 | int adjacent_strings(int str1, int str2); |
| 330 | void mark_string(int str, signed char mx[BOARDMAX], signed char mark); |
| 331 | int are_neighbors(int pos1, int pos2); |
| 332 | |
| 333 | /* Count and/or find liberties at (pos). */ |
| 334 | int countlib(int str); |
| 335 | int findlib(int str, int maxlib, int *libs); |
| 336 | int fastlib(int pos, int color, int ignore_captures); |
| 337 | int approxlib(int pos, int color, int maxlib, int *libs); |
| 338 | int accuratelib(int pos, int color, int maxlib, int *libs); |
| 339 | int count_common_libs(int str1, int str2); |
| 340 | int find_common_libs(int str1, int str2, int maxlib, int *libs); |
| 341 | int have_common_lib(int str1, int str2, int *lib); |
| 342 | |
| 343 | /* Count the number of stones in a string. */ |
| 344 | int countstones(int str); |
| 345 | int findstones(int str, int maxstones, int *stones); |
| 346 | int count_adjacent_stones(int str1, int str2, int maxstones); |
| 347 | |
| 348 | /* Detect a special shape. */ |
| 349 | int send_two_return_one(int move, int color); |
| 350 | |
| 351 | /* Special function for reading.c */ |
| 352 | void incremental_order_moves(int move, int color, int string, |
| 353 | int *number_edges, int *number_same_string, |
| 354 | int *number_own, int *number_opponent, |
| 355 | int *captured_stones, int *threatened_stones, |
| 356 | int *saved_stones, int *number_open); |
| 357 | |
| 358 | /* Board caches initialization functions. */ |
| 359 | void clear_approxlib_cache(void); |
| 360 | void clear_accuratelib_cache(void); |
| 361 | |
| 362 | |
| 363 | /* Is this point inside the board? */ |
| 364 | #if 0 |
| 365 | #define ON_BOARD2(i, j) ((i)>=0 && (j)>=0 && (i)<board_size && (j)<board_size) |
| 366 | #else |
| 367 | /* |
| 368 | * For the case when expr can only be slightly negative, |
| 369 | * if (expr < 0 || expr > something) |
| 370 | * is equivalent to |
| 371 | * if ((unsigned) expr > something) |
| 372 | * |
| 373 | * (I think gcc knows this trick, but it does no harm to |
| 374 | * encode it explicitly since it saves typing !) |
| 375 | */ |
| 376 | #define ON_BOARD2(i, j) ((unsigned) (i) < (unsigned) board_size &&\ |
| 377 | (unsigned) (j) < (unsigned) board_size) |
| 378 | #endif |
| 379 | |
| 380 | #define ASSERT_ON_BOARD2(i, j) ASSERT2(ON_BOARD2((i), (j)), (i), (j)) |
| 381 | |
| 382 | #define ON_BOARD1(pos) (((unsigned) (pos) < BOARDSIZE) && board[pos] != GRAY) |
| 383 | #define ON_BOARD(pos) (board[pos] != GRAY) |
| 384 | #define ASSERT_ON_BOARD1(pos) ASSERT1(ON_BOARD1(pos), (pos)) |
| 385 | |
| 386 | /* Coordinates for the eight directions, ordered |
| 387 | * south, west, north, east, southwest, northwest, northeast, southeast. |
| 388 | * Defined in board.c. |
| 389 | */ |
| 390 | extern int deltai[8]; /* = { 1, 0, -1, 0, 1, -1, -1, 1}; */ |
| 391 | extern int deltaj[8]; /* = { 0, -1, 0, 1, -1, -1, 1, 1}; */ |
| 392 | extern int delta[8]; /* = { NS, -1, -NS, 1, NS-1, -NS-1, -NS+1, NS+1}; */ |
| 393 | |
| 394 | |
| 395 | |
| 396 | /* ================================================================ */ |
| 397 | /* Other functions */ |
| 398 | /* ================================================================ */ |
| 399 | |
| 400 | |
| 401 | /* SGF routines for debugging purposes in sgffile.c */ |
| 402 | void sgffile_begindump(struct SGFTree_t *tree); |
| 403 | void sgffile_enddump(const char *filename); |
| 404 | |
| 405 | |
| 406 | /* Hashing and Caching statistics. */ |
| 407 | struct stats_data { |
| 408 | int nodes; /* Number of visited nodes while reading */ |
| 409 | int read_result_entered; /* Number of read results entered. */ |
| 410 | int read_result_hits; /* Number of hits of read results. */ |
| 411 | int trusted_read_result_hits; /* Number of hits of read results */ |
| 412 | /* with sufficient remaining depth. */ |
| 413 | }; |
| 414 | |
| 415 | extern struct stats_data stats; |
| 416 | |
| 417 | |
| 418 | /* printutils.c */ |
| 419 | int gprintf(const char *fmt, ...); |
| 420 | void vgprintf(FILE *outputfile, const char *fmt, va_list ap); |
| 421 | void mprintf(const char *fmt, ...); |
| 422 | void gfprintf(FILE *outfile, const char *fmt, ...); |
| 423 | |
| 424 | const char *color_to_string(int color); |
| 425 | const char *location_to_string(int pos); |
| 426 | void location_to_buffer(int pos, char *buf); |
| 427 | |
| 428 | int string_to_location(int boardsize, const char *str); |
| 429 | |
| 430 | int is_hoshi_point(int m, int n); |
| 431 | void draw_letter_coordinates(FILE *outfile); |
| 432 | void simple_showboard(FILE *outfile); |
| 433 | |
| 434 | void mark_goal_in_sgf(signed char goal[BOARDMAX]); |
| 435 | |
| 436 | /* ================================================================ */ |
| 437 | /* assertions */ |
| 438 | /* ================================================================ */ |
| 439 | |
| 440 | /* Our own abort() which prints board state on the way out. |
| 441 | * (pos) is a "relevant" board position for info. |
| 442 | */ |
| 443 | void abortgo(const char *file, int line, const char *msg, int pos) |
| 444 | #ifdef __GNUC__ |
| 445 | __attribute__ ((noreturn)) |
| 446 | #endif |
| 447 | ; |
| 448 | |
| 449 | #ifdef GG_TURN_OFF_ASSERTS |
| 450 | #define ASSERT2(x, i, j) |
| 451 | #define ASSERT1(x, pos) |
| 452 | #else |
| 453 | /* avoid dangling else */ |
| 454 | /* FIXME: Should probably re-write these using do {...} while (0) idiom. */ |
| 455 | #define ASSERT2(x, i, j) if (x) ; else abortgo(__FILE__, __LINE__, #x, POS(i, j)) |
| 456 | #define ASSERT1(x, pos) if (x) ; else abortgo(__FILE__, __LINE__, #x, pos) |
| 457 | #endif |
| 458 | |
| 459 | #define gg_assert(x) ASSERT1(x, NO_MOVE) |
| 460 | |
| 461 | /* Are we using valgrind memory checking? */ |
| 462 | #if USE_VALGRIND |
| 463 | #include <valgrind/memcheck.h> |
| 464 | #else |
| 465 | #define VALGRIND_MAKE_WRITABLE(a, b) |
| 466 | #endif |
| 467 | |
| 468 | #endif /* _BOARD_H_ */ |
| 469 | |
| 470 | |
| 471 | /* |
| 472 | * Local Variables: |
| 473 | * tab-width: 8 |
| 474 | * c-basic-offset: 2 |
| 475 | * End: |
| 476 | */ |