1 files changed, 51 insertions, 16 deletions

diff --git a/include/negamax.c b/include/negamax.c
index 995caa6..7b4acc1 100644
--- a/include/negamax.c
+++ b/include/negamax.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,7 +12,7 @@
     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 "negamax.h"
@@ -29,6 +29,26 @@ static uint64_t negamax_best_action;
 static nn_function evaluate;
 
 // ===================================================================
+// check_win memoisation
+// ===================================================================
+
+#define WON_CACHE_SIZE 8192
+
+static uint64_t won_cache_key[WON_CACHE_SIZE];
+static uint8_t won_cache_val[WON_CACHE_SIZE];
+
+static inline enum WIN_TYPE check_win_cached(tak_state_p state,
+                                             const uint64_t hash) {
+  const uint32_t idx = hash & (WON_CACHE_SIZE - 1);
+  if (won_cache_key[idx] == hash)
+    return (enum WIN_TYPE)won_cache_val[idx];
+  const enum WIN_TYPE w = check_win(state);
+  won_cache_key[idx] = hash;
+  won_cache_val[idx] = (uint8_t)w;
+  return w;
+}
+
+// ===================================================================
 // Helper declarations
 // ===================================================================
 
@@ -46,28 +66,37 @@ void negamax_init(const uint8_t new_board_size) {
   tt_init();
 
   if (new_board_size == 5) {
-    evaluate = &nn1986_evaluate_black_win;
+    evaluate = &five_nn_fn;
   } else {
-    evaluate = &nn2690_evaluate_black_win;
+    evaluate = &six_nn_fn;
   }
 }
 
+void negamax_set_evaluator(const nn_function f) { evaluate = f; }
+
 void negamax_free(void) { zobrist_free(); }
 
 float negamax_generate(tak_state_p state) {
-  // We need to start with something outside of [-∞,∞] because those
-  // values are wins
+  // 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;
 
-  tt_init();
+  // The transposition table is deliberately NOT cleared here: entries persist
+  // across plies. This is sound because the table is keyed on (board, side to
+  // move) and an entry is only reusable at a depth no greater than the one it
+  // was stored at. In particular the new root (the previous root's child,
+  // stored at depth D-1) can never be reused at depth D, so every turn still
+  // runs a full fresh search at the root.
+
+  // this is constant across iterative deepening
+  const uint64_t root_hash = zobrist_compute(state);
   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));
+                     (state->ply & 1) ? +1.0 : -1.0, root_hash);
   }
-  tt_free();
 
   action_to_ptn(negamax_best_action, negamax_ptn);
 
@@ -75,9 +104,7 @@ float negamax_generate(tak_state_p state) {
 }
 
 // ===================================================================
-// α-β negamax with iterative deepening, using the nn1986 evaluation
-// function and transposition tables using Zobrist hasing and a
-// chaining hash table
+// α-β negamax with iterative deepening.
 // ===================================================================
 
 static enum TT_FLAG flag;
@@ -103,7 +130,9 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
 
   action_t *actions;
   uint32_t num_actions;
-  if ((actions = actions_generate(state, &num_actions)) == NULL)
+  // the scratch buffer is per-level so that recursion does not clobber
+  const uint32_t level = init_depth - cur_depth;
+  if ((actions = actions_generate_at(state, &num_actions, level)) == NULL)
     return alpha; // should never happen!
 
   // How did we land up with impossible actions for this hash?
@@ -111,6 +140,11 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
     action_move_to_front(entry->action, actions, num_actions);
   }
 
+  // negamax_best_action may not be in this position's move list: if the root
+  // search early-returned from the transposition table (the table persists
+  // across plies), it still holds the *previous* ply's best action, which is a
+  // different side's move. action_move_to_front is a no-op for absent actions,
+  // so this is safe either way.
   if (init_depth > 1 && cur_depth == init_depth) {
     action_move_to_front(negamax_best_action, actions, num_actions);
   }
@@ -125,10 +159,12 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
 
     action_take(state, actions[idx]);
 
+    const uint64_t child_hash = zobrist_compute(state);
+
     // Compute the value of the node
     float node_value;
     if (state->ply >= 2 * state->board_size - 2 &&
-        (w = check_win(state)) < 0xFF) {
+        (w = check_win_cached(state, child_hash)) < 0xFF) {
       node_value = -colour * infty;
       // Check win if far enough into the game
       if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) {
@@ -139,7 +175,7 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
     } 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));
+                            -colour, child_hash);
     } else {
       node_value = colour * evaluate(state);
     }
@@ -156,7 +192,6 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
       break;
   }
 
-  actions_free(actions);
   if (cur_depth == init_depth)
     negamax_best_action = best_action;