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