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

3 files changed, 97 insertions, 117 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) {
diff --git a/include/actions.h b/include/actions.h
index 1550cce..0127119 100644
--- a/include/actions.h
+++ b/include/actions.h
@@ -43,15 +43,6 @@ typedef uint32_t action_t;
   ((type) | (loc) << A_LOC_SHIFT | (data0) << A_DATA0_SHIFT |                  \
    (data1) << A_DATA1_SHIFT)
 
-typedef struct action_node_s {
-  struct action_node_s *next;
-  action_t action;
-} action_node_t;
-
-typedef struct action_list_s {
-  struct action_node_s *head, *tail;
-  uint32_t length;
-} action_list_t;
 
 // ===================================================================
 // Variables
@@ -63,11 +54,14 @@ extern int8_t move_deltas[4];
 // Methods
 // ===================================================================
 
-void action_list_init(const uint8_t board_size);
-void action_list_free(action_list_t *list);
-action_list_t *action_list_generate(tak_state_p state);
+void actions_init(const uint8_t board_size);
+void actions_free(action_t *actions);
 
-int action_move_to_front(const action_t action, action_list_t *list);
+action_t *actions_generate(tak_state_p state, uint32_t *num_actions);
+char action_in_list(action_t action, action_t *actions,
+                    const uint32_t num_actions);
+void action_move_to_front(action_t action, action_t *actions,
+                          const uint32_t num_actions);
 
 void action_take(tak_state_p state, const action_t action);
 void action_undo(tak_state_p state, const action_t action);
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;