diff options
Diffstat (limited to 'include/actions.c')
| -rw-r--r-- | include/actions.c | 67 |
1 files changed, 31 insertions, 36 deletions
diff --git a/include/actions.c b/include/actions.c index 547024a..9b2ae0d 100644 --- a/include/actions.c +++ b/include/actions.c @@ -1,5 +1,5 @@ /* - This file is part of ct. + This file is part of ctak. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -12,16 +12,22 @@ General Public License for more details. You should have received a copy of the GNU General Public License - along with ct. If not, see <https://www.gnu.org/licenses/>. + along with ctak. If not, see <https://www.gnu.org/licenses/>. */ #include "actions.h" #include "tak.h" #include <stdio.h> +#include <stdlib.h> static uint8_t al_board_size; -static uint32_t upper_bound_moves; + +// Scratch move lists, one per recursion level. AL_MAX_ACTIONS is +// sized above the worst case for a 6x6 board (3269 moves). +#define AL_MAX_LEVELS 8 +#define AL_MAX_ACTIONS 4096 +static action_t al_scratch[AL_MAX_LEVELS][AL_MAX_ACTIONS]; // =================================================================== // Helper method declarations @@ -44,8 +50,6 @@ static inline uint8_t check_no_overflow(tak_state_p state, const uint8_t loc, // Exported method implementations // =================================================================== -inline void actions_free(action_t *actions) { free(actions); } - // Keep track of move offsets int8_t move_deltas[4]; @@ -55,27 +59,6 @@ void actions_init(const uint8_t 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 } inline char action_in_list(action_t action, action_t *actions, const uint32_t num_actions) { @@ -84,22 +67,31 @@ inline char action_in_list(action_t action, action_t *actions, const uint32_t nu return idx < num_actions; } -void action_move_to_front(action_t action, action_t *actions, - const uint32_t num_actions) { - (void) num_actions; // yolo +int action_move_to_front(action_t action, action_t *actions, + const uint32_t num_actions) { uint32_t idx; action_t prev = action, temp; - for (idx = 0; actions[idx] != action; idx++) { - temp = actions[idx]; - actions[idx] = prev; + for (idx = 0; idx < num_actions && actions[idx] != action; idx++) + ; + if (idx == num_actions) + return EXIT_FAILURE; // action not in list; nothing to do + for (uint32_t j = 0; j < idx; j++) { + temp = actions[j]; + actions[j] = prev; prev = temp; } actions[idx] = prev; + return EXIT_SUCCESS; +} + +action_t *actions_generate(tak_state_p state, uint32_t *num_actions) { + return actions_generate_at(state, num_actions, 0); } // 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) { +action_t *actions_generate_at(tak_state_p state, uint32_t *num_actions, + const uint32_t level) { /* * The check for whether it's a black piece to be played is actually * black = (ply < 2) ? (ply==1) : (ply & 1), @@ -124,9 +116,12 @@ action_t *actions_generate(tak_state_p state, uint32_t *num_actions) { } } - // TODO: trap errno - action_t *actions = - malloc(sizeof(action_t) * (placements + upper_bound_moves)); + if (level >= AL_MAX_LEVELS) { + fprintf(stderr, "actions_generate_at: level %u exceeds AL_MAX_LEVELS\n", + level); + abort(); + } + action_t *actions = al_scratch[level]; uint32_t total = 0, move_idx = placements, place_idx = placements; // Step across the board |