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