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 */ 477