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, group_t 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->last_move2 = b->last_ko = 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
  41         // Default setup
  42         b->size = 9 + 2;
  43         board_clear(b);
  44
  45         return b;
  46 }
  47
  48 struct board *
  49 board_copy(struct board *b2, struct board *b1)
  50 {
  51         memcpy(b2, b1, sizeof(struct board));
  52
  53         int bsize = board_size2(b2) * sizeof(*b2->b);
  54         int gsize = board_size2(b2) * sizeof(*b2->g);
  55         int fsize = board_size2(b2) * sizeof(*b2->f);
  56         int nsize = board_size2(b2) * sizeof(*b2->n);
  57         int psize = board_size2(b2) * sizeof(*b2->p);
  58         int hsize = board_size2(b2) * 2 * sizeof(*b2->h);
  59         int gisize = board_size2(b2) * sizeof(*b2->gi);
  60 #ifdef WANT_BOARD_C
  61         int csize = board_size2(b2) * sizeof(*b2->c);
  62 #else
  63         int csize = 0;
  64 #endif
  65         void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
  66         memcpy(x, b1->b, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
  67         b2->b = x; x += bsize;
  68         b2->g = x; x += gsize;
  69         b2->f = x; x += fsize;
  70         b2->p = x; x += psize;
  71         b2->n = x; x += nsize;
  72         b2->h = x; x += hsize;
  73         b2->gi = x; x += gisize;
  74 #ifdef WANT_BOARD_C
  75         b2->c = x; x += csize;
  76 #endif
  77
  78         return b2;
  79 }
  80
  81 void
  82 board_done_noalloc(struct board *board)
  83 {
  84         if (board->b) free(board->b);
  85 }
  86
  87 void
  88 board_done(struct board *board)
  89 {
  90         board_done_noalloc(board);
  91         free(board);
  92 }
  93
  94 void
  95 board_resize(struct board *board, int size)
  96 {
  97 #ifdef BOARD_SIZE
  98         assert(board_size(board) == size + 2);
  99 #else
 100         board_size(board) = size + 2 /* S_OFFBOARD margin */;
 101         board_size2(board) = board_size(board) * board_size(board);
 102 #endif
 103         if (board->b)
 104                 free(board->b);
 105
 106         int bsize = board_size2(board) * sizeof(*board->b);
 107         int gsize = board_size2(board) * sizeof(*board->g);
 108         int fsize = board_size2(board) * sizeof(*board->f);
 109         int nsize = board_size2(board) * sizeof(*board->n);
 110         int psize = board_size2(board) * sizeof(*board->p);
 111         int hsize = board_size2(board) * 2 * sizeof(*board->h);
 112         int gisize = board_size2(board) * sizeof(*board->gi);
 113 #ifdef WANT_BOARD_C
 114         int csize = board_size2(board) * sizeof(*board->c);
 115 #else
 116         int csize = 0;
 117 #endif
 118         void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
 119         memset(x, 0, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
 120         board->b = x; x += bsize;
 121         board->g = x; x += gsize;
 122         board->f = x; x += fsize;
 123         board->p = x; x += psize;
 124         board->n = x; x += nsize;
 125         board->h = x; x += hsize;
 126         board->gi = x; x += gisize;
 127 #ifdef WANT_BOARD_C
 128         board->c = x; x += csize;
 129 #endif
 130 }
 131
 132 void
 133 board_clear(struct board *board)
 134 {
 135         int size = board_size(board);
 136         float komi = board->komi;
 137
 138         board_done_noalloc(board);
 139         board_setup(board);
 140         board_resize(board, size - 2 /* S_OFFBOARD margin */);
 141
 142         board->komi = komi;
 143
 144         /* Setup initial symmetry */
 145         board->symmetry.d = 1;
 146         board->symmetry.x1 = board->symmetry.y1 = board_size(board) / 2;
 147         board->symmetry.x2 = board->symmetry.y2 = board_size(board) - 1;
 148         board->symmetry.type = SYM_FULL;
 149
 150         /* Draw the offboard margin */
 151         int top_row = board_size2(board) - board_size(board);
 152         int i;
 153         for (i = 0; i < board_size(board); i++)
 154                 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
 155         for (i = 0; i <= top_row; i += board_size(board))
 156                 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
 157
 158         foreach_point(board) {
 159                 coord_t coord = c;
 160                 if (board_at(board, coord) == S_OFFBOARD)
 161                         continue;
 162                 foreach_neighbor(board, c, {
 163                         inc_neighbor_count_at(board, coord, board_at(board, c));
 164                 } );
 165         } foreach_point_end;
 166
 167         /* First, pass is always a free position. */
 168         board->f[board->flen++] = coord_raw(pass);
 169         /* All positions are free! Except the margin. */
 170         for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
 171                 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
 172                         board->f[board->flen++] = i;
 173
 174         /* Initialize zobrist hashtable. */
 175         foreach_point(board) {
 176                 int max = (sizeof(hash_t) << history_hash_bits);
 177                 /* fast_random() is 16-bit only */
 178                 board->h[coord_raw(c) * 2] = ((hash_t) fast_random(max))
 179                                 | ((hash_t) fast_random(max) << 16)
 180                                 | ((hash_t) fast_random(max) << 32)
 181                                 | ((hash_t) fast_random(max) << 48);
 182                 if (!board->h[coord_raw(c) * 2])
 183                         /* Would be kinda "oops". */
 184                         board->h[coord_raw(c) * 2] = 1;
 185                 /* And once again for white */
 186                 board->h[coord_raw(c) * 2 + 1] = ((hash_t) fast_random(max))
 187                                 | ((hash_t) fast_random(max) << 16)
 188                                 | ((hash_t) fast_random(max) << 32)
 189                                 | ((hash_t) fast_random(max) << 48);
 190                 if (!board->h[coord_raw(c) * 2 + 1])
 191                         board->h[coord_raw(c) * 2 + 1] = 1;
 192         } foreach_point_end;
 193 }
 194
 195
 196 static void
 197 board_print_top(struct board *board, FILE *f, int c)
 198 {
 199         for (int i = 0; i < c; i++) {
 200                 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
 201                 fprintf(f, "      ");
 202                 for (int x = 1; x < board_size(board) - 1; x++)
 203                         fprintf(f, "%c ", asdf[x - 1]);
 204                 fprintf(f, " ");
 205         }
 206         fprintf(f, "\n");
 207         for (int i = 0; i < c; i++) {
 208                 fprintf(f, "    +-");
 209                 for (int x = 1; x < board_size(board) - 1; x++)
 210                         fprintf(f, "--");
 211                 fprintf(f, "+");
 212         }
 213         fprintf(f, "\n");
 214 }
 215
 216 static void
 217 board_print_bottom(struct board *board, FILE *f, int c)
 218 {
 219         for (int i = 0; i < c; i++) {
 220                 fprintf(f, "    +-");
 221                 for (int x = 1; x < board_size(board) - 1; x++)
 222                         fprintf(f, "--");
 223                 fprintf(f, "+");
 224         }
 225         fprintf(f, "\n");
 226 }
 227
 228 typedef void (*board_cprint)(struct board *b, coord_t c, FILE *f);
 229
 230 static void
 231 board_print_row(struct board *board, int y, FILE *f, board_cprint cprint)
 232 {
 233         fprintf(f, " %2d | ", y);
 234         for (int x = 1; x < board_size(board) - 1; x++) {
 235                 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
 236                         fprintf(f, "%c)", stone2char(board_atxy(board, x, y)));
 237                 else
 238                         fprintf(f, "%c ", stone2char(board_atxy(board, x, y)));
 239         }
 240         fprintf(f, "|");
 241         if (cprint) {
 242                 fprintf(f, " %2d | ", y);
 243                 for (int x = 1; x < board_size(board) - 1; x++) {
 244                         cprint(board, coord_xy(board, x, y), f);
 245                 }
 246                 fprintf(f, "|");
 247         }
 248         fprintf(f, "\n");
 249 }
 250
 251 static void
 252 board_print_x(struct board *board, FILE *f, board_cprint cprint)
 253 {
 254         fprintf(f, "Move: % 3d  Komi: %2.1f  Handicap: %d  Captures B: %d W: %d\n",
 255                 board->moves, board->komi, board->handicap,
 256                 board->captures[S_BLACK], board->captures[S_WHITE]);
 257         board_print_top(board, f, 1 + !!cprint);
 258         for (int y = board_size(board) - 2; y >= 1; y--)
 259                 board_print_row(board, y, f, cprint);
 260         board_print_bottom(board, f, 1 + !!cprint);
 261         fprintf(f, "\n");
 262 }
 263
 264 static void
 265 cprint_group(struct board *board, coord_t c, FILE *f)
 266 {
 267         fprintf(f, "%d ", group_base(group_at(board, c)));
 268 }
 269
 270 void
 271 board_print(struct board *board, FILE *f)
 272 {
 273         board_print_x(board, f, DEBUGL(6) ? cprint_group : NULL);
 274 }
 275
 276
 277 /* Update board hash with given coordinate. */
 278 static void profiling_noinline
 279 board_hash_update(struct board *board, coord_t coord, enum stone color)
 280 {
 281         board->hash ^= hash_at(board, coord, color);
 282         if (DEBUGL(8))
 283                 fprintf(stderr, "board_hash_update(%d,%d,%d) ^ %llx -> %llx\n", color, coord_x(coord, board), coord_y(coord, board), hash_at(board, coord, color), board->hash);
 284 }
 285
 286 /* Commit current board hash to history. */
 287 static void profiling_noinline
 288 board_hash_commit(struct board *board)
 289 {
 290         if (DEBUGL(8))
 291                 fprintf(stderr, "board_hash_commit %llx\n", board->hash);
 292         if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
 293                 board->history_hash[board->hash & history_hash_mask] = board->hash;
 294         } else {
 295                 hash_t i = board->hash;
 296                 while (board->history_hash[i & history_hash_mask]) {
 297                         if (board->history_hash[i & history_hash_mask] == board->hash) {
 298                                 if (DEBUGL(5))
 299                                         fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
 300                                                 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
 301                                 board->superko_violation = true;
 302                                 return;
 303                         }
 304                         i = history_hash_next(i);
 305                 }
 306                 board->history_hash[i & history_hash_mask] = board->hash;
 307         }
 308 }
 309
 310
 311 void
 312 board_symmetry_update(struct board *b, struct board_symmetry *symmetry, coord_t c)
 313 {
 314         if (likely(symmetry->type == SYM_NONE)) {
 315                 /* Fully degenerated already. We do not support detection
 316                  * of restoring of symmetry, assuming that this is too rare
 317                  * a case to handle. */
 318                 return;
 319         }
 320
 321         int x = coord_x(c, b), y = coord_y(c, b), t = board_size(b) / 2;
 322         int dx = board_size(b) - 1 - x; /* for SYM_DOWN */
 323         if (DEBUGL(6)) {
 324                 fprintf(stderr, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
 325                         symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
 326                         symmetry->d, symmetry->type, x, y);
 327         }
 328
 329         switch (symmetry->type) {
 330                 case SYM_FULL:
 331                         if (x == t && y == t) {
 332                                 /* Tengen keeps full symmetry. */
 333                                 return;
 334                         }
 335                         /* New symmetry now? */
 336                         if (x == y) {
 337                                 symmetry->type = SYM_DIAG_UP;
 338                                 symmetry->x1 = symmetry->y1 = 1;
 339                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 340                                 symmetry->d = 1;
 341                         } else if (dx == y) {
 342                                 symmetry->type = SYM_DIAG_DOWN;
 343                                 symmetry->x1 = symmetry->y1 = 1;
 344                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 345                                 symmetry->d = 1;
 346                         } else if (x == t) {
 347                                 symmetry->type = SYM_HORIZ;
 348                                 symmetry->y1 = 1;
 349                                 symmetry->y2 = board_size(b) - 1;
 350                                 symmetry->d = 0;
 351                         } else if (y == t) {
 352                                 symmetry->type = SYM_VERT;
 353                                 symmetry->x1 = 1;
 354                                 symmetry->x2 = board_size(b) - 1;
 355                                 symmetry->d = 0;
 356                         } else {
 357 break_symmetry:
 358                                 symmetry->type = SYM_NONE;
 359                                 symmetry->x1 = symmetry->y1 = 1;
 360                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 361                                 symmetry->d = 0;
 362                         }
 363                         break;
 364                 case SYM_DIAG_UP:
 365                         if (x == y)
 366                                 return;
 367                         goto break_symmetry;
 368                 case SYM_DIAG_DOWN:
 369                         if (dx == y)
 370                                 return;
 371                         goto break_symmetry;
 372                 case SYM_HORIZ:
 373                         if (x == t)
 374                                 return;
 375                         goto break_symmetry;
 376                 case SYM_VERT:
 377                         if (y == t)
 378                                 return;
 379                         goto break_symmetry;
 380                 case SYM_NONE:
 381                         assert(0);
 382                         break;
 383         }
 384
 385         if (DEBUGL(6)) {
 386                 fprintf(stderr, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
 387                         symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
 388                         symmetry->d, symmetry->type);
 389         }
 390         /* Whew. */
 391 }
 392
 393
 394 void
 395 board_handicap_stone(struct board *board, int x, int y, FILE *f)
 396 {
 397         struct move m;
 398         m.color = S_BLACK; m.coord = coord_xy(board, x, y);
 399
 400         board_play(board, &m);
 401         /* Simulate white passing; otherwise, UCT search can get confused since
 402          * tree depth parity won't match the color to move. */
 403         board->moves++;
 404
 405         char *str = coord2str(m.coord, board);
 406         if (DEBUGL(1))
 407                 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
 408         fprintf(f, "%s ", str);
 409         free(str);
 410 }
 411
 412 void
 413 board_handicap(struct board *board, int stones, FILE *f)
 414 {
 415         int margin = 3 + (board_size(board) >= 13);
 416         int min = margin;
 417         int mid = board_size(board) / 2;
 418         int max = board_size(board) - 1 - margin;
 419         const int places[][2] = {
 420                 { min, min }, { max, max }, { max, min }, { min, max },
 421                 { min, mid }, { max, mid },
 422                 { mid, min }, { mid, max },
 423                 { mid, mid },
 424         };
 425
 426         board->handicap = stones;
 427
 428         if (stones == 5 || stones == 7) {
 429                 board_handicap_stone(board, mid, mid, f);
 430                 stones--;
 431         }
 432
 433         int i;
 434         for (i = 0; i < stones; i++)
 435                 board_handicap_stone(board, places[i][0], places[i][1], f);
 436 }
 437
 438
 439 static void __attribute__((noinline))
 440 check_libs_consistency(struct board *board, group_t g)
 441 {
 442 #ifdef DEBUG
 443         if (!g) return;
 444         struct group *gi = &board_group_info(board, g);
 445         for (int i = 0; i < GROUP_KEEP_LIBS; i++)
 446                 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
 447                         fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
 448                         assert(0);
 449                 }
 450 #endif
 451 }
 452
 453 static void
 454 board_capturable_add(struct board *board, group_t group)
 455 {
 456 #ifdef WANT_BOARD_C
 457         //fprintf(stderr, "add of group %d (%d)\n", group_base(group), board->clen);
 458         assert(group);
 459         assert(board->clen < board_size2(board));
 460         board->c[board->clen++] = group;
 461 #endif
 462 }
 463 static void
 464 board_capturable_rm(struct board *board, group_t group)
 465 {
 466 #ifdef WANT_BOARD_C
 467         //fprintf(stderr, "rm of group %d\n", group_base(group));
 468         for (int i = 0; i < board->clen; i++) {
 469                 if (unlikely(board->c[i] == group)) {
 470                         board->c[i] = board->c[--board->clen];
 471                         return;
 472                 }
 473         }
 474         fprintf(stderr, "rm of bad group %d\n", group_base(group));
 475         assert(0);
 476 #endif
 477 }
 478
 479 static void
 480 board_group_addlib(struct board *board, group_t group, coord_t coord)
 481 {
 482         if (DEBUGL(7)) {
 483                 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
 484                         group_base(group), coord2sstr(group_base(group), board),
 485                         board_group_info(board, group).libs, coord2sstr(coord, board));
 486         }
 487
 488         check_libs_consistency(board, group);
 489
 490         struct group *gi = &board_group_info(board, group);
 491         if (gi->libs < GROUP_KEEP_LIBS) {
 492                 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
 493 #if 0
 494                         /* Seems extra branch just slows it down */
 495                         if (!gi->lib[i])
 496                                 break;
 497 #endif
 498                         if (unlikely(gi->lib[i] == coord))
 499                                 return;
 500                 }
 501                 if (gi->libs == 0)
 502                         board_capturable_add(board, group);
 503                 else if (gi->libs == 1)
 504                         board_capturable_rm(board, group);
 505                 gi->lib[gi->libs++] = coord;
 506         }
 507
 508         check_libs_consistency(board, group);
 509 }
 510
 511 static void
 512 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
 513 {
 514         /* Add extra liberty from the board to our liberty list. */
 515         unsigned char watermark[board_size2(board) / 8];
 516         memset(watermark, 0, sizeof(watermark));
 517 #define watermark_get(c)        (watermark[coord_raw(c) >> 3] & (1 << (coord_raw(c) & 7)))
 518 #define watermark_set(c)        watermark[coord_raw(c) >> 3] |= (1 << (coord_raw(c) & 7))
 519
 520         for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
 521                 watermark_set(gi->lib[i]);
 522         watermark_set(avoid);
 523
 524         foreach_in_group(board, group) {
 525                 coord_t coord2 = c;
 526                 foreach_neighbor(board, coord2, {
 527                         if (board_at(board, c) + watermark_get(c) != S_NONE)
 528                                 continue;
 529                         watermark_set(c);
 530                         gi->lib[gi->libs++] = c;
 531                         if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
 532                                 return;
 533                 } );
 534         } foreach_in_group_end;
 535 #undef watermark_get
 536 #undef watermark_set
 537 }
 538
 539 static void
 540 board_group_rmlib(struct board *board, group_t group, coord_t coord)
 541 {
 542         if (DEBUGL(7)) {
 543                 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
 544                         group_base(group), coord2sstr(group_base(group), board),
 545                         board_group_info(board, group).libs, coord2sstr(coord, board));
 546         }
 547
 548         struct group *gi = &board_group_info(board, group);
 549         for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
 550 #if 0
 551                 /* Seems extra branch just slows it down */
 552                 if (!gi->lib[i])
 553                         break;
 554 #endif
 555                 if (likely(gi->lib[i] != coord))
 556                         continue;
 557
 558                 gi->lib[i] = gi->lib[--gi->libs];
 559                 gi->lib[gi->libs] = 0;
 560
 561                 check_libs_consistency(board, group);
 562
 563                 /* Postpone refilling lib[] until we need to. */
 564                 assert(GROUP_REFILL_LIBS > 1);
 565                 if (gi->libs > GROUP_REFILL_LIBS)
 566                         return;
 567                 if (gi->libs == GROUP_REFILL_LIBS)
 568                         board_group_find_extra_libs(board, group, gi, coord);
 569
 570                 if (gi->libs == 1)
 571                         board_capturable_add(board, group);
 572                 else if (gi->libs == 0)
 573                         board_capturable_rm(board, group);
 574                 return;
 575         }
 576
 577         /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
 578          * can call this multiple times per coord. */
 579         check_libs_consistency(board, group);
 580         return;
 581 }
 582
 583
 584 /* This is a low-level routine that doesn't maintain consistency
 585  * of all the board data structures. Use board_group_capture() from
 586  * your code. */
 587 static void
 588 board_remove_stone(struct board *board, coord_t c)
 589 {
 590         enum stone color = board_at(board, c);
 591         board_at(board, c) = S_NONE;
 592         group_at(board, c) = 0;
 593         board_hash_update(board, c, color);
 594
 595         /* Increase liberties of surrounding groups */
 596         coord_t coord = c;
 597         foreach_neighbor(board, coord, {
 598                 dec_neighbor_count_at(board, c, color);
 599                 group_t g = group_at(board, c);
 600                 if (g)
 601                         board_group_addlib(board, g, coord);
 602         });
 603
 604         if (DEBUGL(6))
 605                 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
 606         board->f[board->flen++] = coord_raw(c);
 607 }
 608
 609
 610 static void profiling_noinline
 611 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
 612 {
 613         foreach_neighbor(board, coord, {
 614                 if (board_at(board, c) == S_NONE)
 615                         board_group_addlib(board, group, c);
 616         });
 617
 618         group_at(board, coord) = group;
 619         groupnext_at(board, coord) = groupnext_at(board, prevstone);
 620         groupnext_at(board, prevstone) = coord_raw(coord);
 621
 622         if (DEBUGL(8))
 623                 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
 624                         coord_x(prevstone, board), coord_y(prevstone, board),
 625                         coord_x(coord, board), coord_y(coord, board),
 626                         groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
 627                         group_base(group));
 628 }
 629
 630 static void profiling_noinline
 631 merge_groups(struct board *board, group_t group_to, group_t group_from)
 632 {
 633         if (DEBUGL(7))
 634                 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
 635                         group_base(group_from), group_base(group_to));
 636
 637         coord_t last_in_group;
 638         foreach_in_group(board, group_from) {
 639                 last_in_group = c;
 640                 group_at(board, c) = group_to;
 641         } foreach_in_group_end;
 642         groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
 643         groupnext_at(board, group_base(group_to)) = group_base(group_from);
 644
 645         struct group *gi_from = &board_group_info(board, group_from);
 646         struct group *gi_to = &board_group_info(board, group_to);
 647         if (gi_to->libs < GROUP_KEEP_LIBS) {
 648                 for (int i = 0; i < gi_from->libs; i++) {
 649                         for (int j = 0; j < gi_to->libs; j++)
 650                                 if (gi_to->lib[j] == gi_from->lib[i])
 651                                         goto next_from_lib;
 652                         if (gi_to->libs == 0)
 653                                 board_capturable_add(board, group_to);
 654                         else if (gi_to->libs == 1)
 655                                 board_capturable_rm(board, group_to);
 656                         gi_to->lib[gi_to->libs++] = gi_from->lib[i];
 657                         if (gi_to->libs >= GROUP_KEEP_LIBS)
 658                                 break;
 659 next_from_lib:;
 660                 }
 661         }
 662
 663         if (gi_from->libs == 1)
 664                 board_capturable_rm(board, group_from);
 665         memset(gi_from, 0, sizeof(struct group));
 666
 667         if (DEBUGL(7))
 668                 fprintf(stderr, "board_play_raw: merged group: %d\n",
 669                         group_base(group_to));
 670 }
 671
 672 static group_t profiling_noinline
 673 new_group(struct board *board, coord_t coord)
 674 {
 675         group_t group = coord_raw(coord);
 676         struct group *gi = &board_group_info(board, group);
 677         foreach_neighbor(board, coord, {
 678                 if (board_at(board, c) == S_NONE)
 679                         /* board_group_addlib is ridiculously expensive for us */
 680 #if GROUP_KEEP_LIBS < 4
 681                         if (gi->libs < GROUP_KEEP_LIBS)
 682 #endif
 683                         gi->lib[gi->libs++] = c;
 684         });
 685         if (gi->libs == 1)
 686                 board_capturable_add(board, group);
 687         check_libs_consistency(board, group);
 688
 689         group_at(board, coord) = group;
 690         groupnext_at(board, coord) = 0;
 691
 692         if (DEBUGL(8))
 693                 fprintf(stderr, "new_group: added %d,%d to group %d\n",
 694                         coord_x(coord, board), coord_y(coord, board),
 695                         group_base(group));
 696
 697         return group;
 698 }
 699
 700 static inline group_t
 701 play_one_neighbor(struct board *board,
 702                 coord_t coord, enum stone color, enum stone other_color,
 703                 coord_t c, group_t group)
 704 {
 705         enum stone ncolor = board_at(board, c);
 706         group_t ngroup = group_at(board, c);
 707
 708         inc_neighbor_count_at(board, c, color);
 709
 710         if (!ngroup)
 711                 return group;
 712
 713         board_group_rmlib(board, ngroup, coord);
 714         if (DEBUGL(7))
 715                 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
 716                         group_base(ngroup), ncolor, color, other_color);
 717
 718         if (ncolor == color && ngroup != group) {
 719                 if (!group) {
 720                         group = ngroup;
 721                         add_to_group(board, group, c, coord);
 722                 } else {
 723                         merge_groups(board, group, ngroup);
 724                 }
 725         } else if (ncolor == other_color) {
 726                 if (DEBUGL(8)) {
 727                         struct group *gi = &board_group_info(board, ngroup);
 728                         fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
 729                         for (int i = 0; i < GROUP_KEEP_LIBS; i++)
 730                                 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
 731                         fprintf(stderr, "\n");
 732                 }
 733                 if (unlikely(board_group_captured(board, ngroup)))
 734                         board_group_capture(board, ngroup);
 735         }
 736         return group;
 737 }
 738
 739 /* We played on a place with at least one liberty. We will become a member of
 740  * some group for sure. */
 741 static group_t profiling_noinline
 742 board_play_outside(struct board *board, struct move *m, int f)
 743 {
 744         coord_t coord = m->coord;
 745         enum stone color = m->color;
 746         enum stone other_color = stone_other(color);
 747         group_t group = 0;
 748
 749         board->f[f] = board->f[--board->flen];
 750         if (DEBUGL(6))
 751                 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
 752
 753         foreach_neighbor(board, coord, {
 754                         group = play_one_neighbor(board, coord, color, other_color, c, group);
 755         });
 756
 757         if (unlikely(!group))
 758                 group = new_group(board, coord);
 759
 760         board_at(board, coord) = color;
 761         board->last_move2 = board->last_move;
 762         board->last_move = *m;
 763         board->moves++;
 764         board_hash_update(board, coord, color);
 765         board_symmetry_update(board, &board->symmetry, coord);
 766         struct move ko = { pass, S_NONE };
 767         board->ko = ko;
 768
 769         return group;
 770 }
 771
 772 /* We played in an eye-like shape. Either we capture at least one of the eye
 773  * sides in the process of playing, or return -1. */
 774 static int profiling_noinline
 775 board_play_in_eye(struct board *board, struct move *m, int f)
 776 {
 777         coord_t coord = m->coord;
 778         enum stone color = m->color;
 779         /* Check ko: Capture at a position of ko capture one move ago */
 780         if (unlikely(color == board->ko.color && coord_eq(coord, board->ko.coord))) {
 781                 if (DEBUGL(5))
 782                         fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
 783                 return -1;
 784         } else if (DEBUGL(6)) {
 785                 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
 786                         color, coord_x(coord, board), coord_y(coord, board),
 787                         board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
 788         }
 789
 790         struct move ko = { pass, S_NONE };
 791
 792         int captured_groups = 0;
 793
 794         foreach_neighbor(board, coord, {
 795                 group_t g = group_at(board, c);
 796                 if (DEBUGL(7))
 797                         fprintf(stderr, "board_check: group %d has %d libs\n",
 798                                 g, board_group_info(board, g).libs);
 799                 captured_groups += (board_group_info(board, g).libs == 1);
 800         });
 801
 802         if (likely(captured_groups == 0)) {
 803                 if (DEBUGL(5)) {
 804                         if (DEBUGL(6))
 805                                 board_print(board, stderr);
 806                         fprintf(stderr, "board_check: one-stone suicide\n");
 807                 }
 808
 809                 return -1;
 810         }
 811
 812         board->f[f] = board->f[--board->flen];
 813         if (DEBUGL(6))
 814                 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
 815
 816         foreach_neighbor(board, coord, {
 817                 inc_neighbor_count_at(board, c, color);
 818
 819                 group_t group = group_at(board, c);
 820                 if (!group)
 821                         continue;
 822
 823                 board_group_rmlib(board, group, coord);
 824                 if (DEBUGL(7))
 825                         fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
 826                                 group_base(group));
 827
 828                 if (board_group_captured(board, group)) {
 829                         if (board_group_capture(board, group) == 1) {
 830                                 /* If we captured multiple groups at once,
 831                                  * we can't be fighting ko so we don't need
 832                                  * to check for that. */
 833                                 ko.color = stone_other(color);
 834                                 ko.coord = c;
 835                                 board->last_ko = ko;
 836                                 board->last_ko_age = board->moves;
 837                                 if (DEBUGL(5))
 838                                         fprintf(stderr, "guarding ko at %d,%s\n", ko.color, coord2sstr(ko.coord, board));
 839                         }
 840                 }
 841         });
 842
 843         board_at(board, coord) = color;
 844
 845         board->last_move2 = board->last_move;
 846         board->last_move = *m;
 847         board->moves++;
 848         board_hash_update(board, coord, color);
 849         board_hash_commit(board);
 850         board_symmetry_update(board, &board->symmetry, coord);
 851         board->ko = ko;
 852
 853         return !!new_group(board, coord);
 854 }
 855
 856 static int __attribute__((flatten))
 857 board_play_f(struct board *board, struct move *m, int f)
 858 {
 859         if (DEBUGL(7)) {
 860                 fprintf(stderr, "board_play(): ---- Playing %d,%d\n", coord_x(m->coord, board), coord_y(m->coord, board));
 861         }
 862         if (likely(!board_is_eyelike(board, &m->coord, stone_other(m->color)))) {
 863                 /* NOT playing in an eye. Thus this move has to succeed. (This
 864                  * is thanks to New Zealand rules. Otherwise, multi-stone
 865                  * suicide might fail.) */
 866                 group_t group = board_play_outside(board, m, f);
 867                 if (unlikely(board_group_captured(board, group))) {
 868                         board_group_capture(board, group);
 869                 }
 870                 board_hash_commit(board);
 871                 return 0;
 872         } else {
 873                 return board_play_in_eye(board, m, f);
 874         }
 875 }
 876
 877 int
 878 board_play(struct board *board, struct move *m)
 879 {
 880         if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
 881                 board->last_move2 = board->last_move;
 882                 board->last_move = *m;
 883                 return 0;
 884         }
 885
 886         int f;
 887         for (f = 0; f < board->flen; f++)
 888                 if (board->f[f] == coord_raw(m->coord))
 889                         return board_play_f(board, m, f);
 890
 891         if (DEBUGL(7))
 892                 fprintf(stderr, "board_check: stone exists\n");
 893         return -1;
 894 }
 895
 896
 897 static inline bool
 898 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, ppr_permit permit, void *permit_data)
 899 {
 900         coord_raw(*coord) = b->f[f];
 901         if (unlikely(is_pass(*coord)))
 902                 return random_pass;
 903         struct move m = { *coord, color };
 904         if (DEBUGL(6))
 905                 fprintf(stderr, "trying random move %d: %d,%d\n", f, coord_x(*coord, b), coord_y(*coord, b));
 906         return (likely(!board_is_one_point_eye(b, coord, color)) /* bad idea to play into one, usually */
 907                 && board_is_valid_move(b, &m)
 908                 && (!permit || permit(permit_data, b, &m))
 909                 && likely(board_play_f(b, &m, f) >= 0));
 910 }
 911
 912 void
 913 board_play_random(struct board *b, enum stone color, coord_t *coord, ppr_permit permit, void *permit_data)
 914 {
 915         int base = fast_random(b->flen);
 916         coord_pos(*coord, base, b);
 917         if (likely(board_try_random_move(b, color, coord, base, permit, permit_data)))
 918                 return;
 919
 920         int f;
 921         for (f = base + 1; f < b->flen; f++)
 922                 if (board_try_random_move(b, color, coord, f, permit, permit_data))
 923                         return;
 924         for (f = 0; f < base; f++)
 925                 if (board_try_random_move(b, color, coord, f, permit, permit_data))
 926                         return;
 927
 928         *coord = pass;
 929 }
 930
 931
 932 bool
 933 board_is_false_eyelike(struct board *board, coord_t *coord, enum stone eye_color)
 934 {
 935         enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
 936
 937         /* XXX: We attempt false eye detection but we will yield false
 938          * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
 939
 940         foreach_diag_neighbor(board, *coord) {
 941                 color_diag_libs[(enum stone) board_at(board, c)]++;
 942         } foreach_diag_neighbor_end;
 943         /* For false eye, we need two enemy stones diagonally in the
 944          * middle of the board, or just one enemy stone at the edge
 945          * or in the corner. */
 946         color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
 947         return color_diag_libs[stone_other(eye_color)] >= 2;
 948 }
 949
 950 bool
 951 board_is_one_point_eye(struct board *board, coord_t *coord, enum stone eye_color)
 952 {
 953         return board_is_eyelike(board, coord, eye_color)
 954                 && !board_is_false_eyelike(board, coord, eye_color);
 955 }
 956
 957 enum stone
 958 board_get_one_point_eye(struct board *board, coord_t *coord)
 959 {
 960         if (board_is_one_point_eye(board, coord, S_WHITE))
 961                 return S_WHITE;
 962         else if (board_is_one_point_eye(board, coord, S_BLACK))
 963                 return S_BLACK;
 964         else
 965                 return S_NONE;
 966 }
 967
 968
 969 int profiling_noinline
 970 board_group_capture(struct board *board, group_t group)
 971 {
 972         int stones = 0;
 973
 974         foreach_in_group(board, group) {
 975                 board->captures[stone_other(board_at(board, c))]++;
 976                 board_remove_stone(board, c);
 977                 stones++;
 978         } foreach_in_group_end;
 979
 980         if (board_group_info(board, group).libs == 1)
 981                 board_capturable_rm(board, group);
 982         memset(&board_group_info(board, group), 0, sizeof(struct group));
 983
 984         return stones;
 985 }
 986
 987
 988 float
 989 board_fast_score(struct board *board)
 990 {
 991         int scores[S_MAX];
 992         memset(scores, 0, sizeof(scores));
 993
 994         foreach_point(board) {
 995                 enum stone color = board_at(board, c);
 996                 if (color == S_NONE)
 997                         color = board_get_one_point_eye(board, &c);
 998                 scores[color]++;
 999                 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1000         } foreach_point_end;
1001
1002         return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1003 }
1004
1005 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1006
1007 /* One flood-fill iteration; returns true if next iteration
1008  * is required. */
1009 static bool
1010 board_tromp_taylor_iter(struct board *board, int *ownermap)
1011 {
1012         bool needs_update = false;
1013         foreach_point(board) {
1014                 /* Ignore occupied and already-dame positions. */
1015                 if (board_at(board, c) != S_NONE || ownermap[c] == 3)
1016                         continue;
1017                 /* Count neighbors. */
1018                 int nei[4] = {0};
1019                 foreach_neighbor(board, c, {
1020                         nei[ownermap[c]]++;
1021                 });
1022                 /* If we have neighbors of both colors, or dame,
1023                  * we are dame too. */
1024                 if ((nei[1] && nei[2]) || nei[3]) {
1025                         ownermap[c] = 3;
1026                         /* Speed up the propagation. */
1027                         foreach_neighbor(board, c, {
1028                                 if (board_at(board, c) == S_NONE)
1029                                         ownermap[c] = 3;
1030                         });
1031                         needs_update = true;
1032                         continue;
1033                 }
1034                 /* If we have neighbors of one color, we are owned
1035                  * by that color, too. */
1036                 if (!ownermap[c] && (nei[1] || nei[2])) {
1037                         int newowner = nei[1] ? 1 : 2;
1038                         ownermap[c] = newowner;
1039                         /* Speed up the propagation. */
1040                         foreach_neighbor(board, c, {
1041                                 if (board_at(board, c) == S_NONE && !ownermap[c])
1042                                         ownermap[c] = newowner;
1043                         });
1044                         needs_update = true;
1045                         continue;
1046                 }
1047         } foreach_point_end;
1048         return needs_update;
1049 }
1050
1051 /* Tromp-Taylor Counting */
1052 float
1053 board_official_score(struct board *board)
1054 {
1055
1056         /* A point P, not colored C, is said to reach C, if there is a path of
1057          * (vertically or horizontally) adjacent points of P's color from P to
1058          * a point of color C.
1059          *
1060          * A player's score is the number of points of her color, plus the
1061          * number of empty points that reach only her color. */
1062
1063         int ownermap[board_size2(board)];
1064         int s[4] = {0};
1065         foreach_point(board) {
1066                 int o[4] = {0, 1, 2, 0};
1067                 ownermap[c] = o[board_at(board, c)];
1068                 s[board_at(board, c)]++;
1069         } foreach_point_end;
1070
1071         /* We need to special-case empty board. */
1072         if (!s[S_BLACK] && !s[S_WHITE])
1073                 return board->komi + board->handicap;
1074
1075         while (board_tromp_taylor_iter(board, ownermap))
1076                 /* Flood-fill... */;
1077
1078         int scores[S_MAX];
1079         memset(scores, 0, sizeof(scores));
1080
1081         foreach_point(board) {
1082                 assert(board_at(board, c) == S_OFFBOARD || ownermap[c] != 0);
1083                 if (ownermap[c] == 3)
1084                         continue;
1085                 scores[ownermap[c]]++;
1086         } foreach_point_end;
1087
1088         return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1089 }