From 4acb0e597132af9a42bed48bb3deb541af72fab2 Mon Sep 17 00:00:00 2001 From: lemonsqueeze Date: Tue, 12 Jul 2016 02:56:33 +0200 Subject: [PATCH] board.c: merged board_undo.c --- Makefile | 2 +- board.c | 610 ++++++++++++++++++++++++++++++++++++--------- board_undo.c | 797 ----------------------------------------------------------- 3 files changed, 501 insertions(+), 908 deletions(-) delete mode 100644 board_undo.c diff --git a/Makefile b/Makefile index b7dc7ac..bc4cea1 100644 --- a/Makefile +++ b/Makefile @@ -138,7 +138,7 @@ unexport INCLUDES INCLUDES=-I. -OBJS=board.o board_undo.o gtp.o move.o ownermap.o pattern3.o pattern.o patternsp.o patternprob.o playout.o probdist.o random.o stone.o timeinfo.o network.o fbook.o chat.o +OBJS=board.o gtp.o move.o ownermap.o pattern3.o pattern.o patternsp.o patternprob.o playout.o probdist.o random.o stone.o timeinfo.o network.o fbook.o chat.o ifdef DCNN OBJS+=dcnn.o endif diff --git a/board.c b/board.c index ebb07ea..a8de74b 100644 --- a/board.c +++ b/board.c @@ -161,7 +161,58 @@ board_cmp(struct board *b1, struct board *b2) return memcmp(b1->b, b2->b, size); } +int +board_quick_cmp(struct board *b1, struct board *b2) +{ + if (b1->size != b2->size || + b1->size2 != b2->size2 || + b1->bits2 != b2->bits2 || + b1->captures[S_BLACK] != b2->captures[S_BLACK] || + b1->captures[S_WHITE] != b2->captures[S_WHITE] || + b1->moves != b2->moves) { + fprintf(stderr, "differs in main vars\n"); + return 1; + } + if (move_cmp(&b1->last_move, &b2->last_move) || + move_cmp(&b1->last_move2, &b2->last_move2)) { + fprintf(stderr, "differs in last_move\n"); + return 1; + } + if (move_cmp(&b1->ko, &b2->ko) || + move_cmp(&b1->last_ko, &b2->last_ko) || + b1->last_ko_age != b2->last_ko_age) { + fprintf(stderr, "differs in ko\n"); + return 1; + } + int bsize = board_size2(b1) * sizeof(*b1->b); + int gsize = board_size2(b1) * sizeof(*b1->g); + //int fsize = board_size2(b1) * sizeof(*b1->f); + int nsize = board_size2(b1) * sizeof(*b1->n); + int psize = board_size2(b1) * sizeof(*b1->p); + //int hsize = board_size2(b1) * 2 * sizeof(*b1->h); + int gisize = board_size2(b1) * sizeof(*b1->gi); + //int csize = board_size2(board) * sizeof(*b1->c); + //int ssize = board_size2(board) * sizeof(*b1->spathash); + //int p3size = board_size2(board) * sizeof(*b1->pat3); + //int tsize = board_size2(board) * sizeof(*b1->t); + //int tqsize = board_size2(board) * sizeof(*b1->t); + + //int cdsize = board_size2(b1) * sizeof(*b1->coord); + + if (memcmp(b1->b, b2->b, bsize)) { + fprintf(stderr, "differs in b\n"); return 1; } + if (memcmp(b1->g, b2->g, gsize)) { + fprintf(stderr, "differs in g\n"); return 1; } + if (memcmp(b1->n, b2->n, nsize)) { + fprintf(stderr, "differs in n\n"); return 1; } + if (memcmp(b1->p, b2->p, psize)) { + fprintf(stderr, "differs in p\n"); return 1; } + if (memcmp(b1->gi, b2->gi, gisize)) { + fprintf(stderr, "differs in gi\n"); return 1; } + + return 0; +} struct board * @@ -829,7 +880,7 @@ board_atariable_rm(struct board *board, group_t group, coord_t lib1, coord_t lib } static void -board_group_addlib(struct board *board, group_t group, coord_t coord) +board_group_addlib(struct board *board, group_t group, coord_t coord, struct board_undo *u) { if (DEBUGL(7)) { fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n", @@ -837,7 +888,7 @@ board_group_addlib(struct board *board, group_t group, coord_t coord) board_group_info(board, group).libs, coord2sstr(coord, board)); } - check_libs_consistency(board, group); + if (!u) check_libs_consistency(board, group); struct group *gi = &board_group_info(board, group); bool onestone = group_is_onestone(board, group); @@ -851,18 +902,20 @@ board_group_addlib(struct board *board, group_t group, coord_t coord) if (unlikely(gi->lib[i] == coord)) return; } - if (gi->libs == 0) { - board_capturable_add(board, group, coord, onestone); - } else if (gi->libs == 1) { - board_capturable_rm(board, group, gi->lib[0], onestone); - board_atariable_add(board, group, gi->lib[0], coord); - } else if (gi->libs == 2) { - board_atariable_rm(board, group, gi->lib[0], gi->lib[1]); + if (!u) { + if (gi->libs == 0) { + board_capturable_add(board, group, coord, onestone); + } else if (gi->libs == 1) { + board_capturable_rm(board, group, gi->lib[0], onestone); + board_atariable_add(board, group, gi->lib[0], coord); + } else if (gi->libs == 2) { + board_atariable_rm(board, group, gi->lib[0], gi->lib[1]); + } } gi->lib[gi->libs++] = coord; } - check_libs_consistency(board, group); + if (!u) check_libs_consistency(board, group); } static void @@ -894,7 +947,7 @@ board_group_find_extra_libs(struct board *board, group_t group, struct group *gi } static void -board_group_rmlib(struct board *board, group_t group, coord_t coord) +board_group_rmlib(struct board *board, group_t group, coord_t coord, struct board_undo *u) { if (DEBUGL(7)) { fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n", @@ -915,8 +968,8 @@ board_group_rmlib(struct board *board, group_t group, coord_t coord) coord_t lib = gi->lib[i] = gi->lib[--gi->libs]; gi->lib[gi->libs] = 0; - - check_libs_consistency(board, group); + + if (!u) check_libs_consistency(board, group); /* Postpone refilling lib[] until we need to. */ assert(GROUP_REFILL_LIBS > 1); @@ -924,7 +977,8 @@ board_group_rmlib(struct board *board, group_t group, coord_t coord) return; if (gi->libs == GROUP_REFILL_LIBS) board_group_find_extra_libs(board, group, gi, coord); - + if (u) return; + if (gi->libs == 2) { board_atariable_add(board, group, gi->lib[0], gi->lib[1]); } else if (gi->libs == 1) { @@ -937,7 +991,7 @@ board_group_rmlib(struct board *board, group_t group, coord_t coord) /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we * can call this multiple times per coord. */ - check_libs_consistency(board, group); + if (!u) check_libs_consistency(board, group); return; } @@ -945,29 +999,32 @@ board_group_rmlib(struct board *board, group_t group, coord_t coord) /* This is a low-level routine that doesn't maintain consistency * of all the board data structures. */ static void -board_remove_stone(struct board *board, group_t group, coord_t c) +board_remove_stone(struct board *board, group_t group, coord_t c, struct board_undo *u) { enum stone color = board_at(board, c); board_at(board, c) = S_NONE; group_at(board, c) = 0; - board_hash_update(board, c, color); + if (!u) { + board_hash_update(board, c, color); #ifdef BOARD_TRAITS - /* We mark as cannot-capture now. If this is a ko/snapback, - * we will get incremented later in board_group_addlib(). */ - trait_at(board, c, S_BLACK).cap = trait_at(board, c, S_BLACK).cap1 = 0; - trait_at(board, c, S_WHITE).cap = trait_at(board, c, S_WHITE).cap1 = 0; - board_trait_queue(board, c); + /* We mark as cannot-capture now. If this is a ko/snapback, + * we will get incremented later in board_group_addlib(). */ + trait_at(board, c, S_BLACK).cap = trait_at(board, c, S_BLACK).cap1 = 0; + trait_at(board, c, S_WHITE).cap = trait_at(board, c, S_WHITE).cap1 = 0; + board_trait_queue(board, c); #endif + } /* Increase liberties of surrounding groups */ coord_t coord = c; foreach_neighbor(board, coord, { dec_neighbor_count_at(board, c, color); - board_trait_queue(board, c); + if (!u) board_trait_queue(board, c); group_t g = group_at(board, c); if (g && g != group) - board_group_addlib(board, g, coord); + board_group_addlib(board, g, coord, u); }); + if (u) return; #ifdef BOARD_PAT3 /* board_hash_update() might have seen the freed up point as able @@ -982,13 +1039,13 @@ board_remove_stone(struct board *board, group_t group, coord_t c) } static int profiling_noinline -board_group_capture(struct board *board, group_t group) +board_group_capture(struct board *board, group_t group, struct board_undo *u) { int stones = 0; foreach_in_group(board, group) { board->captures[stone_other(board_at(board, c))]++; - board_remove_stone(board, group, c); + board_remove_stone(board, group, c, u); stones++; } foreach_in_group_end; @@ -1001,13 +1058,13 @@ board_group_capture(struct board *board, group_t group) static void profiling_noinline -add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord) +add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord, struct board_undo *u) { #ifdef BOARD_TRAITS struct group *gi = &board_group_info(board, group); bool onestone = group_is_onestone(board, group); - if (gi->libs == 1) { + if (!u && gi->libs == 1) { /* Our group is temporarily in atari; make sure the capturable * counts also correspond to the newly added stone before we * start adding liberties again so bump-dump ops match. */ @@ -1041,7 +1098,7 @@ add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coor foreach_neighbor(board, coord, { if (board_at(board, c) == S_NONE) - board_group_addlib(board, group, c); + board_group_addlib(board, group, c, u); }); if (DEBUGL(8)) @@ -1053,7 +1110,7 @@ add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coor } static void profiling_noinline -merge_groups(struct board *board, group_t group_to, group_t group_from) +merge_groups(struct board *board, group_t group_to, group_t group_from, struct board_undo *u) { if (DEBUGL(7)) fprintf(stderr, "board_play_raw: merging groups %d -> %d\n", @@ -1063,11 +1120,13 @@ merge_groups(struct board *board, group_t group_to, group_t group_from) bool onestone_from = group_is_onestone(board, group_from); bool onestone_to = group_is_onestone(board, group_to); - /* We do this early before the group info is rewritten. */ - if (gi_from->libs == 2) - board_atariable_rm(board, group_from, gi_from->lib[0], gi_from->lib[1]); - else if (gi_from->libs == 1) - board_capturable_rm(board, group_from, gi_from->lib[0], onestone_from); + if (!u) { + /* We do this early before the group info is rewritten. */ + if (gi_from->libs == 2) + board_atariable_rm(board, group_from, gi_from->lib[0], gi_from->lib[1]); + else if (gi_from->libs == 1) + board_capturable_rm(board, group_from, gi_from->lib[0], onestone_from); + } if (DEBUGL(7)) fprintf(stderr,"---- (froml %d, tol %d)\n", gi_from->libs, gi_to->libs); @@ -1077,13 +1136,15 @@ merge_groups(struct board *board, group_t group_to, group_t group_from) for (int j = 0; j < gi_to->libs; j++) if (gi_to->lib[j] == gi_from->lib[i]) goto next_from_lib; - if (gi_to->libs == 0) { - board_capturable_add(board, group_to, gi_from->lib[i], onestone_to); - } else if (gi_to->libs == 1) { - board_capturable_rm(board, group_to, gi_to->lib[0], onestone_to); - board_atariable_add(board, group_to, gi_to->lib[0], gi_from->lib[i]); - } else if (gi_to->libs == 2) { - board_atariable_rm(board, group_to, gi_to->lib[0], gi_to->lib[1]); + if (!u) { + if (gi_to->libs == 0) { + board_capturable_add(board, group_to, gi_from->lib[i], onestone_to); + } else if (gi_to->libs == 1) { + board_capturable_rm(board, group_to, gi_to->lib[0], onestone_to); + board_atariable_add(board, group_to, gi_to->lib[0], gi_from->lib[i]); + } else if (gi_to->libs == 2) { + board_atariable_rm(board, group_to, gi_to->lib[0], gi_to->lib[1]); + } } gi_to->lib[gi_to->libs++] = gi_from->lib[i]; if (gi_to->libs >= GROUP_KEEP_LIBS) @@ -1092,7 +1153,7 @@ next_from_lib:; } } - if (gi_to->libs == 1) { + if (!u && gi_to->libs == 1) { coord_t lib = board_group_info(board, group_to).lib[0]; #ifdef BOARD_TRAITS enum stone capturing_color = stone_other(board_at(board, group_to)); @@ -1139,6 +1200,8 @@ next_from_lib:; last_in_group = c; group_at(board, c) = group_to; } foreach_in_group_end; + + if (u) u->merged[++u->nmerged_tmp].last = last_in_group; groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to)); groupnext_at(board, group_base(group_to)) = group_base(group_from); memset(gi_from, 0, sizeof(struct group)); @@ -1149,7 +1212,7 @@ next_from_lib:; } static group_t profiling_noinline -new_group(struct board *board, coord_t coord) +new_group(struct board *board, coord_t coord, struct board_undo *u) { group_t group = coord; struct group *gi = &board_group_info(board, group); @@ -1165,11 +1228,13 @@ new_group(struct board *board, coord_t coord) group_at(board, coord) = group; groupnext_at(board, coord) = 0; - if (gi->libs == 2) - board_atariable_add(board, group, gi->lib[0], gi->lib[1]); - else if (gi->libs == 1) - board_capturable_add(board, group, gi->lib[0], true); - check_libs_consistency(board, group); + if (!u) { + if (gi->libs == 2) + board_atariable_add(board, group, gi->lib[0], gi->lib[1]); + else if (gi->libs == 1) + board_capturable_add(board, group, gi->lib[0], true); + check_libs_consistency(board, group); + } if (DEBUGL(8)) fprintf(stderr, "new_group: added %d,%d to group %d\n", @@ -1179,10 +1244,75 @@ new_group(struct board *board, coord_t coord) return group; } +static inline void +undo_save_merge(struct board *b, struct board_undo *u, group_t g, coord_t c) +{ + if (g == u->merged[0].group || g == u->merged[1].group || + g == u->merged[2].group || g == u->merged[3].group) + return; + + int i = u->nmerged++; + if (!i) + u->inserted = c; + u->merged[i].group = g; + u->merged[i].last = 0; // can remove + u->merged[i].info = board_group_info(b, g); +} + +static inline void +undo_save_enemy(struct board *b, struct board_undo *u, group_t g) +{ + if (g == u->enemies[0].group || g == u->enemies[1].group || + g == u->enemies[2].group || g == u->enemies[3].group) + return; + + int i = u->nenemies++; + u->enemies[i].group = g; + u->enemies[i].info = board_group_info(b, g); + + int j = 0; + coord_t *stones = u->enemies[i].stones; + if (board_group_info(b, g).libs <= 1) { // Will be captured + foreach_in_group(b, g) { + stones[j++] = c; + } foreach_in_group_end; + u->captures += j; + } + stones[j] = 0; +} + +static void +undo_save_group_info(struct board *b, coord_t coord, enum stone color, struct board_undo *u) +{ + u->next_at = groupnext_at(b, coord); + + foreach_neighbor(b, coord, { + group_t g = group_at(b, c); + + if (board_at(b, c) == color) + undo_save_merge(b, u, g, c); + else if (board_at(b, c) == stone_other(color)) + undo_save_enemy(b, u, g); + }); +} + +static void +undo_save_suicide(struct board *b, coord_t coord, enum stone color, struct board_undo *u) +{ + foreach_neighbor(b, coord, { + if (board_at(b, c) == color) { + // Handle suicide as a capture ... + undo_save_enemy(b, u, group_at(b, c)); + return; + } + }); + assert(0); +} + static inline group_t play_one_neighbor(struct board *board, - coord_t coord, enum stone color, enum stone other_color, - coord_t c, group_t group) + coord_t coord, enum stone color, enum stone other_color, + coord_t c, group_t group, struct board_undo *u) { enum stone ncolor = board_at(board, c); group_t ngroup = group_at(board, c); @@ -1190,12 +1320,12 @@ play_one_neighbor(struct board *board, inc_neighbor_count_at(board, c, color); /* We can be S_NONE, in that case we need to update the safety * trait since we might be left with only one liberty. */ - board_trait_queue(board, c); + if (!u) board_trait_queue(board, c); if (!ngroup) return group; - board_group_rmlib(board, ngroup, coord); + board_group_rmlib(board, ngroup, coord, u); if (DEBUGL(7)) fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n", group_base(ngroup), ncolor, color, other_color); @@ -1203,9 +1333,9 @@ play_one_neighbor(struct board *board, if (ncolor == color && ngroup != group) { if (!group) { group = ngroup; - add_to_group(board, group, c, coord); + add_to_group(board, group, c, coord, u); } else { - merge_groups(board, group, ngroup); + merge_groups(board, group, ngroup, u); } } else if (ncolor == other_color) { if (DEBUGL(8)) { @@ -1216,7 +1346,7 @@ play_one_neighbor(struct board *board, fprintf(stderr, "\n"); } if (unlikely(board_group_captured(board, ngroup))) - board_group_capture(board, ngroup); + board_group_capture(board, ngroup, u); } return group; } @@ -1224,52 +1354,60 @@ play_one_neighbor(struct board *board, /* We played on a place with at least one liberty. We will become a member of * some group for sure. */ static group_t profiling_noinline -board_play_outside(struct board *board, struct move *m, int f) +board_play_outside(struct board *board, struct move *m, int f, struct board_undo *u) { coord_t coord = m->coord; enum stone color = m->color; enum stone other_color = stone_other(color); group_t group = 0; - board->f[f] = board->f[--board->flen]; - if (DEBUGL(6)) - fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]); + if (u) + undo_save_group_info(board, coord, color, u); + else { + board->f[f] = board->f[--board->flen]; + if (DEBUGL(6)) + fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]); #if defined(BOARD_TRAITS) && defined(DEBUG) - /* Sanity check that cap matches reality. */ - { - int a = 0, b = 0; - foreach_neighbor(board, coord, { - group_t g = group_at(board, c); - a += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1); - b += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1) && group_is_onestone(board, g); - }); - assert(a == trait_at(board, coord, color).cap); - assert(b == trait_at(board, coord, color).cap1); + /* Sanity check that cap matches reality. */ + { + int a = 0, b = 0; + foreach_neighbor(board, coord, { + group_t g = group_at(board, c); + a += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1); + b += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1) && group_is_onestone(board, g); + }); + assert(a == trait_at(board, coord, color).cap); + assert(b == trait_at(board, coord, color).cap1); #ifdef BOARD_TRAIT_SAFE - assert(board_trait_safe(board, coord, color) == trait_at(board, coord, color).safe); + assert(board_trait_safe(board, coord, color) == trait_at(board, coord, color).safe); #endif - } + } #endif + } foreach_neighbor(board, coord, { - group = play_one_neighbor(board, coord, color, other_color, c, group); + group = play_one_neighbor(board, coord, color, other_color, c, group, u); }); board_at(board, coord) = color; if (unlikely(!group)) - group = new_group(board, coord); + group = new_group(board, coord, u); - board->last_move4 = board->last_move3; - board->last_move3 = board->last_move2; + if (!u) { + board->last_move4 = board->last_move3; + board->last_move3 = board->last_move2; + } board->last_move2 = board->last_move; board->last_move = *m; board->moves++; - board_hash_update(board, coord, color); - board_symmetry_update(board, &board->symmetry, coord); + if (!u) { + board_hash_update(board, coord, color); + board_symmetry_update(board, &board->symmetry, coord); + } struct move ko = { pass, S_NONE }; board->ko = ko; - check_pat3_consistency(board, coord); + if (!u) check_pat3_consistency(board, coord); return group; } @@ -1277,7 +1415,7 @@ board_play_outside(struct board *board, struct move *m, int f) /* We played in an eye-like shape. Either we capture at least one of the eye * sides in the process of playing, or return -1. */ static int profiling_noinline -board_play_in_eye(struct board *board, struct move *m, int f) +board_play_in_eye(struct board *board, struct move *m, int f, struct board_undo *u) { coord_t coord = m->coord; enum stone color = m->color; @@ -1313,17 +1451,22 @@ board_play_in_eye(struct board *board, struct move *m, int f) return -1; } + + if (!u) { #ifdef BOARD_TRAITS - /* We _will_ for sure capture something. */ - assert(trait_at(board, coord, color).cap > 0); + /* We _will_ for sure capture something. */ + assert(trait_at(board, coord, color).cap > 0); #ifdef BOARD_TRAIT_SAFE - assert(trait_at(board, coord, color).safe == board_trait_safe(board, coord, color)); + assert(trait_at(board, coord, color).safe == board_trait_safe(board, coord, color)); #endif #endif - board->f[f] = board->f[--board->flen]; - if (DEBUGL(6)) - fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]); + board->f[f] = board->f[--board->flen]; + if (DEBUGL(6)) + fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]); + } + else + undo_save_group_info(board, coord, color, u); int ko_caps = 0; coord_t cap_at = pass; @@ -1332,19 +1475,19 @@ board_play_in_eye(struct board *board, struct move *m, int f) /* Originally, this could not have changed any trait * since no neighbors were S_NONE, however by now some * of them might be removed from the board. */ - board_trait_queue(board, c); + if (!u) board_trait_queue(board, c); group_t group = group_at(board, c); if (!group) continue; - board_group_rmlib(board, group, coord); + board_group_rmlib(board, group, coord, u); if (DEBUGL(7)) fprintf(stderr, "board_play_raw: reducing libs for group %d\n", group_base(group)); if (board_group_captured(board, group)) { - ko_caps += board_group_capture(board, group); + ko_caps += board_group_capture(board, group, u); cap_at = c; } }); @@ -1358,26 +1501,30 @@ board_play_in_eye(struct board *board, struct move *m, int f) } board_at(board, coord) = color; - group_t group = new_group(board, coord); + group_t group = new_group(board, coord, u); - board->last_move4 = board->last_move3; - board->last_move3 = board->last_move2; + if (!u) { + board->last_move4 = board->last_move3; + board->last_move3 = board->last_move2; + } board->last_move2 = board->last_move; board->last_move = *m; board->moves++; - board_hash_update(board, coord, color); - board_hash_commit(board); - board_traits_recompute(board); - board_symmetry_update(board, &board->symmetry, coord); + if (!u) { + board_hash_update(board, coord, color); + board_hash_commit(board); + board_traits_recompute(board); + board_symmetry_update(board, &board->symmetry, coord); + } board->ko = ko; - check_pat3_consistency(board, coord); + if (!u) check_pat3_consistency(board, coord); return !!group; } static int __attribute__((flatten)) -board_play_f(struct board *board, struct move *m, int f) +board_play_f(struct board *board, struct move *m, int f, struct board_undo *u) { if (DEBUGL(7)) { fprintf(stderr, "board_play(%s): ---- Playing %d,%d\n", coord2sstr(m->coord, board), coord_x(m->coord, board), coord_y(m->coord, board)); @@ -1386,24 +1533,46 @@ board_play_f(struct board *board, struct move *m, int f) /* NOT playing in an eye. Thus this move has to succeed. (This * is thanks to New Zealand rules. Otherwise, multi-stone * suicide might fail.) */ - group_t group = board_play_outside(board, m, f); + group_t group = board_play_outside(board, m, f, u); if (unlikely(board_group_captured(board, group))) { - board_group_capture(board, group); + if (u) undo_save_suicide(board, m->coord, m->color, u); + board_group_capture(board, group, u); + } + if (!u) { + board_hash_commit(board); + board_traits_recompute(board); } - board_hash_commit(board); - board_traits_recompute(board); return 0; } else { - return board_play_in_eye(board, m, f); + return board_play_in_eye(board, m, f, u); } } -int -board_play(struct board *board, struct move *m) +static void +undo_init(struct board *b, struct move *m, struct board_undo *u) +{ + // Paranoid uninitialized mem test + // memset(u, 0xff, sizeof(*u)); + + u->last_move2 = b->last_move2; + u->ko = b->ko; + u->last_ko = b->last_ko; + u->last_ko_age = b->last_ko_age; + u->captures = 0; + + u->nmerged = u->nmerged_tmp = u->nenemies = 0; + for (int i = 0; i < 4; i++) + u->merged[i].group = u->enemies[i].group = 0; +} + +static int +board_play_(struct board *board, struct move *m, struct board_undo *u) { #ifdef BOARD_UNDO_CHECKS - assert(!board->quicked); + assert(u || !board->quicked); #endif + + if (u) undo_init(board, m, u); if (unlikely(is_pass(m->coord) || is_resign(m->coord))) { if (is_pass(m->coord) && board->rules == RULES_SIMING) { @@ -1413,23 +1582,244 @@ board_play(struct board *board, struct move *m) } struct move nomove = { pass, S_NONE }; board->ko = nomove; - board->last_move4 = board->last_move3; - board->last_move3 = board->last_move2; + if (!u) { + board->last_move4 = board->last_move3; + board->last_move3 = board->last_move2; + } board->last_move2 = board->last_move; board->last_move = *m; return 0; } + if (u) + return board_play_f(board, m, -1, u); + int f; for (f = 0; f < board->flen; f++) if (board->f[f] == m->coord) - return board_play_f(board, m, f); + return board_play_f(board, m, f, u); if (DEBUGL(7)) fprintf(stderr, "board_check: stone exists\n"); return -1; } +int +board_play(struct board *board, struct move *m) +{ + return board_play_(board, m, NULL); +} + +int +board_quick_play(struct board *board, struct move *m, struct board_undo *u) +{ + int r = board_play_(board, m, u); +#ifdef BOARD_UNDO_CHECKS + if (r >= 0) + board->quicked++; +#endif + return r; +} + +static inline void +undo_merge(struct board *b, struct board_undo *u, struct move *m) +{ + coord_t coord = m->coord; + group_t group = group_at(b, coord); + struct undo_merge *merged = u->merged; + + // Others groups, in reverse order ... + for (int i = u->nmerged - 1; i > 0; i--) { + group_t old_group = merged[i].group; + + board_group_info(b, old_group) = merged[i].info; + + groupnext_at(b, group_base(group)) = groupnext_at(b, merged[i].last); + groupnext_at(b, merged[i].last) = 0; + +#if 0 + printf("merged_group[%i]: (last: %s)", i, coord2sstr(merged[i].last, b)); + foreach_in_group(b, old_group) { + printf("%s ", coord2sstr(c, b)); + } foreach_in_group_end; + printf("\n"); +#endif + + foreach_in_group(b, old_group) { + group_at(b, c) = old_group; + } foreach_in_group_end; + } + + // Restore first group + groupnext_at(b, u->inserted) = groupnext_at(b, coord); + board_group_info(b, merged[0].group) = merged[0].info; + +#if 0 + printf("merged_group[0]: "); + foreach_in_group(b, merged[0].group) { + printf("%s ", coord2sstr(c, b)); + } foreach_in_group_end; + printf("\n"); +#endif +} + + +static inline void +restore_enemies(struct board *b, struct board_undo *u, struct move *m) +{ + enum stone color = m->color; + enum stone other_color = stone_other(m->color); + + struct undo_enemy *enemy = u->enemies; + for (int i = 0; i < u->nenemies; i++) { + group_t old_group = enemy[i].group; + + board_group_info(b, old_group) = enemy[i].info; + + coord_t *stones = enemy[i].stones; + for (int j = 0; stones[j]; j++) { + board_at(b, stones[j]) = other_color; + group_at(b, stones[j]) = old_group; + groupnext_at(b, stones[j]) = stones[j + 1]; + + foreach_neighbor(b, stones[j], { + inc_neighbor_count_at(b, c, other_color); + }); + + // Update liberties of neighboring groups + foreach_neighbor(b, stones[j], { + if (board_at(b, c) != color) + continue; + group_t g = group_at(b, c); + if (g == u->merged[0].group || g == u->merged[1].group || g == u->merged[2].group || g == u->merged[3].group) + continue; + board_group_rmlib(b, g, stones[j], u); + }); + } + } +} + +static void +board_undo_stone(struct board *b, struct board_undo *u, struct move *m) +{ + coord_t coord = m->coord; + enum stone color = m->color; + /* - update groups + * - put captures back + */ + + //printf("nmerged: %i\n", u->nmerged); + + // Restore merged groups + if (u->nmerged) + undo_merge(b, u, m); + else // Single stone group undo + memset(&board_group_info(b, group_at(b, coord)), 0, sizeof(struct group)); + + board_at(b, coord) = S_NONE; + group_at(b, coord) = 0; + groupnext_at(b, coord) = u->next_at; + + foreach_neighbor(b, coord, { + dec_neighbor_count_at(b, c, color); + }); + + // Restore enemy groups + if (u->nenemies) { + b->captures[color] -= u->captures; + restore_enemies(b, u, m); + } +} + +static inline void +restore_suicide(struct board *b, struct board_undo *u, struct move *m) +{ + enum stone color = m->color; + enum stone other_color = stone_other(m->color); + + struct undo_enemy *enemy = u->enemies; + for (int i = 0; i < u->nenemies; i++) { + group_t old_group = enemy[i].group; + + board_group_info(b, old_group) = enemy[i].info; + + coord_t *stones = enemy[i].stones; + for (int j = 0; stones[j]; j++) { + board_at(b, stones[j]) = other_color; + group_at(b, stones[j]) = old_group; + groupnext_at(b, stones[j]) = stones[j + 1]; + + foreach_neighbor(b, stones[j], { + inc_neighbor_count_at(b, c, other_color); + }); + + // Update liberties of neighboring groups + foreach_neighbor(b, stones[j], { + if (board_at(b, c) != color) + continue; + group_t g = group_at(b, c); + if (g == u->enemies[0].group || g == u->enemies[1].group || + g == u->enemies[2].group || g == u->enemies[3].group) + continue; + board_group_rmlib(b, g, stones[j], u); + }); + } + } +} + + +static void +board_undo_suicide(struct board *b, struct board_undo *u, struct move *m) +{ + coord_t coord = m->coord; + enum stone other_color = stone_other(m->color); + + // Pretend it's capture ... + struct move m2 = { .coord = m->coord, .color = other_color }; + b->captures[other_color] -= u->captures; + + restore_suicide(b, u, &m2); + + undo_merge(b, u, m); + + board_at(b, coord) = S_NONE; + group_at(b, coord) = 0; + groupnext_at(b, coord) = u->next_at; + + foreach_neighbor(b, coord, { + dec_neighbor_count_at(b, c, m->color); + }); + +} + + +void +board_quick_undo(struct board *b, struct move *m, struct board_undo *u) +{ +#ifdef BOARD_UNDO_CHECKS + b->quicked--; +#endif + + b->last_move = b->last_move2; + b->last_move2 = u->last_move2; + b->ko = u->ko; + b->last_ko = u->last_ko; + b->last_ko_age = u->last_ko_age; + + if (unlikely(is_pass(m->coord) || is_resign(m->coord))) + return; + + b->moves--; + + if (likely(board_at(b, m->coord) == m->color)) + board_undo_stone(b, u, m); + else if (board_at(b, m->coord) == S_NONE) + board_undo_suicide(b, u, m); + else + assert(0); /* Anything else doesn't make sense */ +} + + /* Undo, supported only for pass moves. This form of undo is required by KGS * to settle disputes on dead groups. See also fast_board_undo() */ int board_undo(struct board *board) @@ -1460,7 +1850,7 @@ board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, || (permit && !permit(permit_data, b, &m))) return false; if (m.coord == *coord) { - return likely(board_play_f(b, &m, f) >= 0); + return likely(board_play_f(b, &m, f, NULL) >= 0); } else { *coord = m.coord; // permit modified the coordinate return likely(board_play(b, &m) >= 0); diff --git a/board_undo.c b/board_undo.c deleted file mode 100644 index 38d639c..0000000 --- a/board_undo.c +++ /dev/null @@ -1,797 +0,0 @@ -#include -#include -#include -#include -#include - -//#define DEBUG -#include "board.h" -#include "debug.h" - -#if 0 -#define profiling_noinline __attribute__((noinline)) -#else -#define profiling_noinline -#endif - -#define gi_granularity 4 -#define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity)) - - -int -board_quick_cmp(struct board *b1, struct board *b2) -{ - if (b1->size != b2->size || - b1->size2 != b2->size2 || - b1->bits2 != b2->bits2 || - b1->captures[S_BLACK] != b2->captures[S_BLACK] || - b1->captures[S_WHITE] != b2->captures[S_WHITE] || - b1->moves != b2->moves) { - fprintf(stderr, "differs in main vars\n"); - return 1; - } - if (move_cmp(&b1->last_move, &b2->last_move) || - move_cmp(&b1->last_move2, &b2->last_move2)) { - fprintf(stderr, "differs in last_move\n"); - return 1; - } - if (move_cmp(&b1->ko, &b2->ko) || - move_cmp(&b1->last_ko, &b2->last_ko) || - b1->last_ko_age != b2->last_ko_age) { - fprintf(stderr, "differs in ko\n"); - return 1; - } - - int bsize = board_size2(b1) * sizeof(*b1->b); - int gsize = board_size2(b1) * sizeof(*b1->g); - //int fsize = board_size2(b1) * sizeof(*b1->f); - int nsize = board_size2(b1) * sizeof(*b1->n); - int psize = board_size2(b1) * sizeof(*b1->p); - //int hsize = board_size2(b1) * 2 * sizeof(*b1->h); - int gisize = board_size2(b1) * sizeof(*b1->gi); - //int csize = board_size2(board) * sizeof(*b1->c); - //int ssize = board_size2(board) * sizeof(*b1->spathash); - //int p3size = board_size2(board) * sizeof(*b1->pat3); - //int tsize = board_size2(board) * sizeof(*b1->t); - //int tqsize = board_size2(board) * sizeof(*b1->t); - - //int cdsize = board_size2(b1) * sizeof(*b1->coord); - - if (memcmp(b1->b, b2->b, bsize)) { - fprintf(stderr, "differs in b\n"); return 1; } - if (memcmp(b1->g, b2->g, gsize)) { - fprintf(stderr, "differs in g\n"); return 1; } - if (memcmp(b1->n, b2->n, nsize)) { - fprintf(stderr, "differs in n\n"); return 1; } - if (memcmp(b1->p, b2->p, psize)) { - fprintf(stderr, "differs in p\n"); return 1; } - if (memcmp(b1->gi, b2->gi, gisize)) { - fprintf(stderr, "differs in gi\n"); return 1; } - - return 0; -} - - - -static void -board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid) -{ - /* Add extra liberty from the board to our liberty list. */ - unsigned char watermark[board_size2(board) / 8]; - memset(watermark, 0, sizeof(watermark)); -#define watermark_get(c) (watermark[c >> 3] & (1 << (c & 7))) -#define watermark_set(c) watermark[c >> 3] |= (1 << (c & 7)) - - for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++) - watermark_set(gi->lib[i]); - watermark_set(avoid); - - foreach_in_group(board, group) { - coord_t coord2 = c; - foreach_neighbor(board, coord2, { - if (board_at(board, c) + watermark_get(c) != S_NONE) - continue; - watermark_set(c); - gi->lib[gi->libs++] = c; - if (unlikely(gi->libs >= GROUP_KEEP_LIBS)) - return; - } ); - } foreach_in_group_end; -#undef watermark_get -#undef watermark_set -} - -static void -check_libs_consistency(struct board *board, group_t g) -{ } - -static void -board_group_addlib(struct board *board, group_t group, coord_t coord) -{ - if (DEBUGL(7)) { - fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n", - group_base(group), coord2sstr(group_base(group), board), - board_group_info(board, group).libs, coord2sstr(coord, board)); - } - - check_libs_consistency(board, group); - - struct group *gi = &board_group_info(board, group); - //bool onestone = group_is_onestone(board, group); - if (gi->libs < GROUP_KEEP_LIBS) { - for (int i = 0; i < GROUP_KEEP_LIBS; i++) { -#if 0 - /* Seems extra branch just slows it down */ - if (!gi->lib[i]) - break; -#endif - if (unlikely(gi->lib[i] == coord)) - return; - } - gi->lib[gi->libs++] = coord; - } - - check_libs_consistency(board, group); -} - - -static void -board_group_rmlib(struct board *board, group_t group, coord_t coord) -{ - if (DEBUGL(7)) { - fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n", - group_base(group), coord2sstr(group_base(group), board), - board_group_info(board, group).libs, coord2sstr(coord, board)); - } - - struct group *gi = &board_group_info(board, group); - //bool onestone = group_is_onestone(board, group); - for (int i = 0; i < GROUP_KEEP_LIBS; i++) { -#if 0 - /* Seems extra branch just slows it down */ - if (!gi->lib[i]) - break; -#endif - if (likely(gi->lib[i] != coord)) - continue; - - //coord_t lib = - gi->lib[i] = gi->lib[--gi->libs]; - gi->lib[gi->libs] = 0; - - check_libs_consistency(board, group); - - /* Postpone refilling lib[] until we need to. */ - assert(GROUP_REFILL_LIBS > 1); - if (gi->libs > GROUP_REFILL_LIBS) - return; - if (gi->libs == GROUP_REFILL_LIBS) - board_group_find_extra_libs(board, group, gi, coord); - - return; - } - - /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we - * can call this multiple times per coord. */ - check_libs_consistency(board, group); - return; -} - - -/* This is a low-level routine that doesn't maintain consistency - * of all the board data structures. */ -static void -board_remove_stone(struct board *board, group_t group, coord_t c) -{ - enum stone color = board_at(board, c); - board_at(board, c) = S_NONE; - group_at(board, c) = 0; - - /* Increase liberties of surrounding groups */ - coord_t coord = c; - foreach_neighbor(board, coord, { - dec_neighbor_count_at(board, c, color); - group_t g = group_at(board, c); - if (g && g != group) - board_group_addlib(board, g, coord); - }); -} - -static int profiling_noinline -board_group_capture(struct board *board, group_t group) -{ - int stones = 0; - - foreach_in_group(board, group) { - board->captures[stone_other(board_at(board, c))]++; - board_remove_stone(board, group, c); - stones++; - } foreach_in_group_end; - - struct group *gi = &board_group_info(board, group); - assert(gi->libs == 0); - memset(gi, 0, sizeof(*gi)); - - return stones; -} - -static void profiling_noinline -add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord) -{ - group_at(board, coord) = group; - groupnext_at(board, coord) = groupnext_at(board, prevstone); - groupnext_at(board, prevstone) = coord; - - foreach_neighbor(board, coord, { - if (board_at(board, c) == S_NONE) - board_group_addlib(board, group, c); - }); - - if (DEBUGL(8)) - fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n", - coord_x(prevstone, board), coord_y(prevstone, board), - coord_x(coord, board), coord_y(coord, board), - groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board), - group_base(group)); -} - -static void profiling_noinline -merge_groups(struct board *board, group_t group_to, group_t group_from, struct board_undo *u) -{ - if (DEBUGL(7)) - fprintf(stderr, "board_play_raw: merging groups %d -> %d\n", - group_base(group_from), group_base(group_to)); - struct group *gi_from = &board_group_info(board, group_from); - struct group *gi_to = &board_group_info(board, group_to); - // bool onestone_from = group_is_onestone(board, group_from); - // bool onestone_to = group_is_onestone(board, group_to); - - if (DEBUGL(7)) - fprintf(stderr,"---- (froml %d, tol %d)\n", gi_from->libs, gi_to->libs); - - if (gi_to->libs < GROUP_KEEP_LIBS) { - for (int i = 0; i < gi_from->libs; i++) { - for (int j = 0; j < gi_to->libs; j++) - if (gi_to->lib[j] == gi_from->lib[i]) - goto next_from_lib; - gi_to->lib[gi_to->libs++] = gi_from->lib[i]; - if (gi_to->libs >= GROUP_KEEP_LIBS) - break; -next_from_lib:; - } - } - - //if (gi_to->libs == 1) { - // coord_t lib = board_group_info(board, group_to).lib[0]; - //} - - coord_t last_in_group; - foreach_in_group(board, group_from) { - last_in_group = c; - group_at(board, c) = group_to; - } foreach_in_group_end; - - u->merged[++u->nmerged_tmp].last = last_in_group; - groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to)); - groupnext_at(board, group_base(group_to)) = group_base(group_from); - memset(gi_from, 0, sizeof(struct group)); - - if (DEBUGL(7)) - fprintf(stderr, "board_play_raw: merged group: %d\n", - group_base(group_to)); -} - - -static group_t profiling_noinline -new_group(struct board *board, coord_t coord) -{ - group_t group = coord; - struct group *gi = &board_group_info(board, group); - foreach_neighbor(board, coord, { - if (board_at(board, c) == S_NONE) - /* board_group_addlib is ridiculously expensive for us */ -#if GROUP_KEEP_LIBS < 4 - if (gi->libs < GROUP_KEEP_LIBS) -#endif - gi->lib[gi->libs++] = c; - }); - - group_at(board, coord) = group; - groupnext_at(board, coord) = 0; - - check_libs_consistency(board, group); - - if (DEBUGL(8)) - fprintf(stderr, "new_group: added %d,%d to group %d\n", - coord_x(coord, board), coord_y(coord, board), - group_base(group)); - - return group; -} - -static inline void -undo_save_merge(struct board *b, struct board_undo *u, group_t g, coord_t c) -{ - if (g == u->merged[0].group || g == u->merged[1].group || - g == u->merged[2].group || g == u->merged[3].group) - return; - - int i = u->nmerged++; - if (!i) - u->inserted = c; - u->merged[i].group = g; - u->merged[i].last = 0; // can remove - u->merged[i].info = board_group_info(b, g); -} - -static inline void -undo_save_enemy(struct board *b, struct board_undo *u, group_t g) -{ - if (g == u->enemies[0].group || g == u->enemies[1].group || - g == u->enemies[2].group || g == u->enemies[3].group) - return; - - int i = u->nenemies++; - u->enemies[i].group = g; - u->enemies[i].info = board_group_info(b, g); - - int j = 0; - coord_t *stones = u->enemies[i].stones; - if (board_group_info(b, g).libs <= 1) { // Will be captured - foreach_in_group(b, g) { - stones[j++] = c; - } foreach_in_group_end; - u->captures += j; - } - stones[j] = 0; -} - -static void -undo_save_group_info(struct board *b, coord_t coord, enum stone color, struct board_undo *u) -{ - u->next_at = groupnext_at(b, coord); - - foreach_neighbor(b, coord, { - group_t g = group_at(b, c); - - if (board_at(b, c) == color) - undo_save_merge(b, u, g, c); - else if (board_at(b, c) == stone_other(color)) - undo_save_enemy(b, u, g); - }); -} - -static void -undo_save_suicide(struct board *b, coord_t coord, enum stone color, struct board_undo *u) -{ - foreach_neighbor(b, coord, { - if (board_at(b, c) == color) { - // Handle suicide as a capture ... - undo_save_enemy(b, u, group_at(b, c)); - return; - } - }); - assert(0); -} - -static inline group_t -play_one_neighbor(struct board *board, - coord_t coord, enum stone color, enum stone other_color, - coord_t c, group_t group, struct board_undo *u) -{ - enum stone ncolor = board_at(board, c); - group_t ngroup = group_at(board, c); - - inc_neighbor_count_at(board, c, color); - if (!ngroup) - return group; - - board_group_rmlib(board, ngroup, coord); - if (DEBUGL(7)) - fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n", - group_base(ngroup), ncolor, color, other_color); - - if (ncolor == color && ngroup != group) { - if (!group) { - group = ngroup; - add_to_group(board, group, c, coord); - } else { - merge_groups(board, group, ngroup, u); - } - } else if (ncolor == other_color) { - if (DEBUGL(8)) { - struct group *gi = &board_group_info(board, ngroup); - fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board)); - for (int i = 0; i < GROUP_KEEP_LIBS; i++) - fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board)); - fprintf(stderr, "\n"); - } - if (unlikely(board_group_captured(board, ngroup))) - board_group_capture(board, ngroup); - } - return group; -} - - -/* We played on a place with at least one liberty. We will become a member of - * some group for sure. */ -static group_t profiling_noinline -board_play_outside(struct board *board, struct move *m, struct board_undo *u) -{ - coord_t coord = m->coord; - enum stone color = m->color; - enum stone other_color = stone_other(color); - group_t group = 0; - - undo_save_group_info(board, coord, color, u); - - foreach_neighbor(board, coord, { - group = play_one_neighbor(board, coord, color, other_color, c, group, u); - }); - - board_at(board, coord) = color; - if (unlikely(!group)) - group = new_group(board, coord); - - board->last_move2 = board->last_move; - board->last_move = *m; - board->moves++; - struct move ko = { pass, S_NONE }; - board->ko = ko; - - return group; -} - - -/* We played in an eye-like shape. Either we capture at least one of the eye - * sides in the process of playing, or return -1. */ -static int profiling_noinline -board_play_in_eye(struct board *board, struct move *m, struct board_undo *u) -{ - coord_t coord = m->coord; - enum stone color = m->color; - /* Check ko: Capture at a position of ko capture one move ago */ - if (unlikely(color == board->ko.color && coord == board->ko.coord)) { - if (DEBUGL(5)) - fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color); - return -1; - } else if (DEBUGL(6)) { - fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n", - color, coord_x(coord, board), coord_y(coord, board), - board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board)); - } - - struct move ko = { pass, S_NONE }; - - int captured_groups = 0; - - foreach_neighbor(board, coord, { - group_t g = group_at(board, c); - if (DEBUGL(7)) - fprintf(stderr, "board_check: group %d has %d libs\n", - g, board_group_info(board, g).libs); - captured_groups += (board_group_info(board, g).libs == 1); - }); - - if (likely(captured_groups == 0)) { - if (DEBUGL(5)) { - if (DEBUGL(6)) - board_print(board, stderr); - fprintf(stderr, "board_check: one-stone suicide\n"); - } - - return -1; - } - - undo_save_group_info(board, coord, color, u); - - int ko_caps = 0; - coord_t cap_at = pass; - foreach_neighbor(board, coord, { - inc_neighbor_count_at(board, c, color); - group_t group = group_at(board, c); - if (!group) - continue; - - board_group_rmlib(board, group, coord); - if (DEBUGL(7)) - fprintf(stderr, "board_play_raw: reducing libs for group %d\n", - group_base(group)); - - if (board_group_captured(board, group)) { - ko_caps += board_group_capture(board, group); - cap_at = c; - } - }); - if (ko_caps == 1) { - ko.color = stone_other(color); - ko.coord = cap_at; // unique - board->last_ko = ko; - board->last_ko_age = board->moves; - if (DEBUGL(5)) - fprintf(stderr, "guarding ko at %d,%s\n", ko.color, coord2sstr(ko.coord, board)); - } - - board_at(board, coord) = color; - group_t group = new_group(board, coord); - - board->last_move2 = board->last_move; - board->last_move = *m; - board->moves++; - board->ko = ko; - - return !!group; -} - - -static int __attribute__((flatten)) -board_play_f(struct board *board, struct move *m, struct board_undo *u) -{ - if (DEBUGL(7)) { - fprintf(stderr, "board_play(%s): ---- Playing %d,%d\n", coord2sstr(m->coord, board), coord_x(m->coord, board), coord_y(m->coord, board)); - } - if (likely(!board_is_eyelike(board, m->coord, stone_other(m->color)))) { - /* NOT playing in an eye. Thus this move has to succeed. (This - * is thanks to New Zealand rules. Otherwise, multi-stone - * suicide might fail.) */ - group_t group = board_play_outside(board, m, u); - if (unlikely(board_group_captured(board, group))) { - undo_save_suicide(board, m->coord, m->color, u); - board_group_capture(board, group); - } - return 0; - } else { - return board_play_in_eye(board, m, u); - } -} - -static void -undo_init(struct board *b, struct move *m, struct board_undo *u) -{ - // Paranoid uninitialized mem test - // memset(u, 0xff, sizeof(*u)); - - u->last_move2 = b->last_move2; - u->ko = b->ko; - u->last_ko = b->last_ko; - u->last_ko_age = b->last_ko_age; - u->captures = 0; - - u->nmerged = u->nmerged_tmp = u->nenemies = 0; - for (int i = 0; i < 4; i++) - u->merged[i].group = u->enemies[i].group = 0; -} - - -static inline int -board_quick_play_(struct board *board, struct move *m, struct board_undo *u) -{ - undo_init(board, m, u); - - if (unlikely(is_pass(m->coord) || is_resign(m->coord))) { - struct move nomove = { pass, S_NONE }; - board->ko = nomove; - board->last_move2 = board->last_move; - board->last_move = *m; - return 0; - } - - if (likely(board_at(board, m->coord) == S_NONE)) - return board_play_f(board, m, u); - - if (DEBUGL(7)) - fprintf(stderr, "board_check: stone exists\n"); - return -1; -} - -int -board_quick_play(struct board *board, struct move *m, struct board_undo *u) -{ - int r = board_quick_play_(board, m, u); -#ifdef BOARD_UNDO_CHECKS - if (r >= 0) - board->quicked++; -#endif - return r; -} - -/***********************************************************************************/ - -static inline void -undo_merge(struct board *b, struct board_undo *u, struct move *m) -{ - coord_t coord = m->coord; - group_t group = group_at(b, coord); - struct undo_merge *merged = u->merged; - - // Others groups, in reverse order ... - for (int i = u->nmerged - 1; i > 0; i--) { - group_t old_group = merged[i].group; - - board_group_info(b, old_group) = merged[i].info; - - groupnext_at(b, group_base(group)) = groupnext_at(b, merged[i].last); - groupnext_at(b, merged[i].last) = 0; - -#if 0 - printf("merged_group[%i]: (last: %s)", i, coord2sstr(merged[i].last, b)); - foreach_in_group(b, old_group) { - printf("%s ", coord2sstr(c, b)); - } foreach_in_group_end; - printf("\n"); -#endif - - foreach_in_group(b, old_group) { - group_at(b, c) = old_group; - } foreach_in_group_end; - } - - // Restore first group - groupnext_at(b, u->inserted) = groupnext_at(b, coord); - board_group_info(b, merged[0].group) = merged[0].info; - -#if 0 - printf("merged_group[0]: "); - foreach_in_group(b, merged[0].group) { - printf("%s ", coord2sstr(c, b)); - } foreach_in_group_end; - printf("\n"); -#endif -} - - -static inline void -restore_enemies(struct board *b, struct board_undo *u, struct move *m) -{ - enum stone color = m->color; - enum stone other_color = stone_other(m->color); - - struct undo_enemy *enemy = u->enemies; - for (int i = 0; i < u->nenemies; i++) { - group_t old_group = enemy[i].group; - - board_group_info(b, old_group) = enemy[i].info; - - coord_t *stones = enemy[i].stones; - for (int j = 0; stones[j]; j++) { - board_at(b, stones[j]) = other_color; - group_at(b, stones[j]) = old_group; - groupnext_at(b, stones[j]) = stones[j + 1]; - - foreach_neighbor(b, stones[j], { - inc_neighbor_count_at(b, c, other_color); - }); - - // Update liberties of neighboring groups - foreach_neighbor(b, stones[j], { - if (board_at(b, c) != color) - continue; - group_t g = group_at(b, c); - if (g == u->merged[0].group || g == u->merged[1].group || g == u->merged[2].group || g == u->merged[3].group) - continue; - board_group_rmlib(b, g, stones[j]); - }); - } - } -} - -static void -board_undo_stone(struct board *b, struct board_undo *u, struct move *m) -{ - coord_t coord = m->coord; - enum stone color = m->color; - /* - update groups - * - put captures back - */ - - //printf("nmerged: %i\n", u->nmerged); - - // Restore merged groups - if (u->nmerged) - undo_merge(b, u, m); - else // Single stone group undo - memset(&board_group_info(b, group_at(b, coord)), 0, sizeof(struct group)); - - board_at(b, coord) = S_NONE; - group_at(b, coord) = 0; - groupnext_at(b, coord) = u->next_at; - - foreach_neighbor(b, coord, { - dec_neighbor_count_at(b, c, color); - }); - - // Restore enemy groups - if (u->nenemies) { - b->captures[color] -= u->captures; - restore_enemies(b, u, m); - } -} - -static inline void -restore_suicide(struct board *b, struct board_undo *u, struct move *m) -{ - enum stone color = m->color; - enum stone other_color = stone_other(m->color); - - struct undo_enemy *enemy = u->enemies; - for (int i = 0; i < u->nenemies; i++) { - group_t old_group = enemy[i].group; - - board_group_info(b, old_group) = enemy[i].info; - - coord_t *stones = enemy[i].stones; - for (int j = 0; stones[j]; j++) { - board_at(b, stones[j]) = other_color; - group_at(b, stones[j]) = old_group; - groupnext_at(b, stones[j]) = stones[j + 1]; - - foreach_neighbor(b, stones[j], { - inc_neighbor_count_at(b, c, other_color); - }); - - // Update liberties of neighboring groups - foreach_neighbor(b, stones[j], { - if (board_at(b, c) != color) - continue; - group_t g = group_at(b, c); - if (g == u->enemies[0].group || g == u->enemies[1].group || g == u->enemies[2].group || g == u->enemies[3].group) - continue; - board_group_rmlib(b, g, stones[j]); - }); - } - } -} - - -static void -board_undo_suicide(struct board *b, struct board_undo *u, struct move *m) -{ - coord_t coord = m->coord; - enum stone other_color = stone_other(m->color); - - // Pretend it's capture ... - struct move m2 = { .coord = m->coord, .color = other_color }; - b->captures[other_color] -= u->captures; - - restore_suicide(b, u, &m2); - - undo_merge(b, u, m); - - board_at(b, coord) = S_NONE; - group_at(b, coord) = 0; - groupnext_at(b, coord) = u->next_at; - - foreach_neighbor(b, coord, { - dec_neighbor_count_at(b, c, m->color); - }); - -} - - - -void -board_quick_undo(struct board *b, struct move *m, struct board_undo *u) -{ -#ifdef BOARD_UNDO_CHECKS - b->quicked--; -#endif - - b->last_move = b->last_move2; - b->last_move2 = u->last_move2; - b->ko = u->ko; - b->last_ko = u->last_ko; - b->last_ko_age = u->last_ko_age; - - if (unlikely(is_pass(m->coord) || is_resign(m->coord))) - return; - - b->moves--; - - if (likely(board_at(b, m->coord) == m->color)) - board_undo_stone(b, u, m); - else if (board_at(b, m->coord) == S_NONE) - board_undo_suicide(b, u, m); - else - assert(0); /* Anything else doesn't make sense */ -} - -- 2.11.4.GIT