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