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

1 files changed, 15 insertions, 14 deletions

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; idx<num_actions; idx++) {
+    negamax_display_progress(cur_depth, init_depth, num_actions);
 
-    action_take(state, node->action);
+    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;