diff options
Diffstat (limited to 'include/actions.c')
| -rw-r--r-- | include/actions.c | 276 |
1 files changed, 149 insertions, 127 deletions
diff --git a/include/actions.c b/include/actions.c index 0b7d860..10cb74e 100644 --- a/include/actions.c +++ b/include/actions.c @@ -18,6 +18,21 @@ #include "actions.h" // =================================================================== +// Types +// =================================================================== + +typedef struct action_list_cache_s { + action_list_t *list; + // TODO: Add locks to ensure matches +} action_list_cache_t; + +// =================================================================== +// Variable +// =================================================================== + +static hashtable_t table; + +// =================================================================== // Helper method declarations // =================================================================== @@ -25,6 +40,8 @@ #define CLR_STONE NUM_MASK +static action_list_t *action_list_really_generate(void); + static inline void list_append(action_list_t *list, const enum A_TYPE type, const int8_t loc, const uint8_t data0, @@ -64,7 +81,6 @@ int action_move_to_front(const action_t action, return EXIT_FAILURE; } - void action_list_free(action_list_t *list) { if (list) { action_node_t *n = list->head, *nn; @@ -87,133 +103,9 @@ void action_list_init(void) { move_deltas[3] = +1; } -// We bias place over move by prepending place actions and appending -// move actions to the generated list -action_list_t *action_list_generate(void) { - action_list_t *list = malloc(sizeof(struct action_list_s)); - - // TODO: trap errno - list->length = 0; - list->head = NULL; - - /* - * The check for whether it's a black piece to be played is actually - * black = (ply < 2) ? (ply==1) : (ply & 1), - * but material will always be sufficient in ply < 2 so we might as - * well save on the conditional. - */ - - const uint8_t material = (ply & 1) ? black_count : white_count, - flat = material & 0x7F, - cap = ((ply >= 2) && (material & 0x80)), - standing = ((ply >= 2) && flat); - - // Step across the board - for (int row = 0; row < board_size; row++) { - for (int col = 0; col < board_size; col++) { - // We'll need these at various points: the location of this - // square and the maximum number of stones we could pick up - const int loc = THE_COORDS(col, row); - const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size); - - // Only try moves after CPS and if the colour is correct - if (count) { - if (ply >= 2 && ((colours[loc] & 1) == current_colour)) { - - // Pre-compute end-stops and crushes - uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0}; - - // These are upper bounds, not counting walls and such. - // UP DOWN LEFT RIGHT - end_stops[0] = DANGER_MIN(board_size - row - 1, count); - end_stops[1] = DANGER_MIN(row, count); - end_stops[2] = DANGER_MIN(col, count); - end_stops[3] = DANGER_MIN(board_size - col - 1, count); - - // Now we check for caps and walls - const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE; - for (int d = 0; d < 4; d++){ - const int delta = move_deltas[d]; - const int stop = end_stops[d]; - end_stops[d] = 0; - for (int k = 1; k <= stop; k++) { - const enum STONE_VARIANT stone = STONE_AT(loc+k*delta); - if (stone == STONE_STANDING) { - if (cap_top) { - crushes[d] = 0xFF; - end_stops[d]++; - } - break; - } else if (stone == STONE_CAPSTONE) { - break; - } - end_stops[d]++; - } - } - /* - * For each direction, generate all possible ordered integer - * partitions of 1 ≤ num ≤ count whose number of summands is - * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we - * write summands as steps. - * - * We exploit the `gaps' bijection here and elsewhere - * between ordered {integer partitions of n with s summands} - * and {binary strings of length n-1 with s-1 set bits}. - */ - for (enum MOVE_DIRECTION dir=M_UP; dir<=M_RIGHT; dir++) { - for (uint8_t num = 1; num <= count; num++) { - for (uint8_t steps = 1; - steps <= end_stops[dir] && steps <= num; - steps++) { - uint8_t gaps = - ((1<<(board_size - 2)) - 1) >> (board_size-steps-1); - // For 5x5 this givess 0b0000[0XXX] where steps-1 of - // those X's are 1s (starting with LSB) because 4-1=3 - // and 5-1=4 - do { - /* - * We skip the partition if it calls for multiple - * stones at the end with a crush. - */ - const uint8_t last_drop_check = - (num > 1) ? (gaps & (1 << (num - 2))) : 1; - if (crushes[dir] == 0 || last_drop_check) { - // We have to record a crush! - const uint8_t crush = - (steps == end_stops[dir]) && crushes[dir]; - // Store the move +action_list_t *action_list_generate(const uint64_t hash) { + // We're going to try our luck first in the table - list_append(list, A_MOVE, loc, - (crush << 7) | gaps, - (dir<<4) | num); - } - /* - * With thanks to - * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation - * we have the following magic to generate the next - * permutation of steps-many set bits - */ - uint8_t t = (gaps | (gaps - 1)); - gaps = (t + 1) - | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1)); - } while (gaps && (gaps + 1 <= (1 << (num - 1)))); - } - } - } - } - } // end of if (count) { ... } - else if (material) { - // Empty square, generate placements - if (flat) { - list_prepend(list, A_PLACE, loc, STONE_FLAT, 0); - if (standing) - list_prepend(list, A_PLACE, loc, STONE_STANDING,0); - } - if (cap) - list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0); - } - } - } return list; } @@ -382,6 +274,136 @@ void action_to_ptn(const action_t action, char* out_ptn) { // Helper method implementations // =================================================================== +// We bias place over move by prepending place actions and appending +// move actions to the generated list +action_list_t *action_list_really_generate(void) { + action_list_t *list = malloc(sizeof(struct action_list_s)); + + // TODO: trap errno + list->length = 0; + list->head = NULL; + + /* + * The check for whether it's a black piece to be played is actually + * black = (ply < 2) ? (ply==1) : (ply & 1), + * but material will always be sufficient in ply < 2 so we might as + * well save on the conditional. + */ + + const uint8_t material = (ply & 1) ? black_count : white_count, + flat = material & 0x7F, + cap = ((ply >= 2) && (material & 0x80)), + standing = ((ply >= 2) && flat); + + // Step across the board + for (int row = 0; row < board_size; row++) { + for (int col = 0; col < board_size; col++) { + // We'll need these at various points: the location of this + // square and the maximum number of stones we could pick up + const int loc = THE_COORDS(col, row); + const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size); + + // Only try moves after CPS and if the colour is correct + if (count) { + if (ply >= 2 && ((colours[loc] & 1) == current_colour)) { + + // Pre-compute end-stops and crushes + uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0}; + + // These are upper bounds, not counting walls and such. + // UP DOWN LEFT RIGHT + end_stops[0] = DANGER_MIN(board_size - row - 1, count); + end_stops[1] = DANGER_MIN(row, count); + end_stops[2] = DANGER_MIN(col, count); + end_stops[3] = DANGER_MIN(board_size - col - 1, count); + + // Now we check for caps and walls + const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE; + for (int d = 0; d < 4; d++){ + const int delta = move_deltas[d]; + const int stop = end_stops[d]; + end_stops[d] = 0; + for (int k = 1; k <= stop; k++) { + const enum STONE_VARIANT stone = STONE_AT(loc+k*delta); + if (stone == STONE_STANDING) { + if (cap_top) { + crushes[d] = 0xFF; + end_stops[d]++; + } + break; + } else if (stone == STONE_CAPSTONE) { + break; + } + end_stops[d]++; + } + } + /* + * For each direction, generate all possible ordered integer + * partitions of 1 ≤ num ≤ count whose number of summands is + * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we + * write summands as steps. + * + * We exploit the `gaps' bijection here and elsewhere + * between ordered {integer partitions of n with s summands} + * and {binary strings of length n-1 with s-1 set bits}. + */ + for (enum MOVE_DIRECTION dir=M_UP; dir<=M_RIGHT; dir++) { + for (uint8_t num = 1; num <= count; num++) { + for (uint8_t steps = 1; + steps <= end_stops[dir] && steps <= num; + steps++) { + uint8_t gaps = + ((1<<(board_size - 2)) - 1) >> (board_size-steps-1); + // For 5x5 this givess 0b0000[0XXX] where steps-1 of + // those X's are 1s (starting with LSB) because 4-1=3 + // and 5-1=4 + do { + /* + * We skip the partition if it calls for multiple + * stones at the end with a crush. + */ + const uint8_t last_drop_check = + (num > 1) ? (gaps & (1 << (num - 2))) : 1; + if (crushes[dir] == 0 || last_drop_check) { + // We have to record a crush! + const uint8_t crush = + (steps == end_stops[dir]) && crushes[dir]; + // Store the move + + list_append(list, A_MOVE, loc, + (crush << 7) | gaps, + (dir<<4) | num); + } + /* + * With thanks to + * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation + * we have the following magic to generate the next + * permutation of steps-many set bits + */ + uint8_t t = (gaps | (gaps - 1)); + gaps = (t + 1) + | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1)); + } while (gaps && (gaps + 1 <= (1 << (num - 1)))); + } + } + } + } + } // end of if (count) { ... } + else if (material) { + // Empty square, generate placements + if (flat) { + list_prepend(list, A_PLACE, loc, STONE_FLAT, 0); + if (standing) + list_prepend(list, A_PLACE, loc, STONE_STANDING,0); + } + if (cap) + list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0); + } + } + } + return list; +} + static inline void list_append(action_list_t *list, const enum A_TYPE type, const int8_t loc, const uint8_t data0, |