TD-leaf and another negamax bug

TD-lambda and TD-leaf are separated by the observation that minimax with a parameterised leaf heuristic is differentiable* in the parameters. "All" that had to be done was to extract the "principal variation": which one position survived all of the pruning to become the reported value.

This was a bit fiddly and uncovered a subtle bug (again) in negamax.c: we were not being complete in our overriding of the TT entry and by omitting key it was possible that later searches would find incorrect values.

The more interesting question to me was: how do we introduce enough variety while not corrupting the PV chain? I settled on having selfplay have one of the players be epsilon-random but the other greedy (minimax) and simply report only the greedy portion PV chain. This appears to work well enough in practice and doesn't introduce nonsense training data for the net (we don't force its actions to be nonsensical). I also deciced, perhaps in a departure from tradition, that we had good supervised labels for PVs that happened to be winning states, so the training overrides the targets in that case. Finally rolled back some of the ambition in nn_train.py default arguments.

*almost always

1 files changed, 71 insertions, 19 deletions

diff --git a/include/negamax.c b/include/negamax.c
index 7b4acc1..6c29481 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -17,6 +17,9 @@
 
 #include "negamax.h"
 #include "actions.h"
+#ifdef RECORD_PV
+#include "pv.h"
+#endif
 
 // ===================================================================
 // Variables
@@ -54,7 +57,11 @@ static inline enum WIN_TYPE check_win_cached(tak_state_p state,
 
 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);
+                     const float colour, const uint64_t hash
+#ifdef RECORD_PV
+                     , pv_leaf_t *out_leaf
+#endif
+);
 
 // ===================================================================
 // Exported functions
@@ -84,7 +91,7 @@ float negamax_generate(tak_state_p state) {
 
   negamax_best_action = -1;
 
-  // The transposition table is deliberately NOT cleared here: entries persist
+  // 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,
@@ -93,11 +100,22 @@ float negamax_generate(tak_state_p state) {
 
   // this is constant across iterative deepening
   const uint64_t root_hash = zobrist_compute(state);
+#ifdef RECORD_PV
+  pv_leaf_t iteration_leaf;
+#endif
   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, root_hash);
+                     (state->ply & 1) ? +1.0 : -1.0, root_hash
+#ifdef RECORD_PV
+                     , &iteration_leaf
+#endif
+    );
   }
 
+#ifdef RECORD_PV
+  pv_publish_leaf(&iteration_leaf);
+#endif
+
   action_to_ptn(negamax_best_action, negamax_ptn);
 
   return result;
@@ -112,26 +130,43 @@ static enum WIN_TYPE w;
 
 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) {
+                     const float colour, const uint64_t hash
+#ifdef RECORD_PV
+                     , pv_leaf_t *out_leaf
+#endif
+) {
+
+  // the scratch buffer is per-level so that recursion does not clobber
+  const uint32_t level = init_depth - cur_depth;
 
   tt_entry_t *entry = tt_seek(hash);
 
-  if (entry != NULL && entry->depth >= cur_depth) {
+  // The root never early-returns from the table. Within one game the new
+  // root was only ever stored at depth D-1, so an early return could not
+  // fire anyway; across games the table persists across reset_state and
+  // a stale full-depth entry would early-return and leave
+  // negamax_best_action unset.
+  if (level > 0 && entry != NULL && entry->depth >= cur_depth) {
     if (entry->flag == TT_EXACT) {
+#ifdef RECORD_PV
+      *out_leaf = entry->leaf;
+#endif
       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)
+    if (alpha >= beta) {
+#ifdef RECORD_PV
+      *out_leaf = entry->leaf;
+#endif
       return entry->value;
+    }
   }
 
   action_t *actions;
   uint32_t num_actions;
-  // 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!
 
@@ -153,6 +188,9 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
 
   action_t best_action = actions[0];
   float best_value = -infty;
+#ifdef RECORD_PV
+  pv_leaf_t candidate_leaf, best_leaf;
+#endif
 
   for (uint32_t idx = 0; idx<num_actions; idx++) {
     negamax_display_progress(cur_depth, init_depth, num_actions);
@@ -161,7 +199,7 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
 
     const uint64_t child_hash = zobrist_compute(state);
 
-    // Compute the value of the node
+    // Compute the value of the node and retain the leaf that produced it.
     float node_value;
     if (state->ply >= 2 * state->board_size - 2 &&
         (w = check_win_cached(state, child_hash)) < 0xFF) {
@@ -172,18 +210,31 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
       } else if (w == WIN_DRAW) {
         node_value = 0;
       }
+#ifdef RECORD_PV
+      pv_capture_leaf(&candidate_leaf, state, w);
+#endif
     } 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, child_hash);
+                            -colour, child_hash
+#ifdef RECORD_PV
+                            , &candidate_leaf
+#endif
+      );
     } else {
       node_value = colour * evaluate(state);
+#ifdef RECORD_PV
+      pv_capture_leaf(&candidate_leaf, state, (enum WIN_TYPE)0xFF);
+#endif
     }
     action_undo(state, actions[idx]);
 
-    if (node_value > best_value) {
+    if (idx == 0 || node_value > best_value) {
       best_value = node_value;
       best_action = actions[idx];
+#ifdef RECORD_PV
+      best_leaf = candidate_leaf;
+#endif
     }
 
     if (best_value > alpha)
@@ -195,20 +246,21 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
   if (cur_depth == init_depth)
     negamax_best_action = best_action;
 
+#ifdef RECORD_PV
+  *out_leaf = best_leaf;
+#endif
+
   flag = TT_EXACT;
   if (best_value >= beta)
     flag = TT_LOWERBOUND;
   else if (best_value <= orig_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;
-  }
+  entry = tt_store(hash, flag, cur_depth, best_value, best_action);
+#ifdef RECORD_PV
+  if (entry != NULL)
+    entry->leaf = best_leaf;
+#endif
 
   return best_value;
 }