From 07c5dded49d5943f54cca0c75a7a93a30ee2f323 Mon Sep 17 00:00:00 2001 From: tslil Date: Fri, 2 Jul 2021 12:00:00 -0400 Subject: More towel wringing: re-implemented check_road_colour Previously check_win would call check_road_colour once for each road colour, and check_road_colour would call a depth-first search (DFS) for each of the two axes. This meant that we were doing (up to) *four* depth-first searches for each call of check_win. I have replaced both axial DFS with the world's worst TM implementation of a connected component generation algorithm backed by the least guaranteed disjoint set data structure. Essentially doing anything about union find correctly is slower than just ... not doing it. Although we lose the asymptotic complexity, in practice we're doing this millions of times per turn, for a fixed board size and that's what matters. All in all, it appears that i've managed to shave about 69ns off check_win, per call -- nice! This amounts to 50ms or so saved at depth 5 per engine move, in one of my test games. Unfortunately nearly 99% of the time is still taken by evaluating the convolutional neural network. It's slow. --- include/tak.c | 295 +++++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 191 insertions(+), 104 deletions(-) (limited to 'include/tak.c') diff --git a/include/tak.c b/include/tak.c index 78d3854..962dba6 100644 --- a/include/tak.c +++ b/include/tak.c @@ -32,9 +32,6 @@ uint8_t white_count, black_count, ply; // Helpers // =================================================================== -#define DFS_MASK 0x0C // 0b00001100 -#define NOT_DFS_MASK 0xF3 // 0b11110011 - #define NUM_SQUARES (board_size * board_size) // =================================================================== @@ -233,109 +230,202 @@ try_move(const int8_t location, const enum MOVE_DIRECTION direction, // Checking win // =================================================================== -// Depth-first search of the board for a road with a given -// directionality: -// direction = 0 --> left-to-right, direction = 1 --> bottom-to-top -static uint8_t -dfs_road(uint8_t dfs_stack[NUM_SQUARES], uint8_t dfs_pntr, - const enum COLOUR colour, const uint8_t direction) { - while (dfs_pntr > 0) { - const uint8_t cur = dfs_stack[--dfs_pntr]; - // Made it to the other side? - if ( (direction == 1 && cur >= board_size * (board_size - 1)) - || (direction == 0 && cur % board_size + 1 == board_size) ) - return 1; - - // Check the four neighbours of this cell, provided they exist, - // are inhabited, and are of the appropriate colour - - // Direction: > (same row) - if ( ((cur % board_size) + 1 < board_size) - && (COUNT_AT(cur + 1)) // wont ever be out of bounds - && ((colours[cur+1] & 1) == colour) - && ((celldat[cur+1] & DFS_MASK) == 0) - && (STONE_AT(cur+1) != STONE_STANDING)) { - dfs_stack[dfs_pntr++] = cur + 1; - celldat[cur+1] |= DFS_MASK; - } - - // Direction: < (same row) - if ( (cur % board_size > 0) - && (COUNT_AT(cur - 1)) // wont ever be out of bounds - && ((colours[cur-1] & 1) == colour) - && ((celldat[cur-1] & DFS_MASK) == 0) - && (STONE_AT(cur-1) != STONE_STANDING)) { - dfs_stack[dfs_pntr++] = cur - 1; - celldat[cur-1] |= DFS_MASK; - } - - // Direction: + - if ( (cur + board_size < NUM_SQUARES) - && (COUNT_AT(cur + board_size)) - && ((colours[cur+board_size] & 1) == colour) - && ((celldat[cur+board_size] & DFS_MASK) == 0) - && (STONE_AT(cur+board_size) != STONE_STANDING)) { - dfs_stack[dfs_pntr++] = cur + board_size; - celldat[cur+board_size] |= DFS_MASK; - } - - // Direction: - - if ( (cur >= board_size) - && (COUNT_AT(cur - board_size)) - && ((colours[cur-board_size] & 1) == colour) - && ((celldat[cur-board_size] & DFS_MASK) == 0) - && (STONE_AT(cur-board_size) != STONE_STANDING)) { - dfs_stack[dfs_pntr++] = cur - board_size; - celldat[cur-board_size] |= DFS_MASK; - } - } - return 0; -} - +// Check for the presence of a road connecting opposite sides static enum WIN_TYPE check_road_colour(const enum COLOUR colour) { - uint8_t dfs_stack[NUM_SQUARES]; - uint8_t dfs_pntr; - - // Prime the depth-first-search stack with all boundary cells of - // colour COLOUR. - - const enum WIN_TYPE winner = - (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; - - // We're using the two left-over bits in data_t to track whether - // we've seen it. Reset those before anything. - - for (uint8_t k=0; k 0) + && (COUNT_AT(cur - 1)) // wont ever be out of bounds + && ((colours[cur - 1] & 1) == colour) + && (STONE_AT(cur - 1) != STONE_STANDING)); + + const int lowr_neighbour = ((cur >= board_size) + && (COUNT_AT(cur - board_size)) + && ((colours[cur - board_size] & 1) == colour) + && (STONE_AT(cur - 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 - 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; + } + 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; + } + } else if (touch) { + // we had no left or lower neighbour, so we're on our own + touching[cur] = touch; + } + } + if (col + 2 == board_size) touch |= 8; + else touch &= 0x3; } + if (row + 2 == board_size) touch = 6; + else touch = 4; } - if (dfs_road(dfs_stack, dfs_pntr, colour, 1)) return winner; + + /* + * // Prime the search, we create connected components for all cells + * // that match COLOUR and aren't STANDING on the boundaries + * if ( COUNT_AT(0) && (colours[0] & 1) == colour + * && STONE_AT(0) != STONE_STANDING ) { + * connect[comp_idx++] = 3; + * } + * for (uint8_t k=1; k 0) { + * const uint8_t cur = dfs_stack[--dfs_pntr]; + * // Made it to the other side? + * if ( (cur >= board_size * (board_size - 1) && bottoms[cur]) + * || (cur % board_size + 1 == board_size && lefts[cur]) ) + * { + * return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; + * } + * + * // Check the four neighbours of this cell, provided they exist, + * // are inhabited, and are of the appropriate colour + * + * // Direction: > (same row) + * if ( ((cur % board_size) + 1 < board_size) + * && (COUNT_AT(cur + 1)) // wont ever be out of bounds + * && ((colours[cur+1] & 1) == colour) + * && ((seen[cur+1]) == 0) + * && (STONE_AT(cur+1) != STONE_STANDING)) { + * dfs_stack[dfs_pntr++] = cur + 1; + * seen[cur+1] = 1; + * lefts[cur+1] = lefts[cur]; + * bottoms[cur+1] = bottoms[cur]; + * } + * + * // Direction: < (same row) + * if ( (cur % board_size > 0) + * && (COUNT_AT(cur - 1)) // wont ever be out of bounds + * && ((colours[cur-1] & 1) == colour) + * && ((seen[cur-1]) == 0) + * && (STONE_AT(cur-1) != STONE_STANDING)) { + * dfs_stack[dfs_pntr++] = cur - 1; + * seen[cur - 1] = 1; + * lefts[cur-1] = lefts[cur]; + * bottoms[cur-1] = bottoms[cur]; + * } + * + * // Direction: + + * if ( (cur + board_size < NUM_SQUARES) + * && (COUNT_AT(cur + board_size)) + * && ((colours[cur+board_size] & 1) == colour) + * && ((seen[cur+board_size]) == 0) + * && (STONE_AT(cur+board_size) != STONE_STANDING)) { + * dfs_stack[dfs_pntr++] = cur + board_size; + * seen[cur+board_size] = 1; + * lefts[cur+board_size] = lefts[cur]; + * bottoms[cur+board_size] = bottoms[cur]; + * } + * + * // Direction: - + * if ( (cur >= board_size) + * && (COUNT_AT(cur - board_size)) + * && ((colours[cur-board_size] & 1) == colour) + * && ((seen[cur-board_size]) == 0) + * && (STONE_AT(cur-board_size) != STONE_STANDING)) { + * dfs_stack[dfs_pntr++] = cur - board_size; + * seen[cur-board_size] = 1; + * lefts[cur-board_size] = lefts[cur]; + * bottoms[cur-board_size] = bottoms[cur]; + * } + * } + */ return 0xFF; } @@ -346,9 +436,6 @@ check_win(void) { enum WIN_TYPE rb, rw; rb = check_road_colour(C_BLACK); rw = check_road_colour(C_WHITE); - for (uint8_t k=0; k