diff options
Diffstat (limited to 'include/tak.c')
| -rw-r--r-- | include/tak.c | 214 |
1 files changed, 117 insertions, 97 deletions
diff --git a/include/tak.c b/include/tak.c index 406f8b5..e9f27ff 100644 --- a/include/tak.c +++ b/include/tak.c @@ -50,6 +50,7 @@ void reset_state(tak_state_p state, const uint8_t new_board_size) { state->ply = 0; state->won = 0xFF; // i may live to regret this hack state->current_colour = C_BLACK; + state->hash = 0; // empty board, ply 0 for (uint8_t k = 0; k < NUM_SQUARES(new_board_size); k++) { state->celldat[k] = 0; @@ -154,7 +155,7 @@ enum ACT_RESULT try_move(tak_state_p state, const int8_t location, if (avail == 0) return ACT_ILLEGAL; // Does the current player own the pile? - if ((state->colours[location] & 1) != state->current_colour) + if (TOP_COLOUR_AT(state, location) != state->current_colour) return ACT_ILLEGAL; // Is the desired direction and count on the board? int8_t delta = 0; @@ -239,25 +240,40 @@ enum ACT_RESULT try_move(tak_state_p state, const int8_t location, // Checking win // =================================================================== -// Check for the presence of a road connecting opposite sides -static enum WIN_TYPE check_road_colour(tak_state_p state, - const enum COLOUR colour) { - int component[NUM_SQUARES(state->board_size)], +// Sides of the board a connected component can touch +#define SIDE_BOTTOM 0x1 // row 0 +#define SIDE_TOP 0x2 // last row +#define SIDE_LEFT 0x4 // column 0 +#define SIDE_RIGHT 0x8 // last column +#define SIDES_BOTTOM_TOP (SIDE_BOTTOM | SIDE_TOP) +#define SIDES_LEFT_RIGHT (SIDE_LEFT | SIDE_RIGHT) + +// One bit per colour, set once a road for that colour has been found +#define ROAD_WHITE (1u << C_WHITE) +#define ROAD_BLACK (1u << C_BLACK) +#define ROAD_BOTH (ROAD_WHITE | ROAD_BLACK) + +enum WIN_TYPE check_win(tak_state_p state) { + uint8_t component[NUM_SQUARES(state->board_size)], touching[NUM_SQUARES(state->board_size)]; /* - We're doing a poor version of a disjoint set data structure to - track and merge connected components. The array `component' stores - indices to the representative cells of each connected component. A - cell is representative if component[cell] = cell. We track only - whether representatives are touching sides, and do a 2-dimensional - DP approach to forming these from the board. + We're doing a poor version of a disjoint set data structure to track and + merge connected components. The array `component' stores indices to the + representative cells of each connected component. A cell is representative + if component[cell] = cell. We track only whether representatives are + touching sides, and do a 2-dimensional DP approach to forming these from the + board. Note: we don't track the rank/size of each tree, because we're not - interested in good asymptotic complexity in the size of the board, - merely good performance for a single board size in practice. For - the same reason we also don't do path flattening/halving or - anything. + interested in good asymptotic complexity in the size of the board, merely + good performance for a single board size in practice. For the same reason we + also don't do path flattening/halving or anything. + + A cell is road-eligible only for the colour of its top stone, so black and + white components are disjoint and can share one component/touching pair, + letting us check both colours (and count top-flat stones) in a single pass. + The dragon rule needs the road status of both colours. */ for (int k = 0; k < NUM_SQUARES(state->board_size); k++) { component[k] = k; // every square is in its own connected @@ -265,97 +281,110 @@ static enum WIN_TYPE check_road_colour(tak_state_p state, touching[k] = 0; // and not connected to any sides } - // touching is the bit mask for connectivity, - // bottom | top | left | right - // 1 2 4 8 + uint8_t road = 0; + + // flat count: +1 per top-flat black stone, -1 per top-flat white + int8_t total = 0; + uint8_t board_full = 1; - int touch = 5; + int touch = SIDE_BOTTOM | SIDE_LEFT; for (int row = 0; row < state->board_size; row++) { for (int col = 0; col < state->board_size; col++) { const int cur = THE_COORDS(state->board_size, col, row); - if (COUNT_AT(state, cur) && (state->colours[cur] & 1) == colour && - STONE_AT(state, cur) != STONE_STANDING) { + const uint8_t count = COUNT_AT(state, cur); + if (count == 0) { + board_full = 0; + } else if (STONE_AT(state, cur) == STONE_FLAT) { + total += (TOP_COLOUR_AT(state, cur) == C_BLACK) ? +1 : -1; + } - // do we have any neighbours to the left and below? - const int left_neighbour = - ((cur % state->board_size > 0) && - (COUNT_AT(state, cur - 1)) // wont ever be out of bounds - && ((state->colours[cur - 1] & 1) == colour) && - (STONE_AT(state, cur - 1) != STONE_STANDING)); + if (count && STONE_AT(state, cur) != STONE_STANDING) { + const uint8_t colour = TOP_COLOUR_AT(state, cur); + const uint8_t done = 1u << colour; + if ((road & done) == 0) { - const int lowr_neighbour = - ((cur >= state->board_size) && - (COUNT_AT(state, cur - state->board_size)) && - ((state->colours[cur - state->board_size] & 1) == colour) && - (STONE_AT(state, cur - state->board_size) != STONE_STANDING)); + // do we have any neighbours to the left and below? + const int left_neighbour = + ((cur % state->board_size > 0) && + (COUNT_AT(state, cur - 1)) // wont ever be out of bounds + && (TOP_COLOUR_AT(state, cur - 1) == colour) && + (STONE_AT(state, cur - 1) != STONE_STANDING)); - // always take the component of the lower neighbour if - // possible, failing that take the left neighbour, otherwise - // we're not yet connected, so update our own component. - if (lowr_neighbour) { - // look up the root of the lower neighbour - int root = cur - state->board_size; - while (root != component[root]) - root = component[root]; - // join the set - component[cur] = root; - if (touch) { - // something new - touching[root] |= touch; - // are we done? - if ((touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC) - return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; - } - // if we also have a left neighbour then we should `merge' - // sets, and here we assume that the left neighbour set is - // always smaller (may not be) for the direction of merge - if (left_neighbour) { - int left_root = cur - 1; - while (left_root != component[left_root]) - left_root = component[left_root]; - // merge - const int left_touch = touching[left_root]; - if (left_touch) { - touching[root] |= left_touch; - if ((touching[root] & 0x3) == 0x3 || - (touching[root] & 0xC) == 0xC) - return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; + const int lowr_neighbour = + ((cur >= state->board_size) && + (COUNT_AT(state, cur - state->board_size)) && + (TOP_COLOUR_AT(state, cur - state->board_size) == colour) && + (STONE_AT(state, cur - state->board_size) != STONE_STANDING)); + + // always take the component of the lower neighbour if + // possible, failing that take the left neighbour, otherwise + // we're not yet connected, so update our own component. + if (lowr_neighbour) { + // look up the root of the lower neighbour + int root = cur - state->board_size; + while (root != component[root]) + root = component[root]; + // join the set + component[cur] = root; + if (touch) { + // something new + touching[root] |= touch; + // are we done? + if ((touching[root] & SIDES_BOTTOM_TOP) == SIDES_BOTTOM_TOP || + (touching[root] & SIDES_LEFT_RIGHT) == SIDES_LEFT_RIGHT) + road |= done; } - component[left_root] = root; - } - } else if (left_neighbour) { - int root = cur - 1; - while (root != component[root]) - root = component[root]; - component[cur] = root; - if (touch) { - touching[root] |= touch; - if ((touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC) - return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; + // if we also have a left neighbour then we should `merge' + // sets, and here we assume that the left neighbour set is + // always smaller (may not be) for the direction of merge + if (left_neighbour) { + int left_root = cur - 1; + while (left_root != component[left_root]) + left_root = component[left_root]; + // merge + const int left_touch = touching[left_root]; + if (left_touch) { + touching[root] |= left_touch; + if ((touching[root] & SIDES_BOTTOM_TOP) == SIDES_BOTTOM_TOP || + (touching[root] & SIDES_LEFT_RIGHT) == SIDES_LEFT_RIGHT) + road |= done; + } + component[left_root] = root; + } + } else if (left_neighbour) { + int root = cur - 1; + while (root != component[root]) + root = component[root]; + component[cur] = root; + if (touch) { + touching[root] |= touch; + if ((touching[root] & SIDES_BOTTOM_TOP) == SIDES_BOTTOM_TOP || + (touching[root] & SIDES_LEFT_RIGHT) == SIDES_LEFT_RIGHT) + road |= done; + } + } else if (touch) { + // we had no left or lower neighbour, so we're on our own + touching[cur] = touch; } - } else if (touch) { - // we had no left or lower neighbour, so we're on our own - touching[cur] = touch; + if (road == ROAD_BOTH) + break; // both colours decided, the scan is done } } if (col + 2 == state->board_size) - touch |= 8; + touch |= SIDE_RIGHT; else - touch &= 0x3; + touch &= (SIDE_BOTTOM | SIDE_TOP); } if (row + 2 == state->board_size) - touch = 6; + touch = SIDE_TOP | SIDE_LEFT; else - touch = 4; + touch = SIDE_LEFT; + if (road == ROAD_BOTH) + break; } - return 0xFF; -} -enum WIN_TYPE check_win(tak_state_p state) { - // Road? - enum WIN_TYPE rb, rw; - rb = check_road_colour(state, C_BLACK); - rw = check_road_colour(state, C_WHITE); + const enum WIN_TYPE rw = (road & ROAD_WHITE) ? WIN_ROAD_WHITE : 0xFF, + rb = (road & ROAD_BLACK) ? WIN_ROAD_BLACK : 0xFF; if (rb == WIN_ROAD_BLACK && rw == WIN_ROAD_WHITE) { return (state->ply & 1) ? rb : rw; // Dragons @@ -365,15 +394,6 @@ enum WIN_TYPE check_win(tak_state_p state) { return rb; } - // Do we do a flat count? - int8_t total = 0, board_full = 1; - for (uint8_t k = 0; k < NUM_SQUARES(state->board_size); k++) { - if (COUNT_AT(state, k) == 0) { - board_full = 0; - } else if (STONE_AT(state, k) == STONE_FLAT) { - total += ((state->colours[k] & 1) == C_BLACK) ? +1 : -1; - } - } if (state->black_count == 0 || state->white_count == 0 || board_full) { // Decide based on count if (total > 0) |