board.c

   1 #include <alloca.h>
   2 #include <assert.h>
   3 #include <math.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7
   8 //#define DEBUG
   9 #include "board.h"
  10 #include "debug.h"
  11 #include "fbook.h"
  12 #include "mq.h"
  13 #include "random.h"
  14
  15 #ifdef BOARD_PAT3
  16 #include "pattern3.h"
  17 #endif
  18 #ifdef BOARD_TRAITS
  19 static void board_trait_recompute(struct board *board, coord_t coord);
  20 #include "tactics/selfatari.h"
  21 #endif
  22
  23
  24 #if 0
  25 #define profiling_noinline __attribute__((noinline))
  26 #else
  27 #define profiling_noinline
  28 #endif
  29
  30 #define gi_granularity 4
  31 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
  32
  33
  34 static void
  35 board_setup(struct board *b)
  36 {
  37         memset(b, 0, sizeof(*b));
  38
  39         struct move m = { pass, S_NONE };
  40         b->last_move = b->last_move2 = b->last_move3 = b->last_move4 = b->last_ko = b->ko = m;
  41 }
  42
  43 struct board *
  44 board_init(char *fbookfile)
  45 {
  46         struct board *b = malloc2(sizeof(struct board));
  47         board_setup(b);
  48
  49         b->fbookfile = fbookfile;
  50
  51         // Default setup
  52         b->size = 9 + 2;
  53         board_clear(b);
  54
  55         return b;
  56 }
  57
  58 static size_t
  59 board_alloc(struct board *board)
  60 {
  61         /* We do not allocate the board structure itself but we allocate
  62          * all the arrays with board contents. */
  63
  64         int bsize = board_size2(board) * sizeof(*board->b);
  65         int gsize = board_size2(board) * sizeof(*board->g);
  66         int fsize = board_size2(board) * sizeof(*board->f);
  67         int nsize = board_size2(board) * sizeof(*board->n);
  68         int psize = board_size2(board) * sizeof(*board->p);
  69         int hsize = board_size2(board) * 2 * sizeof(*board->h);
  70         int gisize = board_size2(board) * sizeof(*board->gi);
  71 #ifdef WANT_BOARD_C
  72         int csize = board_size2(board) * sizeof(*board->c);
  73 #else
  74         int csize = 0;
  75 #endif
  76 #ifdef BOARD_PAT3
  77         int p3size = board_size2(board) * sizeof(*board->pat3);
  78 #else
  79         int p3size = 0;
  80 #endif
  81 #ifdef BOARD_TRAITS
  82         int tsize = board_size2(board) * sizeof(*board->t);
  83         int tqsize = board_size2(board) * sizeof(*board->t);
  84 #else
  85         int tsize = 0;
  86         int tqsize = 0;
  87 #endif
  88         int cdsize = board_size2(board) * sizeof(*board->coord);
  89
  90         size_t size = bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + p3size + tsize + tqsize + cdsize;
  91         void *x = malloc2(size);
  92
  93         /* board->b must come first */
  94         board->b = x; x += bsize;
  95         board->g = x; x += gsize;
  96         board->f = x; x += fsize;
  97         board->p = x; x += psize;
  98         board->n = x; x += nsize;
  99         board->h = x; x += hsize;
 100         board->gi = x; x += gisize;
 101 #ifdef WANT_BOARD_C
 102         board->c = x; x += csize;
 103 #endif
 104 #ifdef BOARD_PAT3
 105         board->pat3 = x; x += p3size;
 106 #endif
 107 #ifdef BOARD_TRAITS
 108         board->t = x; x += tsize;
 109         board->tq = x; x += tqsize;
 110 #endif
 111         board->coord = x; x += cdsize;
 112
 113         return size;
 114 }
 115
 116 struct board *
 117 board_copy(struct board *b2, struct board *b1)
 118 {
 119         memcpy(b2, b1, sizeof(struct board));
 120
 121         size_t size = board_alloc(b2);
 122         memcpy(b2->b, b1->b, size);
 123
 124         // XXX: Special semantics.
 125         b2->fbook = NULL;
 126
 127         return b2;
 128 }
 129
 130 void
 131 board_done_noalloc(struct board *board)
 132 {
 133         if (board->b) free(board->b);
 134         if (board->fbook) fbook_done(board->fbook);
 135 }
 136
 137 void
 138 board_done(struct board *board)
 139 {
 140         board_done_noalloc(board);
 141         free(board);
 142 }
 143
 144 void
 145 board_resize(struct board *board, int size)
 146 {
 147 #ifdef BOARD_SIZE
 148         assert(board_size(board) == size + 2);
 149 #endif
 150         assert(size <= BOARD_MAX_SIZE);
 151         board->size = size + 2 /* S_OFFBOARD margin */;
 152         board->size2 = board_size(board) * board_size(board);
 153
 154         board->bits2 = 1;
 155         while ((1 << board->bits2) < board->size2) board->bits2++;
 156
 157         if (board->b)
 158                 free(board->b);
 159
 160         size_t asize = board_alloc(board);
 161         memset(board->b, 0, asize);
 162 }
 163
 164 static void
 165 board_init_data(struct board *board)
 166 {
 167         int size = board_size(board);
 168
 169         board_setup(board);
 170         board_resize(board, size - 2 /* S_OFFBOARD margin */);
 171
 172         /* Setup neighborhood iterators */
 173         board->nei8[0] = -size - 1; // (-1,-1)
 174         board->nei8[1] = 1;
 175         board->nei8[2] = 1;
 176         board->nei8[3] = size - 2; // (-1,0)
 177         board->nei8[4] = 2;
 178         board->nei8[5] = size - 2; // (-1,1)
 179         board->nei8[6] = 1;
 180         board->nei8[7] = 1;
 181         board->dnei[0] = -size - 1;
 182         board->dnei[1] = 2;
 183         board->dnei[2] = size*2 - 2;
 184         board->dnei[3] = 2;
 185
 186         /* Setup initial symmetry */
 187         if (size % 2) {
 188                 board->symmetry.d = 1;
 189                 board->symmetry.x1 = board->symmetry.y1 = board_size(board) / 2;
 190                 board->symmetry.x2 = board->symmetry.y2 = board_size(board) - 1;
 191                 board->symmetry.type = SYM_FULL;
 192         } else {
 193                 /* TODO: We do not handle board symmetry on boards
 194                  * with no tengen yet. */
 195                 board->symmetry.d = 0;
 196                 board->symmetry.x1 = board->symmetry.y1 = 1;
 197                 board->symmetry.x2 = board->symmetry.y2 = board_size(board) - 1;
 198                 board->symmetry.type = SYM_NONE;
 199         }
 200
 201         /* Set up coordinate cache */
 202         foreach_point(board) {
 203                 board->coord[c][0] = c % board_size(board);
 204                 board->coord[c][1] = c / board_size(board);
 205         } foreach_point_end;
 206
 207         /* Draw the offboard margin */
 208         int top_row = board_size2(board) - board_size(board);
 209         int i;
 210         for (i = 0; i < board_size(board); i++)
 211                 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
 212         for (i = 0; i <= top_row; i += board_size(board))
 213                 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
 214
 215         foreach_point(board) {
 216                 coord_t coord = c;
 217                 if (board_at(board, coord) == S_OFFBOARD)
 218                         continue;
 219                 foreach_neighbor(board, c, {
 220                         inc_neighbor_count_at(board, coord, board_at(board, c));
 221                 } );
 222         } foreach_point_end;
 223
 224         /* All positions are free! Except the margin. */
 225         for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
 226                 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
 227                         board->f[board->flen++] = i;
 228
 229         /* Initialize zobrist hashtable. */
 230         /* We will need these to be stable across Pachi runs for
 231          * certain kinds of pattern matching, thus we do not use
 232          * fast_random() for this. */
 233         hash_t hseed = 0x3121110101112131;
 234         foreach_point(board) {
 235                 board->h[c * 2] = (hseed *= 16807);
 236                 if (!board->h[c * 2])
 237                         board->h[c * 2] = 1;
 238                 /* And once again for white */
 239                 board->h[c * 2 + 1] = (hseed *= 16807);
 240                 if (!board->h[c * 2 + 1])
 241                         board->h[c * 2 + 1] = 1;
 242         } foreach_point_end;
 243
 244 #ifdef BOARD_PAT3
 245         /* Initialize 3x3 pattern codes. */
 246         foreach_point(board) {
 247                 if (board_at(board, c) == S_NONE)
 248                         board->pat3[c] = pattern3_hash(board, c);
 249         } foreach_point_end;
 250 #endif
 251 #ifdef BOARD_TRAITS
 252         /* Initialize traits. */
 253         foreach_point(board) {
 254                 trait_at(board, c, S_BLACK).cap = 0;
 255                 trait_at(board, c, S_WHITE).cap = 0;
 256                 trait_at(board, c, S_BLACK).cap1 = 0;
 257                 trait_at(board, c, S_WHITE).cap1 = 0;
 258 #ifdef BOARD_TRAIT_SAFE
 259                 trait_at(board, c, S_BLACK).safe = true;
 260                 trait_at(board, c, S_WHITE).safe = true;
 261 #endif
 262         } foreach_point_end;
 263 #endif
 264 }
 265
 266 void
 267 board_clear(struct board *board)
 268 {
 269         int size = board_size(board);
 270         floating_t komi = board->komi;
 271         char *fbookfile = board->fbookfile;
 272
 273         board_done_noalloc(board);
 274
 275         static struct board bcache[BOARD_MAX_SIZE + 2];
 276         assert(size > 0 && size <= BOARD_MAX_SIZE + 2);
 277         if (bcache[size - 1].size == size) {
 278                 board_copy(board, &bcache[size - 1]);
 279         } else {
 280                 board_init_data(board);
 281                 board_copy(&bcache[size - 1], board);
 282         }
 283
 284         board->komi = komi;
 285         board->fbookfile = fbookfile;
 286
 287         if (board->fbookfile) {
 288                 board->fbook = fbook_init(board->fbookfile, board);
 289         }
 290 }
 291
 292 static char *
 293 board_print_top(struct board *board, char *s, char *end, int c)
 294 {
 295         for (int i = 0; i < c; i++) {
 296                 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
 297                 s += snprintf(s, end - s, "      ");
 298                 for (int x = 1; x < board_size(board) - 1; x++)
 299                         s += snprintf(s, end - s, "%c ", asdf[x - 1]);
 300                 s += snprintf(s, end -s, " ");
 301         }
 302         s += snprintf(s, end - s, "\n");
 303         for (int i = 0; i < c; i++) {
 304                 s += snprintf(s, end - s, "    +-");
 305                 for (int x = 1; x < board_size(board) - 1; x++)
 306                         s += snprintf(s, end - s, "--");
 307                 s += snprintf(s, end - s, "+");
 308         }
 309         s += snprintf(s, end - s, "\n");
 310         return s;
 311 }
 312
 313 static char *
 314 board_print_bottom(struct board *board, char *s, char *end, int c)
 315 {
 316         for (int i = 0; i < c; i++) {
 317                 s += snprintf(s, end - s, "    +-");
 318                 for (int x = 1; x < board_size(board) - 1; x++)
 319                         s += snprintf(s, end - s, "--");
 320                 s += snprintf(s, end - s, "+");
 321         }
 322         s += snprintf(s, end - s, "\n");
 323         return s;
 324 }
 325
 326 static char *
 327 board_print_row(struct board *board, int y, char *s, char *end, board_cprint cprint)
 328 {
 329         s += snprintf(s, end - s, " %2d | ", y);
 330         for (int x = 1; x < board_size(board) - 1; x++) {
 331                 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
 332                         s += snprintf(s, end - s, "%c)", stone2char(board_atxy(board, x, y)));
 333                 else
 334                         s += snprintf(s, end - s, "%c ", stone2char(board_atxy(board, x, y)));
 335         }
 336         s += snprintf(s, end - s, "|");
 337         if (cprint) {
 338                 s += snprintf(s, end - s, " %2d | ", y);
 339                 for (int x = 1; x < board_size(board) - 1; x++) {
 340                         s = cprint(board, coord_xy(board, x, y), s, end);
 341                 }
 342                 s += snprintf(s, end - s, "|");
 343         }
 344         s += snprintf(s, end - s, "\n");
 345         return s;
 346 }
 347
 348 void
 349 board_print_custom(struct board *board, FILE *f, board_cprint cprint)
 350 {
 351         char buf[10240];
 352         char *s = buf;
 353         char *end = buf + sizeof(buf);
 354         s += snprintf(s, end - s, "Move: % 3d  Komi: %2.1f  Handicap: %d  Captures B: %d W: %d\n",
 355                 board->moves, board->komi, board->handicap,
 356                 board->captures[S_BLACK], board->captures[S_WHITE]);
 357         s = board_print_top(board, s, end, 1 + !!cprint);
 358         for (int y = board_size(board) - 2; y >= 1; y--)
 359                 s = board_print_row(board, y, s, end, cprint);
 360         board_print_bottom(board, s, end, 1 + !!cprint);
 361         fprintf(f, "%s\n", buf);
 362 }
 363
 364 static char *
 365 cprint_group(struct board *board, coord_t c, char *s, char *end)
 366 {
 367         s += snprintf(s, end - s, "%d ", group_base(group_at(board, c)));
 368         return s;
 369 }
 370
 371 void
 372 board_print(struct board *board, FILE *f)
 373 {
 374         board_print_custom(board, f, DEBUGL(6) ? cprint_group : NULL);
 375 }
 376
 377
 378 #ifdef BOARD_TRAITS
 379
 380 #if BOARD_TRAIT_SAFE == 1
 381 static bool
 382 board_trait_safe(struct board *board, coord_t coord, enum stone color)
 383 {
 384         return board_safe_to_play(board, coord, color);
 385 }
 386 #elif BOARD_TRAIT_SAFE == 2
 387 static bool
 388 board_trait_safe(struct board *board, coord_t coord, enum stone color)
 389 {
 390         return !is_bad_selfatari(board, color, coord);
 391 }
 392 #endif
 393
 394 static void
 395 board_trait_recompute(struct board *board, coord_t coord)
 396 {
 397         int sfb = -1, sfw = -1;
 398 #ifdef BOARD_TRAIT_SAFE
 399         sfb = trait_at(board, coord, S_BLACK).safe = board_trait_safe(board, coord, S_BLACK);
 400         sfw = trait_at(board, coord, S_WHITE).safe = board_trait_safe(board, coord, S_WHITE);
 401 #endif
 402         if (DEBUGL(8)) {
 403                 fprintf(stderr, "traits[%s:%s lib=%d] (black cap=%d cap1=%d safe=%d) (white cap=%d cap1=%d safe=%d)\n",
 404                         coord2sstr(coord, board), stone2str(board_at(board, coord)), immediate_liberty_count(board, coord),
 405                         trait_at(board, coord, S_BLACK).cap, trait_at(board, coord, S_BLACK).cap1, sfb,
 406                         trait_at(board, coord, S_WHITE).cap, trait_at(board, coord, S_WHITE).cap1, sfw);
 407         }
 408 }
 409 #endif
 410
 411 /* Recompute traits for dirty points that we have previously touched
 412  * somehow (libs of their neighbors changed or so). */
 413 static void
 414 board_traits_recompute(struct board *board)
 415 {
 416 #ifdef BOARD_TRAITS
 417         for (int i = 0; i < board->tqlen; i++) {
 418                 coord_t coord = board->tq[i];
 419                 trait_at(board, coord, S_BLACK).dirty = false;
 420                 if (board_at(board, coord) != S_NONE)
 421                         continue;
 422                 board_trait_recompute(board, coord);
 423         }
 424         board->tqlen = 0;
 425 #endif
 426 }
 427
 428 /* Queue traits of given point for recomputing. */
 429 static void
 430 board_trait_queue(struct board *board, coord_t coord)
 431 {
 432 #ifdef BOARD_TRAITS
 433         if (trait_at(board, coord, S_BLACK).dirty)
 434                 return;
 435         board->tq[board->tqlen++] = coord;
 436         trait_at(board, coord, S_BLACK).dirty = true;
 437 #endif
 438 }
 439
 440
 441 /* Update board hash with given coordinate. */
 442 static void profiling_noinline
 443 board_hash_update(struct board *board, coord_t coord, enum stone color)
 444 {
 445         board->hash ^= hash_at(board, coord, color);
 446         board->qhash[coord_quadrant(coord, board)] ^= hash_at(board, coord, color);
 447         if (DEBUGL(8))
 448                 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);
 449
 450 #if defined(BOARD_PAT3)
 451         /* @color is not what we need in case of capture. */
 452         static const int ataribits[8] = { -1, 0, -1, 1, 2, -1, 3, -1 };
 453         enum stone new_color = board_at(board, coord);
 454         bool in_atari = false;
 455         if (new_color == S_NONE) {
 456                 board->pat3[coord] = pattern3_hash(board, coord);
 457         } else {
 458                 in_atari = (board_group_info(board, group_at(board, coord)).libs == 1);
 459         }
 460         foreach_8neighbor(board, coord) {
 461                 /* Internally, the loop uses fn__i=[0..7]. We can use
 462                  * it directly to address bits within the bitmap of the
 463                  * neighbors since the bitmap order is reverse to the
 464                  * loop order. */
 465                 if (board_at(board, c) != S_NONE)
 466                         continue;
 467                 board->pat3[c] &= ~(3 << (fn__i*2));
 468                 board->pat3[c] |= new_color << (fn__i*2);
 469                 if (ataribits[fn__i] >= 0) {
 470                         board->pat3[c] &= ~(1 << (16 + ataribits[fn__i]));
 471                         board->pat3[c] |= in_atari << (16 + ataribits[fn__i]);
 472                 }
 473 #if defined(BOARD_TRAITS)
 474                 board_trait_queue(board, c);
 475 #endif
 476         } foreach_8neighbor_end;
 477 #endif
 478 }
 479
 480 /* Commit current board hash to history. */
 481 static void profiling_noinline
 482 board_hash_commit(struct board *board)
 483 {
 484         if (DEBUGL(8))
 485                 fprintf(stderr, "board_hash_commit %"PRIhash"\n", board->hash);
 486         if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
 487                 board->history_hash[board->hash & history_hash_mask] = board->hash;
 488         } else {
 489                 hash_t i = board->hash;
 490                 while (board->history_hash[i & history_hash_mask]) {
 491                         if (board->history_hash[i & history_hash_mask] == board->hash) {
 492                                 if (DEBUGL(5))
 493                                         fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
 494                                                 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
 495                                 board->superko_violation = true;
 496                                 return;
 497                         }
 498                         i = history_hash_next(i);
 499                 }
 500                 board->history_hash[i & history_hash_mask] = board->hash;
 501         }
 502 }
 503
 504
 505 void
 506 board_symmetry_update(struct board *b, struct board_symmetry *symmetry, coord_t c)
 507 {
 508         if (likely(symmetry->type == SYM_NONE)) {
 509                 /* Fully degenerated already. We do not support detection
 510                  * of restoring of symmetry, assuming that this is too rare
 511                  * a case to handle. */
 512                 return;
 513         }
 514
 515         int x = coord_x(c, b), y = coord_y(c, b), t = board_size(b) / 2;
 516         int dx = board_size(b) - 1 - x; /* for SYM_DOWN */
 517         if (DEBUGL(6)) {
 518                 fprintf(stderr, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
 519                         symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
 520                         symmetry->d, symmetry->type, x, y);
 521         }
 522
 523         switch (symmetry->type) {
 524                 case SYM_FULL:
 525                         if (x == t && y == t) {
 526                                 /* Tengen keeps full symmetry. */
 527                                 return;
 528                         }
 529                         /* New symmetry now? */
 530                         if (x == y) {
 531                                 symmetry->type = SYM_DIAG_UP;
 532                                 symmetry->x1 = symmetry->y1 = 1;
 533                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 534                                 symmetry->d = 1;
 535                         } else if (dx == y) {
 536                                 symmetry->type = SYM_DIAG_DOWN;
 537                                 symmetry->x1 = symmetry->y1 = 1;
 538                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 539                                 symmetry->d = 1;
 540                         } else if (x == t) {
 541                                 symmetry->type = SYM_HORIZ;
 542                                 symmetry->y1 = 1;
 543                                 symmetry->y2 = board_size(b) - 1;
 544                                 symmetry->d = 0;
 545                         } else if (y == t) {
 546                                 symmetry->type = SYM_VERT;
 547                                 symmetry->x1 = 1;
 548                                 symmetry->x2 = board_size(b) - 1;
 549                                 symmetry->d = 0;
 550                         } else {
 551 break_symmetry:
 552                                 symmetry->type = SYM_NONE;
 553                                 symmetry->x1 = symmetry->y1 = 1;
 554                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 555                                 symmetry->d = 0;
 556                         }
 557                         break;
 558                 case SYM_DIAG_UP:
 559                         if (x == y)
 560                                 return;
 561                         goto break_symmetry;
 562                 case SYM_DIAG_DOWN:
 563                         if (dx == y)
 564                                 return;
 565                         goto break_symmetry;
 566                 case SYM_HORIZ:
 567                         if (x == t)
 568                                 return;
 569                         goto break_symmetry;
 570                 case SYM_VERT:
 571                         if (y == t)
 572                                 return;
 573                         goto break_symmetry;
 574                 case SYM_NONE:
 575                         assert(0);
 576                         break;
 577         }
 578
 579         if (DEBUGL(6)) {
 580                 fprintf(stderr, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
 581                         symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
 582                         symmetry->d, symmetry->type);
 583         }
 584         /* Whew. */
 585 }
 586
 587
 588 void
 589 board_handicap_stone(struct board *board, int x, int y, FILE *f)
 590 {
 591         struct move m;
 592         m.color = S_BLACK; m.coord = coord_xy(board, x, y);
 593
 594         board_play(board, &m);
 595         /* Simulate white passing; otherwise, UCT search can get confused since
 596          * tree depth parity won't match the color to move. */
 597         board->moves++;
 598
 599         char *str = coord2str(m.coord, board);
 600         if (DEBUGL(1))
 601                 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
 602         if (f) fprintf(f, "%s ", str);
 603         free(str);
 604 }
 605
 606 void
 607 board_handicap(struct board *board, int stones, FILE *f)
 608 {
 609         int margin = 3 + (board_size(board) >= 13);
 610         int min = margin;
 611         int mid = board_size(board) / 2;
 612         int max = board_size(board) - 1 - margin;
 613         const int places[][2] = {
 614                 { min, min }, { max, max }, { min, max }, { max, min },
 615                 { min, mid }, { max, mid },
 616                 { mid, min }, { mid, max },
 617                 { mid, mid },
 618         };
 619
 620         board->handicap = stones;
 621
 622         if (stones == 5 || stones == 7) {
 623                 board_handicap_stone(board, mid, mid, f);
 624                 stones--;
 625         }
 626
 627         int i;
 628         for (i = 0; i < stones; i++)
 629                 board_handicap_stone(board, places[i][0], places[i][1], f);
 630 }
 631
 632
 633 static void __attribute__((noinline))
 634 check_libs_consistency(struct board *board, group_t g)
 635 {
 636 #ifdef DEBUG
 637         if (!g) return;
 638         struct group *gi = &board_group_info(board, g);
 639         for (int i = 0; i < GROUP_KEEP_LIBS; i++)
 640                 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
 641                         fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
 642                         assert(0);
 643                 }
 644 #endif
 645 }
 646
 647 static void
 648 check_pat3_consistency(struct board *board, coord_t coord)
 649 {
 650 #ifdef DEBUG
 651         foreach_8neighbor(board, coord) {
 652                 if (board_at(board, c) == S_NONE && pattern3_hash(board, c) != board->pat3[c]) {
 653                         board_print(board, stderr);
 654                         fprintf(stderr, "%s(%d)->%s(%d) computed %x != stored %x (%d)\n", coord2sstr(coord, board), coord, coord2sstr(c, board), c, pattern3_hash(board, c), board->pat3[c], fn__i);
 655                         assert(0);
 656                 }
 657         } foreach_8neighbor_end;
 658 #endif
 659 }
 660
 661 static void
 662 board_capturable_add(struct board *board, group_t group, coord_t lib, bool onestone)
 663 {
 664         //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
 665 #ifdef BOARD_TRAITS
 666         /* Increase capturable count trait of my last lib. */
 667         enum stone capturing_color = stone_other(board_at(board, group));
 668         assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
 669         foreach_neighbor(board, lib, {
 670                 if (DEBUGL(8) && group_at(board, c) == group)
 671                         fprintf(stderr, "%s[%d] %s cap bump bc of %s(%d) member %s onestone %d\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap, stone2str(capturing_color), coord2sstr(group, board), board_group_info(board, group).libs, coord2sstr(c, board), onestone);
 672                 trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group);
 673                 trait_at(board, lib, capturing_color).cap1 += (group_at(board, c) == group && onestone);
 674         });
 675         board_trait_queue(board, lib);
 676 #endif
 677
 678 #ifdef BOARD_PAT3
 679         int fn__i = 0;
 680         foreach_neighbor(board, lib, {
 681                 board->pat3[lib] |= (group_at(board, c) == group) << (16 + 3 - fn__i);
 682                 fn__i++;
 683         });
 684 #endif
 685
 686 #ifdef WANT_BOARD_C
 687         /* Update the list of capturable groups. */
 688         assert(group);
 689         assert(board->clen < board_size2(board));
 690         board->c[board->clen++] = group;
 691 #endif
 692 }
 693 static void
 694 board_capturable_rm(struct board *board, group_t group, coord_t lib, bool onestone)
 695 {
 696         //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
 697 #ifdef BOARD_TRAITS
 698         /* Decrease capturable count trait of my previously-last lib. */
 699         enum stone capturing_color = stone_other(board_at(board, group));
 700         assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
 701         foreach_neighbor(board, lib, {
 702                 if (DEBUGL(8) && group_at(board, c) == group)
 703                         fprintf(stderr, "%s[%d] cap dump bc of %s(%d) member %s onestone %d\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap, coord2sstr(group, board), board_group_info(board, group).libs, coord2sstr(c, board), onestone);
 704                 trait_at(board, lib, capturing_color).cap -= (group_at(board, c) == group);
 705                 trait_at(board, lib, capturing_color).cap1 -= (group_at(board, c) == group && onestone);
 706         });
 707         board_trait_queue(board, lib);
 708 #endif
 709
 710 #ifdef BOARD_PAT3
 711         int fn__i = 0;
 712         foreach_neighbor(board, lib, {
 713                 board->pat3[lib] &= ~((group_at(board, c) == group) << (16 + 3 - fn__i));
 714                 fn__i++;
 715         });
 716 #endif
 717
 718 #ifdef WANT_BOARD_C
 719         /* Update the list of capturable groups. */
 720         for (int i = 0; i < board->clen; i++) {
 721                 if (unlikely(board->c[i] == group)) {
 722                         board->c[i] = board->c[--board->clen];
 723                         return;
 724                 }
 725         }
 726         fprintf(stderr, "rm of bad group %d\n", group_base(group));
 727         assert(0);
 728 #endif
 729 }
 730
 731 static void
 732 board_atariable_add(struct board *board, group_t group, coord_t lib1, coord_t lib2)
 733 {
 734 #ifdef BOARD_TRAITS
 735         board_trait_queue(board, lib1);
 736         board_trait_queue(board, lib2);
 737 #endif
 738 }
 739 static void
 740 board_atariable_rm(struct board *board, group_t group, coord_t lib1, coord_t lib2)
 741 {
 742 #ifdef BOARD_TRAITS
 743         board_trait_queue(board, lib1);
 744         board_trait_queue(board, lib2);
 745 #endif
 746 }
 747
 748 static void
 749 board_group_addlib(struct board *board, group_t group, coord_t coord)
 750 {
 751         if (DEBUGL(7)) {
 752                 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
 753                         group_base(group), coord2sstr(group_base(group), board),
 754                         board_group_info(board, group).libs, coord2sstr(coord, board));
 755         }
 756
 757         check_libs_consistency(board, group);
 758
 759         struct group *gi = &board_group_info(board, group);
 760         bool onestone = group_is_onestone(board, group);
 761         if (gi->libs < GROUP_KEEP_LIBS) {
 762                 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
 763 #if 0
 764                         /* Seems extra branch just slows it down */
 765                         if (!gi->lib[i])
 766                                 break;
 767 #endif
 768                         if (unlikely(gi->lib[i] == coord))
 769                                 return;
 770                 }
 771                 if (gi->libs == 0) {
 772                         board_capturable_add(board, group, coord, onestone);
 773                 } else if (gi->libs == 1) {
 774                         board_capturable_rm(board, group, gi->lib[0], onestone);
 775                         board_atariable_add(board, group, gi->lib[0], coord);
 776                 } else if (gi->libs == 2) {
 777                         board_atariable_rm(board, group, gi->lib[0], gi->lib[1]);
 778                 }
 779                 gi->lib[gi->libs++] = coord;
 780         }
 781
 782         check_libs_consistency(board, group);
 783 }
 784
 785 static void
 786 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
 787 {
 788         /* Add extra liberty from the board to our liberty list. */
 789         unsigned char watermark[board_size2(board) / 8];
 790         memset(watermark, 0, sizeof(watermark));
 791 #define watermark_get(c)        (watermark[c >> 3] & (1 << (c & 7)))
 792 #define watermark_set(c)        watermark[c >> 3] |= (1 << (c & 7))
 793
 794         for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
 795                 watermark_set(gi->lib[i]);
 796         watermark_set(avoid);
 797
 798         foreach_in_group(board, group) {
 799                 coord_t coord2 = c;
 800                 foreach_neighbor(board, coord2, {
 801                         if (board_at(board, c) + watermark_get(c) != S_NONE)
 802                                 continue;
 803                         watermark_set(c);
 804                         gi->lib[gi->libs++] = c;
 805                         if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
 806                                 return;
 807                 } );
 808         } foreach_in_group_end;
 809 #undef watermark_get
 810 #undef watermark_set
 811 }
 812
 813 static void
 814 board_group_rmlib(struct board *board, group_t group, coord_t coord)
 815 {
 816         if (DEBUGL(7)) {
 817                 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
 818                         group_base(group), coord2sstr(group_base(group), board),
 819                         board_group_info(board, group).libs, coord2sstr(coord, board));
 820         }
 821
 822         struct group *gi = &board_group_info(board, group);
 823         bool onestone = group_is_onestone(board, group);
 824         for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
 825 #if 0
 826                 /* Seems extra branch just slows it down */
 827                 if (!gi->lib[i])
 828                         break;
 829 #endif
 830                 if (likely(gi->lib[i] != coord))
 831                         continue;
 832
 833                 coord_t lib = gi->lib[i] = gi->lib[--gi->libs];
 834                 gi->lib[gi->libs] = 0;
 835
 836                 check_libs_consistency(board, group);
 837
 838                 /* Postpone refilling lib[] until we need to. */
 839                 assert(GROUP_REFILL_LIBS > 1);
 840                 if (gi->libs > GROUP_REFILL_LIBS)
 841                         return;
 842                 if (gi->libs == GROUP_REFILL_LIBS)
 843                         board_group_find_extra_libs(board, group, gi, coord);
 844
 845                 if (gi->libs == 2) {
 846                         board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
 847                 } else if (gi->libs == 1) {
 848                         board_capturable_add(board, group, gi->lib[0], onestone);
 849                         board_atariable_rm(board, group, gi->lib[0], lib);
 850                 } else if (gi->libs == 0)
 851                         board_capturable_rm(board, group, lib, onestone);
 852                 return;
 853         }
 854
 855         /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
 856          * can call this multiple times per coord. */
 857         check_libs_consistency(board, group);
 858         return;
 859 }
 860
 861
 862 /* This is a low-level routine that doesn't maintain consistency
 863  * of all the board data structures. */
 864 static void
 865 board_remove_stone(struct board *board, group_t group, coord_t c)
 866 {
 867         enum stone color = board_at(board, c);
 868         board_at(board, c) = S_NONE;
 869         group_at(board, c) = 0;
 870         board_hash_update(board, c, color);
 871 #ifdef BOARD_TRAITS
 872         /* We mark as cannot-capture now. If this is a ko/snapback,
 873          * we will get incremented later in board_group_addlib(). */
 874         trait_at(board, c, S_BLACK).cap = trait_at(board, c, S_BLACK).cap1 = 0;
 875         trait_at(board, c, S_WHITE).cap = trait_at(board, c, S_WHITE).cap1 = 0;
 876         board_trait_queue(board, c);
 877 #endif
 878
 879         /* Increase liberties of surrounding groups */
 880         coord_t coord = c;
 881         foreach_neighbor(board, coord, {
 882                 dec_neighbor_count_at(board, c, color);
 883                 board_trait_queue(board, c);
 884                 group_t g = group_at(board, c);
 885                 if (g && g != group)
 886                         board_group_addlib(board, g, coord);
 887         });
 888
 889 #ifdef BOARD_PAT3
 890         /* board_hash_update() might have seen the freed up point as able
 891          * to capture another group in atari that only after the loop
 892          * above gained enough liberties. Reset pat3 again. */
 893         board->pat3[c] = pattern3_hash(board, c);
 894 #endif
 895
 896         if (DEBUGL(6))
 897                 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
 898         board->f[board->flen++] = c;
 899 }
 900
 901 static int profiling_noinline
 902 board_group_capture(struct board *board, group_t group)
 903 {
 904         int stones = 0;
 905
 906         foreach_in_group(board, group) {
 907                 board->captures[stone_other(board_at(board, c))]++;
 908                 board_remove_stone(board, group, c);
 909                 stones++;
 910         } foreach_in_group_end;
 911
 912         struct group *gi = &board_group_info(board, group);
 913         assert(gi->libs == 0);
 914         memset(gi, 0, sizeof(*gi));
 915
 916         return stones;
 917 }
 918
 919
 920 static void profiling_noinline
 921 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
 922 {
 923 #ifdef BOARD_TRAITS
 924         struct group *gi = &board_group_info(board, group);
 925         bool onestone = group_is_onestone(board, group);
 926
 927         if (gi->libs == 1) {
 928                 /* Our group is temporarily in atari; make sure the capturable
 929                  * counts also correspond to the newly added stone before we
 930                  * start adding liberties again so bump-dump ops match. */
 931                 enum stone capturing_color = stone_other(board_at(board, group));
 932                 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
 933
 934                 coord_t lib = board_group_info(board, group).lib[0];
 935                 if (coord_is_adjecent(lib, coord, board)) {
 936                         if (DEBUGL(8))
 937                                 fprintf(stderr, "add_to_group %s: %s[%d] bump\n", coord2sstr(group, board), coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap);
 938                         trait_at(board, lib, capturing_color).cap++;
 939                         /* This is never a 1-stone group, obviously. */
 940                         board_trait_queue(board, lib);
 941                 }
 942
 943                 if (onestone) {
 944                         /* We are not 1-stone group anymore, update the cap1
 945                          * counter specifically. */
 946                         foreach_neighbor(board, group, {
 947                                 if (board_at(board, c) != S_NONE) continue;
 948                                 trait_at(board, c, capturing_color).cap1--;
 949                                 board_trait_queue(board, c);
 950                         });
 951                 }
 952         }
 953 #endif
 954
 955         group_at(board, coord) = group;
 956         groupnext_at(board, coord) = groupnext_at(board, prevstone);
 957         groupnext_at(board, prevstone) = coord;
 958
 959         foreach_neighbor(board, coord, {
 960                 if (board_at(board, c) == S_NONE)
 961                         board_group_addlib(board, group, c);
 962         });
 963
 964         if (DEBUGL(8))
 965                 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
 966                         coord_x(prevstone, board), coord_y(prevstone, board),
 967                         coord_x(coord, board), coord_y(coord, board),
 968                         groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
 969                         group_base(group));
 970 }
 971
 972 static void profiling_noinline
 973 merge_groups(struct board *board, group_t group_to, group_t group_from)
 974 {
 975         if (DEBUGL(7))
 976                 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
 977                         group_base(group_from), group_base(group_to));
 978         struct group *gi_from = &board_group_info(board, group_from);
 979         struct group *gi_to = &board_group_info(board, group_to);
 980         bool onestone_from = group_is_onestone(board, group_from);
 981         bool onestone_to = group_is_onestone(board, group_to);
 982
 983         /* We do this early before the group info is rewritten. */
 984         if (gi_from->libs == 2)
 985                 board_atariable_rm(board, group_from, gi_from->lib[0], gi_from->lib[1]);
 986         else if (gi_from->libs == 1)
 987                 board_capturable_rm(board, group_from, gi_from->lib[0], onestone_from);
 988
 989         if (DEBUGL(7))
 990                 fprintf(stderr,"---- (froml %d, tol %d)\n", gi_from->libs, gi_to->libs);
 991
 992         if (gi_to->libs < GROUP_KEEP_LIBS) {
 993                 for (int i = 0; i < gi_from->libs; i++) {
 994                         for (int j = 0; j < gi_to->libs; j++)
 995                                 if (gi_to->lib[j] == gi_from->lib[i])
 996                                         goto next_from_lib;
 997                         if (gi_to->libs == 0) {
 998                                 board_capturable_add(board, group_to, gi_from->lib[i], onestone_to);
 999                         } else if (gi_to->libs == 1) {
1000                                 board_capturable_rm(board, group_to, gi_to->lib[0], onestone_to);
1001                                 board_atariable_add(board, group_to, gi_to->lib[0], gi_from->lib[i]);
1002                         } else if (gi_to->libs == 2) {
1003                                 board_atariable_rm(board, group_to, gi_to->lib[0], gi_to->lib[1]);
1004                         }
1005                         gi_to->lib[gi_to->libs++] = gi_from->lib[i];
1006                         if (gi_to->libs >= GROUP_KEEP_LIBS)
1007                                 break;
1008 next_from_lib:;
1009                 }
1010         }
1011
1012         if (gi_to->libs == 1) {
1013                 coord_t lib = board_group_info(board, group_to).lib[0];
1014 #ifdef BOARD_TRAITS
1015                 enum stone capturing_color = stone_other(board_at(board, group_to));
1016                 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
1017
1018                 /* Our group is currently in atari; make sure we properly
1019                  * count in even the neighbors from the other group in the
1020                  * capturable counter. */
1021                 foreach_neighbor(board, lib, {
1022                         if (DEBUGL(8) && group_at(board, c) == group_from)
1023                                 fprintf(stderr, "%s[%d] cap bump\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap);
1024                         trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group_from);
1025                         /* This is never a 1-stone group, obviously. */
1026                 });
1027                 board_trait_queue(board, lib);
1028
1029                 if (onestone_to) {
1030                         /* We are not 1-stone group anymore, update the cap1
1031                          * counter specifically. */
1032                         foreach_neighbor(board, group_to, {
1033                                 if (board_at(board, c) != S_NONE) continue;
1034                                 trait_at(board, c, capturing_color).cap1--;
1035                                 board_trait_queue(board, c);
1036                         });
1037                 }
1038 #endif
1039 #ifdef BOARD_PAT3
1040                 if (gi_from->libs == 1) {
1041                         /* We removed group_from from capturable groups,
1042                          * therefore switching the atari flag off.
1043                          * We need to set it again since group_to is also
1044                          * capturable. */
1045                         int fn__i = 0;
1046                         foreach_neighbor(board, lib, {
1047                                 board->pat3[lib] |= (group_at(board, c) == group_from) << (16 + 3 - fn__i);
1048                                 fn__i++;
1049                         });
1050                 }
1051 #endif
1052         }
1053
1054         coord_t last_in_group;
1055         foreach_in_group(board, group_from) {
1056                 last_in_group = c;
1057                 group_at(board, c) = group_to;
1058         } foreach_in_group_end;
1059         groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
1060         groupnext_at(board, group_base(group_to)) = group_base(group_from);
1061         memset(gi_from, 0, sizeof(struct group));
1062
1063         if (DEBUGL(7))
1064                 fprintf(stderr, "board_play_raw: merged group: %d\n",
1065                         group_base(group_to));
1066 }
1067
1068 static group_t profiling_noinline
1069 new_group(struct board *board, coord_t coord)
1070 {
1071         group_t group = coord;
1072         struct group *gi = &board_group_info(board, group);
1073         foreach_neighbor(board, coord, {
1074                 if (board_at(board, c) == S_NONE)
1075                         /* board_group_addlib is ridiculously expensive for us */
1076 #if GROUP_KEEP_LIBS < 4
1077                         if (gi->libs < GROUP_KEEP_LIBS)
1078 #endif
1079                         gi->lib[gi->libs++] = c;
1080         });
1081
1082         group_at(board, coord) = group;
1083         groupnext_at(board, coord) = 0;
1084
1085         if (gi->libs == 2)
1086                 board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
1087         else if (gi->libs == 1)
1088                 board_capturable_add(board, group, gi->lib[0], true);
1089         check_libs_consistency(board, group);
1090
1091         if (DEBUGL(8))
1092                 fprintf(stderr, "new_group: added %d,%d to group %d\n",
1093                         coord_x(coord, board), coord_y(coord, board),
1094                         group_base(group));
1095
1096         return group;
1097 }
1098
1099 static inline group_t
1100 play_one_neighbor(struct board *board,
1101                 coord_t coord, enum stone color, enum stone other_color,
1102                 coord_t c, group_t group)
1103 {
1104         enum stone ncolor = board_at(board, c);
1105         group_t ngroup = group_at(board, c);
1106
1107         inc_neighbor_count_at(board, c, color);
1108         /* We can be S_NONE, in that case we need to update the safety
1109          * trait since we might be left with only one liberty. */
1110         board_trait_queue(board, c);
1111
1112         if (!ngroup)
1113                 return group;
1114
1115         board_group_rmlib(board, ngroup, coord);
1116         if (DEBUGL(7))
1117                 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
1118                         group_base(ngroup), ncolor, color, other_color);
1119
1120         if (ncolor == color && ngroup != group) {
1121                 if (!group) {
1122                         group = ngroup;
1123                         add_to_group(board, group, c, coord);
1124                 } else {
1125                         merge_groups(board, group, ngroup);
1126                 }
1127         } else if (ncolor == other_color) {
1128                 if (DEBUGL(8)) {
1129                         struct group *gi = &board_group_info(board, ngroup);
1130                         fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
1131                         for (int i = 0; i < GROUP_KEEP_LIBS; i++)
1132                                 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
1133                         fprintf(stderr, "\n");
1134                 }
1135                 if (unlikely(board_group_captured(board, ngroup)))
1136                         board_group_capture(board, ngroup);
1137         }
1138         return group;
1139 }
1140
1141 /* We played on a place with at least one liberty. We will become a member of
1142  * some group for sure. */
1143 static group_t profiling_noinline
1144 board_play_outside(struct board *board, struct move *m, int f)
1145 {
1146         coord_t coord = m->coord;
1147         enum stone color = m->color;
1148         enum stone other_color = stone_other(color);
1149         group_t group = 0;
1150
1151         board->f[f] = board->f[--board->flen];
1152         if (DEBUGL(6))
1153                 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1154
1155 #if defined(BOARD_TRAITS) && defined(DEBUG)
1156         /* Sanity check that cap matches reality. */
1157         {
1158                 int a = 0, b = 0;
1159                 foreach_neighbor(board, coord, {
1160                         group_t g = group_at(board, c);
1161                         a += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1);
1162                         b += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1) && group_is_onestone(board, g);
1163                 });
1164                 assert(a == trait_at(board, coord, color).cap);
1165                 assert(b == trait_at(board, coord, color).cap1);
1166 #ifdef BOARD_TRAIT_SAFE
1167                 assert(board_trait_safe(board, coord, color) == trait_at(board, coord, color).safe);
1168 #endif
1169         }
1170 #endif
1171         foreach_neighbor(board, coord, {
1172                 group = play_one_neighbor(board, coord, color, other_color, c, group);
1173         });
1174
1175         board_at(board, coord) = color;
1176         if (unlikely(!group))
1177                 group = new_group(board, coord);
1178
1179         board->last_move2 = board->last_move;
1180         board->last_move = *m;
1181         board->moves++;
1182         board_hash_update(board, coord, color);
1183         board_symmetry_update(board, &board->symmetry, coord);
1184         struct move ko = { pass, S_NONE };
1185         board->ko = ko;
1186
1187         check_pat3_consistency(board, coord);
1188
1189         return group;
1190 }
1191
1192 /* We played in an eye-like shape. Either we capture at least one of the eye
1193  * sides in the process of playing, or return -1. */
1194 static int profiling_noinline
1195 board_play_in_eye(struct board *board, struct move *m, int f)
1196 {
1197         coord_t coord = m->coord;
1198         enum stone color = m->color;
1199         /* Check ko: Capture at a position of ko capture one move ago */
1200         if (unlikely(color == board->ko.color && coord == board->ko.coord)) {
1201                 if (DEBUGL(5))
1202                         fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
1203                 return -1;
1204         } else if (DEBUGL(6)) {
1205                 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1206                         color, coord_x(coord, board), coord_y(coord, board),
1207                         board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
1208         }
1209
1210         struct move ko = { pass, S_NONE };
1211
1212         int captured_groups = 0;
1213
1214         foreach_neighbor(board, coord, {
1215                 group_t g = group_at(board, c);
1216                 if (DEBUGL(7))
1217                         fprintf(stderr, "board_check: group %d has %d libs\n",
1218                                 g, board_group_info(board, g).libs);
1219                 captured_groups += (board_group_info(board, g).libs == 1);
1220         });
1221
1222         if (likely(captured_groups == 0)) {
1223                 if (DEBUGL(5)) {
1224                         if (DEBUGL(6))
1225                                 board_print(board, stderr);
1226                         fprintf(stderr, "board_check: one-stone suicide\n");
1227                 }
1228
1229                 return -1;
1230         }
1231 #ifdef BOARD_TRAITS
1232         /* We _will_ for sure capture something. */
1233         assert(trait_at(board, coord, color).cap > 0);
1234 #ifdef BOARD_TRAIT_SAFE
1235         assert(trait_at(board, coord, color).safe == board_trait_safe(board, coord, color));
1236 #endif
1237 #endif
1238
1239         board->f[f] = board->f[--board->flen];
1240         if (DEBUGL(6))
1241                 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1242
1243         foreach_neighbor(board, coord, {
1244                 inc_neighbor_count_at(board, c, color);
1245                 /* Originally, this could not have changed any trait
1246                  * since no neighbors were S_NONE, however by now some
1247                  * of them might be removed from the board. */
1248                 board_trait_queue(board, c);
1249
1250                 group_t group = group_at(board, c);
1251                 if (!group)
1252                         continue;
1253
1254                 board_group_rmlib(board, group, coord);
1255                 if (DEBUGL(7))
1256                         fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
1257                                 group_base(group));
1258
1259                 if (board_group_captured(board, group)) {
1260                         if (board_group_capture(board, group) == 1) {
1261                                 /* If we captured multiple groups at once,
1262                                  * we can't be fighting ko so we don't need
1263                                  * to check for that. */
1264                                 ko.color = stone_other(color);
1265                                 ko.coord = c;
1266                                 board->last_ko = ko;
1267                                 board->last_ko_age = board->moves;
1268                                 if (DEBUGL(5))
1269                                         fprintf(stderr, "guarding ko at %d,%s\n", ko.color, coord2sstr(ko.coord, board));
1270                         }
1271                 }
1272         });
1273
1274         board_at(board, coord) = color;
1275         group_t group = new_group(board, coord);
1276
1277         board->last_move2 = board->last_move;
1278         board->last_move = *m;
1279         board->moves++;
1280         board_hash_update(board, coord, color);
1281         board_hash_commit(board);
1282         board_traits_recompute(board);
1283         board_symmetry_update(board, &board->symmetry, coord);
1284         board->ko = ko;
1285
1286         check_pat3_consistency(board, coord);
1287
1288         return !!group;
1289 }
1290
1291 static int __attribute__((flatten))
1292 board_play_f(struct board *board, struct move *m, int f)
1293 {
1294         if (DEBUGL(7)) {
1295                 fprintf(stderr, "board_play(%s): ---- Playing %d,%d\n", coord2sstr(m->coord, board), coord_x(m->coord, board), coord_y(m->coord, board));
1296         }
1297         if (likely(!board_is_eyelike(board, m->coord, stone_other(m->color)))) {
1298                 /* NOT playing in an eye. Thus this move has to succeed. (This
1299                  * is thanks to New Zealand rules. Otherwise, multi-stone
1300                  * suicide might fail.) */
1301                 group_t group = board_play_outside(board, m, f);
1302                 if (unlikely(board_group_captured(board, group))) {
1303                         board_group_capture(board, group);
1304                 }
1305                 board_hash_commit(board);
1306                 board_traits_recompute(board);
1307                 return 0;
1308         } else {
1309                 return board_play_in_eye(board, m, f);
1310         }
1311 }
1312
1313 int
1314 board_play(struct board *board, struct move *m)
1315 {
1316         if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
1317                 struct move nomove = { pass, S_NONE };
1318                 board->ko = nomove;
1319                 board->last_move4 = board->last_move3;
1320                 board->last_move3 = board->last_move2;
1321                 board->last_move2 = board->last_move;
1322                 board->last_move = *m;
1323                 return 0;
1324         }
1325
1326         int f;
1327         for (f = 0; f < board->flen; f++)
1328                 if (board->f[f] == m->coord)
1329                         return board_play_f(board, m, f);
1330
1331         if (DEBUGL(7))
1332                 fprintf(stderr, "board_check: stone exists\n");
1333         return -1;
1334 }
1335
1336 /* Undo, supported only for pass moves. This form of undo is required by KGS
1337  * to settle disputes on dead groups. (Undo of real moves would be more complex
1338  * particularly for capturing moves.) */
1339 int board_undo(struct board *board)
1340 {
1341         if (!is_pass(board->last_move.coord))
1342                 return -1;
1343         board->last_move = board->last_move2;
1344         board->last_move2 = board->last_move3;
1345         board->last_move3 = board->last_move4;
1346         if (board->last_ko_age == board->moves)
1347                 board->ko = board->last_ko;
1348         return 0;
1349 }
1350
1351 static inline bool
1352 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, ppr_permit permit, void *permit_data)
1353 {
1354         *coord = b->f[f];
1355         struct move m = { *coord, color };
1356         if (DEBUGL(6))
1357                 fprintf(stderr, "trying random move %d: %d,%d %s %d\n", f, coord_x(*coord, b), coord_y(*coord, b), coord2sstr(*coord, b), board_is_valid_move(b, &m));
1358         if (unlikely(board_is_one_point_eye(b, *coord, color)) /* bad idea to play into one, usually */
1359                 || !board_is_valid_move(b, &m)
1360                 || (permit && !permit(permit_data, b, &m)))
1361                 return false;
1362         if (m.coord == *coord) {
1363                 return likely(board_play_f(b, &m, f) >= 0);
1364         } else {
1365                 *coord = m.coord; // permit modified the coordinate
1366                 return likely(board_play(b, &m) >= 0);
1367         }
1368 }
1369
1370 void
1371 board_play_random(struct board *b, enum stone color, coord_t *coord, ppr_permit permit, void *permit_data)
1372 {
1373         if (unlikely(b->flen == 0))
1374                 goto pass;
1375
1376         int base = fast_random(b->flen), f;
1377         for (f = base; f < b->flen; f++)
1378                 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1379                         return;
1380         for (f = 0; f < base; f++)
1381                 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1382                         return;
1383
1384 pass:
1385         *coord = pass;
1386         struct move m = { pass, color };
1387         board_play(b, &m);
1388 }
1389
1390
1391 bool
1392 board_is_false_eyelike(struct board *board, coord_t coord, enum stone eye_color)
1393 {
1394         enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
1395
1396         /* XXX: We attempt false eye detection but we will yield false
1397          * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1398
1399         foreach_diag_neighbor(board, coord) {
1400                 color_diag_libs[(enum stone) board_at(board, c)]++;
1401         } foreach_diag_neighbor_end;
1402         /* For false eye, we need two enemy stones diagonally in the
1403          * middle of the board, or just one enemy stone at the edge
1404          * or in the corner. */
1405         color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
1406         return color_diag_libs[stone_other(eye_color)] >= 2;
1407 }
1408
1409 bool
1410 board_is_one_point_eye(struct board *board, coord_t coord, enum stone eye_color)
1411 {
1412         return board_is_eyelike(board, coord, eye_color)
1413                 && !board_is_false_eyelike(board, coord, eye_color);
1414 }
1415
1416 enum stone
1417 board_get_one_point_eye(struct board *board, coord_t coord)
1418 {
1419         if (board_is_one_point_eye(board, coord, S_WHITE))
1420                 return S_WHITE;
1421         else if (board_is_one_point_eye(board, coord, S_BLACK))
1422                 return S_BLACK;
1423         else
1424                 return S_NONE;
1425 }
1426
1427
1428 floating_t
1429 board_fast_score(struct board *board)
1430 {
1431         int scores[S_MAX];
1432         memset(scores, 0, sizeof(scores));
1433
1434         foreach_point(board) {
1435                 enum stone color = board_at(board, c);
1436                 if (color == S_NONE && board->rules != RULES_STONES_ONLY)
1437                         color = board_get_one_point_eye(board, c);
1438                 scores[color]++;
1439                 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1440         } foreach_point_end;
1441
1442         return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1443 }
1444
1445 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1446
1447 /* One flood-fill iteration; returns true if next iteration
1448  * is required. */
1449 static bool
1450 board_tromp_taylor_iter(struct board *board, int *ownermap)
1451 {
1452         bool needs_update = false;
1453         foreach_free_point(board) {
1454                 /* Ignore occupied and already-dame positions. */
1455                 assert(board_at(board, c) == S_NONE);
1456                 if (board->rules == RULES_STONES_ONLY)
1457                     ownermap[c] = 3;
1458                 if (ownermap[c] == 3)
1459                         continue;
1460                 /* Count neighbors. */
1461                 int nei[4] = {0};
1462                 foreach_neighbor(board, c, {
1463                         nei[ownermap[c]]++;
1464                 });
1465                 /* If we have neighbors of both colors, or dame,
1466                  * we are dame too. */
1467                 if ((nei[1] && nei[2]) || nei[3]) {
1468                         ownermap[c] = 3;
1469                         /* Speed up the propagation. */
1470                         foreach_neighbor(board, c, {
1471                                 if (board_at(board, c) == S_NONE)
1472                                         ownermap[c] = 3;
1473                         });
1474                         needs_update = true;
1475                         continue;
1476                 }
1477                 /* If we have neighbors of one color, we are owned
1478                  * by that color, too. */
1479                 if (!ownermap[c] && (nei[1] || nei[2])) {
1480                         int newowner = nei[1] ? 1 : 2;
1481                         ownermap[c] = newowner;
1482                         /* Speed up the propagation. */
1483                         foreach_neighbor(board, c, {
1484                                 if (board_at(board, c) == S_NONE && !ownermap[c])
1485                                         ownermap[c] = newowner;
1486                         });
1487                         needs_update = true;
1488                         continue;
1489                 }
1490         } foreach_free_point_end;
1491         return needs_update;
1492 }
1493
1494 /* Tromp-Taylor Counting */
1495 floating_t
1496 board_official_score(struct board *board, struct move_queue *q)
1497 {
1498
1499         /* A point P, not colored C, is said to reach C, if there is a path of
1500          * (vertically or horizontally) adjacent points of P's color from P to
1501          * a point of color C.
1502          *
1503          * A player's score is the number of points of her color, plus the
1504          * number of empty points that reach only her color. */
1505
1506         int ownermap[board_size2(board)];
1507         int s[4] = {0};
1508         const int o[4] = {0, 1, 2, 0};
1509         foreach_point(board) {
1510                 ownermap[c] = o[board_at(board, c)];
1511                 s[board_at(board, c)]++;
1512         } foreach_point_end;
1513
1514         if (q) {
1515                 /* Process dead groups. */
1516                 for (unsigned int i = 0; i < q->moves; i++) {
1517                         foreach_in_group(board, q->move[i]) {
1518                                 enum stone color = board_at(board, c);
1519                                 ownermap[c] = o[stone_other(color)];
1520                                 s[color]--; s[stone_other(color)]++;
1521                         } foreach_in_group_end;
1522                 }
1523         }
1524
1525         /* We need to special-case empty board. */
1526         if (!s[S_BLACK] && !s[S_WHITE])
1527                 return board->komi + board->handicap;
1528
1529         while (board_tromp_taylor_iter(board, ownermap))
1530                 /* Flood-fill... */;
1531
1532         int scores[S_MAX];
1533         memset(scores, 0, sizeof(scores));
1534
1535         foreach_point(board) {
1536                 assert(board_at(board, c) == S_OFFBOARD || ownermap[c] != 0);
1537                 if (ownermap[c] == 3)
1538                         continue;
1539                 scores[ownermap[c]]++;
1540         } foreach_point_end;
1541
1542         return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1543 }