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