board.c

   1 #include <assert.h>
   2 #include <math.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 //#define DEBUG
   8 #include "board.h"
   9 #include "debug.h"
  10 #include "fbook.h"
  11 #include "mq.h"
  12 #include "random.h"
  13
  14 #ifdef BOARD_SPATHASH
  15 #include "patternsp.h"
  16 #endif
  17 #ifdef BOARD_PAT3
  18 #include "pattern3.h"
  19 #endif
  20 #ifdef BOARD_TRAITS
  21 static void board_trait_recompute(struct board *board, coord_t coord);
  22 #include "tactics/selfatari.h"
  23 #endif
  24
  25
  26 #if 0
  27 #define profiling_noinline __attribute__((noinline))
  28 #else
  29 #define profiling_noinline
  30 #endif
  31
  32 #define gi_granularity 4
  33 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
  34
  35
  36 static void
  37 board_setup(struct board *b)
  38 {
  39         memset(b, 0, sizeof(*b));
  40
  41         struct move m = { pass, S_NONE };
  42         b->last_move = b->last_move2 = b->last_move3 = b->last_move4 = b->last_ko = b->ko = m;
  43 }
  44
  45 struct board *
  46 board_init(char *fbookfile)
  47 {
  48         struct board *b = malloc2(sizeof(struct board));
  49         board_setup(b);
  50
  51         b->fbookfile = fbookfile;
  52
  53         // Default setup
  54         b->size = 9 + 2;
  55         board_clear(b);
  56
  57         return b;
  58 }
  59
  60 static size_t
  61 board_alloc(struct board *board)
  62 {
  63         /* We do not allocate the board structure itself but we allocate
  64          * all the arrays with board contents. */
  65
  66         int bsize = board_size2(board) * sizeof(*board->b);
  67         int gsize = board_size2(board) * sizeof(*board->g);
  68         int fsize = board_size2(board) * sizeof(*board->f);
  69         int nsize = board_size2(board) * sizeof(*board->n);
  70         int psize = board_size2(board) * sizeof(*board->p);
  71         int hsize = board_size2(board) * 2 * sizeof(*board->h);
  72         int gisize = board_size2(board) * sizeof(*board->gi);
  73 #ifdef WANT_BOARD_C
  74         int csize = board_size2(board) * sizeof(*board->c);
  75 #else
  76         int csize = 0;
  77 #endif
  78 #ifdef BOARD_SPATHASH
  79         int ssize = board_size2(board) * sizeof(*board->spathash);
  80 #else
  81         int ssize = 0;
  82 #endif
  83 #ifdef BOARD_PAT3
  84         int p3size = board_size2(board) * sizeof(*board->pat3);
  85 #else
  86         int p3size = 0;
  87 #endif
  88 #ifdef BOARD_TRAITS
  89         int tsize = board_size2(board) * sizeof(*board->t);
  90         int tqsize = board_size2(board) * sizeof(*board->t);
  91 #else
  92         int tsize = 0;
  93         int tqsize = 0;
  94 #endif
  95         int cdsize = board_size2(board) * sizeof(*board->coord);
  96
  97         size_t size = bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize + tqsize + cdsize;
  98         void *x = malloc2(size);
  99
 100         /* board->b must come first */
 101         board->b = x; x += bsize;
 102         board->g = x; x += gsize;
 103         board->f = x; x += fsize;
 104         board->p = x; x += psize;
 105         board->n = x; x += nsize;
 106         board->h = x; x += hsize;
 107         board->gi = x; x += gisize;
 108 #ifdef WANT_BOARD_C
 109         board->c = x; x += csize;
 110 #endif
 111 #ifdef BOARD_SPATHASH
 112         board->spathash = x; x += ssize;
 113 #endif
 114 #ifdef BOARD_PAT3
 115         board->pat3 = x; x += p3size;
 116 #endif
 117 #ifdef BOARD_TRAITS
 118         board->t = x; x += tsize;
 119         board->tq = x; x += tqsize;
 120 #endif
 121         board->coord = x; x += cdsize;
 122
 123         return size;
 124 }
 125
 126 int
 127 board_cmp(struct board *b1, struct board *b2)
 128 {
 129         void **p1 = (void**)b1,  **p2 = (void**)b2;
 130         for (unsigned int i = 0; i < sizeof(struct board) / sizeof(void*); i++)
 131                 if (p1[i] != p2[i] &&
 132                     &p1[i] != (void**)&b1->b &&
 133                     &p1[i] != (void**)&b1->g &&
 134                     &p1[i] != (void**)&b1->f &&
 135                     &p1[i] != (void**)&b1->n &&
 136                     &p1[i] != (void**)&b1->p &&
 137                     &p1[i] != (void**)&b1->h &&
 138                     &p1[i] != (void**)&b1->gi &&
 139 #ifdef WANT_BOARD_C
 140                     &p1[i] != (void**)&b1->c &&
 141 #endif
 142 #ifdef BOARD_SPATHASH
 143                     &p1[i] != (void**)&b1->spathash &&
 144 #endif
 145 #ifdef BOARD_PAT3
 146                     &p1[i] != (void**)&b1->pat3 &&
 147 #endif
 148 #ifdef BOARD_TRAITS
 149                     &p1[i] != (void**)&b1->t &&
 150                     &p1[i] != (void**)&b1->tq &&
 151 #endif
 152                     &p1[i] != (void**)&b1->coord)
 153                         return 1;
 154
 155         /* Find alloc size */
 156         struct board tmp;
 157         board_setup(&tmp);
 158         size_t size = board_alloc(&tmp);
 159         board_done_noalloc(&tmp);
 160
 161         return memcmp(b1->b, b2->b, size);
 162 }
 163
 164 int
 165 board_quick_cmp(struct board *b1, struct board *b2)
 166 {
 167         if (b1->size != b2->size ||
 168             b1->size2 != b2->size2 ||
 169             b1->bits2 != b2->bits2 ||
 170             b1->captures[S_BLACK] != b2->captures[S_BLACK] ||
 171             b1->captures[S_WHITE] != b2->captures[S_WHITE] ||
 172             b1->moves != b2->moves) {
 173                 fprintf(stderr, "differs in main vars\n");
 174                 return 1;
 175         }
 176         if (move_cmp(&b1->last_move, &b2->last_move) ||
 177             move_cmp(&b1->last_move2, &b2->last_move2)) {
 178                 fprintf(stderr, "differs in last_move\n");
 179                 return 1;
 180         }
 181         if (move_cmp(&b1->ko, &b2->ko) ||
 182             move_cmp(&b1->last_ko, &b2->last_ko) ||
 183             b1->last_ko_age != b2->last_ko_age) {
 184                 fprintf(stderr, "differs in ko\n");
 185                 return 1;
 186         }
 187
 188         int bsize = board_size2(b1) * sizeof(*b1->b);
 189         int gsize = board_size2(b1) * sizeof(*b1->g);
 190         //int fsize = board_size2(b1) * sizeof(*b1->f);
 191         int nsize = board_size2(b1) * sizeof(*b1->n);
 192         int psize = board_size2(b1) * sizeof(*b1->p);
 193         //int hsize = board_size2(b1) * 2 * sizeof(*b1->h);
 194         int gisize = board_size2(b1) * sizeof(*b1->gi);
 195         //int csize = board_size2(board) * sizeof(*b1->c);
 196         //int ssize = board_size2(board) * sizeof(*b1->spathash);
 197         //int p3size = board_size2(board) * sizeof(*b1->pat3);
 198         //int tsize = board_size2(board) * sizeof(*b1->t);
 199         //int tqsize = board_size2(board) * sizeof(*b1->t);
 200
 201         //int cdsize = board_size2(b1) * sizeof(*b1->coord);
 202
 203         if (memcmp(b1->b,  b2->b,  bsize)) {
 204                 fprintf(stderr, "differs in b\n");  return 1;  }
 205         if (memcmp(b1->g,  b2->g,  gsize)) {
 206                 fprintf(stderr, "differs in g\n");  return 1;  }
 207         if (memcmp(b1->n,  b2->n,  nsize)) {
 208                 fprintf(stderr, "differs in n\n");  return 1;  }
 209         if (memcmp(b1->p,  b2->p,  psize)) {
 210                 fprintf(stderr, "differs in p\n");  return 1;  }
 211         if (memcmp(b1->gi, b2->gi, gisize)) {
 212                 fprintf(stderr, "differs in gi\n");  return 1;  }
 213
 214         return 0;
 215 }
 216
 217
 218 struct board *
 219 board_copy(struct board *b2, struct board *b1)
 220 {
 221         memcpy(b2, b1, sizeof(struct board));
 222
 223         size_t size = board_alloc(b2);
 224         memcpy(b2->b, b1->b, size);
 225
 226         // XXX: Special semantics.
 227         b2->fbook = NULL;
 228
 229         return b2;
 230 }
 231
 232 void
 233 board_done_noalloc(struct board *board)
 234 {
 235         if (board->b) free(board->b);
 236         if (board->fbook) fbook_done(board->fbook);
 237 }
 238
 239 void
 240 board_done(struct board *board)
 241 {
 242         board_done_noalloc(board);
 243         free(board);
 244 }
 245
 246 void
 247 board_resize(struct board *board, int size)
 248 {
 249 #ifdef BOARD_SIZE
 250         assert(board_size(board) == size + 2);
 251 #endif
 252         assert(size <= BOARD_MAX_SIZE);
 253         board->size = size + 2 /* S_OFFBOARD margin */;
 254         board->size2 = board_size(board) * board_size(board);
 255
 256         board->bits2 = 1;
 257         while ((1 << board->bits2) < board->size2) board->bits2++;
 258
 259         if (board->b)
 260                 free(board->b);
 261
 262         size_t asize = board_alloc(board);
 263         memset(board->b, 0, asize);
 264 }
 265
 266 static void
 267 board_init_data(struct board *board)
 268 {
 269         int size = board_size(board);
 270
 271         board_setup(board);
 272         board_resize(board, size - 2 /* S_OFFBOARD margin */);
 273
 274         /* Setup neighborhood iterators */
 275         board->nei8[0] = -size - 1; // (-1,-1)
 276         board->nei8[1] = 1;
 277         board->nei8[2] = 1;
 278         board->nei8[3] = size - 2; // (-1,0)
 279         board->nei8[4] = 2;
 280         board->nei8[5] = size - 2; // (-1,1)
 281         board->nei8[6] = 1;
 282         board->nei8[7] = 1;
 283         board->dnei[0] = -size - 1;
 284         board->dnei[1] = 2;
 285         board->dnei[2] = size*2 - 2;
 286         board->dnei[3] = 2;
 287
 288         /* Setup initial symmetry */
 289         if (size % 2) {
 290                 board->symmetry.d = 1;
 291                 board->symmetry.x1 = board->symmetry.y1 = board_size(board) / 2;
 292                 board->symmetry.x2 = board->symmetry.y2 = board_size(board) - 1;
 293                 board->symmetry.type = SYM_FULL;
 294         } else {
 295                 /* TODO: We do not handle board symmetry on boards
 296                  * with no tengen yet. */
 297                 board->symmetry.d = 0;
 298                 board->symmetry.x1 = board->symmetry.y1 = 1;
 299                 board->symmetry.x2 = board->symmetry.y2 = board_size(board) - 1;
 300                 board->symmetry.type = SYM_NONE;
 301         }
 302
 303         /* Set up coordinate cache */
 304         foreach_point(board) {
 305                 board->coord[c][0] = c % board_size(board);
 306                 board->coord[c][1] = c / board_size(board);
 307         } foreach_point_end;
 308
 309         /* Draw the offboard margin */
 310         int top_row = board_size2(board) - board_size(board);
 311         int i;
 312         for (i = 0; i < board_size(board); i++)
 313                 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
 314         for (i = 0; i <= top_row; i += board_size(board))
 315                 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
 316
 317         foreach_point(board) {
 318                 coord_t coord = c;
 319                 if (board_at(board, coord) == S_OFFBOARD)
 320                         continue;
 321                 foreach_neighbor(board, c, {
 322                         inc_neighbor_count_at(board, coord, board_at(board, c));
 323                 } );
 324         } foreach_point_end;
 325
 326         /* All positions are free! Except the margin. */
 327         for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
 328                 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
 329                         board->f[board->flen++] = i;
 330
 331         /* Initialize zobrist hashtable. */
 332         /* We will need these to be stable across Pachi runs for
 333          * certain kinds of pattern matching, thus we do not use
 334          * fast_random() for this. */
 335         hash_t hseed = 0x3121110101112131;
 336         foreach_point(board) {
 337                 board->h[c * 2] = (hseed *= 16807);
 338                 if (!board->h[c * 2])
 339                         board->h[c * 2] = 1;
 340                 /* And once again for white */
 341                 board->h[c * 2 + 1] = (hseed *= 16807);
 342                 if (!board->h[c * 2 + 1])
 343                         board->h[c * 2 + 1] = 1;
 344         } foreach_point_end;
 345
 346 #ifdef BOARD_SPATHASH
 347         /* Initialize spatial hashes. */
 348         foreach_point(board) {
 349                 for (int d = 1; d <= BOARD_SPATHASH_MAXD; d++) {
 350                         for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 351                                 ptcoords_at(x, y, c, board, j);
 352                                 board->spathash[coord_xy(board, x, y)][d - 1][0] ^=
 353                                         pthashes[0][j][board_at(board, c)];
 354                                 board->spathash[coord_xy(board, x, y)][d - 1][1] ^=
 355                                         pthashes[0][j][stone_other(board_at(board, c))];
 356                         }
 357                 }
 358         } foreach_point_end;
 359 #endif
 360 #ifdef BOARD_PAT3
 361         /* Initialize 3x3 pattern codes. */
 362         foreach_point(board) {
 363                 if (board_at(board, c) == S_NONE)
 364                         board->pat3[c] = pattern3_hash(board, c);
 365         } foreach_point_end;
 366 #endif
 367 #ifdef BOARD_TRAITS
 368         /* Initialize traits. */
 369         foreach_point(board) {
 370                 trait_at(board, c, S_BLACK).cap = 0;
 371                 trait_at(board, c, S_WHITE).cap = 0;
 372                 trait_at(board, c, S_BLACK).cap1 = 0;
 373                 trait_at(board, c, S_WHITE).cap1 = 0;
 374 #ifdef BOARD_TRAIT_SAFE
 375                 trait_at(board, c, S_BLACK).safe = true;
 376                 trait_at(board, c, S_WHITE).safe = true;
 377 #endif
 378         } foreach_point_end;
 379 #endif
 380 }
 381
 382 void
 383 board_clear(struct board *board)
 384 {
 385         int size = board_size(board);
 386         floating_t komi = board->komi;
 387         char *fbookfile = board->fbookfile;
 388         enum go_ruleset rules = board->rules;
 389
 390         board_done_noalloc(board);
 391
 392         static struct board bcache[BOARD_MAX_SIZE + 2];
 393         assert(size > 0 && size <= BOARD_MAX_SIZE + 2);
 394         if (bcache[size - 1].size == size) {
 395                 board_copy(board, &bcache[size - 1]);
 396         } else {
 397                 board_init_data(board);
 398                 board_copy(&bcache[size - 1], board);
 399         }
 400
 401         board->komi = komi;
 402         board->fbookfile = fbookfile;
 403         board->rules = rules;
 404
 405         if (board->fbookfile) {
 406                 board->fbook = fbook_init(board->fbookfile, board);
 407         }
 408 }
 409
 410 static char *
 411 board_print_top(struct board *board, char *s, char *end, int c)
 412 {
 413         for (int i = 0; i < c; i++) {
 414                 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
 415                 s += snprintf(s, end - s, "      ");
 416                 for (int x = 1; x < board_size(board) - 1; x++)
 417                         s += snprintf(s, end - s, "%c ", asdf[x - 1]);
 418                 s += snprintf(s, end -s, " ");
 419         }
 420         s += snprintf(s, end - s, "\n");
 421         for (int i = 0; i < c; i++) {
 422                 s += snprintf(s, end - s, "    +-");
 423                 for (int x = 1; x < board_size(board) - 1; x++)
 424                         s += snprintf(s, end - s, "--");
 425                 s += snprintf(s, end - s, "+");
 426         }
 427         s += snprintf(s, end - s, "\n");
 428         return s;
 429 }
 430
 431 static char *
 432 board_print_bottom(struct board *board, char *s, char *end, int c)
 433 {
 434         for (int i = 0; i < c; i++) {
 435                 s += snprintf(s, end - s, "    +-");
 436                 for (int x = 1; x < board_size(board) - 1; x++)
 437                         s += snprintf(s, end - s, "--");
 438                 s += snprintf(s, end - s, "+");
 439         }
 440         s += snprintf(s, end - s, "\n");
 441         return s;
 442 }
 443
 444 static char *
 445 board_print_row(struct board *board, int y, char *s, char *end, board_cprint cprint, void *data)
 446 {
 447         s += snprintf(s, end - s, " %2d | ", y);
 448         for (int x = 1; x < board_size(board) - 1; x++) {
 449                 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
 450                         s += snprintf(s, end - s, "%c)", stone2char(board_atxy(board, x, y)));
 451                 else
 452                         s += snprintf(s, end - s, "%c ", stone2char(board_atxy(board, x, y)));
 453         }
 454         s += snprintf(s, end - s, "|");
 455         if (cprint) {
 456                 s += snprintf(s, end - s, " %2d | ", y);
 457                 for (int x = 1; x < board_size(board) - 1; x++) {
 458                         s = cprint(board, coord_xy(board, x, y), s, end, data);
 459                 }
 460                 s += snprintf(s, end - s, "|");
 461         }
 462         s += snprintf(s, end - s, "\n");
 463         return s;
 464 }
 465
 466 void
 467 board_print_custom(struct board *board, FILE *f, board_cprint cprint, void *data)
 468 {
 469         char buf[10240];
 470         char *s = buf;
 471         char *end = buf + sizeof(buf);
 472         s += snprintf(s, end - s, "Move: % 3d  Komi: %2.1f  Handicap: %d  Captures B: %d W: %d\n",
 473                 board->moves, board->komi, board->handicap,
 474                 board->captures[S_BLACK], board->captures[S_WHITE]);
 475         s = board_print_top(board, s, end, 1 + !!cprint);
 476         for (int y = board_size(board) - 2; y >= 1; y--)
 477                 s = board_print_row(board, y, s, end, cprint, data);
 478         board_print_bottom(board, s, end, 1 + !!cprint);
 479         fprintf(f, "%s\n", buf);
 480 }
 481
 482 static char *
 483 cprint_group(struct board *board, coord_t c, char *s, char *end, void *data)
 484 {
 485         s += snprintf(s, end - s, "%d ", group_base(group_at(board, c)));
 486         return s;
 487 }
 488
 489 void
 490 board_print(struct board *board, FILE *f)
 491 {
 492         board_print_custom(board, f, DEBUGL(6) ? cprint_group : NULL, NULL);
 493 }
 494
 495
 496 #ifdef BOARD_TRAITS
 497
 498 #if BOARD_TRAIT_SAFE == 1
 499 static bool
 500 board_trait_safe(struct board *board, coord_t coord, enum stone color)
 501 {
 502         return board_safe_to_play(board, coord, color);
 503 }
 504 #elif BOARD_TRAIT_SAFE == 2
 505 static bool
 506 board_trait_safe(struct board *board, coord_t coord, enum stone color)
 507 {
 508         return !is_bad_selfatari(board, color, coord);
 509 }
 510 #endif
 511
 512 static void
 513 board_trait_recompute(struct board *board, coord_t coord)
 514 {
 515         int sfb = -1, sfw = -1;
 516 #ifdef BOARD_TRAIT_SAFE
 517         sfb = trait_at(board, coord, S_BLACK).safe = board_trait_safe(board, coord, S_BLACK);
 518         sfw = trait_at(board, coord, S_WHITE).safe = board_trait_safe(board, coord, S_WHITE);
 519 #endif
 520         if (DEBUGL(8)) {
 521                 fprintf(stderr, "traits[%s:%s lib=%d] (black cap=%d cap1=%d safe=%d) (white cap=%d cap1=%d safe=%d)\n",
 522                         coord2sstr(coord, board), stone2str(board_at(board, coord)), immediate_liberty_count(board, coord),
 523                         trait_at(board, coord, S_BLACK).cap, trait_at(board, coord, S_BLACK).cap1, sfb,
 524                         trait_at(board, coord, S_WHITE).cap, trait_at(board, coord, S_WHITE).cap1, sfw);
 525         }
 526 }
 527 #endif
 528
 529 /* Recompute traits for dirty points that we have previously touched
 530  * somehow (libs of their neighbors changed or so). */
 531 static void
 532 board_traits_recompute(struct board *board)
 533 {
 534 #ifdef BOARD_TRAITS
 535         for (int i = 0; i < board->tqlen; i++) {
 536                 coord_t coord = board->tq[i];
 537                 trait_at(board, coord, S_BLACK).dirty = false;
 538                 if (board_at(board, coord) != S_NONE)
 539                         continue;
 540                 board_trait_recompute(board, coord);
 541         }
 542         board->tqlen = 0;
 543 #endif
 544 }
 545
 546 /* Queue traits of given point for recomputing. */
 547 static void
 548 board_trait_queue(struct board *board, coord_t coord)
 549 {
 550 #ifdef BOARD_TRAITS
 551         if (trait_at(board, coord, S_BLACK).dirty)
 552                 return;
 553         board->tq[board->tqlen++] = coord;
 554         trait_at(board, coord, S_BLACK).dirty = true;
 555 #endif
 556 }
 557
 558
 559 /* Update board hash with given coordinate. */
 560 static void profiling_noinline
 561 board_hash_update(struct board *board, coord_t coord, enum stone color)
 562 {
 563         board->hash ^= hash_at(board, coord, color);
 564         board->qhash[coord_quadrant(coord, board)] ^= hash_at(board, coord, color);
 565         if (DEBUGL(8))
 566                 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);
 567
 568 #ifdef BOARD_SPATHASH
 569         /* Gridcular metric is reflective, so we update all hashes
 570          * of appropriate ditance in OUR circle. */
 571         for (int d = 1; d <= BOARD_SPATHASH_MAXD; d++) {
 572                 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 573                         ptcoords_at(x, y, coord, board, j);
 574                         /* We either changed from S_NONE to color
 575                          * or vice versa; doesn't matter. */
 576                         board->spathash[coord_xy(board, x, y)][d - 1][0] ^=
 577                                 pthashes[0][j][color] ^ pthashes[0][j][S_NONE];
 578                         board->spathash[coord_xy(board, x, y)][d - 1][1] ^=
 579                                 pthashes[0][j][stone_other(color)] ^ pthashes[0][j][S_NONE];
 580                 }
 581         }
 582 #endif
 583
 584 #if defined(BOARD_PAT3)
 585         /* @color is not what we need in case of capture. */
 586         static const int ataribits[8] = { -1, 0, -1, 1, 2, -1, 3, -1 };
 587         enum stone new_color = board_at(board, coord);
 588         bool in_atari = false;
 589         if (new_color == S_NONE) {
 590                 board->pat3[coord] = pattern3_hash(board, coord);
 591         } else {
 592                 in_atari = (board_group_info(board, group_at(board, coord)).libs == 1);
 593         }
 594         foreach_8neighbor(board, coord) {
 595                 /* Internally, the loop uses fn__i=[0..7]. We can use
 596                  * it directly to address bits within the bitmap of the
 597                  * neighbors since the bitmap order is reverse to the
 598                  * loop order. */
 599                 if (board_at(board, c) != S_NONE)
 600                         continue;
 601                 board->pat3[c] &= ~(3 << (fn__i*2));
 602                 board->pat3[c] |= new_color << (fn__i*2);
 603                 if (ataribits[fn__i] >= 0) {
 604                         board->pat3[c] &= ~(1 << (16 + ataribits[fn__i]));
 605                         board->pat3[c] |= in_atari << (16 + ataribits[fn__i]);
 606                 }
 607 #if defined(BOARD_TRAITS)
 608                 board_trait_queue(board, c);
 609 #endif
 610         } foreach_8neighbor_end;
 611 #endif
 612 }
 613
 614 /* Commit current board hash to history. */
 615 static void profiling_noinline
 616 board_hash_commit(struct board *board)
 617 {
 618         if (DEBUGL(8))
 619                 fprintf(stderr, "board_hash_commit %"PRIhash"\n", board->hash);
 620         if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
 621                 board->history_hash[board->hash & history_hash_mask] = board->hash;
 622         } else {
 623                 hash_t i = board->hash;
 624                 while (board->history_hash[i & history_hash_mask]) {
 625                         if (board->history_hash[i & history_hash_mask] == board->hash) {
 626                                 if (DEBUGL(5))
 627                                         fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
 628                                                 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
 629                                 board->superko_violation = true;
 630                                 return;
 631                         }
 632                         i = history_hash_next(i);
 633                 }
 634                 board->history_hash[i & history_hash_mask] = board->hash;
 635         }
 636 }
 637
 638
 639 void
 640 board_symmetry_update(struct board *b, struct board_symmetry *symmetry, coord_t c)
 641 {
 642         if (likely(symmetry->type == SYM_NONE)) {
 643                 /* Fully degenerated already. We do not support detection
 644                  * of restoring of symmetry, assuming that this is too rare
 645                  * a case to handle. */
 646                 return;
 647         }
 648
 649         int x = coord_x(c, b), y = coord_y(c, b), t = board_size(b) / 2;
 650         int dx = board_size(b) - 1 - x; /* for SYM_DOWN */
 651         if (DEBUGL(6)) {
 652                 fprintf(stderr, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
 653                         symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
 654                         symmetry->d, symmetry->type, x, y);
 655         }
 656
 657         switch (symmetry->type) {
 658                 case SYM_FULL:
 659                         if (x == t && y == t) {
 660                                 /* Tengen keeps full symmetry. */
 661                                 return;
 662                         }
 663                         /* New symmetry now? */
 664                         if (x == y) {
 665                                 symmetry->type = SYM_DIAG_UP;
 666                                 symmetry->x1 = symmetry->y1 = 1;
 667                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 668                                 symmetry->d = 1;
 669                         } else if (dx == y) {
 670                                 symmetry->type = SYM_DIAG_DOWN;
 671                                 symmetry->x1 = symmetry->y1 = 1;
 672                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 673                                 symmetry->d = 1;
 674                         } else if (x == t) {
 675                                 symmetry->type = SYM_HORIZ;
 676                                 symmetry->y1 = 1;
 677                                 symmetry->y2 = board_size(b) - 1;
 678                                 symmetry->d = 0;
 679                         } else if (y == t) {
 680                                 symmetry->type = SYM_VERT;
 681                                 symmetry->x1 = 1;
 682                                 symmetry->x2 = board_size(b) - 1;
 683                                 symmetry->d = 0;
 684                         } else {
 685 break_symmetry:
 686                                 symmetry->type = SYM_NONE;
 687                                 symmetry->x1 = symmetry->y1 = 1;
 688                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 689                                 symmetry->d = 0;
 690                         }
 691                         break;
 692                 case SYM_DIAG_UP:
 693                         if (x == y)
 694                                 return;
 695                         goto break_symmetry;
 696                 case SYM_DIAG_DOWN:
 697                         if (dx == y)
 698                                 return;
 699                         goto break_symmetry;
 700                 case SYM_HORIZ:
 701                         if (x == t)
 702                                 return;
 703                         goto break_symmetry;
 704                 case SYM_VERT:
 705                         if (y == t)
 706                                 return;
 707                         goto break_symmetry;
 708                 case SYM_NONE:
 709                         assert(0);
 710                         break;
 711         }
 712
 713         if (DEBUGL(6)) {
 714                 fprintf(stderr, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
 715                         symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
 716                         symmetry->d, symmetry->type);
 717         }
 718         /* Whew. */
 719 }
 720
 721
 722 void
 723 board_handicap_stone(struct board *board, int x, int y, FILE *f)
 724 {
 725         struct move m;
 726         m.color = S_BLACK; m.coord = coord_xy(board, x, y);
 727
 728         board_play(board, &m);
 729         /* Simulate white passing; otherwise, UCT search can get confused since
 730          * tree depth parity won't match the color to move. */
 731         board->moves++;
 732
 733         char *str = coord2str(m.coord, board);
 734         if (DEBUGL(1))
 735                 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
 736         if (f) fprintf(f, "%s ", str);
 737         free(str);
 738 }
 739
 740 void
 741 board_handicap(struct board *board, int stones, FILE *f)
 742 {
 743         int margin = 3 + (board_size(board) >= 13);
 744         int min = margin;
 745         int mid = board_size(board) / 2;
 746         int max = board_size(board) - 1 - margin;
 747         const int places[][2] = {
 748                 { min, min }, { max, max }, { min, max }, { max, min },
 749                 { min, mid }, { max, mid },
 750                 { mid, min }, { mid, max },
 751                 { mid, mid },
 752         };
 753
 754         board->handicap = stones;
 755
 756         if (stones == 5 || stones == 7) {
 757                 board_handicap_stone(board, mid, mid, f);
 758                 stones--;
 759         }
 760
 761         int i;
 762         for (i = 0; i < stones; i++)
 763                 board_handicap_stone(board, places[i][0], places[i][1], f);
 764 }
 765
 766
 767 static void __attribute__((noinline))
 768 check_libs_consistency(struct board *board, group_t g)
 769 {
 770 #ifdef DEBUG
 771         if (!g) return;
 772         struct group *gi = &board_group_info(board, g);
 773         for (int i = 0; i < GROUP_KEEP_LIBS; i++)
 774                 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
 775                         fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
 776                         assert(0);
 777                 }
 778 #endif
 779 }
 780
 781 static void
 782 check_pat3_consistency(struct board *board, coord_t coord)
 783 {
 784 #ifdef DEBUG
 785         foreach_8neighbor(board, coord) {
 786                 if (board_at(board, c) == S_NONE && pattern3_hash(board, c) != board->pat3[c]) {
 787                         board_print(board, stderr);
 788                         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);
 789                         assert(0);
 790                 }
 791         } foreach_8neighbor_end;
 792 #endif
 793 }
 794
 795 static void
 796 board_capturable_add(struct board *board, group_t group, coord_t lib, bool onestone)
 797 {
 798         //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
 799 #ifdef BOARD_TRAITS
 800         /* Increase capturable count trait of my last lib. */
 801         enum stone capturing_color = stone_other(board_at(board, group));
 802         assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
 803         foreach_neighbor(board, lib, {
 804                 if (DEBUGL(8) && group_at(board, c) == group)
 805                         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);
 806                 trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group);
 807                 trait_at(board, lib, capturing_color).cap1 += (group_at(board, c) == group && onestone);
 808         });
 809         board_trait_queue(board, lib);
 810 #endif
 811
 812 #ifdef BOARD_PAT3
 813         int fn__i = 0;
 814         foreach_neighbor(board, lib, {
 815                 board->pat3[lib] |= (group_at(board, c) == group) << (16 + 3 - fn__i);
 816                 fn__i++;
 817         });
 818 #endif
 819
 820 #ifdef WANT_BOARD_C
 821         /* Update the list of capturable groups. */
 822         assert(group);
 823         assert(board->clen < board_size2(board));
 824         board->c[board->clen++] = group;
 825 #endif
 826 }
 827 static void
 828 board_capturable_rm(struct board *board, group_t group, coord_t lib, bool onestone)
 829 {
 830         //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
 831 #ifdef BOARD_TRAITS
 832         /* Decrease capturable count trait of my previously-last lib. */
 833         enum stone capturing_color = stone_other(board_at(board, group));
 834         assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
 835         foreach_neighbor(board, lib, {
 836                 if (DEBUGL(8) && group_at(board, c) == group)
 837                         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);
 838                 trait_at(board, lib, capturing_color).cap -= (group_at(board, c) == group);
 839                 trait_at(board, lib, capturing_color).cap1 -= (group_at(board, c) == group && onestone);
 840         });
 841         board_trait_queue(board, lib);
 842 #endif
 843
 844 #ifdef BOARD_PAT3
 845         int fn__i = 0;
 846         foreach_neighbor(board, lib, {
 847                 board->pat3[lib] &= ~((group_at(board, c) == group) << (16 + 3 - fn__i));
 848                 fn__i++;
 849         });
 850 #endif
 851
 852 #ifdef WANT_BOARD_C
 853         /* Update the list of capturable groups. */
 854         for (int i = 0; i < board->clen; i++) {
 855                 if (unlikely(board->c[i] == group)) {
 856                         board->c[i] = board->c[--board->clen];
 857                         return;
 858                 }
 859         }
 860         fprintf(stderr, "rm of bad group %d\n", group_base(group));
 861         assert(0);
 862 #endif
 863 }
 864
 865 static void
 866 board_atariable_add(struct board *board, group_t group, coord_t lib1, coord_t lib2)
 867 {
 868 #ifdef BOARD_TRAITS
 869         board_trait_queue(board, lib1);
 870         board_trait_queue(board, lib2);
 871 #endif
 872 }
 873 static void
 874 board_atariable_rm(struct board *board, group_t group, coord_t lib1, coord_t lib2)
 875 {
 876 #ifdef BOARD_TRAITS
 877         board_trait_queue(board, lib1);
 878         board_trait_queue(board, lib2);
 879 #endif
 880 }
 881
 882 static void
 883 board_group_addlib(struct board *board, group_t group, coord_t coord, struct board_undo *u)
 884 {
 885         if (DEBUGL(7)) {
 886                 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
 887                         group_base(group), coord2sstr(group_base(group), board),
 888                         board_group_info(board, group).libs, coord2sstr(coord, board));
 889         }
 890
 891         if (!u) check_libs_consistency(board, group);
 892
 893         struct group *gi = &board_group_info(board, group);
 894         bool onestone = group_is_onestone(board, group);
 895         if (gi->libs < GROUP_KEEP_LIBS) {
 896                 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
 897 #if 0
 898                         /* Seems extra branch just slows it down */
 899                         if (!gi->lib[i])
 900                                 break;
 901 #endif
 902                         if (unlikely(gi->lib[i] == coord))
 903                                 return;
 904                 }
 905                 if (!u) {
 906                         if (gi->libs == 0) {
 907                                 board_capturable_add(board, group, coord, onestone);
 908                         } else if (gi->libs == 1) {
 909                                 board_capturable_rm(board, group, gi->lib[0], onestone);
 910                                 board_atariable_add(board, group, gi->lib[0], coord);
 911                         } else if (gi->libs == 2) {
 912                                 board_atariable_rm(board, group, gi->lib[0], gi->lib[1]);
 913                         }
 914                 }
 915                 gi->lib[gi->libs++] = coord;
 916         }
 917
 918         if (!u) check_libs_consistency(board, group);
 919 }
 920
 921 static void
 922 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
 923 {
 924         /* Add extra liberty from the board to our liberty list. */
 925         unsigned char watermark[board_size2(board) / 8];
 926         memset(watermark, 0, sizeof(watermark));
 927 #define watermark_get(c)        (watermark[c >> 3] & (1 << (c & 7)))
 928 #define watermark_set(c)        watermark[c >> 3] |= (1 << (c & 7))
 929
 930         for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
 931                 watermark_set(gi->lib[i]);
 932         watermark_set(avoid);
 933
 934         foreach_in_group(board, group) {
 935                 coord_t coord2 = c;
 936                 foreach_neighbor(board, coord2, {
 937                         if (board_at(board, c) + watermark_get(c) != S_NONE)
 938                                 continue;
 939                         watermark_set(c);
 940                         gi->lib[gi->libs++] = c;
 941                         if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
 942                                 return;
 943                 } );
 944         } foreach_in_group_end;
 945 #undef watermark_get
 946 #undef watermark_set
 947 }
 948
 949 static void
 950 board_group_rmlib(struct board *board, group_t group, coord_t coord, struct board_undo *u)
 951 {
 952         if (DEBUGL(7)) {
 953                 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
 954                         group_base(group), coord2sstr(group_base(group), board),
 955                         board_group_info(board, group).libs, coord2sstr(coord, board));
 956         }
 957
 958         struct group *gi = &board_group_info(board, group);
 959         bool onestone = group_is_onestone(board, group);
 960         for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
 961 #if 0
 962                 /* Seems extra branch just slows it down */
 963                 if (!gi->lib[i])
 964                         break;
 965 #endif
 966                 if (likely(gi->lib[i] != coord))
 967                         continue;
 968
 969                 coord_t lib = gi->lib[i] = gi->lib[--gi->libs];
 970                 gi->lib[gi->libs] = 0;
 971
 972                 if (!u) check_libs_consistency(board, group);
 973
 974                 /* Postpone refilling lib[] until we need to. */
 975                 assert(GROUP_REFILL_LIBS > 1);
 976                 if (gi->libs > GROUP_REFILL_LIBS)
 977                         return;
 978                 if (gi->libs == GROUP_REFILL_LIBS)
 979                         board_group_find_extra_libs(board, group, gi, coord);
 980                 if (u) return;
 981
 982                 if (gi->libs == 2) {
 983                         board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
 984                 } else if (gi->libs == 1) {
 985                         board_capturable_add(board, group, gi->lib[0], onestone);
 986                         board_atariable_rm(board, group, gi->lib[0], lib);
 987                 } else if (gi->libs == 0)
 988                         board_capturable_rm(board, group, lib, onestone);
 989                 return;
 990         }
 991
 992         /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
 993          * can call this multiple times per coord. */
 994         if (!u) check_libs_consistency(board, group);
 995         return;
 996 }
 997
 998
 999 /* This is a low-level routine that doesn't maintain consistency
1000  * of all the board data structures. */
1001 static void
1002 board_remove_stone(struct board *board, group_t group, coord_t c, struct board_undo *u)
1003 {
1004         enum stone color = board_at(board, c);
1005         board_at(board, c) = S_NONE;
1006         group_at(board, c) = 0;
1007         if (!u) {
1008                 board_hash_update(board, c, color);
1009 #ifdef BOARD_TRAITS
1010                 /* We mark as cannot-capture now. If this is a ko/snapback,
1011                  * we will get incremented later in board_group_addlib(). */
1012                 trait_at(board, c, S_BLACK).cap = trait_at(board, c, S_BLACK).cap1 = 0;
1013                 trait_at(board, c, S_WHITE).cap = trait_at(board, c, S_WHITE).cap1 = 0;
1014                 board_trait_queue(board, c);
1015 #endif
1016         }
1017
1018         /* Increase liberties of surrounding groups */
1019         coord_t coord = c;
1020         foreach_neighbor(board, coord, {
1021                 dec_neighbor_count_at(board, c, color);
1022                 if (!u) board_trait_queue(board, c);
1023                 group_t g = group_at(board, c);
1024                 if (g && g != group)
1025                         board_group_addlib(board, g, coord, u);
1026         });
1027         if (u) return;
1028
1029 #ifdef BOARD_PAT3
1030         /* board_hash_update() might have seen the freed up point as able
1031          * to capture another group in atari that only after the loop
1032          * above gained enough liberties. Reset pat3 again. */
1033         board->pat3[c] = pattern3_hash(board, c);
1034 #endif
1035
1036         if (DEBUGL(6))
1037                 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
1038         board->f[board->flen++] = c;
1039 }
1040
1041 static int profiling_noinline
1042 board_group_capture(struct board *board, group_t group, struct board_undo *u)
1043 {
1044         int stones = 0;
1045
1046         foreach_in_group(board, group) {
1047                 board->captures[stone_other(board_at(board, c))]++;
1048                 board_remove_stone(board, group, c, u);
1049                 stones++;
1050         } foreach_in_group_end;
1051
1052         struct group *gi = &board_group_info(board, group);
1053         assert(gi->libs == 0);
1054         memset(gi, 0, sizeof(*gi));
1055
1056         return stones;
1057 }
1058
1059
1060 static void profiling_noinline
1061 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord, struct board_undo *u)
1062 {
1063 #ifdef BOARD_TRAITS
1064         struct group *gi = &board_group_info(board, group);
1065         bool onestone = group_is_onestone(board, group);
1066
1067         if (!u && gi->libs == 1) {
1068                 /* Our group is temporarily in atari; make sure the capturable
1069                  * counts also correspond to the newly added stone before we
1070                  * start adding liberties again so bump-dump ops match. */
1071                 enum stone capturing_color = stone_other(board_at(board, group));
1072                 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
1073
1074                 coord_t lib = board_group_info(board, group).lib[0];
1075                 if (coord_is_adjecent(lib, coord, board)) {
1076                         if (DEBUGL(8))
1077                                 fprintf(stderr, "add_to_group %s: %s[%d] bump\n", coord2sstr(group, board), coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap);
1078                         trait_at(board, lib, capturing_color).cap++;
1079                         /* This is never a 1-stone group, obviously. */
1080                         board_trait_queue(board, lib);
1081                 }
1082
1083                 if (onestone) {
1084                         /* We are not 1-stone group anymore, update the cap1
1085                          * counter specifically. */
1086                         foreach_neighbor(board, group, {
1087                                 if (board_at(board, c) != S_NONE) continue;
1088                                 trait_at(board, c, capturing_color).cap1--;
1089                                 board_trait_queue(board, c);
1090                         });
1091                 }
1092         }
1093 #endif
1094
1095         group_at(board, coord) = group;
1096         groupnext_at(board, coord) = groupnext_at(board, prevstone);
1097         groupnext_at(board, prevstone) = coord;
1098
1099         foreach_neighbor(board, coord, {
1100                 if (board_at(board, c) == S_NONE)
1101                         board_group_addlib(board, group, c, u);
1102         });
1103
1104         if (DEBUGL(8))
1105                 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
1106                         coord_x(prevstone, board), coord_y(prevstone, board),
1107                         coord_x(coord, board), coord_y(coord, board),
1108                         groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
1109                         group_base(group));
1110 }
1111
1112 static void profiling_noinline
1113 merge_groups(struct board *board, group_t group_to, group_t group_from, struct board_undo *u)
1114 {
1115         if (DEBUGL(7))
1116                 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
1117                         group_base(group_from), group_base(group_to));
1118         struct group *gi_from = &board_group_info(board, group_from);
1119         struct group *gi_to = &board_group_info(board, group_to);
1120         bool onestone_from = group_is_onestone(board, group_from);
1121         bool onestone_to = group_is_onestone(board, group_to);
1122
1123         if (!u) {
1124                 /* We do this early before the group info is rewritten. */
1125                 if (gi_from->libs == 2)
1126                         board_atariable_rm(board, group_from, gi_from->lib[0], gi_from->lib[1]);
1127                 else if (gi_from->libs == 1)
1128                         board_capturable_rm(board, group_from, gi_from->lib[0], onestone_from);
1129         }
1130
1131         if (DEBUGL(7))
1132                 fprintf(stderr,"---- (froml %d, tol %d)\n", gi_from->libs, gi_to->libs);
1133
1134         if (gi_to->libs < GROUP_KEEP_LIBS) {
1135                 for (int i = 0; i < gi_from->libs; i++) {
1136                         for (int j = 0; j < gi_to->libs; j++)
1137                                 if (gi_to->lib[j] == gi_from->lib[i])
1138                                         goto next_from_lib;
1139                         if (!u) {
1140                                 if (gi_to->libs == 0) {
1141                                         board_capturable_add(board, group_to, gi_from->lib[i], onestone_to);
1142                                 } else if (gi_to->libs == 1) {
1143                                         board_capturable_rm(board, group_to, gi_to->lib[0], onestone_to);
1144                                         board_atariable_add(board, group_to, gi_to->lib[0], gi_from->lib[i]);
1145                                 } else if (gi_to->libs == 2) {
1146                                         board_atariable_rm(board, group_to, gi_to->lib[0], gi_to->lib[1]);
1147                                 }
1148                         }
1149                         gi_to->lib[gi_to->libs++] = gi_from->lib[i];
1150                         if (gi_to->libs >= GROUP_KEEP_LIBS)
1151                                 break;
1152 next_from_lib:;
1153                 }
1154         }
1155
1156         if (!u && gi_to->libs == 1) {
1157                 coord_t lib = board_group_info(board, group_to).lib[0];
1158 #ifdef BOARD_TRAITS
1159                 enum stone capturing_color = stone_other(board_at(board, group_to));
1160                 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
1161
1162                 /* Our group is currently in atari; make sure we properly
1163                  * count in even the neighbors from the other group in the
1164                  * capturable counter. */
1165                 foreach_neighbor(board, lib, {
1166                         if (DEBUGL(8) && group_at(board, c) == group_from)
1167                                 fprintf(stderr, "%s[%d] cap bump\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap);
1168                         trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group_from);
1169                         /* This is never a 1-stone group, obviously. */
1170                 });
1171                 board_trait_queue(board, lib);
1172
1173                 if (onestone_to) {
1174                         /* We are not 1-stone group anymore, update the cap1
1175                          * counter specifically. */
1176                         foreach_neighbor(board, group_to, {
1177                                 if (board_at(board, c) != S_NONE) continue;
1178                                 trait_at(board, c, capturing_color).cap1--;
1179                                 board_trait_queue(board, c);
1180                         });
1181                 }
1182 #endif
1183 #ifdef BOARD_PAT3
1184                 if (gi_from->libs == 1) {
1185                         /* We removed group_from from capturable groups,
1186                          * therefore switching the atari flag off.
1187                          * We need to set it again since group_to is also
1188                          * capturable. */
1189                         int fn__i = 0;
1190                         foreach_neighbor(board, lib, {
1191                                 board->pat3[lib] |= (group_at(board, c) == group_from) << (16 + 3 - fn__i);
1192                                 fn__i++;
1193                         });
1194                 }
1195 #endif
1196         }
1197
1198         coord_t last_in_group;
1199         foreach_in_group(board, group_from) {
1200                 last_in_group = c;
1201                 group_at(board, c) = group_to;
1202         } foreach_in_group_end;
1203
1204         if (u) u->merged[++u->nmerged_tmp].last = last_in_group;
1205         groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
1206         groupnext_at(board, group_base(group_to)) = group_base(group_from);
1207         memset(gi_from, 0, sizeof(struct group));
1208
1209         if (DEBUGL(7))
1210                 fprintf(stderr, "board_play_raw: merged group: %d\n",
1211                         group_base(group_to));
1212 }
1213
1214 static group_t profiling_noinline
1215 new_group(struct board *board, coord_t coord, struct board_undo *u)
1216 {
1217         group_t group = coord;
1218         struct group *gi = &board_group_info(board, group);
1219         foreach_neighbor(board, coord, {
1220                 if (board_at(board, c) == S_NONE)
1221                         /* board_group_addlib is ridiculously expensive for us */
1222 #if GROUP_KEEP_LIBS < 4
1223                         if (gi->libs < GROUP_KEEP_LIBS)
1224 #endif
1225                         gi->lib[gi->libs++] = c;
1226         });
1227
1228         group_at(board, coord) = group;
1229         groupnext_at(board, coord) = 0;
1230
1231         if (!u) {
1232                 if (gi->libs == 2)
1233                         board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
1234                 else if (gi->libs == 1)
1235                         board_capturable_add(board, group, gi->lib[0], true);
1236                 check_libs_consistency(board, group);
1237         }
1238
1239         if (DEBUGL(8))
1240                 fprintf(stderr, "new_group: added %d,%d to group %d\n",
1241                         coord_x(coord, board), coord_y(coord, board),
1242                         group_base(group));
1243
1244         return group;
1245 }
1246
1247 static inline void
1248 undo_save_merge(struct board *b, struct board_undo *u, group_t g, coord_t c)
1249 {
1250         if (g == u->merged[0].group || g == u->merged[1].group ||
1251             g == u->merged[2].group || g == u->merged[3].group)
1252                 return;
1253
1254         int i = u->nmerged++;
1255         if (!i)
1256                 u->inserted = c;
1257         u->merged[i].group = g;
1258         u->merged[i].last = 0;   // can remove
1259         u->merged[i].info = board_group_info(b, g);
1260 }
1261
1262 static inline void
1263 undo_save_enemy(struct board *b, struct board_undo *u, group_t g)
1264 {
1265         if (g == u->enemies[0].group || g == u->enemies[1].group ||
1266             g == u->enemies[2].group || g == u->enemies[3].group)
1267                 return;
1268
1269         int i = u->nenemies++;
1270         u->enemies[i].group = g;
1271         u->enemies[i].info = board_group_info(b, g);
1272
1273         int j = 0;
1274         coord_t *stones = u->enemies[i].stones;
1275         if (board_group_info(b, g).libs <= 1) { // Will be captured
1276                 foreach_in_group(b, g) {
1277                         stones[j++] = c;
1278                 } foreach_in_group_end;
1279                 u->captures += j;
1280         }
1281         stones[j] = 0;
1282 }
1283
1284 static void
1285 undo_save_group_info(struct board *b, coord_t coord, enum stone color, struct board_undo *u)
1286 {
1287         u->next_at = groupnext_at(b, coord);
1288
1289         foreach_neighbor(b, coord, {
1290                 group_t g = group_at(b, c);
1291
1292                 if (board_at(b, c) == color)
1293                         undo_save_merge(b, u, g, c);
1294                 else if (board_at(b, c) == stone_other(color))
1295                         undo_save_enemy(b, u, g);
1296         });
1297 }
1298
1299 static void
1300 undo_save_suicide(struct board *b, coord_t coord, enum stone color, struct board_undo *u)
1301 {
1302         foreach_neighbor(b, coord, {
1303                 if (board_at(b, c) == color) {
1304                         // Handle suicide as a capture ...
1305                         undo_save_enemy(b, u, group_at(b, c));
1306                         return;
1307                 }
1308         });
1309         assert(0);
1310 }
1311
1312 static inline group_t
1313 play_one_neighbor(struct board *board,
1314                   coord_t coord, enum stone color, enum stone other_color,
1315                   coord_t c, group_t group, struct board_undo *u)
1316 {
1317         enum stone ncolor = board_at(board, c);
1318         group_t ngroup = group_at(board, c);
1319
1320         inc_neighbor_count_at(board, c, color);
1321         /* We can be S_NONE, in that case we need to update the safety
1322          * trait since we might be left with only one liberty. */
1323         if (!u) board_trait_queue(board, c);
1324
1325         if (!ngroup)
1326                 return group;
1327
1328         board_group_rmlib(board, ngroup, coord, u);
1329         if (DEBUGL(7))
1330                 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
1331                         group_base(ngroup), ncolor, color, other_color);
1332
1333         if (ncolor == color && ngroup != group) {
1334                 if (!group) {
1335                         group = ngroup;
1336                         add_to_group(board, group, c, coord, u);
1337                 } else {
1338                         merge_groups(board, group, ngroup, u);
1339                 }
1340         } else if (ncolor == other_color) {
1341                 if (DEBUGL(8)) {
1342                         struct group *gi = &board_group_info(board, ngroup);
1343                         fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
1344                         for (int i = 0; i < GROUP_KEEP_LIBS; i++)
1345                                 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
1346                         fprintf(stderr, "\n");
1347                 }
1348                 if (unlikely(board_group_captured(board, ngroup)))
1349                         board_group_capture(board, ngroup, u);
1350         }
1351         return group;
1352 }
1353
1354 /* We played on a place with at least one liberty. We will become a member of
1355  * some group for sure. */
1356 static group_t profiling_noinline
1357 board_play_outside(struct board *board, struct move *m, int f, struct board_undo *u)
1358 {
1359         coord_t coord = m->coord;
1360         enum stone color = m->color;
1361         enum stone other_color = stone_other(color);
1362         group_t group = 0;
1363
1364         if (u)
1365                 undo_save_group_info(board, coord, color, u);
1366         else {
1367                 board->f[f] = board->f[--board->flen];
1368                 if (DEBUGL(6))
1369                         fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1370
1371 #if defined(BOARD_TRAITS) && defined(DEBUG)
1372                 /* Sanity check that cap matches reality. */
1373                 {
1374                         int a = 0, b = 0;
1375                         foreach_neighbor(board, coord, {
1376                                         group_t g = group_at(board, c);
1377                                         a += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1);
1378                                         b += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1) && group_is_onestone(board, g);
1379                                 });
1380                         assert(a == trait_at(board, coord, color).cap);
1381                         assert(b == trait_at(board, coord, color).cap1);
1382 #ifdef BOARD_TRAIT_SAFE
1383                         assert(board_trait_safe(board, coord, color) == trait_at(board, coord, color).safe);
1384 #endif
1385                 }
1386 #endif
1387         }
1388         foreach_neighbor(board, coord, {
1389                         group = play_one_neighbor(board, coord, color, other_color, c, group, u);
1390         });
1391
1392         board_at(board, coord) = color;
1393         if (unlikely(!group))
1394                 group = new_group(board, coord, u);
1395
1396         if (!u) {
1397                 board->last_move4 = board->last_move3;
1398                 board->last_move3 = board->last_move2;
1399         }
1400         board->last_move2 = board->last_move;
1401         board->last_move = *m;
1402         board->moves++;
1403         if (!u) {
1404                 board_hash_update(board, coord, color);
1405                 board_symmetry_update(board, &board->symmetry, coord);
1406         }
1407         struct move ko = { pass, S_NONE };
1408         board->ko = ko;
1409
1410         if (!u) check_pat3_consistency(board, coord);
1411
1412         return group;
1413 }
1414
1415 /* We played in an eye-like shape. Either we capture at least one of the eye
1416  * sides in the process of playing, or return -1. */
1417 static int profiling_noinline
1418 board_play_in_eye(struct board *board, struct move *m, int f, struct board_undo *u)
1419 {
1420         coord_t coord = m->coord;
1421         enum stone color = m->color;
1422         /* Check ko: Capture at a position of ko capture one move ago */
1423         if (unlikely(color == board->ko.color && coord == board->ko.coord)) {
1424                 if (DEBUGL(5))
1425                         fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
1426                 return -1;
1427         } else if (DEBUGL(6)) {
1428                 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1429                         color, coord_x(coord, board), coord_y(coord, board),
1430                         board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
1431         }
1432
1433         struct move ko = { pass, S_NONE };
1434
1435         int captured_groups = 0;
1436
1437         foreach_neighbor(board, coord, {
1438                 group_t g = group_at(board, c);
1439                 if (DEBUGL(7))
1440                         fprintf(stderr, "board_check: group %d has %d libs\n",
1441                                 g, board_group_info(board, g).libs);
1442                 captured_groups += (board_group_info(board, g).libs == 1);
1443         });
1444
1445         if (likely(captured_groups == 0)) {
1446                 if (DEBUGL(5)) {
1447                         if (DEBUGL(6))
1448                                 board_print(board, stderr);
1449                         fprintf(stderr, "board_check: one-stone suicide\n");
1450                 }
1451
1452                 return -1;
1453         }
1454
1455         if (!u) {
1456 #ifdef BOARD_TRAITS
1457                 /* We _will_ for sure capture something. */
1458                 assert(trait_at(board, coord, color).cap > 0);
1459 #ifdef BOARD_TRAIT_SAFE
1460                 assert(trait_at(board, coord, color).safe == board_trait_safe(board, coord, color));
1461 #endif
1462 #endif
1463
1464                 board->f[f] = board->f[--board->flen];
1465                 if (DEBUGL(6))
1466                         fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1467         }
1468         else
1469                 undo_save_group_info(board, coord, color, u);
1470
1471         int ko_caps = 0;
1472         coord_t cap_at = pass;
1473         foreach_neighbor(board, coord, {
1474                 inc_neighbor_count_at(board, c, color);
1475                 /* Originally, this could not have changed any trait
1476                  * since no neighbors were S_NONE, however by now some
1477                  * of them might be removed from the board. */
1478                 if (!u) board_trait_queue(board, c);
1479
1480                 group_t group = group_at(board, c);
1481                 if (!group)
1482                         continue;
1483
1484                 board_group_rmlib(board, group, coord, u);
1485                 if (DEBUGL(7))
1486                         fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
1487                                 group_base(group));
1488
1489                 if (board_group_captured(board, group)) {
1490                         ko_caps += board_group_capture(board, group, u);
1491                         cap_at = c;
1492                 }
1493         });
1494         if (ko_caps == 1) {
1495                 ko.color = stone_other(color);
1496                 ko.coord = cap_at; // unique
1497                 board->last_ko = ko;
1498                 board->last_ko_age = board->moves;
1499                 if (DEBUGL(5))
1500                         fprintf(stderr, "guarding ko at %d,%s\n", ko.color, coord2sstr(ko.coord, board));
1501         }
1502
1503         board_at(board, coord) = color;
1504         group_t group = new_group(board, coord, u);
1505
1506         if (!u) {
1507                 board->last_move4 = board->last_move3;
1508                 board->last_move3 = board->last_move2;
1509         }
1510         board->last_move2 = board->last_move;
1511         board->last_move = *m;
1512         board->moves++;
1513         if (!u) {
1514                 board_hash_update(board, coord, color);
1515                 board_hash_commit(board);
1516                 board_traits_recompute(board);
1517                 board_symmetry_update(board, &board->symmetry, coord);
1518         }
1519         board->ko = ko;
1520
1521         if (!u) check_pat3_consistency(board, coord);
1522
1523         return !!group;
1524 }
1525
1526 static int __attribute__((flatten))
1527 board_play_f(struct board *board, struct move *m, int f, struct board_undo *u)
1528 {
1529         if (DEBUGL(7)) {
1530                 fprintf(stderr, "board_play(%s): ---- Playing %d,%d\n", coord2sstr(m->coord, board), coord_x(m->coord, board), coord_y(m->coord, board));
1531         }
1532         if (likely(!board_is_eyelike(board, m->coord, stone_other(m->color)))) {
1533                 /* NOT playing in an eye. Thus this move has to succeed. (This
1534                  * is thanks to New Zealand rules. Otherwise, multi-stone
1535                  * suicide might fail.) */
1536                 group_t group = board_play_outside(board, m, f, u);
1537                 if (unlikely(board_group_captured(board, group))) {
1538                         if (u) undo_save_suicide(board, m->coord, m->color, u);
1539                         board_group_capture(board, group, u);
1540                 }
1541                 if (!u) {
1542                         board_hash_commit(board);
1543                         board_traits_recompute(board);
1544                 }
1545                 return 0;
1546         } else {
1547                 return board_play_in_eye(board, m, f, u);
1548         }
1549 }
1550
1551 static void
1552 undo_init(struct board *b, struct move *m, struct board_undo *u)
1553 {
1554         // Paranoid uninitialized mem test
1555         // memset(u, 0xff, sizeof(*u));
1556
1557         u->last_move2 = b->last_move2;
1558         u->ko = b->ko;
1559         u->last_ko = b->last_ko;
1560         u->last_ko_age = b->last_ko_age;
1561         u->captures = 0;
1562
1563         u->nmerged = u->nmerged_tmp = u->nenemies = 0;
1564         for (int i = 0; i < 4; i++)
1565                 u->merged[i].group = u->enemies[i].group = 0;
1566 }
1567
1568 static int
1569 board_play_(struct board *board, struct move *m, struct board_undo *u)
1570 {
1571 #ifdef BOARD_UNDO_CHECKS
1572         assert(u || !board->quicked);
1573 #endif
1574
1575         if (u) undo_init(board, m, u);
1576
1577         if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
1578                 if (is_pass(m->coord) && board->rules == RULES_SIMING) {
1579                         /* On pass, the player gives a pass stone
1580                          * to the opponent. */
1581                         board->captures[stone_other(m->color)]++;
1582                 }
1583                 struct move nomove = { pass, S_NONE };
1584                 board->ko = nomove;
1585                 if (!u) {
1586                         board->last_move4 = board->last_move3;
1587                         board->last_move3 = board->last_move2;
1588                 }
1589                 board->last_move2 = board->last_move;
1590                 board->last_move = *m;
1591                 return 0;
1592         }
1593
1594         if (u)
1595                 return board_play_f(board, m, -1, u);
1596
1597         int f;
1598         for (f = 0; f < board->flen; f++)
1599                 if (board->f[f] == m->coord)
1600                         return board_play_f(board, m, f, u);
1601
1602         if (DEBUGL(7))
1603                 fprintf(stderr, "board_check: stone exists\n");
1604         return -1;
1605 }
1606
1607 int
1608 board_play(struct board *board, struct move *m)
1609 {
1610         return board_play_(board, m, NULL);
1611 }
1612
1613 int
1614 board_quick_play(struct board *board, struct move *m, struct board_undo *u)
1615 {
1616         int r = board_play_(board, m, u);
1617 #ifdef BOARD_UNDO_CHECKS
1618         if (r >= 0)
1619                 board->quicked++;
1620 #endif
1621         return r;
1622 }
1623
1624 static inline void
1625 undo_merge(struct board *b, struct board_undo *u, struct move *m)
1626 {
1627         coord_t coord = m->coord;
1628         group_t group = group_at(b, coord);
1629         struct undo_merge *merged = u->merged;
1630
1631         // Others groups, in reverse order ...
1632         for (int i = u->nmerged - 1; i > 0; i--) {
1633                 group_t old_group = merged[i].group;
1634
1635                 board_group_info(b, old_group) = merged[i].info;
1636
1637                 groupnext_at(b, group_base(group)) = groupnext_at(b, merged[i].last);
1638                 groupnext_at(b, merged[i].last) = 0;
1639
1640 #if 0
1641                 printf("merged_group[%i]:   (last: %s)", i, coord2sstr(merged[i].last, b));
1642                 foreach_in_group(b, old_group) {
1643                         printf("%s ", coord2sstr(c, b));
1644                 } foreach_in_group_end;
1645                 printf("\n");
1646 #endif
1647
1648                 foreach_in_group(b, old_group) {
1649                         group_at(b, c) = old_group;
1650                 } foreach_in_group_end;
1651         }
1652
1653         // Restore first group
1654         groupnext_at(b, u->inserted) = groupnext_at(b, coord);
1655         board_group_info(b, merged[0].group) = merged[0].info;
1656
1657 #if 0
1658         printf("merged_group[0]: ");
1659         foreach_in_group(b, merged[0].group) {
1660                 printf("%s ", coord2sstr(c, b));
1661         } foreach_in_group_end;
1662         printf("\n");
1663 #endif
1664 }
1665
1666
1667 static inline void
1668 restore_enemies(struct board *b, struct board_undo *u, struct move *m)
1669 {
1670         enum stone color = m->color;
1671         enum stone other_color = stone_other(m->color);
1672
1673         struct undo_enemy *enemy = u->enemies;
1674         for (int i = 0; i < u->nenemies; i++) {
1675                 group_t old_group = enemy[i].group;
1676
1677                 board_group_info(b, old_group) = enemy[i].info;
1678
1679                 coord_t *stones = enemy[i].stones;
1680                 for (int j = 0; stones[j]; j++) {
1681                         board_at(b, stones[j]) = other_color;
1682                         group_at(b, stones[j]) = old_group;
1683                         groupnext_at(b, stones[j]) = stones[j + 1];
1684
1685                         foreach_neighbor(b, stones[j], {
1686                                 inc_neighbor_count_at(b, c, other_color);
1687                         });
1688
1689                         // Update liberties of neighboring groups
1690                         foreach_neighbor(b, stones[j], {
1691                                         if (board_at(b, c) != color)
1692                                                 continue;
1693                                         group_t g = group_at(b, c);
1694                                         if (g == u->merged[0].group || g == u->merged[1].group || g == u->merged[2].group || g == u->merged[3].group)
1695                                                 continue;
1696                                         board_group_rmlib(b, g, stones[j], u);
1697                                 });
1698                 }
1699         }
1700 }
1701
1702 static void
1703 board_undo_stone(struct board *b, struct board_undo *u, struct move *m)
1704 {
1705         coord_t coord = m->coord;
1706         enum stone color = m->color;
1707         /* - update groups
1708          * - put captures back
1709          */
1710
1711         //printf("nmerged: %i\n", u->nmerged);
1712
1713         // Restore merged groups
1714         if (u->nmerged)
1715                 undo_merge(b, u, m);
1716         else                    // Single stone group undo
1717                 memset(&board_group_info(b, group_at(b, coord)), 0, sizeof(struct group));
1718
1719         board_at(b, coord) = S_NONE;
1720         group_at(b, coord) = 0;
1721         groupnext_at(b, coord) = u->next_at;
1722
1723         foreach_neighbor(b, coord, {
1724                         dec_neighbor_count_at(b, c, color);
1725         });
1726
1727         // Restore enemy groups
1728         if (u->nenemies) {
1729                 b->captures[color] -= u->captures;
1730                 restore_enemies(b, u, m);
1731         }
1732 }
1733
1734 static inline void
1735 restore_suicide(struct board *b, struct board_undo *u, struct move *m)
1736 {
1737         enum stone color = m->color;
1738         enum stone other_color = stone_other(m->color);
1739
1740         struct undo_enemy *enemy = u->enemies;
1741         for (int i = 0; i < u->nenemies; i++) {
1742                 group_t old_group = enemy[i].group;
1743
1744                 board_group_info(b, old_group) = enemy[i].info;
1745
1746                 coord_t *stones = enemy[i].stones;
1747                 for (int j = 0; stones[j]; j++) {
1748                         board_at(b, stones[j]) = other_color;
1749                         group_at(b, stones[j]) = old_group;
1750                         groupnext_at(b, stones[j]) = stones[j + 1];
1751
1752                         foreach_neighbor(b, stones[j], {
1753                                 inc_neighbor_count_at(b, c, other_color);
1754                         });
1755
1756                         // Update liberties of neighboring groups
1757                         foreach_neighbor(b, stones[j], {
1758                                         if (board_at(b, c) != color)
1759                                                 continue;
1760                                         group_t g = group_at(b, c);
1761                                         if (g == u->enemies[0].group || g == u->enemies[1].group ||
1762                                             g == u->enemies[2].group || g == u->enemies[3].group)
1763                                                 continue;
1764                                         board_group_rmlib(b, g, stones[j], u);
1765                                 });
1766                 }
1767         }
1768 }
1769
1770
1771 static void
1772 board_undo_suicide(struct board *b, struct board_undo *u, struct move *m)
1773 {
1774         coord_t coord = m->coord;
1775         enum stone other_color = stone_other(m->color);
1776
1777         // Pretend it's capture ...
1778         struct move m2 = { .coord = m->coord, .color = other_color };
1779         b->captures[other_color] -= u->captures;
1780
1781         restore_suicide(b, u, &m2);
1782
1783         undo_merge(b, u, m);
1784
1785         board_at(b, coord) = S_NONE;
1786         group_at(b, coord) = 0;
1787         groupnext_at(b, coord) = u->next_at;
1788
1789         foreach_neighbor(b, coord, {
1790                 dec_neighbor_count_at(b, c, m->color);
1791         });
1792
1793 }
1794
1795
1796 void
1797 board_quick_undo(struct board *b, struct move *m, struct board_undo *u)
1798 {
1799 #ifdef BOARD_UNDO_CHECKS
1800         b->quicked--;
1801 #endif
1802
1803         b->last_move = b->last_move2;
1804         b->last_move2 = u->last_move2;
1805         b->ko = u->ko;
1806         b->last_ko = u->last_ko;
1807         b->last_ko_age = u->last_ko_age;
1808
1809         if (unlikely(is_pass(m->coord) || is_resign(m->coord)))
1810                 return;
1811
1812         b->moves--;
1813
1814         if (likely(board_at(b, m->coord) == m->color))
1815                 board_undo_stone(b, u, m);
1816         else if (board_at(b, m->coord) == S_NONE)
1817                 board_undo_suicide(b, u, m);
1818         else
1819                 assert(0);      /* Anything else doesn't make sense */
1820 }
1821
1822
1823 /* Undo, supported only for pass moves. This form of undo is required by KGS
1824  * to settle disputes on dead groups. See also fast_board_undo() */
1825 int board_undo(struct board *board)
1826 {
1827         if (!is_pass(board->last_move.coord))
1828                 return -1;
1829         if (board->rules == RULES_SIMING) {
1830                 /* Return pass stone to the passing player. */
1831                 board->captures[stone_other(board->last_move.color)]--;
1832         }
1833         board->last_move = board->last_move2;
1834         board->last_move2 = board->last_move3;
1835         board->last_move3 = board->last_move4;
1836         if (board->last_ko_age == board->moves)
1837                 board->ko = board->last_ko;
1838         return 0;
1839 }
1840
1841 static inline bool
1842 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, ppr_permit permit, void *permit_data)
1843 {
1844         *coord = b->f[f];
1845         struct move m = { *coord, color };
1846         if (DEBUGL(6))
1847                 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));
1848         if (unlikely(board_is_one_point_eye(b, *coord, color)) /* bad idea to play into one, usually */
1849                 || !board_is_valid_move(b, &m)
1850                 || (permit && !permit(permit_data, b, &m)))
1851                 return false;
1852         if (m.coord == *coord) {
1853                 return likely(board_play_f(b, &m, f, NULL) >= 0);
1854         } else {
1855                 *coord = m.coord; // permit modified the coordinate
1856                 return likely(board_play(b, &m) >= 0);
1857         }
1858 }
1859
1860 void
1861 board_play_random(struct board *b, enum stone color, coord_t *coord, ppr_permit permit, void *permit_data)
1862 {
1863         if (unlikely(b->flen == 0))
1864                 goto pass;
1865
1866         int base = fast_random(b->flen), f;
1867         for (f = base; f < b->flen; f++)
1868                 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1869                         return;
1870         for (f = 0; f < base; f++)
1871                 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1872                         return;
1873
1874 pass:
1875         *coord = pass;
1876         struct move m = { pass, color };
1877         board_play(b, &m);
1878 }
1879
1880
1881 bool
1882 board_is_false_eyelike(struct board *board, coord_t coord, enum stone eye_color)
1883 {
1884         enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
1885
1886         /* XXX: We attempt false eye detection but we will yield false
1887          * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1888
1889         foreach_diag_neighbor(board, coord) {
1890                 color_diag_libs[(enum stone) board_at(board, c)]++;
1891         } foreach_diag_neighbor_end;
1892         /* For false eye, we need two enemy stones diagonally in the
1893          * middle of the board, or just one enemy stone at the edge
1894          * or in the corner. */
1895         color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
1896         return color_diag_libs[stone_other(eye_color)] >= 2;
1897 }
1898
1899 bool
1900 board_is_one_point_eye(struct board *board, coord_t coord, enum stone eye_color)
1901 {
1902         return board_is_eyelike(board, coord, eye_color)
1903                 && !board_is_false_eyelike(board, coord, eye_color);
1904 }
1905
1906 enum stone
1907 board_get_one_point_eye(struct board *board, coord_t coord)
1908 {
1909         if (board_is_one_point_eye(board, coord, S_WHITE))
1910                 return S_WHITE;
1911         else if (board_is_one_point_eye(board, coord, S_BLACK))
1912                 return S_BLACK;
1913         else
1914                 return S_NONE;
1915 }
1916
1917
1918 floating_t
1919 board_fast_score(struct board *board)
1920 {
1921         int scores[S_MAX];
1922         memset(scores, 0, sizeof(scores));
1923
1924         foreach_point(board) {
1925                 enum stone color = board_at(board, c);
1926                 if (color == S_NONE && board->rules != RULES_STONES_ONLY)
1927                         color = board_get_one_point_eye(board, c);
1928                 scores[color]++;
1929                 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1930         } foreach_point_end;
1931
1932         return board->komi + (board->rules != RULES_SIMING ? board->handicap : 0) + scores[S_WHITE] - scores[S_BLACK];
1933 }
1934
1935 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1936
1937 /* One flood-fill iteration; returns true if next iteration
1938  * is required. */
1939 static bool
1940 board_tromp_taylor_iter(struct board *board, int *ownermap)
1941 {
1942         bool needs_update = false;
1943         foreach_free_point(board) {
1944                 /* Ignore occupied and already-dame positions. */
1945                 assert(board_at(board, c) == S_NONE);
1946                 if (board->rules == RULES_STONES_ONLY)
1947                     ownermap[c] = 3;
1948                 if (ownermap[c] == 3)
1949                         continue;
1950                 /* Count neighbors. */
1951                 int nei[4] = {0};
1952                 foreach_neighbor(board, c, {
1953                         nei[ownermap[c]]++;
1954                 });
1955                 /* If we have neighbors of both colors, or dame,
1956                  * we are dame too. */
1957                 if ((nei[1] && nei[2]) || nei[3]) {
1958                         ownermap[c] = 3;
1959                         /* Speed up the propagation. */
1960                         foreach_neighbor(board, c, {
1961                                 if (board_at(board, c) == S_NONE)
1962                                         ownermap[c] = 3;
1963                         });
1964                         needs_update = true;
1965                         continue;
1966                 }
1967                 /* If we have neighbors of one color, we are owned
1968                  * by that color, too. */
1969                 if (!ownermap[c] && (nei[1] || nei[2])) {
1970                         int newowner = nei[1] ? 1 : 2;
1971                         ownermap[c] = newowner;
1972                         /* Speed up the propagation. */
1973                         foreach_neighbor(board, c, {
1974                                 if (board_at(board, c) == S_NONE && !ownermap[c])
1975                                         ownermap[c] = newowner;
1976                         });
1977                         needs_update = true;
1978                         continue;
1979                 }
1980         } foreach_free_point_end;
1981         return needs_update;
1982 }
1983
1984 /* Tromp-Taylor Counting */
1985 floating_t
1986 board_official_score(struct board *board, struct move_queue *q)
1987 {
1988
1989         /* A point P, not colored C, is said to reach C, if there is a path of
1990          * (vertically or horizontally) adjacent points of P's color from P to
1991          * a point of color C.
1992          *
1993          * A player's score is the number of points of her color, plus the
1994          * number of empty points that reach only her color. */
1995
1996         int ownermap[board_size2(board)];
1997         int s[4] = {0};
1998         const int o[4] = {0, 1, 2, 0};
1999         foreach_point(board) {
2000                 ownermap[c] = o[board_at(board, c)];
2001                 s[board_at(board, c)]++;
2002         } foreach_point_end;
2003
2004         if (q) {
2005                 /* Process dead groups. */
2006                 for (unsigned int i = 0; i < q->moves; i++) {
2007                         foreach_in_group(board, q->move[i]) {
2008                                 enum stone color = board_at(board, c);
2009                                 ownermap[c] = o[stone_other(color)];
2010                                 s[color]--; s[stone_other(color)]++;
2011                         } foreach_in_group_end;
2012                 }
2013         }
2014
2015         /* We need to special-case empty board. */
2016         if (!s[S_BLACK] && !s[S_WHITE])
2017                 return board->komi;
2018
2019         while (board_tromp_taylor_iter(board, ownermap))
2020                 /* Flood-fill... */;
2021
2022         int scores[S_MAX];
2023         memset(scores, 0, sizeof(scores));
2024
2025         foreach_point(board) {
2026                 assert(board_at(board, c) == S_OFFBOARD || ownermap[c] != 0);
2027                 if (ownermap[c] == 3)
2028                         continue;
2029                 scores[ownermap[c]]++;
2030         } foreach_point_end;
2031
2032         return board->komi + (board->rules != RULES_SIMING ? board->handicap : 0) + scores[S_WHITE] - scores[S_BLACK];
2033 }
2034
2035 bool
2036 board_set_rules(struct board *board, char *name)
2037 {
2038         if (!strcasecmp(name, "japanese")) {
2039                 board->rules = RULES_JAPANESE;
2040         } else if (!strcasecmp(name, "chinese")) {
2041                 board->rules = RULES_CHINESE;
2042         } else if (!strcasecmp(name, "aga")) {
2043                 board->rules = RULES_AGA;
2044         } else if (!strcasecmp(name, "new_zealand")) {
2045                 board->rules = RULES_NEW_ZEALAND;
2046         } else if (!strcasecmp(name, "siming") || !strcasecmp(name, "simplified_ing")) {
2047                 board->rules = RULES_SIMING;
2048         } else {
2049                 return false;
2050         }
2051         return true;
2052 }