board.c

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