board.c

   1 #include <alloca.h>
   2 #include <assert.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #include "board.h"
   8 #include "debug.h"
   9 #include "random.h"
  10
  11 int board_group_capture(struct board *board, group_t group);
  12
  13 bool random_pass = false;
  14
  15
  16 #if 0
  17 #define profiling_noinline __attribute__((noinline))
  18 #else
  19 #define profiling_noinline
  20 #endif
  21
  22 #define gi_granularity 4
  23 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
  24
  25
  26 static void
  27 board_setup(struct board *b)
  28 {
  29         memset(b, 0, sizeof(*b));
  30
  31         struct move m = { pass, S_NONE };
  32         b->last_move = b->ko = m;
  33 }
  34
  35 struct board *
  36 board_init(void)
  37 {
  38         struct board *b = malloc(sizeof(struct board));
  39         board_setup(b);
  40         return b;
  41 }
  42
  43 struct board *
  44 board_copy(struct board *b2, struct board *b1)
  45 {
  46         memcpy(b2, b1, sizeof(struct board));
  47
  48         int bsize = board_size2(b2) * sizeof(*b2->b);
  49         int gsize = board_size2(b2) * sizeof(*b2->g);
  50         int fsize = board_size2(b2) * sizeof(*b2->f);
  51         int nsize = board_size2(b2) * sizeof(*b2->n);
  52         int psize = board_size2(b2) * sizeof(*b2->p);
  53         int hsize = board_size2(b2) * 2 * sizeof(*b2->h);
  54         int gisize = board_size2(b2) * sizeof(*b2->gi);
  55 #ifdef WANT_BOARD_C
  56         int csize = board_size2(b2) * sizeof(*b2->c);
  57 #else
  58         int csize = 0;
  59 #endif
  60         void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
  61         memcpy(x, b1->b, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
  62         b2->b = x; x += bsize;
  63         b2->g = x; x += gsize;
  64         b2->f = x; x += fsize;
  65         b2->p = x; x += psize;
  66         b2->n = x; x += nsize;
  67         b2->h = x; x += hsize;
  68         b2->gi = x; x += gisize;
  69 #ifdef WANT_BOARD_C
  70         b2->c = x; x += csize;
  71 #endif
  72
  73         return b2;
  74 }
  75
  76 void
  77 board_done_noalloc(struct board *board)
  78 {
  79         if (board->b) free(board->b);
  80 }
  81
  82 void
  83 board_done(struct board *board)
  84 {
  85         board_done_noalloc(board);
  86         free(board);
  87 }
  88
  89 void
  90 board_resize(struct board *board, int size)
  91 {
  92 #ifdef BOARD_SIZE
  93         assert(board_size(board) == size + 2);
  94 #else
  95         board_size(board) = size + 2 /* S_OFFBOARD margin */;
  96         board_size2(board) = board_size(board) * board_size(board);
  97 #endif
  98         if (board->b)
  99                 free(board->b);
 100
 101         int bsize = board_size2(board) * sizeof(*board->b);
 102         int gsize = board_size2(board) * sizeof(*board->g);
 103         int fsize = board_size2(board) * sizeof(*board->f);
 104         int nsize = board_size2(board) * sizeof(*board->n);
 105         int psize = board_size2(board) * sizeof(*board->p);
 106         int hsize = board_size2(board) * 2 * sizeof(*board->h);
 107         int gisize = board_size2(board) * sizeof(*board->gi);
 108 #ifdef WANT_BOARD_C
 109         int csize = board_size2(board) * sizeof(*board->c);
 110 #else
 111         int csize = 0;
 112 #endif
 113         void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
 114         memset(x, 0, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
 115         board->b = x; x += bsize;
 116         board->g = x; x += gsize;
 117         board->f = x; x += fsize;
 118         board->p = x; x += psize;
 119         board->n = x; x += nsize;
 120         board->h = x; x += hsize;
 121         board->gi = x; x += gisize;
 122 #ifdef WANT_BOARD_C
 123         board->c = x; x += csize;
 124 #endif
 125 }
 126
 127 void
 128 board_clear(struct board *board)
 129 {
 130         int size = board_size(board);
 131
 132         board_done_noalloc(board);
 133         board_setup(board);
 134         board_resize(board, size - 2 /* S_OFFBOARD margin */);
 135
 136         /* Setup initial symmetry */
 137         board->symmetry.d = 1;
 138         board->symmetry.x1 = board->symmetry.y1 = board->size / 2;
 139         board->symmetry.x2 = board->symmetry.y2 = board->size - 1;
 140         board->symmetry.type = SYM_FULL;
 141
 142         /* Draw the offboard margin */
 143         int top_row = board_size2(board) - board_size(board);
 144         int i;
 145         for (i = 0; i < board_size(board); i++)
 146                 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
 147         for (i = 0; i <= top_row; i += board_size(board))
 148                 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
 149
 150         foreach_point(board) {
 151                 coord_t coord = c;
 152                 if (board_at(board, coord) == S_OFFBOARD)
 153                         continue;
 154                 foreach_neighbor(board, c, {
 155                         inc_neighbor_count_at(board, coord, board_at(board, c));
 156                 } );
 157         } foreach_point_end;
 158
 159         /* First, pass is always a free position. */
 160         board->f[board->flen++] = coord_raw(pass);
 161         /* All positions are free! Except the margin. */
 162         for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
 163                 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
 164                         board->f[board->flen++] = i;
 165
 166         /* Initialize zobrist hashtable. */
 167         foreach_point(board) {
 168                 int max = (sizeof(hash_t) << history_hash_bits);
 169                 /* fast_random() is 16-bit only */
 170                 board->h[coord_raw(c) * 2] = ((hash_t) fast_random(max))
 171                                 | ((hash_t) fast_random(max) << 16)
 172                                 | ((hash_t) fast_random(max) << 32)
 173                                 | ((hash_t) fast_random(max) << 48);
 174                 if (!board->h[coord_raw(c) * 2])
 175                         /* Would be kinda "oops". */
 176                         board->h[coord_raw(c) * 2] = 1;
 177                 /* And once again for white */
 178                 board->h[coord_raw(c) * 2 + 1] = ((hash_t) fast_random(max))
 179                                 | ((hash_t) fast_random(max) << 16)
 180                                 | ((hash_t) fast_random(max) << 32)
 181                                 | ((hash_t) fast_random(max) << 48);
 182                 if (!board->h[coord_raw(c) * 2 + 1])
 183                         board->h[coord_raw(c) * 2 + 1] = 1;
 184         } foreach_point_end;
 185 }
 186
 187
 188 void
 189 board_print(struct board *board, FILE *f)
 190 {
 191         fprintf(f, "Move: % 3d  Komi: %2.1f  Captures B: %d W: %d\n     ",
 192                 board->moves, board->komi,
 193                 board->captures[S_BLACK], board->captures[S_WHITE]);
 194         int x, y;
 195         char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
 196         for (x = 1; x < board_size(board) - 1; x++)
 197                 fprintf(f, "%c ", asdf[x - 1]);
 198         fprintf(f, "\n   +-");
 199         for (x = 1; x < board_size(board) - 1; x++)
 200                 fprintf(f, "--");
 201         fprintf(f, "+\n");
 202         for (y = board_size(board) - 2; y >= 1; y--) {
 203                 fprintf(f, "%2d | ", y);
 204                 for (x = 1; x < board_size(board) - 1; x++) {
 205                         if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
 206                                 fprintf(f, "%c)", stone2char(board_atxy(board, x, y)));
 207                         else
 208                                 fprintf(f, "%c ", stone2char(board_atxy(board, x, y)));
 209                 }
 210                 if (DEBUGL(6)) {
 211                         fprintf(f, "| ");
 212                         for (x = 1; x < board_size(board) - 1; x++) {
 213                                 fprintf(f, "%d ", group_base(group_atxy(board, x, y)));
 214                         }
 215                 }
 216                 fprintf(f, "|\n");
 217         }
 218         fprintf(f, "   +-");
 219         for (x = 1; x < board_size(board) - 1; x++)
 220                 fprintf(f, "--");
 221         fprintf(f, "+\n\n");
 222 }
 223
 224
 225 /* Update board hash with given coordinate. */
 226 static void profiling_noinline
 227 board_hash_update(struct board *board, coord_t coord, enum stone color)
 228 {
 229         board->hash ^= hash_at(board, coord, color);
 230         if (DEBUGL(8))
 231                 fprintf(stderr, "board_hash_update(%d,%d,%d) ^ %llx -> %llx\n", color, coord_x(coord, board), coord_y(coord, board), hash_at(board, coord, color), board->hash);
 232 }
 233
 234 /* Commit current board hash to history. */
 235 static void profiling_noinline
 236 board_hash_commit(struct board *board)
 237 {
 238         if (DEBUGL(8))
 239                 fprintf(stderr, "board_hash_commit %llx\n", board->hash);
 240         if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
 241                 board->history_hash[board->hash & history_hash_mask] = board->hash;
 242         } else {
 243                 hash_t i = board->hash;
 244                 while (board->history_hash[i & history_hash_mask]) {
 245                         if (board->history_hash[i & history_hash_mask] == board->hash) {
 246                                 if (DEBUGL(5))
 247                                         fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
 248                                                 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
 249                                 board->superko_violation = true;
 250                                 return;
 251                         }
 252                         i = history_hash_next(i);
 253                 }
 254                 board->history_hash[i & history_hash_mask] = board->hash;
 255         }
 256 }
 257
 258
 259 void
 260 board_symmetry_update(struct board *b, struct board_symmetry *symmetry, coord_t c)
 261 {
 262         if (likely(symmetry->type == SYM_NONE)) {
 263                 /* Fully degenerated already. We do not support detection
 264                  * of restoring of symmetry, assuming that this is too rare
 265                  * a case to handle. */
 266                 return;
 267         }
 268
 269         int x = coord_x(c, b), y = coord_y(c, b), t = board_size(b) / 2;
 270         int dx = board_size(b) - 1 - x; /* for SYM_DOWN */
 271         if (DEBUGL(6)) {
 272                 fprintf(stderr, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
 273                         symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
 274                         symmetry->d, symmetry->type, x, y);
 275         }
 276
 277         switch (symmetry->type) {
 278                 case SYM_FULL:
 279                         if (x == t && y == t) {
 280                                 /* Tengen keeps full symmetry. */
 281                                 return;
 282                         }
 283                         /* New symmetry now? */
 284                         if (x == y) {
 285                                 symmetry->type = SYM_DIAG_UP;
 286                                 symmetry->x1 = symmetry->y1 = 1;
 287                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 288                                 symmetry->d = 1;
 289                         } else if (dx == y) {
 290                                 symmetry->type = SYM_DIAG_DOWN;
 291                                 symmetry->x1 = symmetry->y1 = 1;
 292                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 293                                 symmetry->d = 1;
 294                         } else if (x == t) {
 295                                 symmetry->type = SYM_HORIZ;
 296                                 symmetry->y1 = 1;
 297                                 symmetry->y2 = board_size(b) - 1;
 298                                 symmetry->d = 0;
 299                         } else if (y == t) {
 300                                 symmetry->type = SYM_VERT;
 301                                 symmetry->x1 = 1;
 302                                 symmetry->x2 = board_size(b) - 1;
 303                                 symmetry->d = 0;
 304                         } else {
 305 break_symmetry:
 306                                 symmetry->type = SYM_NONE;
 307                                 symmetry->x1 = symmetry->y1 = 1;
 308                                 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
 309                                 symmetry->d = 0;
 310                         }
 311                         break;
 312                 case SYM_DIAG_UP:
 313                         if (x == y)
 314                                 return;
 315                         goto break_symmetry;
 316                 case SYM_DIAG_DOWN:
 317                         if (dx == y)
 318                                 return;
 319                         goto break_symmetry;
 320                 case SYM_HORIZ:
 321                         if (x == t)
 322                                 return;
 323                         goto break_symmetry;
 324                 case SYM_VERT:
 325                         if (y == t)
 326                                 return;
 327                         goto break_symmetry;
 328                 case SYM_NONE:
 329                         assert(0);
 330                         break;
 331         }
 332
 333         if (DEBUGL(6)) {
 334                 fprintf(stderr, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
 335                         symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
 336                         symmetry->d, symmetry->type);
 337         }
 338         /* Whew. */
 339 }
 340
 341
 342 void
 343 board_handicap_stone(struct board *board, int x, int y, FILE *f)
 344 {
 345         struct move m;
 346         m.color = S_BLACK;
 347         coord_xy(m.coord, x, y, board);
 348
 349         board_play(board, &m);
 350         /* Simulate white passing; otherwise, UCT search can get confused since
 351          * tree depth parity won't match the color to move. */
 352         board->moves++;
 353
 354         char *str = coord2str(m.coord, board);
 355         if (DEBUGL(1))
 356                 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
 357         fprintf(f, "%s ", str);
 358         free(str);
 359 }
 360
 361 void
 362 board_handicap(struct board *board, int stones, FILE *f)
 363 {
 364         int margin = 3 + (board_size(board) >= 13);
 365         int min = margin;
 366         int mid = board_size(board) / 2;
 367         int max = board_size(board) - 1 - margin;
 368         const int places[][2] = {
 369                 { min, min }, { max, max }, { max, min }, { min, max },
 370                 { min, mid }, { max, mid },
 371                 { mid, min }, { mid, max },
 372                 { mid, mid },
 373         };
 374
 375         board->handicap = stones;
 376
 377         if (stones == 5 || stones == 7) {
 378                 board_handicap_stone(board, mid, mid, f);
 379                 stones--;
 380         }
 381
 382         int i;
 383         for (i = 0; i < stones; i++)
 384                 board_handicap_stone(board, places[i][0], places[i][1], f);
 385 }
 386
 387
 388 static void __attribute__((noinline))
 389 check_libs_consistency(struct board *board, group_t g)
 390 {
 391 #ifdef DEBUG
 392         if (!g) return;
 393         struct group *gi = &board_group_info(board, g);
 394         for (int i = 0; i < GROUP_KEEP_LIBS; i++)
 395                 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
 396                         fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
 397                         assert(0);
 398                 }
 399 #endif
 400 }
 401
 402 static void
 403 board_capturable_add(struct board *board, group_t group)
 404 {
 405 #ifdef WANT_BOARD_C
 406         //fprintf(stderr, "add of group %d (%d)\n", group_base(group), board->clen);
 407         assert(group);
 408         assert(board->clen < board_size2(board));
 409         board->c[board->clen++] = group;
 410 #endif
 411 }
 412 static void
 413 board_capturable_rm(struct board *board, group_t group)
 414 {
 415 #ifdef WANT_BOARD_C
 416         //fprintf(stderr, "rm of group %d\n", group_base(group));
 417         for (int i = 0; i < board->clen; i++) {
 418                 if (unlikely(board->c[i] == group)) {
 419                         board->c[i] = board->c[--board->clen];
 420                         return;
 421                 }
 422         }
 423         fprintf(stderr, "rm of bad group %d\n", group_base(group));
 424         assert(0);
 425 #endif
 426 }
 427
 428 static void
 429 board_group_addlib(struct board *board, group_t group, coord_t coord)
 430 {
 431         if (DEBUGL(7)) {
 432                 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
 433                         group_base(group), coord2sstr(group_base(group), board),
 434                         board_group_info(board, group).libs, coord2sstr(coord, board));
 435         }
 436
 437         check_libs_consistency(board, group);
 438
 439         struct group *gi = &board_group_info(board, group);
 440         if (gi->libs < GROUP_KEEP_LIBS) {
 441                 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
 442 #if 0
 443                         /* Seems extra branch just slows it down */
 444                         if (!gi->lib[i])
 445                                 break;
 446 #endif
 447                         if (unlikely(gi->lib[i] == coord))
 448                                 return;
 449                 }
 450                 if (gi->libs == 0)
 451                         board_capturable_add(board, group);
 452                 else if (gi->libs == 1)
 453                         board_capturable_rm(board, group);
 454                 gi->lib[gi->libs++] = coord;
 455         }
 456
 457         check_libs_consistency(board, group);
 458 }
 459
 460 static void
 461 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
 462 {
 463         /* Add extra liberty from the board to our liberty list. */
 464         enum stone watermark[board_size2(board)];
 465         memcpy(watermark, board->b, sizeof(watermark));
 466
 467         for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
 468                 watermark[coord_raw(gi->lib[i])] = S_OFFBOARD;
 469         watermark[coord_raw(avoid)] = S_OFFBOARD;
 470
 471         foreach_in_group(board, group) {
 472                 coord_t coord2 = c;
 473                 foreach_neighbor(board, coord2, {
 474                         if (likely(watermark[coord_raw(c)] != S_NONE))
 475                                 continue;
 476                         watermark[coord_raw(c)] = S_OFFBOARD;
 477                         gi->lib[gi->libs++] = c;
 478                         if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
 479                                 return;
 480                 } );
 481         } foreach_in_group_end;
 482 }
 483
 484 static void
 485 board_group_rmlib(struct board *board, group_t group, coord_t coord)
 486 {
 487         if (DEBUGL(7)) {
 488                 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
 489                         group_base(group), coord2sstr(group_base(group), board),
 490                         board_group_info(board, group).libs, coord2sstr(coord, board));
 491         }
 492
 493         struct group *gi = &board_group_info(board, group);
 494         for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
 495 #if 0
 496                 /* Seems extra branch just slows it down */
 497                 if (!gi->lib[i])
 498                         break;
 499 #endif
 500                 if (likely(gi->lib[i] != coord))
 501                         continue;
 502
 503                 gi->lib[i] = gi->lib[--gi->libs];
 504                 gi->lib[gi->libs] = 0;
 505
 506                 check_libs_consistency(board, group);
 507
 508                 /* Postpone refilling lib[] until we need to. */
 509                 assert(GROUP_REFILL_LIBS > 1);
 510                 if (gi->libs > GROUP_REFILL_LIBS)
 511                         return;
 512                 if (gi->libs == GROUP_REFILL_LIBS)
 513                         board_group_find_extra_libs(board, group, gi, coord);
 514
 515                 if (gi->libs == 1)
 516                         board_capturable_add(board, group);
 517                 else if (gi->libs == 0)
 518                         board_capturable_rm(board, group);
 519                 return;
 520         }
 521
 522         /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
 523          * can call this multiple times per coord. */
 524         check_libs_consistency(board, group);
 525         return;
 526 }
 527
 528
 529 /* This is a low-level routine that doesn't maintain consistency
 530  * of all the board data structures. Use board_group_capture() from
 531  * your code. */
 532 static void
 533 board_remove_stone(struct board *board, coord_t c)
 534 {
 535         enum stone color = board_at(board, c);
 536         board_at(board, c) = S_NONE;
 537         group_at(board, c) = 0;
 538         board_hash_update(board, c, color);
 539
 540         /* Increase liberties of surrounding groups */
 541         coord_t coord = c;
 542         foreach_neighbor(board, coord, {
 543                 dec_neighbor_count_at(board, c, color);
 544                 group_t g = group_at(board, c);
 545                 if (g)
 546                         board_group_addlib(board, g, coord);
 547         });
 548
 549         if (DEBUGL(6))
 550                 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
 551         board->f[board->flen++] = coord_raw(c);
 552 }
 553
 554
 555 static void profiling_noinline
 556 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
 557 {
 558         foreach_neighbor(board, coord, {
 559                 if (board_at(board, c) == S_NONE)
 560                         board_group_addlib(board, group, c);
 561         });
 562
 563         group_at(board, coord) = group;
 564         groupnext_at(board, coord) = groupnext_at(board, prevstone);
 565         groupnext_at(board, prevstone) = coord_raw(coord);
 566
 567         if (DEBUGL(8))
 568                 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
 569                         coord_x(prevstone, board), coord_y(prevstone, board),
 570                         coord_x(coord, board), coord_y(coord, board),
 571                         groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
 572                         group_base(group));
 573 }
 574
 575 static void profiling_noinline
 576 merge_groups(struct board *board, group_t group_to, group_t group_from)
 577 {
 578         if (DEBUGL(7))
 579                 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
 580                         group_base(group_from), group_base(group_to));
 581
 582         coord_t last_in_group;
 583         foreach_in_group(board, group_from) {
 584                 last_in_group = c;
 585                 group_at(board, c) = group_to;
 586         } foreach_in_group_end;
 587         groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
 588         groupnext_at(board, group_base(group_to)) = group_base(group_from);
 589
 590         struct group *gi_from = &board_group_info(board, group_from);
 591         struct group *gi_to = &board_group_info(board, group_to);
 592         if (gi_to->libs < GROUP_KEEP_LIBS) {
 593                 for (int i = 0; i < gi_from->libs; i++) {
 594                         for (int j = 0; j < gi_to->libs; j++)
 595                                 if (gi_to->lib[j] == gi_from->lib[i])
 596                                         goto next_from_lib;
 597                         if (gi_to->libs == 0)
 598                                 board_capturable_add(board, group_to);
 599                         else if (gi_to->libs == 1)
 600                                 board_capturable_rm(board, group_to);
 601                         gi_to->lib[gi_to->libs++] = gi_from->lib[i];
 602                         if (gi_to->libs >= GROUP_KEEP_LIBS)
 603                                 break;
 604 next_from_lib:;
 605                 }
 606         }
 607
 608         if (gi_from->libs == 1)
 609                 board_capturable_rm(board, group_from);
 610         memset(gi_from, 0, sizeof(struct group));
 611
 612         if (DEBUGL(7))
 613                 fprintf(stderr, "board_play_raw: merged group: %d\n",
 614                         group_base(group_to));
 615 }
 616
 617 static group_t profiling_noinline
 618 new_group(struct board *board, coord_t coord)
 619 {
 620         group_t group = coord_raw(coord);
 621         struct group *gi = &board_group_info(board, group);
 622         foreach_neighbor(board, coord, {
 623                 if (board_at(board, c) == S_NONE)
 624                         /* board_group_addlib is ridiculously expensive for us */
 625 #if GROUP_KEEP_LIBS < 4
 626                         if (gi->libs < GROUP_KEEP_LIBS)
 627 #endif
 628                         gi->lib[gi->libs++] = c;
 629         });
 630         if (gi->libs == 1)
 631                 board_capturable_add(board, group);
 632         check_libs_consistency(board, group);
 633
 634         group_at(board, coord) = group;
 635         groupnext_at(board, coord) = 0;
 636
 637         if (DEBUGL(8))
 638                 fprintf(stderr, "new_group: added %d,%d to group %d\n",
 639                         coord_x(coord, board), coord_y(coord, board),
 640                         group_base(group));
 641
 642         return group;
 643 }
 644
 645 static inline group_t
 646 play_one_neighbor(struct board *board,
 647                 coord_t coord, enum stone color, enum stone other_color,
 648                 coord_t c, group_t group)
 649 {
 650         enum stone ncolor = board_at(board, c);
 651         group_t ngroup = group_at(board, c);
 652
 653         inc_neighbor_count_at(board, c, color);
 654
 655         if (!ngroup)
 656                 return group;
 657
 658         board_group_rmlib(board, ngroup, coord);
 659         if (DEBUGL(7))
 660                 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
 661                         group_base(ngroup), ncolor, color, other_color);
 662
 663         if (ncolor == color && ngroup != group) {
 664                 if (!group) {
 665                         group = ngroup;
 666                         add_to_group(board, group, c, coord);
 667                 } else {
 668                         merge_groups(board, group, ngroup);
 669                 }
 670         } else if (ncolor == other_color) {
 671                 if (DEBUGL(8)) {
 672                         struct group *gi = &board_group_info(board, ngroup);
 673                         fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
 674                         for (int i = 0; i < GROUP_KEEP_LIBS; i++)
 675                                 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
 676                         fprintf(stderr, "\n");
 677                 }
 678                 if (unlikely(board_group_captured(board, ngroup)))
 679                         board_group_capture(board, ngroup);
 680         }
 681         return group;
 682 }
 683
 684 /* We played on a place with at least one liberty. We will become a member of
 685  * some group for sure. */
 686 static group_t profiling_noinline
 687 board_play_outside(struct board *board, struct move *m, int f)
 688 {
 689         coord_t coord = m->coord;
 690         enum stone color = m->color;
 691         enum stone other_color = stone_other(color);
 692         group_t group = 0;
 693
 694         board->f[f] = board->f[--board->flen];
 695         if (DEBUGL(6))
 696                 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
 697
 698         foreach_neighbor(board, coord, {
 699                         group = play_one_neighbor(board, coord, color, other_color, c, group);
 700         });
 701
 702         if (unlikely(!group))
 703                 group = new_group(board, coord);
 704
 705         board_at(board, coord) = color;
 706         board->last_move = *m;
 707         board->moves++;
 708         board_hash_update(board, coord, color);
 709         board_symmetry_update(board, &board->symmetry, coord);
 710         struct move ko = { pass, S_NONE };
 711         board->ko = ko;
 712
 713         return group;
 714 }
 715
 716 /* We played in an eye-like shape. Either we capture at least one of the eye
 717  * sides in the process of playing, or return -1. */
 718 static int profiling_noinline
 719 board_play_in_eye(struct board *board, struct move *m, int f)
 720 {
 721         coord_t coord = m->coord;
 722         enum stone color = m->color;
 723         /* Check ko: Capture at a position of ko capture one move ago */
 724         if (unlikely(color == board->ko.color && coord_eq(coord, board->ko.coord))) {
 725                 if (DEBUGL(5))
 726                         fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
 727                 return -1;
 728         } else if (DEBUGL(6)) {
 729                 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
 730                         color, coord_x(coord, board), coord_y(coord, board),
 731                         board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
 732         }
 733
 734         struct move ko = { pass, S_NONE };
 735
 736         int captured_groups = 0;
 737
 738         foreach_neighbor(board, coord, {
 739                 group_t g = group_at(board, c);
 740                 if (DEBUGL(7))
 741                         fprintf(stderr, "board_check: group %d has %d libs\n",
 742                                 g, board_group_info(board, g).libs);
 743                 captured_groups += (board_group_info(board, g).libs == 1);
 744         });
 745
 746         if (likely(captured_groups == 0)) {
 747                 if (DEBUGL(5)) {
 748                         if (DEBUGL(6))
 749                                 board_print(board, stderr);
 750                         fprintf(stderr, "board_check: one-stone suicide\n");
 751                 }
 752
 753                 return -1;
 754         }
 755
 756         board->f[f] = board->f[--board->flen];
 757         if (DEBUGL(6))
 758                 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
 759
 760         foreach_neighbor(board, coord, {
 761                 inc_neighbor_count_at(board, c, color);
 762
 763                 group_t group = group_at(board, c);
 764                 if (!group)
 765                         continue;
 766
 767                 board_group_rmlib(board, group, coord);
 768                 if (DEBUGL(7))
 769                         fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
 770                                 group_base(group));
 771
 772                 if (board_group_captured(board, group)) {
 773                         if (board_group_capture(board, group) == 1) {
 774                                 /* If we captured multiple groups at once,
 775                                  * we can't be fighting ko so we don't need
 776                                  * to check for that. */
 777                                 ko.color = stone_other(color);
 778                                 ko.coord = c;
 779                                 if (DEBUGL(5))
 780                                         fprintf(stderr, "guarding ko at %d,%d,%d\n", ko.color, coord_x(ko.coord, board), coord_y(ko.coord, board));
 781                         }
 782                 }
 783         });
 784
 785         board_at(board, coord) = color;
 786
 787         board->last_move = *m;
 788         board->moves++;
 789         board_hash_update(board, coord, color);
 790         board_hash_commit(board);
 791         board_symmetry_update(board, &board->symmetry, coord);
 792         board->ko = ko;
 793
 794         return !!new_group(board, coord);
 795 }
 796
 797 static int __attribute__((flatten))
 798 board_play_f(struct board *board, struct move *m, int f)
 799 {
 800         if (DEBUGL(7)) {
 801                 fprintf(stderr, "board_play(): ---- Playing %d,%d\n", coord_x(m->coord, board), coord_y(m->coord, board));
 802         }
 803         if (likely(!board_is_eyelike(board, &m->coord, stone_other(m->color)))) {
 804                 /* NOT playing in an eye. Thus this move has to succeed. (This
 805                  * is thanks to New Zealand rules. Otherwise, multi-stone
 806                  * suicide might fail.) */
 807                 group_t group = board_play_outside(board, m, f);
 808                 if (unlikely(board_group_captured(board, group))) {
 809                         board_group_capture(board, group);
 810                 }
 811                 board_hash_commit(board);
 812                 return 0;
 813         } else {
 814                 return board_play_in_eye(board, m, f);
 815         }
 816 }
 817
 818 int
 819 board_play(struct board *board, struct move *m)
 820 {
 821         if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
 822                 board->last_move = *m;
 823                 return 0;
 824         }
 825
 826         int f;
 827         for (f = 0; f < board->flen; f++)
 828                 if (board->f[f] == coord_raw(m->coord))
 829                         return board_play_f(board, m, f);
 830
 831         if (DEBUGL(7))
 832                 fprintf(stderr, "board_check: stone exists\n");
 833         return -1;
 834 }
 835
 836
 837 static inline bool
 838 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, ppr_permit permit, void *permit_data)
 839 {
 840         coord_raw(*coord) = b->f[f];
 841         if (unlikely(is_pass(*coord)))
 842                 return random_pass;
 843         struct move m = { *coord, color };
 844         if (DEBUGL(6))
 845                 fprintf(stderr, "trying random move %d: %d,%d\n", f, coord_x(*coord, b), coord_y(*coord, b));
 846         return (likely(!board_is_one_point_eye(b, coord, color)) /* bad idea to play into one, usually */
 847                 && (!permit || permit(permit_data, b, &m))
 848                 && likely(board_play_f(b, &m, f) >= 0));
 849 }
 850
 851 void
 852 board_play_random(struct board *b, enum stone color, coord_t *coord, ppr_permit permit, void *permit_data)
 853 {
 854         int base = fast_random(b->flen);
 855         coord_pos(*coord, base, b);
 856         if (likely(board_try_random_move(b, color, coord, base, permit, permit_data)))
 857                 return;
 858
 859         int f;
 860         for (f = base + 1; f < b->flen; f++)
 861                 if (board_try_random_move(b, color, coord, f, permit, permit_data))
 862                         return;
 863         for (f = 0; f < base; f++)
 864                 if (board_try_random_move(b, color, coord, f, permit, permit_data))
 865                         return;
 866
 867         *coord = pass;
 868 }
 869
 870
 871 bool
 872 board_is_eyelike(struct board *board, coord_t *coord, enum stone eye_color)
 873 {
 874         return (neighbor_count_at(board, *coord, eye_color)
 875                 + neighbor_count_at(board, *coord, S_OFFBOARD)) == 4;
 876 }
 877
 878 bool
 879 board_is_false_eyelike(struct board *board, coord_t *coord, enum stone eye_color)
 880 {
 881         enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
 882
 883         /* XXX: We attempt false eye detection but we will yield false
 884          * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
 885
 886         foreach_diag_neighbor(board, *coord) {
 887                 color_diag_libs[(enum stone) board_at(board, c)]++;
 888         } foreach_diag_neighbor_end;
 889         /* For false eye, we need two enemy stones diagonally in the
 890          * middle of the board, or just one enemy stone at the edge
 891          * or in the corner. */
 892         color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
 893         return color_diag_libs[stone_other(eye_color)] >= 2;
 894 }
 895
 896 bool
 897 board_is_one_point_eye(struct board *board, coord_t *coord, enum stone eye_color)
 898 {
 899         return board_is_eyelike(board, coord, eye_color)
 900                 && !board_is_false_eyelike(board, coord, eye_color);
 901 }
 902
 903 enum stone
 904 board_get_one_point_eye(struct board *board, coord_t *coord)
 905 {
 906         if (board_is_one_point_eye(board, coord, S_WHITE))
 907                 return S_WHITE;
 908         else if (board_is_one_point_eye(board, coord, S_BLACK))
 909                 return S_BLACK;
 910         else
 911                 return S_NONE;
 912 }
 913
 914
 915 int profiling_noinline
 916 board_group_capture(struct board *board, group_t group)
 917 {
 918         int stones = 0;
 919
 920         foreach_in_group(board, group) {
 921                 board->captures[stone_other(board_at(board, c))]++;
 922                 board_remove_stone(board, c);
 923                 stones++;
 924         } foreach_in_group_end;
 925
 926         if (board_group_info(board, group).libs == 1)
 927                 board_capturable_rm(board, group);
 928         memset(&board_group_info(board, group), 0, sizeof(struct group));
 929
 930         return stones;
 931 }
 932
 933 bool
 934 board_group_in_atari(struct board *board, group_t group, coord_t *lastlib)
 935 {
 936         if (board_group_info(board, group).libs != 1)
 937                 return false;
 938         *lastlib = board_group_info(board, group).lib[0];
 939         return true;
 940 }
 941
 942 bool
 943 board_group_can_atari(struct board *board, group_t group, coord_t lastlib[2])
 944 {
 945         if (board_group_info(board, group).libs != 2)
 946                 return false;
 947         lastlib[0] = board_group_info(board, group).lib[0];
 948         lastlib[1] = board_group_info(board, group).lib[1];
 949         return true;
 950 }
 951
 952
 953 static enum stone
 954 board_tromp_taylor_owner(struct board *board, coord_t c)
 955 {
 956         int x = coord_x(c, board), y = coord_y(c, board);
 957         enum stone color = S_NONE;
 958 #define TEST_REACH(xx, yy) \
 959         { \
 960                 enum stone c2 = board_atxy(board, xx, yy); \
 961                 if (c2 != S_NONE) { \
 962                         if (color != S_NONE && color != c2) \
 963                                 return S_NONE; \
 964                         color = c2; \
 965                         break; \
 966                 } \
 967         }
 968         for (int i = x; i > 0; i--)
 969                 TEST_REACH(i, y);
 970         for (int i = x; i < board_size(board) - 1; i++)
 971                 TEST_REACH(i, y);
 972         for (int i = y; i > 0; i--)
 973                 TEST_REACH(x, i);
 974         for (int i = y; i < board_size(board) - 1; i++)
 975                 TEST_REACH(x, i);
 976         return color;
 977 }
 978
 979 /* Tromp-Taylor Counting */
 980 float
 981 board_official_score(struct board *board)
 982 {
 983
 984         /* A point P, not colored C, is said to reach C, if there is a path of
 985          * (vertically or horizontally) adjacent points of P's color from P to
 986          * a point of color C.
 987          *
 988          * A player's score is the number of points of her color, plus the
 989          * number of empty points that reach only her color. */
 990
 991         int scores[S_MAX];
 992         memset(scores, 0, sizeof(scores));
 993
 994         foreach_point(board) {
 995                 enum stone color = board_at(board, c);
 996                 if (color == S_NONE)
 997                         color = board_tromp_taylor_owner(board, c);
 998                 scores[color]++;
 999         } foreach_point_end;
1000
1001         return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1002 }
1003
1004 float
1005 board_fast_score(struct board *board)
1006 {
1007         int scores[S_MAX];
1008         memset(scores, 0, sizeof(scores));
1009
1010         foreach_point(board) {
1011                 enum stone color = board_at(board, c);
1012                 if (color == S_NONE)
1013                         color = board_get_one_point_eye(board, &c);
1014                 scores[color]++;
1015                 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1016         } foreach_point_end;
1017
1018         return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1019 }
1020
1021
1022 bool
1023 is_selfatari(struct board *b, enum stone color, coord_t to)
1024 {
1025         //fprintf(stderr, "sar check %s %s\n", stone2str(color), coord2sstr(to, b));
1026         /* Assess if we actually gain any liberties by this escape route.
1027          * Note that this is not 100% as we cannot check whether we are
1028          * connecting out or just to ourselves. */
1029         int groupcts[S_MAX] = {};
1030         group_t groupids[S_MAX][4] = {};
1031         foreach_neighbor(b, to, {
1032                 enum stone s = board_at(b, c);
1033                 groupids[s][groupcts[s]++] = group_at(b, c);
1034         });
1035
1036         /* More than one immediate liberty, thumbs up! */
1037         if (groupcts[S_NONE] > 1)
1038                 return false;
1039
1040         /* Quickly weed out suicides. */
1041         if (groupcts[stone_other(color)] + groupcts[S_OFFBOARD] == 4 &&
1042             board_group_info(b, groupids[stone_other(color)][0]).libs > 1)
1043                 return true;
1044
1045         /* We may be looking for one extra liberty.
1046          * In that case, @needs_more_lib is id of group
1047          * already providing one, don't consider it again. */
1048         group_t needs_more_lib = 0;
1049         /* ID of the first liberty, providing it again is not
1050          * interesting. */
1051         coord_t needs_more_lib_except = 0;
1052
1053         /* Examine friendly groups: */
1054         for (int i = 0; i < 4; i++) {
1055                 /* We can escape by connecting to this group if it's
1056                  * not in atari. */
1057                 group_t g = groupids[color][i];
1058                 if (!g || board_group_info(b, g).libs == 1)
1059                         continue;
1060
1061                 /* Could we self-atari the group here? */
1062                 if (board_group_info(b, g).libs > 2)
1063                         return false;
1064
1065                 /* We need to have another liberty, and
1066                  * it must not be the other liberty of
1067                  * the group. */
1068                 int lib2 = board_group_info(b, g).lib[0];
1069                 if (lib2 == to) lib2 = board_group_info(b, g).lib[1];
1070                 /* Maybe we already looked at another
1071                  * group providing one liberty? */
1072                 if (needs_more_lib && needs_more_lib != g
1073                     && needs_more_lib_except != lib2)
1074                         return false;
1075
1076                 /* Can we get the liberty locally? */
1077                 /* Yes if we are route to more liberties... */
1078                 if (groupcts[S_NONE] > 1)
1079                         return false;
1080                 /* ...or one liberty, but not lib2. */
1081                 if (groupcts[S_NONE] > 0
1082                     && abs(lib2 - to) != 1
1083                     && abs(lib2 - to) != board_size(b))
1084                         return false;
1085
1086                 /* ...ok, then we can still contribute a liberty
1087                  * later by capturing something. */
1088                 needs_more_lib = g;
1089                 needs_more_lib_except = lib2;
1090         }
1091
1092         //fprintf(stderr, "no friendly group\n");
1093
1094         /* We may be able to gain a liberty by capturing this group. */
1095         group_t can_capture = 0;
1096
1097         /* Examine enemy groups: */
1098         for (int i = 0; i < 4; i++) {
1099                 /* We can escape by capturing this group if it's in atari. */
1100                 group_t g = groupids[stone_other(color)][i];
1101                 if (!g || board_group_info(b, g).libs > 1)
1102                         continue;
1103
1104                 /* But we need to get to at least two liberties by this;
1105                  * we already have one outside liberty, or the group is
1106                  * more than 1 stone (in that case, capturing is always
1107                  * nice!). */
1108                 if (groupcts[S_NONE] > 0 || !group_is_onestone(b, g))
1109                         return false;
1110                 /* ...or, it's a ko stone. */
1111                 if (neighbor_count_at(b, g, color) == 3)
1112                         return false;
1113                 /* ...or, we already have one indirect liberty provided
1114                  * by another group. */
1115                 if (needs_more_lib || (can_capture && can_capture != g))
1116                         return false;
1117                 can_capture = g;
1118
1119         }
1120
1121         //fprintf(stderr, "no cap group\n");
1122
1123         /* There is another possibility - we can self-atari if it is
1124          * a nakade: we put an enemy group in atari from the inside. */
1125         /* This branch also allows eyes falsification:
1126          * O O O . .  (This is different from throw-in to false eye
1127          * X X O O .  checked below in that there is no X stone at the
1128          * X . X O .  right of the star point in this diagram.)
1129          * X X X O O
1130          * X O * . . */
1131         /* TODO: Allow to only nakade if the created shape is dead
1132          * (http://senseis.xmp.net/?Nakade). */
1133
1134         /* The nakade is valid only if it's valid for all surrounding
1135          * enemy groups, thus we do the check only once - for the
1136          * first one. */
1137         group_t g = groupids[stone_other(color)][0];
1138         if (g && board_group_info(b, g).libs == 2) {
1139                 /* We must make sure the other liberty of that group:
1140                  * (i) is an internal liberty
1141                  * (ii) filling it to capture our group will not gain
1142                  * safety */
1143
1144                 /* Let's look at the other liberty neighbors: */
1145                 int lib2 = board_group_info(b, g).lib[0];
1146                 if (lib2 == to) lib2 = board_group_info(b, g).lib[1];
1147                 foreach_neighbor(b, lib2, {
1148                         /* This neighbor of course does not contribute
1149                          * anything to the enemy. */
1150                         if (board_at(b, c) == S_OFFBOARD)
1151                                 continue;
1152
1153                         /* If the other liberty has empty neighbor,
1154                          * it must be the original liberty; otherwise,
1155                          * since the whole group has only 2 liberties,
1156                          * the other liberty may not be internal and
1157                          * we are nakade'ing eyeless group from outside,
1158                          * which is stupid. */
1159                         if (board_at(b, c) == S_NONE) {
1160                                 if (c == to)
1161                                         continue;
1162                                 else
1163                                         goto invalid_nakade;
1164                         }
1165
1166                         int g2 = group_at(b, c);
1167                         /* If the neighbor is of our color, it must
1168                          * be our group; if it is a different group,
1169                          * we won't allow the self-atari. */
1170                         /* X X X X  We will not allow play on 'a',
1171                          * X X a X  because 'b' would capture two
1172                          * X O b X  different groups, forming two
1173                          * X X X X  eyes. */
1174                         if (board_at(b, c) == color) {
1175                                 /* Our group == one of the groups
1176                                  * we (@to) are connected to. */
1177                                 int j;
1178                                 for (j = 0; j < 4; j++)
1179                                         if (groupids[color][j] == g2)
1180                                                 break;
1181                                 if (j == 4)
1182                                         goto invalid_nakade;
1183                                 continue;
1184                         }
1185
1186                         /* The neighbor is enemy color. It's ok if
1187                          * it's still the same group or this is its
1188                          * only liberty. */
1189                         if (g == g2 || board_group_info(b, g2).libs == 1)
1190                                 continue;
1191                         /* Otherwise, it must have the exact same
1192                          * liberties as the original enemy group. */
1193                         if (board_group_info(b, g2).libs > 2
1194                             || board_group_info(b, g2).lib[0] == to
1195                             || board_group_info(b, g2).lib[1] == to)
1196                                 goto invalid_nakade;
1197                 });
1198
1199                 /* Now, we must distinguish between nakade and eye
1200                  * falsification; we must not falsify an eye by more
1201                  * than two stones. */
1202                 if (groupcts[color] < 1 ||
1203                     (groupcts[color] == 1 && group_is_onestone(b, groupids[color][0])))
1204                         return false;
1205
1206                 /* We would create more than 2-stone group; in that
1207                  * case, the liberty of our result must be lib2,
1208                  * indicating this really is a nakade. */
1209                 for (int j = 0; j < 4; j++) {
1210                         group_t g2 = groupids[color][j];
1211                         if (!g2) continue;
1212                         assert(board_group_info(b, g2).libs <= 2);
1213                         if (board_group_info(b, g2).libs == 2) {
1214                                 if (board_group_info(b, g2).lib[0] != lib2
1215                                     && board_group_info(b, g2).lib[1] != lib2)
1216                                         goto invalid_nakade;
1217                         } else {
1218                                 assert(board_group_info(b, g2).lib[0] == to);
1219                         }
1220                 }
1221
1222                 return false;
1223
1224 invalid_nakade:;
1225         }
1226
1227         //fprintf(stderr, "no nakade group\n");
1228
1229         /* We can be throwing-in to false eye:
1230          * X X X O X X X O X X X X X
1231          * X . * X * O . X * O O . X
1232          * # # # # # # # # # # # # # */
1233         /* We cannot sensibly throw-in into a corner. */
1234         if (neighbor_count_at(b, to, S_OFFBOARD) < 2
1235             && neighbor_count_at(b, to, stone_other(color))
1236                + neighbor_count_at(b, to, S_OFFBOARD) == 3
1237             && board_is_false_eyelike(b, &to, stone_other(color))) {
1238                 assert(groupcts[color] <= 1);
1239                 /* Single-stone throw-in is ok. */
1240                 if (groupcts[color] == 0)
1241                         return false;
1242
1243                 /* Bad throwin: we are connected to a group whose
1244                  * other liberty is a connection out
1245                  * X X O X X X O X
1246                  * X . X . O O . X
1247                  * # # # # # # # # */
1248                 group_t g = groupids[color][0];
1249                 assert(board_group_info(b, g).libs <= 2);
1250                 /* Suicide is not ok. */
1251                 if (board_group_info(b, g).libs == 1)
1252                         return true;
1253
1254                 int lib2 = board_group_info(b, g).lib[0];
1255                 if (lib2 == to) lib2 = board_group_info(b, g).lib[1];
1256                 /* This is actually slightly more general than above,
1257                  * and not perfect (the other group can be in atari),
1258                  * but should be ok. */
1259                 if (neighbor_count_at(b, to, color) + neighbor_count_at(b, to, S_NONE) > 1)
1260                         return false;
1261         }
1262
1263         //fprintf(stderr, "no throw-in group\n");
1264
1265         /* No way to pull out, no way to connect out. This really
1266          * is a bad self-atari! */
1267         return true;
1268 }
1269
1270
1271 bool
1272 board_stone_radar(struct board *b, coord_t coord, int distance)
1273 {
1274         int bounds[4] = {
1275                 coord_x(coord, b) - distance,
1276                 coord_y(coord, b) - distance,
1277                 coord_x(coord, b) + distance,
1278                 coord_y(coord, b) + distance
1279         };
1280         for (int i = 0; i < 4; i++)
1281                 if (bounds[i] < 1)
1282                         bounds[i] = 1;
1283                 else if (bounds[i] > board_size(b) - 2)
1284                         bounds[i] = board_size(b) - 2;
1285         for (int x = bounds[0]; x <= bounds[2]; x++)
1286                 for (int y = bounds[1]; y <= bounds[3]; y++)
1287                         if (board_atxy(b, x, y) != S_NONE) {
1288                                 //fprintf(stderr, "radar %d,%d,%d: %d,%d (%d)\n", coord_x(coord, b), coord_y(coord, b), distance, x, y, board_atxy(b, x, y));
1289                                 return true;
1290                         }
1291         return false;
1292 }