From f0139acd1d648dd1db93ee3d3b75546fb7b24c77 Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Sun, 29 Jan 2023 20:49:04 +0100 Subject: switch to returning an array of actions instead of a linked list - attempts to keep the same move ordering as the list method - saves ~170msec on a depth 7 search for a given board configuration - there is room to improve the pre-allocation size estimates, these bounds are not obviously tight and it may or may not be faster to have tighter bounds or even some form of estimation --- include/negamax.c | 29 +++++++++++++++-------------- 1 file changed, 15 insertions(+), 14 deletions(-) (limited to 'include/negamax.c') diff --git a/include/negamax.c b/include/negamax.c index 584b43c..dd769ad 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -41,7 +41,7 @@ static float negamax(tak_state_p state, const uint8_t cur_depth, // =================================================================== void negamax_init(const uint8_t new_board_size) { - action_list_init(new_board_size); + actions_init(new_board_size); zobrist_init(new_board_size); tt_init(); @@ -102,26 +102,27 @@ static float negamax(tak_state_p state, const uint8_t cur_depth, return entry->value; } - action_list_t *list; - if ((list = action_list_generate(state)) == NULL) + action_t *actions; + uint32_t num_actions; + if ((actions = actions_generate(state, &num_actions)) == NULL) return alpha; // should never happen! - if (entry != NULL) { - action_move_to_front(entry->action, list); + // How did we land up with impossible actions for this hash? + if (entry != NULL && action_in_list(entry->action, actions, num_actions)) { + action_move_to_front(entry->action, actions, num_actions); } if (init_depth > 1 && cur_depth == init_depth) { - action_move_to_front(negamax_best_action, list); + action_move_to_front(negamax_best_action, actions, num_actions); } - // TODO: what to do if this is never written to? - action_t best_action = list->head->action; + action_t best_action = actions[0]; float best_value = -infty; - for (action_node_t *node = list->head; node != NULL; node = node->next) { - negamax_display_progress(cur_depth, init_depth, list->length); + for (uint32_t idx = 0; idxaction); + action_take(state, actions[idx]); // Compute the value of the node float node_value; @@ -141,11 +142,11 @@ static float negamax(tak_state_p state, const uint8_t cur_depth, } else { node_value = colour * evaluate(state); } - action_undo(state, node->action); + action_undo(state, actions[idx]); if (node_value > best_value) { best_value = node_value; - best_action = node->action; + best_action = actions[idx]; } if (best_value > alpha) @@ -154,7 +155,7 @@ static float negamax(tak_state_p state, const uint8_t cur_depth, break; } - action_list_free(list); + actions_free(actions); if (cur_depth == init_depth) negamax_best_action = best_action; -- cgit v1.2.3