board_undo.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
  11 #if 0
  12 #define profiling_noinline __attribute__((noinline))
  13 #else
  14 #define profiling_noinline
  15 #endif
  16
  17 #define gi_granularity 4
  18 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
  19
  20
  21 int
  22 board_quick_cmp(struct board *b1, struct board *b2)
  23 {
  24         if (b1->size != b2->size ||
  25             b1->size2 != b2->size2 ||
  26             b1->bits2 != b2->bits2 ||
  27             b1->captures[S_BLACK] != b2->captures[S_BLACK] ||
  28             b1->captures[S_WHITE] != b2->captures[S_WHITE] ||
  29             b1->moves != b2->moves) {
  30                 fprintf(stderr, "differs in main vars\n");
  31                 return 1;
  32         }
  33         if (move_cmp(&b1->last_move, &b2->last_move) ||
  34             move_cmp(&b1->last_move2, &b2->last_move2)) {
  35                 fprintf(stderr, "differs in last_move\n");
  36                 return 1;
  37         }
  38         if (move_cmp(&b1->ko, &b2->ko) ||
  39             move_cmp(&b1->last_ko, &b2->last_ko) ||
  40             b1->last_ko_age != b2->last_ko_age) {
  41                 fprintf(stderr, "differs in ko\n");
  42                 return 1;
  43         }
  44
  45         int bsize = board_size2(b1) * sizeof(*b1->b);
  46         int gsize = board_size2(b1) * sizeof(*b1->g);
  47         //int fsize = board_size2(b1) * sizeof(*b1->f);
  48         int nsize = board_size2(b1) * sizeof(*b1->n);
  49         int psize = board_size2(b1) * sizeof(*b1->p);
  50         //int hsize = board_size2(b1) * 2 * sizeof(*b1->h);
  51         int gisize = board_size2(b1) * sizeof(*b1->gi);
  52         //int csize = board_size2(board) * sizeof(*b1->c);
  53         //int ssize = board_size2(board) * sizeof(*b1->spathash);
  54         //int p3size = board_size2(board) * sizeof(*b1->pat3);
  55         //int tsize = board_size2(board) * sizeof(*b1->t);
  56         //int tqsize = board_size2(board) * sizeof(*b1->t);
  57
  58         //int cdsize = board_size2(b1) * sizeof(*b1->coord);
  59
  60         if (memcmp(b1->b,  b2->b,  bsize)) {
  61                 fprintf(stderr, "differs in b\n");  return 1;  }
  62         if (memcmp(b1->g,  b2->g,  gsize)) {
  63                 fprintf(stderr, "differs in g\n");  return 1;  }
  64         if (memcmp(b1->n,  b2->n,  nsize)) {
  65                 fprintf(stderr, "differs in n\n");  return 1;  }
  66         if (memcmp(b1->p,  b2->p,  psize)) {
  67                 fprintf(stderr, "differs in p\n");  return 1;  }
  68         if (memcmp(b1->gi, b2->gi, gisize)) {
  69                 fprintf(stderr, "differs in gi\n");  return 1;  }
  70
  71         return 0;
  72 }
  73
  74
  75
  76 static void
  77 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
  78 {
  79         /* Add extra liberty from the board to our liberty list. */
  80         unsigned char watermark[board_size2(board) / 8];
  81         memset(watermark, 0, sizeof(watermark));
  82 #define watermark_get(c)        (watermark[c >> 3] & (1 << (c & 7)))
  83 #define watermark_set(c)        watermark[c >> 3] |= (1 << (c & 7))
  84
  85         for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
  86                 watermark_set(gi->lib[i]);
  87         watermark_set(avoid);
  88
  89         foreach_in_group(board, group) {
  90                 coord_t coord2 = c;
  91                 foreach_neighbor(board, coord2, {
  92                         if (board_at(board, c) + watermark_get(c) != S_NONE)
  93                                 continue;
  94                         watermark_set(c);
  95                         gi->lib[gi->libs++] = c;
  96                         if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
  97                                 return;
  98                 } );
  99         } foreach_in_group_end;
 100 #undef watermark_get
 101 #undef watermark_set
 102 }
 103
 104 static void
 105 check_libs_consistency(struct board *board, group_t g)
 106 { }
 107
 108 static void
 109 board_group_addlib(struct board *board, group_t group, coord_t coord)
 110 {
 111         if (DEBUGL(7)) {
 112                 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
 113                         group_base(group), coord2sstr(group_base(group), board),
 114                         board_group_info(board, group).libs, coord2sstr(coord, board));
 115         }
 116
 117         check_libs_consistency(board, group);
 118
 119         struct group *gi = &board_group_info(board, group);
 120         //bool onestone = group_is_onestone(board, group);
 121         if (gi->libs < GROUP_KEEP_LIBS) {
 122                 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
 123 #if 0
 124                         /* Seems extra branch just slows it down */
 125                         if (!gi->lib[i])
 126                                 break;
 127 #endif
 128                         if (unlikely(gi->lib[i] == coord))
 129                                 return;
 130                 }
 131                 gi->lib[gi->libs++] = coord;
 132         }
 133
 134         check_libs_consistency(board, group);
 135 }
 136
 137
 138 static void
 139 board_group_rmlib(struct board *board, group_t group, coord_t coord)
 140 {
 141         if (DEBUGL(7)) {
 142                 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
 143                         group_base(group), coord2sstr(group_base(group), board),
 144                         board_group_info(board, group).libs, coord2sstr(coord, board));
 145         }
 146
 147         struct group *gi = &board_group_info(board, group);
 148         //bool onestone = group_is_onestone(board, group);
 149         for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
 150 #if 0
 151                 /* Seems extra branch just slows it down */
 152                 if (!gi->lib[i])
 153                         break;
 154 #endif
 155                 if (likely(gi->lib[i] != coord))
 156                         continue;
 157
 158                 //coord_t lib =
 159                 gi->lib[i] = gi->lib[--gi->libs];
 160                 gi->lib[gi->libs] = 0;
 161
 162                 check_libs_consistency(board, group);
 163
 164                 /* Postpone refilling lib[] until we need to. */
 165                 assert(GROUP_REFILL_LIBS > 1);
 166                 if (gi->libs > GROUP_REFILL_LIBS)
 167                         return;
 168                 if (gi->libs == GROUP_REFILL_LIBS)
 169                         board_group_find_extra_libs(board, group, gi, coord);
 170
 171                 return;
 172         }
 173
 174         /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
 175          * can call this multiple times per coord. */
 176         check_libs_consistency(board, group);
 177         return;
 178 }
 179
 180
 181 /* This is a low-level routine that doesn't maintain consistency
 182  * of all the board data structures. */
 183 static void
 184 board_remove_stone(struct board *board, group_t group, coord_t c)
 185 {
 186         enum stone color = board_at(board, c);
 187         board_at(board, c) = S_NONE;
 188         group_at(board, c) = 0;
 189
 190         /* Increase liberties of surrounding groups */
 191         coord_t coord = c;
 192         foreach_neighbor(board, coord, {
 193                 dec_neighbor_count_at(board, c, color);
 194                 group_t g = group_at(board, c);
 195                 if (g && g != group)
 196                         board_group_addlib(board, g, coord);
 197         });
 198 }
 199
 200 static int profiling_noinline
 201 board_group_capture(struct board *board, group_t group)
 202 {
 203         int stones = 0;
 204
 205         foreach_in_group(board, group) {
 206                 board->captures[stone_other(board_at(board, c))]++;
 207                 board_remove_stone(board, group, c);
 208                 stones++;
 209         } foreach_in_group_end;
 210
 211         struct group *gi = &board_group_info(board, group);
 212         assert(gi->libs == 0);
 213         memset(gi, 0, sizeof(*gi));
 214
 215         return stones;
 216 }
 217
 218 static void profiling_noinline
 219 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
 220 {
 221         group_at(board, coord) = group;
 222         groupnext_at(board, coord) = groupnext_at(board, prevstone);
 223         groupnext_at(board, prevstone) = coord;
 224
 225         foreach_neighbor(board, coord, {
 226                 if (board_at(board, c) == S_NONE)
 227                         board_group_addlib(board, group, c);
 228         });
 229
 230         if (DEBUGL(8))
 231                 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
 232                         coord_x(prevstone, board), coord_y(prevstone, board),
 233                         coord_x(coord, board), coord_y(coord, board),
 234                         groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
 235                         group_base(group));
 236 }
 237
 238 static void profiling_noinline
 239 merge_groups(struct board *board, group_t group_to, group_t group_from, struct board_undo *u)
 240 {
 241         if (DEBUGL(7))
 242                 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
 243                         group_base(group_from), group_base(group_to));
 244         struct group *gi_from = &board_group_info(board, group_from);
 245         struct group *gi_to = &board_group_info(board, group_to);
 246         // bool onestone_from = group_is_onestone(board, group_from);
 247         // bool onestone_to = group_is_onestone(board, group_to);
 248
 249         if (DEBUGL(7))
 250                 fprintf(stderr,"---- (froml %d, tol %d)\n", gi_from->libs, gi_to->libs);
 251
 252         if (gi_to->libs < GROUP_KEEP_LIBS) {
 253                 for (int i = 0; i < gi_from->libs; i++) {
 254                         for (int j = 0; j < gi_to->libs; j++)
 255                                 if (gi_to->lib[j] == gi_from->lib[i])
 256                                         goto next_from_lib;
 257                         gi_to->lib[gi_to->libs++] = gi_from->lib[i];
 258                         if (gi_to->libs >= GROUP_KEEP_LIBS)
 259                                 break;
 260 next_from_lib:;
 261                 }
 262         }
 263
 264         //if (gi_to->libs == 1) {
 265         //      coord_t lib = board_group_info(board, group_to).lib[0];
 266         //}
 267
 268         coord_t last_in_group;
 269         foreach_in_group(board, group_from) {
 270                 last_in_group = c;
 271                 group_at(board, c) = group_to;
 272         } foreach_in_group_end;
 273
 274         u->merged[++u->nmerged_tmp].last = last_in_group;
 275         groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
 276         groupnext_at(board, group_base(group_to)) = group_base(group_from);
 277         memset(gi_from, 0, sizeof(struct group));
 278
 279         if (DEBUGL(7))
 280                 fprintf(stderr, "board_play_raw: merged group: %d\n",
 281                         group_base(group_to));
 282 }
 283
 284
 285 static group_t profiling_noinline
 286 new_group(struct board *board, coord_t coord)
 287 {
 288         group_t group = coord;
 289         struct group *gi = &board_group_info(board, group);
 290         foreach_neighbor(board, coord, {
 291                 if (board_at(board, c) == S_NONE)
 292                         /* board_group_addlib is ridiculously expensive for us */
 293 #if GROUP_KEEP_LIBS < 4
 294                         if (gi->libs < GROUP_KEEP_LIBS)
 295 #endif
 296                         gi->lib[gi->libs++] = c;
 297         });
 298
 299         group_at(board, coord) = group;
 300         groupnext_at(board, coord) = 0;
 301
 302         check_libs_consistency(board, group);
 303
 304         if (DEBUGL(8))
 305                 fprintf(stderr, "new_group: added %d,%d to group %d\n",
 306                         coord_x(coord, board), coord_y(coord, board),
 307                         group_base(group));
 308
 309         return group;
 310 }
 311
 312 static inline void
 313 undo_save_merge(struct board *b, struct board_undo *u, group_t g, coord_t c)
 314 {
 315         if (g == u->merged[0].group || g == u->merged[1].group ||
 316             g == u->merged[2].group || g == u->merged[3].group)
 317                 return;
 318
 319         int i = u->nmerged++;
 320         if (!i)
 321                 u->inserted = c;
 322         u->merged[i].group = g;
 323         u->merged[i].last = 0;   // can remove
 324         u->merged[i].info = board_group_info(b, g);
 325 }
 326
 327 static inline void
 328 undo_save_enemy(struct board *b, struct board_undo *u, group_t g)
 329 {
 330         if (g == u->enemies[0].group || g == u->enemies[1].group ||
 331             g == u->enemies[2].group || g == u->enemies[3].group)
 332                 return;
 333
 334         int i = u->nenemies++;
 335         u->enemies[i].group = g;
 336         u->enemies[i].info = board_group_info(b, g);
 337
 338         int j = 0;
 339         coord_t *stones = u->enemies[i].stones;
 340         if (board_group_info(b, g).libs <= 1) { // Will be captured
 341                 foreach_in_group(b, g) {
 342                         stones[j++] = c;
 343                 } foreach_in_group_end;
 344                 u->captures += j;
 345         }
 346         stones[j] = 0;
 347 }
 348
 349 static void
 350 undo_save_group_info(struct board *b, coord_t coord, enum stone color, struct board_undo *u)
 351 {
 352         u->next_at = groupnext_at(b, coord);
 353
 354         foreach_neighbor(b, coord, {
 355                 group_t g = group_at(b, c);
 356
 357                 if (board_at(b, c) == color)
 358                         undo_save_merge(b, u, g, c);
 359                 else if (board_at(b, c) == stone_other(color))
 360                         undo_save_enemy(b, u, g);
 361         });
 362 }
 363
 364 static void
 365 undo_save_suicide(struct board *b, coord_t coord, enum stone color, struct board_undo *u)
 366 {
 367         foreach_neighbor(b, coord, {
 368                 if (board_at(b, c) == color) {
 369                         // Handle suicide as a capture ...
 370                         undo_save_enemy(b, u, group_at(b, c));
 371                         return;
 372                 }
 373         });
 374         assert(0);
 375 }
 376
 377 static inline group_t
 378 play_one_neighbor(struct board *board,
 379                   coord_t coord, enum stone color, enum stone other_color,
 380                   coord_t c, group_t group, struct board_undo *u)
 381 {
 382         enum stone ncolor = board_at(board, c);
 383         group_t ngroup = group_at(board, c);
 384
 385         inc_neighbor_count_at(board, c, color);
 386         if (!ngroup)
 387                 return group;
 388
 389         board_group_rmlib(board, ngroup, coord);
 390         if (DEBUGL(7))
 391                 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
 392                         group_base(ngroup), ncolor, color, other_color);
 393
 394         if (ncolor == color && ngroup != group) {
 395                 if (!group) {
 396                         group = ngroup;
 397                         add_to_group(board, group, c, coord);
 398                 } else {
 399                         merge_groups(board, group, ngroup, u);
 400                 }
 401         } else if (ncolor == other_color) {
 402                 if (DEBUGL(8)) {
 403                         struct group *gi = &board_group_info(board, ngroup);
 404                         fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
 405                         for (int i = 0; i < GROUP_KEEP_LIBS; i++)
 406                                 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
 407                         fprintf(stderr, "\n");
 408                 }
 409                 if (unlikely(board_group_captured(board, ngroup)))
 410                         board_group_capture(board, ngroup);
 411         }
 412         return group;
 413 }
 414
 415
 416 /* We played on a place with at least one liberty. We will become a member of
 417  * some group for sure. */
 418 static group_t profiling_noinline
 419 board_play_outside(struct board *board, struct move *m, struct board_undo *u)
 420 {
 421         coord_t coord = m->coord;
 422         enum stone color = m->color;
 423         enum stone other_color = stone_other(color);
 424         group_t group = 0;
 425
 426         undo_save_group_info(board, coord, color, u);
 427
 428         foreach_neighbor(board, coord, {
 429                 group = play_one_neighbor(board, coord, color, other_color, c, group, u);
 430         });
 431
 432         board_at(board, coord) = color;
 433         if (unlikely(!group))
 434                 group = new_group(board, coord);
 435
 436         board->last_move2 = board->last_move;
 437         board->last_move = *m;
 438         board->moves++;
 439         struct move ko = { pass, S_NONE };
 440         board->ko = ko;
 441
 442         return group;
 443 }
 444
 445
 446 /* We played in an eye-like shape. Either we capture at least one of the eye
 447  * sides in the process of playing, or return -1. */
 448 static int profiling_noinline
 449 board_play_in_eye(struct board *board, struct move *m, struct board_undo *u)
 450 {
 451         coord_t coord = m->coord;
 452         enum stone color = m->color;
 453         /* Check ko: Capture at a position of ko capture one move ago */
 454         if (unlikely(color == board->ko.color && coord == board->ko.coord)) {
 455                 if (DEBUGL(5))
 456                         fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
 457                 return -1;
 458         } else if (DEBUGL(6)) {
 459                 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
 460                         color, coord_x(coord, board), coord_y(coord, board),
 461                         board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
 462         }
 463
 464         struct move ko = { pass, S_NONE };
 465
 466         int captured_groups = 0;
 467
 468         foreach_neighbor(board, coord, {
 469                 group_t g = group_at(board, c);
 470                 if (DEBUGL(7))
 471                         fprintf(stderr, "board_check: group %d has %d libs\n",
 472                                 g, board_group_info(board, g).libs);
 473                 captured_groups += (board_group_info(board, g).libs == 1);
 474         });
 475
 476         if (likely(captured_groups == 0)) {
 477                 if (DEBUGL(5)) {
 478                         if (DEBUGL(6))
 479                                 board_print(board, stderr);
 480                         fprintf(stderr, "board_check: one-stone suicide\n");
 481                 }
 482
 483                 return -1;
 484         }
 485
 486         undo_save_group_info(board, coord, color, u);
 487
 488         int ko_caps = 0;
 489         coord_t cap_at = pass;
 490         foreach_neighbor(board, coord, {
 491                 inc_neighbor_count_at(board, c, color);
 492                 group_t group = group_at(board, c);
 493                 if (!group)
 494                         continue;
 495
 496                 board_group_rmlib(board, group, coord);
 497                 if (DEBUGL(7))
 498                         fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
 499                                 group_base(group));
 500
 501                 if (board_group_captured(board, group)) {
 502                         ko_caps += board_group_capture(board, group);
 503                         cap_at = c;
 504                 }
 505         });
 506         if (ko_caps == 1) {
 507                 ko.color = stone_other(color);
 508                 ko.coord = cap_at; // unique
 509                 board->last_ko = ko;
 510                 board->last_ko_age = board->moves;
 511                 if (DEBUGL(5))
 512                         fprintf(stderr, "guarding ko at %d,%s\n", ko.color, coord2sstr(ko.coord, board));
 513         }
 514
 515         board_at(board, coord) = color;
 516         group_t group = new_group(board, coord);
 517
 518         board->last_move2 = board->last_move;
 519         board->last_move = *m;
 520         board->moves++;
 521         board->ko = ko;
 522
 523         return !!group;
 524 }
 525
 526
 527 static int __attribute__((flatten))
 528 board_play_f(struct board *board, struct move *m, struct board_undo *u)
 529 {
 530         if (DEBUGL(7)) {
 531                 fprintf(stderr, "board_play(%s): ---- Playing %d,%d\n", coord2sstr(m->coord, board), coord_x(m->coord, board), coord_y(m->coord, board));
 532         }
 533         if (likely(!board_is_eyelike(board, m->coord, stone_other(m->color)))) {
 534                 /* NOT playing in an eye. Thus this move has to succeed. (This
 535                  * is thanks to New Zealand rules. Otherwise, multi-stone
 536                  * suicide might fail.) */
 537                 group_t group = board_play_outside(board, m, u);
 538                 if (unlikely(board_group_captured(board, group))) {
 539                         undo_save_suicide(board, m->coord, m->color, u);
 540                         board_group_capture(board, group);
 541                 }
 542                 return 0;
 543         } else {
 544                 return board_play_in_eye(board, m, u);
 545         }
 546 }
 547
 548 static void
 549 undo_init(struct board *b, struct move *m, struct board_undo *u)
 550 {
 551         // Paranoid uninitialized mem test
 552         // memset(u, 0xff, sizeof(*u));
 553
 554         u->last_move2 = b->last_move2;
 555         u->ko = b->ko;
 556         u->last_ko = b->last_ko;
 557         u->last_ko_age = b->last_ko_age;
 558         u->captures = 0;
 559
 560         u->nmerged = u->nmerged_tmp = u->nenemies = 0;
 561         for (int i = 0; i < 4; i++)
 562                 u->merged[i].group = u->enemies[i].group = 0;
 563 }
 564
 565
 566 static inline int
 567 board_quick_play_(struct board *board, struct move *m, struct board_undo *u)
 568 {
 569         undo_init(board, m, u);
 570
 571         if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
 572                 struct move nomove = { pass, S_NONE };
 573                 board->ko = nomove;
 574                 board->last_move2 = board->last_move;
 575                 board->last_move = *m;
 576                 return 0;
 577         }
 578
 579         if (likely(board_at(board, m->coord) == S_NONE))
 580                 return board_play_f(board, m, u);
 581
 582         if (DEBUGL(7))
 583                 fprintf(stderr, "board_check: stone exists\n");
 584         return -1;
 585 }
 586
 587 int
 588 board_quick_play(struct board *board, struct move *m, struct board_undo *u)
 589 {
 590         int r = board_quick_play_(board, m, u);
 591 #ifdef BOARD_UNDO_CHECKS
 592         if (r >= 0)
 593                 board->quicked++;
 594 #endif
 595         return r;
 596 }
 597
 598 /***********************************************************************************/
 599
 600 static inline void
 601 undo_merge(struct board *b, struct board_undo *u, struct move *m)
 602 {
 603         coord_t coord = m->coord;
 604         group_t group = group_at(b, coord);
 605         struct undo_merge *merged = u->merged;
 606
 607         // Others groups, in reverse order ...
 608         for (int i = u->nmerged - 1; i > 0; i--) {
 609                 group_t old_group = merged[i].group;
 610
 611                 board_group_info(b, old_group) = merged[i].info;
 612
 613                 groupnext_at(b, group_base(group)) = groupnext_at(b, merged[i].last);
 614                 groupnext_at(b, merged[i].last) = 0;
 615
 616 #if 0
 617                 printf("merged_group[%i]:   (last: %s)", i, coord2sstr(merged[i].last, b));
 618                 foreach_in_group(b, old_group) {
 619                         printf("%s ", coord2sstr(c, b));
 620                 } foreach_in_group_end;
 621                 printf("\n");
 622 #endif
 623
 624                 foreach_in_group(b, old_group) {
 625                         group_at(b, c) = old_group;
 626                 } foreach_in_group_end;
 627         }
 628
 629         // Restore first group
 630         groupnext_at(b, u->inserted) = groupnext_at(b, coord);
 631         board_group_info(b, merged[0].group) = merged[0].info;
 632
 633 #if 0
 634         printf("merged_group[0]: ");
 635         foreach_in_group(b, merged[0].group) {
 636                 printf("%s ", coord2sstr(c, b));
 637         } foreach_in_group_end;
 638         printf("\n");
 639 #endif
 640 }
 641
 642
 643 static inline void
 644 restore_enemies(struct board *b, struct board_undo *u, struct move *m)
 645 {
 646         enum stone color = m->color;
 647         enum stone other_color = stone_other(m->color);
 648
 649         struct undo_enemy *enemy = u->enemies;
 650         for (int i = 0; i < u->nenemies; i++) {
 651                 group_t old_group = enemy[i].group;
 652
 653                 board_group_info(b, old_group) = enemy[i].info;
 654
 655                 coord_t *stones = enemy[i].stones;
 656                 for (int j = 0; stones[j]; j++) {
 657                         board_at(b, stones[j]) = other_color;
 658                         group_at(b, stones[j]) = old_group;
 659                         groupnext_at(b, stones[j]) = stones[j + 1];
 660
 661                         foreach_neighbor(b, stones[j], {
 662                                 inc_neighbor_count_at(b, c, other_color);
 663                         });
 664
 665                         // Update liberties of neighboring groups
 666                         foreach_neighbor(b, stones[j], {
 667                                         if (board_at(b, c) != color)
 668                                                 continue;
 669                                         group_t g = group_at(b, c);
 670                                         if (g == u->merged[0].group || g == u->merged[1].group || g == u->merged[2].group || g == u->merged[3].group)
 671                                                 continue;
 672                                         board_group_rmlib(b, g, stones[j]);
 673                                 });
 674                 }
 675         }
 676 }
 677
 678 static void
 679 board_undo_stone(struct board *b, struct board_undo *u, struct move *m)
 680 {
 681         coord_t coord = m->coord;
 682         enum stone color = m->color;
 683         /* - update groups
 684          * - put captures back
 685          */
 686
 687         //printf("nmerged: %i\n", u->nmerged);
 688
 689         // Restore merged groups
 690         if (u->nmerged)
 691                 undo_merge(b, u, m);
 692         else                    // Single stone group undo
 693                 memset(&board_group_info(b, group_at(b, coord)), 0, sizeof(struct group));
 694
 695         board_at(b, coord) = S_NONE;
 696         group_at(b, coord) = 0;
 697         groupnext_at(b, coord) = u->next_at;
 698
 699         foreach_neighbor(b, coord, {
 700                         dec_neighbor_count_at(b, c, color);
 701         });
 702
 703         // Restore enemy groups
 704         if (u->nenemies) {
 705                 b->captures[color] -= u->captures;
 706                 restore_enemies(b, u, m);
 707         }
 708 }
 709
 710 static inline void
 711 restore_suicide(struct board *b, struct board_undo *u, struct move *m)
 712 {
 713         enum stone color = m->color;
 714         enum stone other_color = stone_other(m->color);
 715
 716         struct undo_enemy *enemy = u->enemies;
 717         for (int i = 0; i < u->nenemies; i++) {
 718                 group_t old_group = enemy[i].group;
 719
 720                 board_group_info(b, old_group) = enemy[i].info;
 721
 722                 coord_t *stones = enemy[i].stones;
 723                 for (int j = 0; stones[j]; j++) {
 724                         board_at(b, stones[j]) = other_color;
 725                         group_at(b, stones[j]) = old_group;
 726                         groupnext_at(b, stones[j]) = stones[j + 1];
 727
 728                         foreach_neighbor(b, stones[j], {
 729                                 inc_neighbor_count_at(b, c, other_color);
 730                         });
 731
 732                         // Update liberties of neighboring groups
 733                         foreach_neighbor(b, stones[j], {
 734                                         if (board_at(b, c) != color)
 735                                                 continue;
 736                                         group_t g = group_at(b, c);
 737                                         if (g == u->enemies[0].group || g == u->enemies[1].group || g == u->enemies[2].group || g == u->enemies[3].group)
 738                                                 continue;
 739                                         board_group_rmlib(b, g, stones[j]);
 740                                 });
 741                 }
 742         }
 743 }
 744
 745
 746 static void
 747 board_undo_suicide(struct board *b, struct board_undo *u, struct move *m)
 748 {
 749         coord_t coord = m->coord;
 750         enum stone other_color = stone_other(m->color);
 751
 752         // Pretend it's capture ...
 753         struct move m2 = { .coord = m->coord, .color = other_color };
 754         b->captures[other_color] -= u->captures;
 755
 756         restore_suicide(b, u, &m2);
 757
 758         undo_merge(b, u, m);
 759
 760         board_at(b, coord) = S_NONE;
 761         group_at(b, coord) = 0;
 762         groupnext_at(b, coord) = u->next_at;
 763
 764         foreach_neighbor(b, coord, {
 765                 dec_neighbor_count_at(b, c, m->color);
 766         });
 767
 768 }
 769
 770
 771
 772 void
 773 board_quick_undo(struct board *b, struct move *m, struct board_undo *u)
 774 {
 775 #ifdef BOARD_UNDO_CHECKS
 776         b->quicked--;
 777 #endif
 778
 779         b->last_move = b->last_move2;
 780         b->last_move2 = u->last_move2;
 781         b->ko = u->ko;
 782         b->last_ko = u->last_ko;
 783         b->last_ko_age = u->last_ko_age;
 784
 785         if (unlikely(is_pass(m->coord) || is_resign(m->coord)))
 786                 return;
 787
 788         b->moves--;
 789
 790         if (likely(board_at(b, m->coord) == m->color))
 791                 board_undo_stone(b, u, m);
 792         else if (board_at(b, m->coord) == S_NONE)
 793                 board_undo_suicide(b, u, m);
 794         else
 795                 assert(0);      /* Anything else doesn't make sense */
 796 }
 797