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, 24 insertions, 6 deletions

diff --git a/include/tt.h b/include/tt.h
index b8e1a2e..60b9b66 100644
--- a/include/tt.h
+++ b/include/tt.h
@@ -28,6 +28,10 @@
 
 enum TT_FLAG { TT_EXACT, TT_LOWERBOUND, TT_UPPERBOUND };
 
+#ifdef RECORD_PV
+#include <pv.h>
+#endif
+
 typedef struct tt_node_s {
   uint16_t gen;
   uint64_t key;
@@ -35,6 +39,10 @@ typedef struct tt_node_s {
   uint8_t depth;
   float value;
   action_t action;
+#ifdef RECORD_PV
+  // use for generating training data only
+  pv_leaf_t leaf;
+#endif
 } tt_entry_t;
 
 // ===================================================================
@@ -48,15 +56,25 @@ typedef struct tt_node_s {
 // Methods
 // ===================================================================
 
-// Bump the generation counter, invalidating all entries (memsets the
-// table on wraparound). Called from negamax_init when the board size
-// (and hence the zobrist table) changes; entries are otherwise kept
-// across plies on purpose (see negamax.c).
+// Bump the generation counter, invalidating all entries. Called from
+// negamax_init when the board size (and hence the zobrist table) changes;
+// entries are otherwise kept across plies on purpose (see negamax.c).
 int tt_init(void);
 
 tt_entry_t *tt_seek(const uint64_t key);
 
-int tt_insert(const uint64_t key, const enum TT_FLAG flag, const uint8_t depth,
-              const float value, const action_t action);
+// Store a search result for `key', returning the entry it was written to, or
+// NULL when the replacement policy keeps the current occupant instead.
+//
+// Replacement policy per slot:
+//
+//   - generation and key match: always update
+//
+//   - otherwise (empty slot, stale generation, or a different key): replace the
+//     occupant unless it is a deeper search of a different position, which is
+//     kept.
+tt_entry_t *tt_store(const uint64_t key, const enum TT_FLAG flag,
+                     const uint8_t depth, const float value,
+                     const action_t action);
 
 #endif