switch to explicit game state & important bug fix & clang format

Previously the code base assumed that there was a single, global game
state which was the implicit target of all actions taken. Looking
ahead at architectural improvements, this has now been (almost
entirely) made explicit and functions take tak_state_p where
necessary (and also where unnecessary).

Two important fixes to actions.c were made:

- Previously when generating the possible stack moves, stack height
overflows (> 15) were not taken into account and this resulted in the
tree search corrupting the board state. Now action search does not
list all legal actions, rather the subset of these encodeable by the
implementation.

- The check for crushing on a stack move was incorrect (too strict),
and this resulted in many legitimate moves being igonored.

Finally, in other changes, weights have also been improved by training
all games instead of some subset for chosen players, and clang-format
was run on the codebase.

1 files changed, 106 insertions, 102 deletions

diff --git a/include/negamax.c b/include/negamax.c
index e85aba9..0f2c450 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -16,6 +16,7 @@
 */
 
 #include "negamax.h"
+#include "actions.h"
 
 // ===================================================================
 // Variables
@@ -30,43 +31,40 @@ static uint64_t negamax_best_action;
 // Helper declarations
 // ===================================================================
 
-static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
-                                         float alpha, float beta,
-                                         const float colour, const uint64_t hash);
+static float negamax(tak_state_p state, const uint8_t cur_depth,
+                     const uint8_t init_depth, float alpha, float beta,
+                     const float colour, const uint64_t hash);
 
 // ===================================================================
 // Exported functions
 // ===================================================================
 
 void negamax_init(const uint8_t new_board_size) {
-    board_size = new_board_size;
-    action_list_init();
-    zobrist_init();
-    tt_init();
+  action_list_init(new_board_size);
+  zobrist_init(new_board_size);
+  tt_init();
 }
 
-void negamax_free(void) {
-    zobrist_free();
-}
+void negamax_free(void) { zobrist_free(); }
 
-float negamax_generate(void) {
-    // We need to start with something outside of [-∞,∞] because those
-    // values are wins
-    const float safe_infty = infty + 1;
-    float result = -infty;
+float negamax_generate(tak_state_p state) {
+  // We need to start with something outside of [-∞,∞] because those
+  // values are wins
+  const float safe_infty = infty + 1;
+  float result = -infty;
 
-    negamax_best_action = -1;
+  negamax_best_action = -1;
 
-    tt_init();
-    for (int d = 1; d <= negamax_search_depth; d++) {
-        result = negamax(d, d, -safe_infty, safe_infty,
-                                         (ply & 1) ? +1.0 : -1.0, zobrist_compute());
-    }
-    tt_free();
+  tt_init();
+  for (int d = 1; d <= negamax_search_depth; d++) {
+    result = negamax(state, d, d, -safe_infty, safe_infty,
+                     (state->ply & 1) ? +1.0 : -1.0, zobrist_compute(state));
+  }
+  tt_free();
 
-    action_to_ptn(negamax_best_action, negamax_ptn);
+  action_to_ptn(negamax_best_action, negamax_ptn);
 
-    return result;
+  return result;
 }
 
 // ===================================================================
@@ -78,89 +76,95 @@ float negamax_generate(void) {
 static enum TT_FLAG flag;
 static enum WIN_TYPE w;
 
-static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
-                                         float alpha, float beta,
-                                         const float colour, const uint64_t hash) {
-
-    tt_entry_t *entry = tt_seek(hash);
-
-    // CAUTION: ≥ breaks search stability (vs =) on shallow depths
-    if (entry != NULL && entry->depth >= cur_depth) {
-        if (entry->flag == TT_EXACT) {
-            return entry->value;
-        } else if (entry->flag == TT_LOWERBOUND && entry->value > alpha) {
-            alpha = entry->value;
-        } else if (entry->flag == TT_UPPERBOUND && entry->value < beta) {
-            beta = entry->value;
-        }
-        if (alpha >= beta) return entry->value;
-    }
+static float negamax(tak_state_p state, const uint8_t cur_depth,
+                     const uint8_t init_depth, float alpha, float beta,
+                     const float colour, const uint64_t hash) {
 
-    action_list_t *list;
-    if ((list = action_list_generate()) == NULL)
-        return alpha; // should never happen!
-
-    if (entry != NULL) {
-        action_move_to_front(entry->action, list);
-    }
+  tt_entry_t *entry = tt_seek(hash);
 
-    if (init_depth > 1 && cur_depth == init_depth) {
-        action_move_to_front(negamax_best_action, list);
+  // CAUTION: ≥ breaks search stability (vs =) on shallow depths
+  if (entry != NULL && entry->depth >= cur_depth) {
+    if (entry->flag == TT_EXACT) {
+      return entry->value;
+    } else if (entry->flag == TT_LOWERBOUND && entry->value > alpha) {
+      alpha = entry->value;
+    } else if (entry->flag == TT_UPPERBOUND && entry->value < beta) {
+      beta = entry->value;
     }
-
-    // TODO: what to do if this is never written to?
-    action_t best_action = list->head->action;
-    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);
-
-        action_take(node->action);
-
-        // Compute the value of the node
-        float node_value;
-        if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) {
-            node_value = -colour*infty;
-            // Check win if far enough into the game
-            if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) {
-                node_value = colour*infty;
-            } else if (w == WIN_DRAW) {
-                node_value = 0;
-            }
-        } else if (cur_depth > 1) {
-            // If nobody won, or too early and not leaf, recurse
-            node_value = -negamax(cur_depth - 1, init_depth,
-                                                        -beta, -alpha,
-                                                        -colour, zobrist_compute());
-        } else {
-            node_value = colour * nn1986_evaluate_black_win();
-        }
-        action_undo(node->action);
-
-        if (node_value > best_value) {
-            best_value = node_value;
-            best_action = node->action;
-        }
-
-        if (best_value > alpha) alpha = best_value;
-        if (alpha >= beta) break;
+    if (alpha >= beta)
+      return entry->value;
+  }
+
+  action_list_t *list;
+  if ((list = action_list_generate(state)) == NULL)
+    return alpha; // should never happen!
+
+  if (entry != NULL) {
+    action_move_to_front(entry->action, list);
+  }
+
+  if (init_depth > 1 && cur_depth == init_depth) {
+    action_move_to_front(negamax_best_action, list);
+  }
+
+  // TODO: what to do if this is never written to?
+  action_t best_action = list->head->action;
+  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);
+
+    action_take(state, node->action);
+
+    // Compute the value of the node
+    float node_value;
+    if (state->ply >= 2 * state->board_size - 2 &&
+        (w = check_win(state)) < 0xFF) {
+      node_value = -colour * infty;
+      // Check win if far enough into the game
+      if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) {
+        node_value = colour * infty;
+      } else if (w == WIN_DRAW) {
+        node_value = 0;
+      }
+    } else if (cur_depth > 1) {
+      // If nobody won, or too early and not leaf, recurse
+      node_value = -negamax(state, cur_depth - 1, init_depth, -beta, -alpha,
+                            -colour, zobrist_compute(state));
+    } else {
+      node_value = colour * nn1986_evaluate_black_win(state);
     }
+    action_undo(state, node->action);
 
-    action_list_free(list);
-    if (cur_depth == init_depth) negamax_best_action = best_action;
-
-    flag = TT_EXACT;
-    if (best_value >= beta) flag = TT_LOWERBOUND;
-    else if (best_value <= alpha) flag = TT_UPPERBOUND;
-
-    if (entry == NULL) {
-        tt_insert(hash, flag, cur_depth, best_value, best_action);
-    } else {
-        entry->flag = flag;
-        entry->value = best_value;
-        entry->depth = cur_depth;
-        entry->action = best_action;
+    if (node_value > best_value) {
+      best_value = node_value;
+      best_action = node->action;
     }
 
-    return best_value;
+    if (best_value > alpha)
+      alpha = best_value;
+    if (alpha >= beta)
+      break;
+  }
+
+  action_list_free(list);
+  if (cur_depth == init_depth)
+    negamax_best_action = best_action;
+
+  flag = TT_EXACT;
+  if (best_value >= beta)
+    flag = TT_LOWERBOUND;
+  else if (best_value <= alpha)
+    flag = TT_UPPERBOUND;
+
+  if (entry == NULL) {
+    tt_insert(hash, flag, cur_depth, best_value, best_action);
+  } else {
+    entry->flag = flag;
+    entry->value = best_value;
+    entry->depth = cur_depth;
+    entry->action = best_action;
+  }
+
+  return best_value;
 }