diff options
Diffstat (limited to 'include/actions.c')
| -rw-r--r-- | include/actions.c | 165 |
1 files changed, 75 insertions, 90 deletions
diff --git a/include/actions.c b/include/actions.c index 6303822..547024a 100644 --- a/include/actions.c +++ b/include/actions.c @@ -21,6 +21,7 @@ #include <stdio.h> static uint8_t al_board_size; +static uint32_t upper_bound_moves; // =================================================================== // Helper method declarations @@ -30,14 +31,6 @@ static uint8_t al_board_size; #define CLR_STONE NUM_MASK -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 list_prepend(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(tak_state_p state); static inline void inline_prev_ply(tak_state_p state); @@ -51,56 +44,62 @@ static inline uint8_t check_no_overflow(tak_state_p state, const uint8_t loc, // 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); - } -} +inline void actions_free(action_t *actions) { free(actions); } // Keep track of move offsets int8_t move_deltas[4]; -void action_list_init(const uint8_t board_size) { +void actions_init(const uint8_t board_size) { al_board_size = board_size; move_deltas[0] = +board_size; move_deltas[1] = -board_size; move_deltas[2] = -1; move_deltas[3] = +1; + + const uint32_t five_cumulative_partitions = 7 + 5 + 3 + 2 + 1; // 18 + const uint32_t six_cumulative_partitions = + 11 + five_cumulative_partitions; // 29 + if (board_size == 5) { + // 26 = 3*3 + 4*3 + 1 + + // which means central squares (4 dirs), sides (3 dirs), one corner (2 dirs) + upper_bound_moves = 4 * 3 * 3 + 3 * 4 * 3 + 2 * 1; + upper_bound_moves *= five_cumulative_partitions; + } else { + // 31 = 4*4 + 3*4 + 3 + + // which means central squares (4 dirs), three sides (3 dirs) and an extra + // three squares on the last side (1 dir) + upper_bound_moves = 4 * 4 * 4 + 3 * 3 * 4 + 3 * 3; + upper_bound_moves *= six_cumulative_partitions; + } + // In summary, using typedef uint32_t action_t + // 74 * 18 = 1332 for 5x5, ~5.2 Kb + // 109 * 29 = 3161 for 6x6, ~12.3 Kb } -// We bias place over move by prepending place actions and appending -// move actions to the generated list -action_list_t *action_list_generate(tak_state_p state) { - action_list_t *list = malloc(sizeof(struct action_list_s)); +inline char action_in_list(action_t action, action_t *actions, const uint32_t num_actions) { + uint32_t idx; + for (idx = 0; idx < num_actions && actions[idx] != action; idx++); + return idx < num_actions; +} - // TODO: trap errno - list->length = 0; - list->head = NULL; +void action_move_to_front(action_t action, action_t *actions, + const uint32_t num_actions) { + (void) num_actions; // yolo + uint32_t idx; + action_t prev = action, temp; + for (idx = 0; actions[idx] != action; idx++) { + temp = actions[idx]; + actions[idx] = prev; + prev = temp; + } + actions[idx] = prev; +} +// We bias place over move by prepending place actions and appending +// move actions to the generated list +action_t *actions_generate(tak_state_p state, uint32_t *num_actions) { /* * The check for whether it's a black piece to be played is actually * black = (ply < 2) ? (ply==1) : (ply & 1), @@ -114,6 +113,22 @@ action_list_t *action_list_generate(tak_state_p state) { cap = ((state->ply >= 2) && (material & 0x80)), standing = ((state->ply >= 2) && flat); + // Count placement options + uint32_t placements = 0; + const uint32_t how_many = (flat ? 1 : 0) + (cap ? 1 : 0) + (standing ? 1 : 0); + for (int row = 0; row < state->board_size; row++) { + for (int col = 0; col < state->board_size; col++) { + const int l = THE_COORDS(al_board_size, col, row); + if (COUNT_AT(state, l) == 0) + placements += how_many; + } + } + + // TODO: trap errno + action_t *actions = + malloc(sizeof(action_t) * (placements + upper_bound_moves)); + uint32_t total = 0, move_idx = placements, place_idx = placements; + // Step across the board for (int row = 0; row < state->board_size; row++) { for (int col = 0; col < state->board_size; col++) { @@ -192,9 +207,10 @@ action_list_t *action_list_generate(tak_state_p state) { can_and_must_crush || crushes[dir] != steps; if (no_overflow && crush_check) { // Store the move - list_append(list, A_MOVE, loc, - (can_and_must_crush << 7) | gaps, + actions[move_idx++] = + A_BUILD(A_MOVE, loc, (can_and_must_crush << 7) | gaps, (dir << 4) | num); + total++; } /* * With thanks to @@ -214,16 +230,22 @@ action_list_t *action_list_generate(tak_state_p state) { 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); + actions[--place_idx] = A_BUILD(A_PLACE, loc, STONE_FLAT, 0); + total++; + if (standing) { + actions[--place_idx] = A_BUILD(A_PLACE, loc, STONE_STANDING, 0); + total++; + } + } + if (cap) { + actions[--place_idx] = A_BUILD(A_PLACE, loc, STONE_CAPSTONE, 0); + total++; } - if (cap) - list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0); } } } - return list; + *num_actions = total; + return actions; } void action_take(tak_state_p state, const action_t action) { @@ -406,43 +428,6 @@ void action_to_ptn(const action_t action, char *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_node_t)); - // TODO: trap errno - - new->next = NULL; - new->action = A_BUILD(type, loc, data0, data1); - - if (list->length) { - list->tail->next = new; - list->tail = new; - } else { - list->head = new; - list->tail = new; - } - - list->length++; -} - -static inline void list_prepend(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 = list->head; - list->head = new; - new->action = A_BUILD(type, loc, data0, data1); - - if (list->length == 0) { - list->tail = new; - } - - list->length++; -} - static inline void inline_next_ply(tak_state_p state) { state->ply++; if (state->ply == 2) { |