From de4f20f28afe23ecfc546ad242e5bb44710996cc Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Tue, 26 Jan 2021 17:42:53 -0500 Subject: Storing best moves! --- include/actions.c | 404 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 404 insertions(+) create mode 100644 include/actions.c (limited to 'include/actions.c') diff --git a/include/actions.c b/include/actions.c new file mode 100644 index 0000000..9b3534b --- /dev/null +++ b/include/actions.c @@ -0,0 +1,404 @@ +#include "actions.h" + +// =================================================================== +// Helper method declarations +// =================================================================== + +#define DANGER_MIN(a,b) (((a)<(b))?(a):(b)) + +#define CLR_STONE NUM_MASK + +#define TYPE_SHIFT 24 +#define LOC_SHIFT 16 +#define DATA0_SHIFT 8 + +#define GET_TYPE(a) (enum A_TYPE)((a)>>TYPE_SHIFT) +#define GET_LOC(a) (int8_t)(((a)>>LOC_SHIFT) & 0xFF) +#define GET_DATA0(a) (uint8_t)(((a)>>DATA0_SHIFT) & 0xFF) +#define GET_DATA1(a) (uint8_t)((a) & 0xFF) + +static inline void +list_append(action_list_t *list, const enum A_TYPE type, + const int8_t loc, const uint8_t data0, + const uint8_t data1); + +static inline void +inline_next_ply(void); + +static inline void +inline_prev_ply(void); + +// =================================================================== +// Exported method implementations +// =================================================================== + +int action_move_to_front(const action_t action, + action_list_t *list) { + action_node_t *n = list->head; + + // TODO: what if it's not in the list? + + while (n) { + if (n->action == action) { + const action_t t = list->head->action; + list->head->action = action; + n->action = t; + return EXIT_SUCCESS; + } + n = n->next; + } + + return EXIT_FAILURE; +} + + +void action_list_free(action_list_t *list) { + if (list) { + action_node_t *n = list->head, *nn; + while (n) { + nn = n->next; + free(n); + n = nn; + } + free(list); + } +} + +// Keep track of move offsets +static int8_t deltas[4]; + +void action_list_init(void) { + deltas[0] = +board_size; + deltas[1] = -board_size; + deltas[2] = -1; + deltas[3] = +1; +} + +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 = 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 + */ + 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++) { + // TODO: Generalise to board_size! + uint8_t gaps = 0x07 >> (board_size-steps-1); + // 0b0000[0111] 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_append(list, A_PLACE, loc, STONE_FLAT, 0); + if (standing) + list_append(list, A_PLACE, loc, STONE_STANDING,0); + } + if (cap) + list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0); + } + } + } + return list; +} + +void action_take(const action_t action) { + const int8_t loc = GET_LOC(action); + if (GET_TYPE(action) == A_PLACE) { + const uint8_t black = (current_colour == C_BLACK); + switch (GET_DATA0(action)) { + case STONE_FLAT: { + if (black) black_count--; + else white_count--; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_FLAT; + break; + } + case STONE_STANDING: { + if (black) black_count--; + else white_count--; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_STANDING; + break; + } + default: { + if (black) black_count &= 0x7F; + else white_count &= 0x7F; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_CAPSTONE; + break; + } + } + } else { + // not interested in whether we crushed, it will work out by + // anyway because we overwrite the top stone type. See (*) later + // for when we do need to know. + const uint8_t gaps = GET_DATA0(action) & 0x7F, + num = GET_DATA1(action) & 0x0F, // unpack + dir = GET_DATA1(action) >> 4; + int8_t delta = deltas[dir]; + + // Use the Kernighan method to count the set bits + int8_t steps = 1; + for (uint8_t _gaps = gaps; _gaps; steps++) _gaps &= _gaps - 1; + + // Move top stone type to destination + celldat[loc+steps*delta] &= CLR_STONE; // necessary for crushing + celldat[loc+steps*delta] |= STONE_AT(loc); + celldat[loc] &= CLR_STONE; + celldat[loc] |= STONE_FLAT; // should be optimised out + + uint8_t total = 1, gap_bit = 1 << (num - 2); // it's not important + // what negative + // shifts do here, we + // don't use gap_bit + // if num < 2 + // move stuff starting at destination + for (uint8_t d = 1; d < num; d++, total++, gap_bit >>= 1) { + // We took a step, move everything over so far + if (gaps & gap_bit) { + colours[loc+steps*delta] <<= total; + colours[loc+steps*delta] |= colours[loc] & ((1 << total) - 1); + colours[loc] >>= total; + celldat[loc+steps*delta] += total*NUM_INC; + celldat[loc] -= total*NUM_INC; + // Reset for next step + total = 0; + steps--; + } + } + // Move what remains (steps == 1 here always, so we simplify) + colours[loc+delta] <<= total; + colours[loc+delta] |= colours[loc] & ((1 << total) - 1); + colours[loc] >>= total; + celldat[loc+delta] += total*NUM_INC; + celldat[loc] -= total*NUM_INC; + } + // Next ply + inline_next_ply(); +} + +void action_undo(const action_t action) { + // Previous ply + inline_prev_ply(); + + const int8_t loc = GET_LOC(action); + if (GET_TYPE(action) == A_PLACE) { + const uint8_t black = (current_colour == C_BLACK); + celldat[loc] = 0; + if (GET_DATA0(action) == STONE_CAPSTONE) { + if (black) black_count |= 0x80; + else white_count |= 0x80; + } else { + if (black) black_count++; + else white_count++; + } + } else { + // See action_take for comments, this is the time reversal, but + // there is one caveat -- undoing a crush! (*) + const uint8_t gaps = GET_DATA0(action) & 0x7F, + crush = GET_DATA0(action) & 0x80, + num = GET_DATA1(action) & 0x0F, + dir = GET_DATA1(action) >> 4; + const int8_t delta = deltas[dir]; + + int8_t steps = 1; + uint8_t gap_bit = 1, total = 1; + for (int8_t d = 1; d < num; d++, total++, gap_bit <<= 1) { + if (gaps & gap_bit) { + colours[loc] <<= total; + colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1); + colours[loc+steps*delta] >>= total; + celldat[loc] += total*NUM_INC; + celldat[loc+steps*delta] -= total*NUM_INC; + total = 0; + steps++; + } + } + colours[loc] <<= total; + colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1); + colours[loc+steps*delta] >>= total; + + celldat[loc] += total*NUM_INC; + // celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0 + celldat[loc] |= STONE_AT(loc+steps*delta); + celldat[loc+steps*delta] -= total*NUM_INC; + celldat[loc+steps*delta] &= CLR_STONE; + if (crush) { + celldat[loc+steps*delta] |= STONE_STANDING; + } else { + celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out + } + } +} + +void action_to_ptn(const action_t action, char* out_ptn) { + const int8_t loc = GET_LOC(action); + if (GET_TYPE(action) == A_PLACE) { + generate_place(loc, GET_DATA0(action), out_ptn); + } else { + const uint8_t gaps = GET_DATA0(action) & 0x7F, + num = GET_DATA1(action) & 0x0F, // unpack + dir = GET_DATA1(action) >> 4; + + uint8_t drops[board_size]; // we only ever need board_size-1 in + // drops actually, the last spot is to + // skip a bounds check at (**) + uint8_t mask = 1, steps = 0; + // Translate to a drop sequence + drops[0] = 1; mask = 1; + for (uint8_t d = 1; d < num; d++) { + if (gaps & mask) { + steps++; + drops[steps] = 1; // (**) no bounds check + } else { + drops[steps] += 1; + } + mask <<= 1; + } + generate_move(loc, dir, steps+1, drops, out_ptn); + } +} + +// =================================================================== +// Helper method implementations +// =================================================================== + +static inline void +list_append(action_list_t *list, const enum A_TYPE type, + const int8_t loc, const uint8_t data0, + const uint8_t data1) { + action_node_t *new = malloc(sizeof(action_list_t)); + // TODO: trap errno + + new->next = NULL; + new->action = (type << TYPE_SHIFT) + | (loc << LOC_SHIFT) + | (data0 << DATA0_SHIFT) + | data1; + + if (list->length) { + list->tail->next = new; + list->tail = new; + } else { + list->head = new; + list->tail = new; + } + + list->length++; +} + +static inline void +inline_next_ply(void) { + ply++; + if (ply == 2) { + current_colour = C_WHITE; + } else { + if (current_colour == C_BLACK) current_colour = C_WHITE; + else current_colour = C_BLACK; + } +} + +static inline void +inline_prev_ply(void) { + if (ply>0) ply--; + if (ply == 1) { + current_colour = C_WHITE; + } else { + if (current_colour == C_BLACK) current_colour = C_WHITE; + else current_colour = C_BLACK; + } +} -- cgit v1.2.3