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