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