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, 52 insertions, 43 deletions

diff --git a/src/selfplay.c b/src/selfplay.c
index 6da4f6e..8cd11b9 100644
--- a/src/selfplay.c
+++ b/src/selfplay.c
@@ -14,7 +14,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 <stdio.h>
@@ -26,18 +26,24 @@
 #include "actions.h"
 #include "negamax.h"
 #include "nn.h"
+#include "pv.h"
 #include "tak.h"
 #include "xorshift64.h"
 
+#ifndef RECORD_PV
+#error "selfplay must be built with -DRECORD_PV (see the selfplay Makefile target)"
+#endif
+
 #define MAX_PLY 256
-#define MAX_INP (3 + 6 * 6)
+#define MAX_CELLS (6 * 6)
 
 static tak_state_p state;
 static uint32_t min_ply;
 
-// Positions buffered for the game (the net input only)
-static float rows[MAX_PLY][MAX_INP];
-static uint32_t row_ply[MAX_PLY];
+static float row_head[MAX_PLY][3];
+static uint8_t row_cells[MAX_PLY][MAX_CELLS];
+static uint8_t row_term[MAX_PLY];
+static float row_terminal_value[MAX_PLY];
 static uint32_t n_rows;
 static uint32_t game_id; // PID, tags every row so games can be grouped
 
@@ -48,29 +54,44 @@ void negamax_display_progress(const uint8_t cur_depth,
   (void)(init_depth);
   (void)(length);
 }
+static float win_value(const enum WIN_TYPE w) {
+  switch (w) {
+  case WIN_FLAT_BLACK:
+  case WIN_ROAD_BLACK:
+    return 1.0f;
+  case WIN_FLAT_WHITE:
+  case WIN_ROAD_WHITE:
+    return -1.0f;
+  default:
+    return 0.0f;
+  }
+}
+
 static int play_game(const uint32_t eps10000) {
   reset_state(state, state->board_size);
   n_rows = 0;
 
+  const enum COLOUR eps_side = (rand32() & 1) ? C_BLACK : C_WHITE;
+
   char ptn[16];
   for (uint32_t ply = 0; ply < MAX_PLY; ply++) {
-    // The engine's best move for this position (sets negamax_ptn)
     negamax_generate(state);
 
-    if (rand32() % 10000 < eps10000) {
-      // Epsilon: uniform random legal move
+    if (state->current_colour == eps_side && rand32() % 10000 < eps10000) {
       uint32_t n_actions;
       action_t *actions = actions_generate(state, &n_actions);
       action_to_ptn(actions[rand32() % n_actions], ptn);
     } else {
-      // Greedy: the engine's best move
       strcpy(ptn, negamax_ptn);
     }
 
-    // Buffer this position, before the move changes the board
-    if (ply >= min_ply && n_rows < MAX_PLY) {
-      nn_prepare_input(rows[n_rows], state);
-      row_ply[n_rows] = ply;
+    const pv_leaf_t *leaf = pv_get_leaf();
+    if (leaf->current_colour != eps_side && ply >= min_ply &&
+        n_rows < MAX_PLY) {
+      memcpy(row_head[n_rows], leaf->head, sizeof(row_head[n_rows]));
+      memcpy(row_cells[n_rows], leaf->cells, sizeof(row_cells[n_rows]));
+      row_term[n_rows] = leaf->terminal;
+      row_terminal_value[n_rows] = leaf->terminal_value;
       n_rows++;
     }
 
@@ -89,52 +110,36 @@ static int play_game(const uint32_t eps10000) {
 
   const uint8_t n_cells = state->board_size * state->board_size;
 
-  // final outcome from black's perspective
-  float R;
-  switch (state->won) {
-    case WIN_FLAT_BLACK:
-    case WIN_ROAD_BLACK:
-    R = 1.0f;
-    break;
-    case WIN_FLAT_WHITE:
-    case WIN_ROAD_WHITE:
-    R = -1.0f;
-    break;
-    default:
-    R = 0.0f;
-    break;
-  }
+  // final outcome of the played game, from black's perspective
+  const float R = win_value(state->won);
 
   for (uint32_t k = 0; k < n_rows; k++) {
-    fprintf(stdout, "%d,%.8f,%.8f,", (int)rows[k][0], rows[k][1],
-            rows[k][2]);
+    fprintf(stdout, "%.8f,%.8f,%.8f,", row_head[k][0], row_head[k][1],
+            row_head[k][2]);
     for (uint8_t c = 0; c < n_cells; c++)
-      fprintf(stdout, "%.2f,", rows[k][3 + c]);
-    fprintf(stdout, "%u,%u,%.0f\n", game_id, row_ply[k], R);
+      fprintf(stdout, "%u,", (unsigned)row_cells[k][c]);
+    fprintf(stdout, "%u,%.0f,%u,%.0f\n", game_id, R,
+            (unsigned)row_term[k], row_terminal_value[k]);
   }
 
   return (int)n_rows;
 }
 
-const char *license =
-    "selfplay, one game of self-play training data for the ct net\n\
+const char *usage =
+  "selfplay, one game of asymmetric self-play training data.\n\
 Usage: selfplay <size> <eps> <depth> <min_ply>\n\
-Plays a single game of <size>x<size>. On each ply the engine's best move is played with probability 1-eps, and a uniform random legal move with probability eps. Every position from ply <min_ply> onwards is written to stdout as one CSV row:\n\
-\n\
-  parity,white_flats,black_flats,<board values...>,game_id,ply,R\n\
+Plays a single asymmetric game of <size>x<size> self-play: one side plays the engine's best move at every ply (pure minimax) and the other side plays the engine's best move except that with probability eps it plays a uniform random legal move; the colour assignment of these two players is random. Only the deterministic side's plies are written to stdout, one CSV row per recorded search, from ply <min_ply> onwards:\n\
 \n\
-The first 3 + size*size columns are the training input, game_id identifies the game, ply is the move number the position precedes, and R is the game's final outcome from black's perspective (+1 black won, -1 white won, 0 draw). nn_train.py runs many of these in parallel, pools the rows, and derives TD(lambda) targets from them.\n\
+parity,white_flats,black_flats,<cell ids...>,game_id,R,terminal,leaf_R\n\
+nn_train.py runs many of these in parallel to generate training data.\n\
 \n\
 Copyright (C) 2026, tslil clingman\n\
 \n\
-This program is free software: you can redistribute it and/or modify\n  \
-it under the terms of the GNU General Public License as published by\n  \
-the Free Software Foundation, either version 3 of the License, or\n\
-(at your option) any later version.";
+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 the Free Software Foundation, either version 3 of the License, or (at your option) any later version.";
 
 int main(int argc, char **argv) {
   if (argc != 5) {
-    puts(license);
+    puts(usage);
     return EXIT_FAILURE;
   }
 
@@ -147,6 +152,10 @@ int main(int argc, char **argv) {
     fprintf(stderr, "selfplay: size must be 5 or 6\n");
     return EXIT_FAILURE;
   }
+  if (negamax_search_depth > NEGAMAX_MAX_DEPTH) {
+    fprintf(stderr, "selfplay: depth must be <= %d\n", NEGAMAX_MAX_DEPTH);
+    return EXIT_FAILURE;
+  }
   if (eps10000 >= 10000) {
     fprintf(stderr, "selfplay: eps must be < 1\n");
     return EXIT_FAILURE;