board.c

   1 #include <alloca.h>
   2 #include <assert.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #include "board.h"
   8 #include "debug.h"
   9 #include "random.h"
  10
  11 int board_group_capture(struct board *board, int group);
  12
  13 bool random_pass = false;
  14
  15
  16 #if 0
  17 #define profiling_noinline __attribute__((noinline))
  18 #else
  19 #define profiling_noinline
  20 #endif
  21
  22 #define gi_granularity 4
  23 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
  24
  25
  26 static void
  27 board_setup(struct board *b)
  28 {
  29         memset(b, 0, sizeof(*b));
  30
  31         struct move m = { pass, S_NONE };
  32         b->last_move = b->ko = m;
  33 }
  34
  35 struct board *
  36 board_init(void)
  37 {
  38         struct board *b = malloc(sizeof(struct board));
  39         board_setup(b);
  40         return b;
  41 }
  42
  43 struct board *
  44 board_copy(struct board *b2, struct board *b1)
  45 {
  46         memcpy(b2, b1, sizeof(struct board));
  47
  48         int bsize = board_size2(b2) * sizeof(*b2->b);
  49         int gsize = board_size2(b2) * sizeof(*b2->g);
  50         int fsize = board_size2(b2) * sizeof(*b2->f);
  51         int nsize = board_size2(b2) * sizeof(*b2->n);
  52         int psize = board_size2(b2) * sizeof(*b2->p);
  53         int hsize = board_size2(b2) * 2 * sizeof(*b2->h);
  54         int gisize = board_size2(b2) * sizeof(*b2->gi);
  55 #ifdef WANT_BOARD_C
  56         int csize = board_size2(b2) * sizeof(*b2->c);
  57 #else
  58         int csize = 0;
  59 #endif
  60         void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
  61         memcpy(x, b1->b, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
  62         b2->b = x; x += bsize;
  63         b2->g = x; x += gsize;
  64         b2->f = x; x += fsize;
  65         b2->p = x; x += psize;
  66         b2->n = x; x += nsize;
  67         b2->h = x; x += hsize;
  68         b2->gi = x; x += gisize;
  69 #ifdef WANT_BOARD_C
  70         b2->c = x; x += csize;
  71 #endif
  72
  73         return b2;
  74 }
  75
  76 void
  77 board_done_noalloc(struct board *board)
  78 {
  79         if (board->b) free(board->b);
  80 }
  81
  82 void
  83 board_done(struct board *board)
  84 {
  85         board_done_noalloc(board);
  86         free(board);
  87 }
  88
  89 void
  90 board_resize(struct board *board, int size)
  91 {
  92 #ifdef BOARD_SIZE
  93         assert(board_size(board) == size + 2);
  94 #else
  95         board_size(board) = size + 2 /* S_OFFBOARD margin */;
  96         board_size2(board) = board_size(board) * board_size(board);
  97 #endif
  98         if (board->b)
  99                 free(board->b);
 100
 101         int bsize = board_size2(board) * sizeof(*board->b);
 102         int gsize = board_size2(board) * sizeof(*board->g);
 103         int fsize = board_size2(board) * sizeof(*board->f);
 104         int nsize = board_size2(board) * sizeof(*board->n);
 105         int psize = board_size2(board) * sizeof(*board->p);
 106         int hsize = board_size2(board) * 2 * sizeof(*board->h);
 107         int gisize = board_size2(board) * sizeof(*board->gi);
 108 #ifdef WANT_BOARD_C
 109         int csize = board_size2(board) * sizeof(*board->c);
 110 #else
 111         int csize = 0;
 112 #endif
 113         void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
 114         memset(x, 0, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
 115         board->b = x; x += bsize;
 116         board->g = x; x += gsize;
 117         board->f = x; x += fsize;
 118         board->p = x; x += psize;
 119         board->n = x; x += nsize;
 120         board->h = x; x += hsize;
 121         board->gi = x; x += gisize;
 122 #ifdef WANT_BOARD_C
 123         board->c = x; x += csize;
 124 #endif
 125 }
 126
 127 void
 128 board_clear(struct board *board)
 129 {
 130         int size = board_size(board);
 131
 132         board_done_noalloc(board);
 133         board_setup(board);
 134         board_resize(board, size - 2 /* S_OFFBOARD margin */);
 135
 136         /* Draw the offboard margin */
 137         int top_row = board_size2(board) - board_size(board);
 138         int i;
 139         for (i = 0; i < board_size(board); i++)
 140                 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
 141         for (i = 0; i <= top_row; i += board_size(board))
 142                 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
 143
 144         foreach_point(board) {
 145                 coord_t coord = c;
 146                 if (board_at(board, coord) == S_OFFBOARD)
 147                         continue;
 148                 foreach_neighbor(board, c, {
 149                         inc_neighbor_count_at(board, coord, board_at(board, c));
 150                 } );
 151         } foreach_point_end;
 152
 153         /* First, pass is always a free position. */
 154         board->f[board->flen++] = coord_raw(pass);
 155         /* All positions are free! Except the margin. */
 156         for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
 157                 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
 158                         board->f[board->flen++] = i;
 159
 160         /* Initialize zobrist hashtable. */
 161         foreach_point(board) {
 162                 int max = (sizeof(hash_t) << history_hash_bits);
 163                 /* fast_random() is 16-bit only */
 164                 board->h[coord_raw(c) * 2] = ((hash_t) fast_random(max))
 165                                 | ((hash_t) fast_random(max) << 16)
 166                                 | ((hash_t) fast_random(max) << 32)
 167                                 | ((hash_t) fast_random(max) << 48);
 168                 if (!board->h[coord_raw(c) * 2])
 169                         /* Would be kinda "oops". */
 170                         board->h[coord_raw(c) * 2] = 1;
 171                 /* And once again for white */
 172                 board->h[coord_raw(c) * 2 + 1] = ((hash_t) fast_random(max))
 173                                 | ((hash_t) fast_random(max) << 16)
 174                                 | ((hash_t) fast_random(max) << 32)
 175                                 | ((hash_t) fast_random(max) << 48);
 176                 if (!board->h[coord_raw(c) * 2 + 1])
 177                         board->h[coord_raw(c) * 2 + 1] = 1;
 178         } foreach_point_end;
 179 }
 180
 181
 182 void
 183 board_print(struct board *board, FILE *f)
 184 {
 185         fprintf(f, "Move: % 3d  Komi: %2.1f  Captures B: %d W: %d\n     ",
 186                 board->moves, board->komi,
 187                 board->captures[S_BLACK], board->captures[S_WHITE]);
 188         int x, y;
 189         char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
 190         for (x = 1; x < board_size(board) - 1; x++)
 191                 fprintf(f, "%c ", asdf[x - 1]);
 192         fprintf(f, "\n   +-");
 193         for (x = 1; x < board_size(board) - 1; x++)
 194                 fprintf(f, "--");
 195         fprintf(f, "+\n");
 196         for (y = board_size(board) - 2; y >= 1; y--) {
 197                 fprintf(f, "%2d | ", y);
 198                 for (x = 1; x < board_size(board) - 1; x++) {
 199                         if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
 200                                 fprintf(f, "%c)", stone2char(board_atxy(board, x, y)));
 201                         else
 202                                 fprintf(f, "%c ", stone2char(board_atxy(board, x, y)));
 203                 }
 204                 if (DEBUGL(6)) {
 205                         fprintf(f, "| ");
 206                         for (x = 1; x < board_size(board) - 1; x++) {
 207                                 fprintf(f, "%d ", group_atxy(board, x, y));
 208                         }
 209                 }
 210                 fprintf(f, "|\n");
 211         }
 212         fprintf(f, "   +-");
 213         for (x = 1; x < board_size(board) - 1; x++)
 214                 fprintf(f, "--");
 215         fprintf(f, "+\n\n");
 216 }
 217
 218
 219 /* Update board hash with given coordinate. */
 220 static void profiling_noinline
 221 board_hash_update(struct board *board, coord_t coord, enum stone color)
 222 {
 223         board->hash ^= hash_at(board, coord, color);
 224         if (DEBUGL(8))
 225                 fprintf(stderr, "board_hash_update(%d,%d,%d) ^ %llx -> %llx\n", color, coord_x(coord, board), coord_y(coord, board), hash_at(board, coord, color), board->hash);
 226 }
 227
 228 /* Commit current board hash to history. */
 229 static void profiling_noinline
 230 board_hash_commit(struct board *board)
 231 {
 232         if (DEBUGL(8))
 233                 fprintf(stderr, "board_hash_commit %llx\n", board->hash);
 234         if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
 235                 board->history_hash[board->hash & history_hash_mask] = board->hash;
 236         } else {
 237                 hash_t i = board->hash;
 238                 while (board->history_hash[i & history_hash_mask]) {
 239                         if (board->history_hash[i & history_hash_mask] == board->hash) {
 240                                 if (DEBUGL(5))
 241                                         fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
 242                                                 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
 243                                 board->superko_violation = true;
 244                                 return;
 245                         }
 246                         i = history_hash_next(i);
 247                 }
 248                 board->history_hash[i & history_hash_mask] = board->hash;
 249         }
 250 }
 251
 252
 253 void
 254 board_handicap_stone(struct board *board, int x, int y, FILE *f)
 255 {
 256         struct move m;
 257         m.color = S_BLACK;
 258         coord_xy(m.coord, x, y, board);
 259
 260         board_play(board, &m);
 261
 262         char *str = coord2str(m.coord, board);
 263         if (DEBUGL(1))
 264                 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
 265         fprintf(f, "%s ", str);
 266         free(str);
 267 }
 268
 269 void
 270 board_handicap(struct board *board, int stones, FILE *f)
 271 {
 272         int margin = 3 + (board_size(board) >= 13);
 273         int min = margin;
 274         int mid = board_size(board) / 2;
 275         int max = board_size(board) - 1 - margin;
 276         const int places[][2] = {
 277                 { min, min }, { max, max }, { max, min }, { min, max },
 278                 { min, mid }, { max, mid },
 279                 { mid, min }, { mid, max },
 280                 { mid, mid },
 281         };
 282
 283         board->handicap = stones;
 284
 285         if (stones == 5 || stones == 7) {
 286                 board_handicap_stone(board, mid, mid, f);
 287                 stones--;
 288         }
 289
 290         int i;
 291         for (i = 0; i < stones; i++)
 292                 board_handicap_stone(board, places[i][0], places[i][1], f);
 293 }
 294
 295
 296 static void __attribute__((noinline))
 297 check_libs_consistency(struct board *board, group_t g)
 298 {
 299 #ifdef DEBUG
 300         if (!g) return;
 301         struct group *gi = &board_group_info(board, g);
 302         for (int i = 0; i < gi_libs_bound(*gi); i++)
 303                 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
 304                         fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(g, board));
 305                         assert(0);
 306                 }
 307 #endif
 308 }
 309
 310 static void
 311 board_capturable_add(struct board *board, group_t group)
 312 {
 313 #ifdef WANT_BOARD_C
 314         //fprintf(stderr, "add of group %d (%d)\n", group, board->clen);
 315         assert(board->clen < board_size2(board));
 316         board->c[board->clen++] = group;
 317 #endif
 318 }
 319 static void
 320 board_capturable_rm(struct board *board, group_t group)
 321 {
 322 #ifdef WANT_BOARD_C
 323         //fprintf(stderr, "rm of group %d\n", group);
 324         for (int i = 0; i < board->clen; i++) {
 325                 if (unlikely(board->c[i] == group)) {
 326                         board->c[i] = board->c[--board->clen];
 327                         return;
 328                 }
 329         }
 330         fprintf(stderr, "rm of bad group %d\n", group);
 331         assert(0);
 332 #endif
 333 }
 334
 335 static void
 336 board_group_addlib(struct board *board, group_t group, coord_t coord, bool fresh)
 337 {
 338         if (DEBUGL(7)) {
 339                 fprintf(stderr, "Group %d[%s]: Adding liberty %s\n",
 340                         group, coord2sstr(group, board), coord2sstr(coord, board));
 341         }
 342
 343         check_libs_consistency(board, group);
 344
 345         struct group *gi = &board_group_info(board, group);
 346         if (gi->libs < GROUP_KEEP_LIBS) {
 347                 if (!fresh)
 348                         for (int i = 0; i < gi_libs_bound(*gi); i++)
 349                                 if (unlikely(gi->lib[i] == coord))
 350                                         return;
 351                 if (gi->libs == 0)
 352                         board_capturable_add(board, group);
 353                 else if (gi->libs == 1)
 354                         board_capturable_rm(board, group);
 355                 gi->lib[gi->libs++] = coord;
 356         }
 357
 358         check_libs_consistency(board, group);
 359 }
 360
 361 static void
 362 board_group_rmlib(struct board *board, group_t group, coord_t coord)
 363 {
 364         if (DEBUGL(7)) {
 365                 fprintf(stderr, "Group %d[%s]: Removing liberty %s\n",
 366                         group, coord2sstr(group, board), coord2sstr(coord, board));
 367         }
 368
 369         struct group *gi = &board_group_info(board, group);
 370         int j = gi_libs_bound(*gi);
 371         for (int i = 0; i < j; i++) {
 372                 if (likely(gi->lib[i] != coord))
 373                         continue;
 374
 375                 for (i++; i < gi_libs_bound(*gi); i++) {
 376                         gi->lib[i - 1] = gi->lib[i];
 377                         if (!gi->lib[i])
 378                                 break; /* Unfilled liberties. */
 379                 }
 380                 gi->lib[--gi->libs] = 0;
 381
 382                 check_libs_consistency(board, group);
 383                 if (gi->libs < GROUP_KEEP_LIBS - 1) {
 384                         if (gi->libs == 1)
 385                                 board_capturable_add(board, group);
 386                         else if (gi->libs == 0)
 387                                 board_capturable_rm(board, group);
 388                         return;
 389                 }
 390                 /* Postpone refilling lib[] until we need to. */
 391                 if (i > GROUP_REFILL_LIBS)
 392                         return;
 393                 goto find_extra_lib;
 394         }
 395
 396         /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
 397          * can call this multiple times per coord. */
 398         check_libs_consistency(board, group);
 399         return;
 400
 401         /* Add extra liberty from the board to our liberty list. */
 402 find_extra_lib:;
 403         bool watermark[board_size2(board)];
 404         memset(watermark, 0, sizeof(watermark));
 405
 406         foreach_in_group(board, group) {
 407                 coord_t coord2 = c;
 408                 foreach_neighbor(board, coord2, {
 409                         if (likely(watermark[coord_raw(c)]))
 410                                 continue;
 411                         watermark[coord_raw(c)] = true;
 412                         if (c != coord && board_at(board, c) == S_NONE) {
 413                                 bool next = false;
 414                                 for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++) {
 415                                         if (gi->lib[i] == c) {
 416                                                 next = true;
 417                                                 break;
 418                                         }
 419                                 }
 420                                 if (!next) {
 421                                         gi->lib[gi->libs++] = c;
 422                                         if (gi->libs >= GROUP_KEEP_LIBS)
 423                                                 return;
 424                                 }
 425                         }
 426                 } );
 427         } foreach_in_group_end;
 428 }
 429
 430
 431 /* This is a low-level routine that doesn't maintain consistency
 432  * of all the board data structures. Use board_group_capture() from
 433  * your code. */
 434 static void
 435 board_remove_stone(struct board *board, coord_t c)
 436 {
 437         enum stone color = board_at(board, c);
 438         board_at(board, c) = S_NONE;
 439         group_at(board, c) = 0;
 440         board_hash_update(board, c, color);
 441
 442         /* Increase liberties of surrounding groups */
 443         coord_t coord = c;
 444         foreach_neighbor(board, coord, {
 445                 dec_neighbor_count_at(board, c, color);
 446                 board_group_addlib(board, group_at(board, c), coord, true);
 447         });
 448
 449         if (DEBUGL(6))
 450                 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
 451         board->f[board->flen++] = coord_raw(c);
 452 }
 453
 454
 455 static void profiling_noinline
 456 add_to_group(struct board *board, int gid, coord_t prevstone, coord_t coord)
 457 {
 458         foreach_neighbor(board, coord, {
 459                 if (board_at(board, c) == S_NONE)
 460                         board_group_addlib(board, gid, c, false);
 461         });
 462
 463         group_at(board, coord) = gid;
 464         groupnext_at(board, coord) = groupnext_at(board, prevstone);
 465         groupnext_at(board, prevstone) = coord_raw(coord);
 466
 467         if (DEBUGL(8))
 468                 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
 469                         coord_x(prevstone, board), coord_y(prevstone, board),
 470                         coord_x(coord, board), coord_y(coord, board),
 471                         groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
 472                         gid);
 473 }
 474
 475 static void profiling_noinline
 476 merge_groups(struct board *board, group_t group_to, group_t group_from)
 477 {
 478         if (DEBUGL(7))
 479                 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
 480                         group_from, group_to);
 481
 482         coord_t last_in_group;
 483         foreach_in_group(board, group_from) {
 484                 last_in_group = c;
 485                 group_at(board, c) = group_to;
 486         } foreach_in_group_end;
 487         groupnext_at(board, last_in_group) = groupnext_at(board, group_to);
 488         groupnext_at(board, group_to) = group_from;
 489
 490         struct group *gi_from = &board_group_info(board, group_from);
 491         struct group *gi_to = &board_group_info(board, group_to);
 492         if (gi_to->libs < GROUP_KEEP_LIBS) {
 493                 for (int i = 0; i < gi_from->libs; i++) {
 494                         for (int j = 0; j < gi_to->libs; j++)
 495                                 if (gi_to->lib[j] == gi_from->lib[i])
 496                                         goto next_from_lib;
 497                         if (gi_to->libs == 0)
 498                                 board_capturable_add(board, group_to);
 499                         else if (gi_to->libs == 1)
 500                                 board_capturable_rm(board, group_to);
 501                         gi_to->lib[gi_to->libs++] = gi_from->lib[i];
 502                         if (gi_to->libs >= GROUP_KEEP_LIBS)
 503                                 break;
 504 next_from_lib:;
 505                 }
 506         }
 507
 508         if (gi_from->libs == 1)
 509                 board_capturable_rm(board, group_from);
 510         memset(gi_from, 0, sizeof(struct group));
 511
 512         if (DEBUGL(7))
 513                 fprintf(stderr, "board_play_raw: merged group: %d\n",
 514                         group_to);
 515 }
 516
 517 static group_t profiling_noinline
 518 new_group(struct board *board, coord_t coord)
 519 {
 520         group_t gid = coord_raw(coord);
 521         struct group *gi = &board_group_info(board, gid);
 522         foreach_neighbor(board, coord, {
 523                 if (board_at(board, c) == S_NONE)
 524                         /* board_group_addlib is ridiculously expensive for us */
 525 #if GROUP_KEEP_LIBS < 4
 526                         if (gi->libs < GROUP_KEEP_LIBS)
 527 #endif
 528                         gi->lib[gi->libs++] = c;
 529         });
 530         if (gi->libs == 1)
 531                 board_capturable_add(board, gid);
 532         check_libs_consistency(board, gid);
 533
 534         group_at(board, coord) = gid;
 535         groupnext_at(board, coord) = 0;
 536
 537         if (DEBUGL(8))
 538                 fprintf(stderr, "new_group: added %d,%d to group %d\n",
 539                         coord_x(coord, board), coord_y(coord, board),
 540                         gid);
 541
 542         return gid;
 543 }
 544
 545 /* We played on a place with at least one liberty. We will become a member of
 546  * some group for sure. */
 547 static int profiling_noinline
 548 board_play_outside(struct board *board, struct move *m, int f)
 549 {
 550         coord_t coord = m->coord;
 551         enum stone color = m->color;
 552         enum stone other_color = stone_other(color);
 553         int gid = 0;
 554
 555         board->f[f] = board->f[--board->flen];
 556         if (DEBUGL(6))
 557                 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
 558
 559         foreach_neighbor(board, coord, {
 560                 enum stone ncolor = board_at(board, c);
 561                 group_t ngroup = group_at(board, c);
 562
 563                 inc_neighbor_count_at(board, c, color);
 564
 565                 if (!ngroup)
 566                         continue;
 567
 568                 board_group_rmlib(board, ngroup, coord);
 569                 if (DEBUGL(7))
 570                         fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
 571                                 ngroup, ncolor, color, other_color);
 572
 573                 if (ncolor == color && ngroup != gid) {
 574                         if (gid <= 0) {
 575                                 gid = ngroup;
 576                                 add_to_group(board, gid, c, coord);
 577                         } else {
 578                                 merge_groups(board, gid, ngroup);
 579                         }
 580                 } else if (ncolor == other_color) {
 581                         if (DEBUGL(8)) {
 582                                 struct group *gi = &board_group_info(board, ngroup);
 583                                 fprintf(stderr, "testing captured group %d[%s]: ", ngroup, coord2sstr(ngroup, board));
 584                                 for (int i = 0; i < gi_libs_bound(*gi); i++)
 585                                         fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
 586                                 fprintf(stderr, "\n");
 587                         }
 588                         if (unlikely(board_group_captured(board, ngroup)))
 589                                 board_group_capture(board, ngroup);
 590                 }
 591         });
 592
 593         if (unlikely(gid <= 0))
 594                 gid = new_group(board, coord);
 595
 596         board_at(board, coord) = color;
 597         board->last_move = *m;
 598         board->moves++;
 599         board_hash_update(board, coord, color);
 600         struct move ko = { pass, S_NONE };
 601         board->ko = ko;
 602
 603         return gid;
 604 }
 605
 606 /* We played in an eye-like shape. Either we capture at least one of the eye
 607  * sides in the process of playing, or return -1. */
 608 static int profiling_noinline
 609 board_play_in_eye(struct board *board, struct move *m, int f)
 610 {
 611         coord_t coord = m->coord;
 612         enum stone color = m->color;
 613         /* Check ko: Capture at a position of ko capture one move ago */
 614         if (unlikely(color == board->ko.color && coord_eq(coord, board->ko.coord))) {
 615                 if (DEBUGL(5))
 616                         fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
 617                 return -1;
 618         } else if (DEBUGL(6)) {
 619                 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
 620                         color, coord_x(coord, board), coord_y(coord, board),
 621                         board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
 622         }
 623
 624         struct move ko = { pass, S_NONE };
 625
 626         board->f[f] = board->f[--board->flen];
 627         if (DEBUGL(6))
 628                 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
 629
 630         int captured_groups = 0;
 631
 632         foreach_neighbor(board, coord, {
 633                 group_t group = group_at(board, c);
 634                 if (!group)
 635                         continue;
 636
 637                 board_group_rmlib(board, group, coord);
 638                 if (DEBUGL(7))
 639                         fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
 640                                 group);
 641
 642                 if (unlikely(board_group_captured(board, group))) {
 643                         captured_groups++;
 644                         if (board_group_capture(board, group) == 1) {
 645                                 /* If we captured multiple groups at once,
 646                                  * we can't be fighting ko so we don't need
 647                                  * to check for that. */
 648                                 ko.color = stone_other(color);
 649                                 ko.coord = c;
 650                                 if (DEBUGL(5))
 651                                         fprintf(stderr, "guarding ko at %d,%d,%d\n", ko.color, coord_x(ko.coord, board), coord_y(ko.coord, board));
 652                         }
 653                 }
 654         });
 655
 656         if (likely(captured_groups == 0)) {
 657                 if (DEBUGL(5)) {
 658                         if (DEBUGL(6))
 659                                 board_print(board, stderr);
 660                         fprintf(stderr, "board_check: one-stone suicide\n");
 661                 }
 662
 663                 foreach_neighbor(board, coord, {
 664                         board_group_addlib(board, group_at(board, c), coord, true);
 665                         if (DEBUGL(7))
 666                                 fprintf(stderr, "board_play_raw: restoring libs for group %d\n",
 667                                         group_at(board, c));
 668                 });
 669
 670                 coord_t c = coord;
 671                 if (DEBUGL(6))
 672                         fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
 673                 board->f[board->flen++] = coord_raw(c);
 674                 return -1;
 675         }
 676
 677         foreach_neighbor(board, coord, {
 678                 inc_neighbor_count_at(board, c, color);
 679         });
 680
 681         board_at(board, coord) = color;
 682
 683         board->last_move = *m;
 684         board->moves++;
 685         board_hash_update(board, coord, color);
 686         board_hash_commit(board);
 687         board->ko = ko;
 688
 689         return new_group(board, coord);
 690 }
 691
 692 static int __attribute__((flatten))
 693 board_play_f(struct board *board, struct move *m, int f)
 694 {
 695         if (DEBUGL(7)) {
 696                 fprintf(stderr, "board_play(): ---- Playing %d,%d\n", coord_x(m->coord, board), coord_y(m->coord, board));
 697         }
 698         if (likely(!board_is_eyelike(board, &m->coord, stone_other(m->color)))) {
 699                 /* NOT playing in an eye. Thus this move has to succeed. (This
 700                  * is thanks to New Zealand rules. Otherwise, multi-stone
 701                  * suicide might fail.) */
 702                 int gid = board_play_outside(board, m, f);
 703                 if (unlikely(board_group_captured(board, gid))) {
 704                         board_group_capture(board, gid);
 705                 }
 706                 board_hash_commit(board);
 707                 return 0;
 708         } else {
 709                 return board_play_in_eye(board, m, f);
 710         }
 711 }
 712
 713 int
 714 board_play(struct board *board, struct move *m)
 715 {
 716         if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
 717                 board->last_move = *m;
 718                 return 0;
 719         }
 720
 721         int f;
 722         for (f = 0; f < board->flen; f++)
 723                 if (board->f[f] == coord_raw(m->coord))
 724                         return board_play_f(board, m, f);
 725
 726         if (DEBUGL(7))
 727                 fprintf(stderr, "board_check: stone exists\n");
 728         return -1;
 729 }
 730
 731
 732 static inline bool
 733 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f)
 734 {
 735         coord_raw(*coord) = b->f[f];
 736         if (is_pass(*coord))
 737                 return random_pass;
 738         struct move m = { *coord, color };
 739         if (DEBUGL(6))
 740                 fprintf(stderr, "trying random move %d: %d,%d\n", f, coord_x(*coord, b), coord_y(*coord, b));
 741         return (!board_is_one_point_eye(b, coord, color) /* bad idea to play into one, usually */
 742                 && board_play_f(b, &m, f) >= 0);
 743 }
 744
 745 void
 746 board_play_random(struct board *b, enum stone color, coord_t *coord)
 747 {
 748         int base = fast_random(b->flen);
 749         coord_pos(*coord, base, b);
 750         if (likely(board_try_random_move(b, color, coord, base)))
 751                 return;
 752
 753         int f;
 754         for (f = base + 1; f < b->flen; f++)
 755                 if (board_try_random_move(b, color, coord, f))
 756                         return;
 757         for (f = 0; f < base; f++)
 758                 if (board_try_random_move(b, color, coord, f))
 759                         return;
 760
 761         *coord = pass;
 762 }
 763
 764
 765 bool
 766 board_is_eyelike(struct board *board, coord_t *coord, enum stone eye_color)
 767 {
 768         return (neighbor_count_at(board, *coord, eye_color) + neighbor_count_at(board, *coord, S_OFFBOARD)) == 4;
 769 }
 770
 771 bool
 772 board_is_one_point_eye(struct board *board, coord_t *coord, enum stone eye_color)
 773 {
 774         enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
 775
 776         if (likely(neighbor_count_at(board, *coord, eye_color) + neighbor_count_at(board, *coord, S_OFFBOARD) < 4)) {
 777                 return false;
 778         }
 779
 780         /* XXX: We attempt false eye detection but we will yield false
 781          * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
 782
 783         foreach_diag_neighbor(board, *coord) {
 784                 color_diag_libs[(enum stone) board_at(board, c)]++;
 785         } foreach_diag_neighbor_end;
 786         color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
 787         return likely(color_diag_libs[stone_other(eye_color)] < 2);
 788 }
 789
 790 enum stone
 791 board_get_one_point_eye(struct board *board, coord_t *coord)
 792 {
 793         if (board_is_one_point_eye(board, coord, S_WHITE))
 794                 return S_WHITE;
 795         else if (board_is_one_point_eye(board, coord, S_BLACK))
 796                 return S_BLACK;
 797         else
 798                 return S_NONE;
 799 }
 800
 801
 802 int profiling_noinline
 803 board_group_capture(struct board *board, int group)
 804 {
 805         int stones = 0;
 806
 807         foreach_in_group(board, group) {
 808                 board->captures[stone_other(board_at(board, c))]++;
 809                 board_remove_stone(board, c);
 810                 stones++;
 811         } foreach_in_group_end;
 812
 813         if (board_group_info(board, group).libs == 1)
 814                 board_capturable_rm(board, group);
 815         memset(&board_group_info(board, group), 0, sizeof(struct group));
 816
 817         return stones;
 818 }
 819
 820 bool
 821 board_group_in_atari(struct board *board, group_t group, coord_t *lastlib)
 822 {
 823         if (board_group_info(board, group).libs != 1)
 824                 return false;
 825         *lastlib = board_group_info(board, group).lib[0];
 826         return true;
 827 }
 828
 829 bool
 830 board_group_can_atari(struct board *board, group_t group, coord_t lastlib[2])
 831 {
 832         if (board_group_info(board, group).libs != 2)
 833                 return false;
 834         lastlib[0] = board_group_info(board, group).lib[0];
 835         lastlib[1] = board_group_info(board, group).lib[1];
 836         return true;
 837 }
 838
 839
 840 static enum stone
 841 board_tromp_taylor_owner(struct board *board, coord_t c)
 842 {
 843         int x = coord_x(c, board), y = coord_y(c, board);
 844         enum stone color = S_NONE;
 845 #define TEST_REACH(xx, yy) \
 846         { \
 847                 enum stone c2 = board_atxy(board, xx, yy); \
 848                 if (c2 != S_NONE) { \
 849                         if (color != S_NONE && color != c2) \
 850                                 return S_NONE; \
 851                         color = c2; \
 852                         break; \
 853                 } \
 854         }
 855         for (int i = x; i > 0; i--)
 856                 TEST_REACH(i, y);
 857         for (int i = x; i < board_size(board) - 1; i++)
 858                 TEST_REACH(i, y);
 859         for (int i = y; i > 0; i--)
 860                 TEST_REACH(x, i);
 861         for (int i = y; i < board_size(board) - 1; i++)
 862                 TEST_REACH(x, i);
 863         return color;
 864 }
 865
 866 /* Tromp-Taylor Counting */
 867 float
 868 board_official_score(struct board *board)
 869 {
 870
 871         /* A point P, not colored C, is said to reach C, if there is a path of
 872          * (vertically or horizontally) adjacent points of P's color from P to
 873          * a point of color C.
 874          *
 875          * A player's score is the number of points of her color, plus the
 876          * number of empty points that reach only her color. */
 877
 878         int scores[S_MAX];
 879         memset(scores, 0, sizeof(scores));
 880
 881         foreach_point(board) {
 882                 enum stone color = board_at(board, c);
 883                 if (color == S_NONE)
 884                         color = board_tromp_taylor_owner(board, c);
 885                 scores[color]++;
 886         } foreach_point_end;
 887
 888         return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
 889 }
 890
 891 float
 892 board_fast_score(struct board *board)
 893 {
 894         int scores[S_MAX];
 895         memset(scores, 0, sizeof(scores));
 896
 897         foreach_point(board) {
 898                 enum stone color = board_at(board, c);
 899                 if (color == S_NONE)
 900                         color = board_get_one_point_eye(board, &c);
 901                 scores[color]++;
 902                 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
 903         } foreach_point_end;
 904
 905         return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
 906 }
 907
 908
 909 bool
 910 valid_escape_route(struct board *b, enum stone color, coord_t to)
 911 {
 912         /* Assess if we actually gain any liberties by this escape route.
 913          * Note that this is not 100% as we cannot check whether we are
 914          * connecting out or just to ourselves. */
 915         /* Also, we prohibit 1-1 here:
 916          *  X X X X |
 917          *  O X O O |
 918          *  O O X O |
 919          *  .(O)X . |
 920          *  --------+
 921          */
 922         int friends = neighbor_count_at(b, to, color);
 923         int borders = neighbor_count_at(b, to, S_OFFBOARD);
 924         int libs = immediate_liberty_count(b, to);
 925         return (friends > 1 && friends + borders < 4) || (libs > 1);
 926 }
 927
 928
 929 bool
 930 board_stone_radar(struct board *b, coord_t coord, int distance)
 931 {
 932         int bounds[4] = {
 933                 coord_x(coord, b) - distance,
 934                 coord_y(coord, b) - distance,
 935                 coord_x(coord, b) + distance,
 936                 coord_y(coord, b) + distance
 937         };
 938         for (int i = 0; i < 4; i++)
 939                 if (bounds[i] < 1)
 940                         bounds[i] = 1;
 941                 else if (bounds[i] > board_size(b) - 2)
 942                         bounds[i] = board_size(b) - 2;
 943         for (int x = bounds[0]; x <= bounds[2]; x++)
 944                 for (int y = bounds[1]; y <= bounds[3]; y++)
 945                         if (board_atxy(b, x, y) != S_NONE) {
 946                                 //fprintf(stderr, "radar %d,%d,%d: %d,%d (%d)\n", coord_x(coord, b), coord_y(coord, b), distance, x, y, board_atxy(b, x, y));
 947                                 return true;
 948                         }
 949         return false;
 950 }