From 1ca3309dad9d412870b2b793f33af7a7ccabd514 Mon Sep 17 00:00:00 2001 From: tslil Date: Thu, 3 Sep 2026 20:17:22 +0100 Subject: 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 --- src/match.c | 27 ++++++------- src/nn_train.py | 116 +++++++++++++++++++++++++++++++------------------------- src/selfplay.c | 95 +++++++++++++++++++++++++--------------------- 3 files changed, 128 insertions(+), 110 deletions(-) (limited to 'src') diff --git a/src/match.c b/src/match.c index 1c706cd..49ff9c9 100644 --- a/src/match.c +++ b/src/match.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 . + along with ctak. If not, see . */ #include #include @@ -37,7 +37,7 @@ static inline float five_cand(tak_state_p state) { static float cur_board[FIVE_INP_NUM] NN_ALIGNED; - nn_prepare_input(cur_board, state); + nn_prepare_input(cur_board, state, cand_five_embedding); return eval_net(cur_board, FIVE_INP_NUM, &cand_five_dense_weights[0][0], cand_five_dense_biases, cand_five_logit_weights, cand_five_logit_bias, FIVE_DENSE_NUM); @@ -46,7 +46,7 @@ static inline float five_cand(tak_state_p state) { static inline float six_cand(tak_state_p state) { static float cur_board[SIX_INP_NUM] NN_ALIGNED; - nn_prepare_input(cur_board, state); + nn_prepare_input(cur_board, state, cand_six_embedding); return eval_net(cur_board, SIX_INP_NUM, &cand_six_dense_weights[0][0], cand_six_dense_biases, cand_six_logit_weights, cand_six_logit_bias, SIX_DENSE_NUM); @@ -107,16 +107,16 @@ static int play_game(const nn_function current_fn, const nn_function cand_fn, switch (state->won) { case WIN_DRAW: - return -1; - case WIN_FLAT_BLACK: + return -1; + case WIN_FLAT_BLACK: case WIN_ROAD_BLACK: return C_BLACK; case WIN_FLAT_WHITE: case WIN_ROAD_WHITE: return C_WHITE; default: - fprintf(stderr, "match: game did not end cleanly (won=%d)\n", state->won); - return -2; + // ply cap reached with no winner: a draw + return -1; } } @@ -124,7 +124,7 @@ static int play_game(const nn_function current_fn, const nn_function cand_fn, // Main // =================================================================== -const char *license = +const char *usage = "match, one Tak game of the current weights against the candidate.\n\ \n \ usage: match \n\ @@ -137,14 +137,11 @@ nn_train.py runs many of these in parallel to score the candidate against the cu \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 != 4) { - puts(license); + puts(usage); return EXIT_FAILURE; } @@ -179,9 +176,7 @@ int main(int argc, char **argv) { const int winner = play_game(current_fn, cand_fn, current_fn_colour, eps10000); const char *name; - if (winner == -2) - name = "abort"; - else if (winner == -1) + if (winner == -1) name = "draw"; else if (winner == (int)current_fn_colour) name = "current"; diff --git a/src/nn_train.py b/src/nn_train.py index 8025b68..73a5eaf 100755 --- a/src/nn_train.py +++ b/src/nn_train.py @@ -48,7 +48,7 @@ import pandas as pd import torch from tqdm import tqdm -from torch.nn import MSELoss, Linear, Module +from torch.nn import Embedding, MSELoss, Linear, Module from torch import Tensor @@ -97,38 +97,35 @@ def _fmt_matrix(mat: np.ndarray, per_line: int = 8) -> str: def td_lambda_targets( - values: Tensor, + leaf_values: Tensor, result: float, td_lambda: float, ) -> Tensor: - # values: V(s_t) for t = 0..T-1, shape [T] - # result: final result R of the game - - # This is ema, computed backwards - # target[T-1] = R - # target[t] = (1 - lambda) * V(s_{t+1}) + lambda * target[t+1] - length = len(values) - targets = torch.empty_like(values) + targets = torch.empty_like(leaf_values) targets[-1] = result - for ply in range(length - 2, -1, -1): - targets[ply] = (1.0 - td_lambda) * values[ply + 1] + td_lambda * targets[ + + # G[t] = (1-lambda)V[t+1] + lambda G[t+1] + for ply in range(len(leaf_values) - 2, -1, -1): + targets[ply] = (1.0 - td_lambda) * leaf_values[ply + 1] + td_lambda * targets[ ply + 1 ] + return targets @dataclass(frozen=True) class SelfPlayRecords: - positions: Tensor # [n, inp_dim] feature vector of each position + positions: Tensor # [n, inp_dim] game_ids: Tensor # [n] id of the game the position belongs to - plies: Tensor # [n] ply number (position is before this move) - results: Tensor # [n] final result from black's perspective (+1 black won, -1 white won, 0 draw) + results: Tensor # [n] final played result from black's perspective + terminals: Tensor # [n] true when the recorded position is a terminal leaf + terminal_values: Tensor # [n] exact value of a terminal leaf, otherwise 0 @classmethod def load_selfplay( cls, fn: Path, size: int, device: torch.device ) -> SelfPlayRecords: - # [ net input: 0-inp_dim ] [game_id] [ply] [game result] + # [net input] [game_id] [played result] [terminal flag] [leaf result] df = pd.read_csv(fn, header=None) inp_dim = NET_DIMS[size][0] return cls( @@ -141,12 +138,18 @@ class SelfPlayRecords: df.iloc[:, inp_dim].to_numpy(dtype=np.int64), device=device, ), - plies=torch.tensor( - df.iloc[:, inp_dim + 1].to_numpy(dtype=np.int64), + results=torch.tensor( + df.iloc[:, inp_dim + 1].to_numpy(dtype=np.float32), + dtype=torch.float32, device=device, ), - results=torch.tensor( - df.iloc[:, inp_dim + 2].to_numpy(dtype=np.float32), + terminals=torch.tensor( + df.iloc[:, inp_dim + 2].to_numpy(dtype=np.bool_), + dtype=torch.bool, + device=device, + ), + terminal_values=torch.tensor( + df.iloc[:, inp_dim + 3].to_numpy(dtype=np.float32), dtype=torch.float32, device=device, ), @@ -160,8 +163,9 @@ class SelfPlayRecords: return cls( positions=torch.concat([spr.positions for spr in sprs]), game_ids=torch.concat([spr.game_ids for spr in sprs]), - plies=torch.concat([spr.plies for spr in sprs]), results=torch.concat([spr.results for spr in sprs]), + terminals=torch.concat([spr.terminals for spr in sprs]), + terminal_values=torch.concat([spr.terminal_values for spr in sprs]), ) def make_training_data( @@ -175,9 +179,16 @@ class SelfPlayRecords: for game_id in torch.unique(self.game_ids): in_game = self.game_ids == game_id - game_values = values[in_game] + game_terminals = self.terminals[in_game] + game_terminal_values = self.terminal_values[in_game] + game_values = values[in_game].clone() + game_values[game_terminals] = game_terminal_values[game_terminals] game_result = self.results[in_game][0].item() - targets[in_game] = td_lambda_targets(game_values, game_result, td_lambda) + game_targets = td_lambda_targets(game_values, game_result, td_lambda) + # Terminal positions are also direct supervised examples. Do this + # after constructing the TD sequence so it does not reset the EMA. + game_targets[game_terminals] = game_terminal_values[game_terminals] + targets[in_game] = game_targets return self.positions, targets @@ -190,11 +201,18 @@ class SelfPlayRecords: class Net(Module): def __init__(self, inp_dim: int, hidden: int) -> None: super().__init__() + # learned 7-way cell-state embedding (empty, {black, white} x + # {flat, standing, road}); the slot layout must match nn.c + self.embedding = Embedding(7, 1) self.hidden = Linear(inp_dim, hidden, bias=True) self.output = Linear(hidden, 1, bias=True) def forward(self, x: Tensor) -> Tensor: - hidden = torch.relu(self.hidden(x)) + # x: [n, 3 + n_cells]; the first 3 columns are the fixed head + # inputs, the rest are raw cell states (0..6) + n = x.shape[0] + inp = torch.cat([x[:, :3], self.embedding(x[:, 3:].long()).view(n, -1)], dim=1) + hidden = torch.relu(self.hidden(inp)) return torch.tanh(self.output(hidden)).squeeze(-1) def fit( @@ -272,6 +290,7 @@ class Net(Module): prefix = ("cand_" if cand else "") + ("five" if size == 5 else "six") upper = "FIVE" if size == 5 else "SIX" + E = self.embedding.weight.detach().cpu().numpy() W = self.hidden.weight.detach().cpu().numpy() B = self.hidden.bias.detach().cpu().numpy() LW = self.output.weight.detach().cpu().numpy().ravel() @@ -282,6 +301,10 @@ class Net(Module): for p in performance: _ = f.write(f"/* {p} */\n") _ = f.write(f'#include "weights_{size}.h"\n\n') + _ = f.write( + f"const float {prefix}_embedding[7] =\n" + f"{{\n{_fmt_flat(E, per_line=7)}\n}};\n\n" + ) _ = f.write( f"const float {prefix}_dense_weights[{upper}_DENSE_NUM]" f"[{upper}_INP_NUM] NN_ALIGNED =\n{{\n{_fmt_matrix(W)}\n}};\n\n" @@ -340,7 +363,6 @@ class TournamentResult: champ: int cand: int draws: int - cand_rate: float def run_matches( @@ -365,14 +387,7 @@ def run_matches( champ = winners.count("current") cand = winners.count("candidate") draws = winners.count("draw") - aborts = len(winners) - champ - cand - draws - played = len(winners) - aborts - return TournamentResult( - champ=champ, - cand=cand, - draws=draws, - cand_rate=(cand + 0.5 * draws) / played if played else 0.0, - ) + return TournamentResult(champ=champ, cand=cand, draws=draws) # =================================================================== @@ -420,10 +435,10 @@ def run_step( print(f"\n== iteration {iter} ==") - # 1. self-play with the installed champion (include/weights_.c) + # 1. rebuild selfplay _ = subprocess.run(["make", "selfplay"], cwd=root, check=True, capture_output=True) - # 2. generate self-play data (one game per process, in parallel) + # 2. generate self-play data eps = max(eps_min, eps_start * (eps_decay ** (iter - 1))) csv = make_csv(iter) print(f"selfplay, eps={eps:.4f}, depth {depth}, {games} games on {procs} procs") @@ -446,7 +461,7 @@ def run_step( # 3. fine-tune the champion on TD(lambda) targets -> candidate device = next(champ.parameters()).device csvs = [make_csv(i) for i in range(max(iter - replay_iters, 1), iter + 1)] - print("Loading data from", csvs) + print("Loading data from", [str(c) for c in csvs]) records = SelfPlayRecords.load_merge(csvs, size, device) cand = copy.deepcopy(champ) @@ -465,7 +480,7 @@ def run_step( cand=True, ) - # 4. build the match driver (champion + candidate linked) + # 4. build the match driver (champion + candidate) _ = subprocess.run(["make", "match"], cwd=root, check=True, capture_output=True) # 5. tournament + decision @@ -480,8 +495,7 @@ def run_step( decided = tournament_result.champ + tournament_result.cand rate = tournament_result.cand / decided if decided else 0.0 print( - f"champ {tournament_result.champ} - {tournament_result.cand} cand, {tournament_result.draws} draws, " - + f"winrate={rate:.3f}, cand_rate={tournament_result.cand_rate:.3f}" + f"champ {tournament_result.champ} - {tournament_result.cand} cand, {tournament_result.draws} draws, winrate={rate:.3f}" ) promote = decided >= int(0.25 * tournament_games) and rate >= promote_rate @@ -489,7 +503,7 @@ def run_step( cand.to_c( size, root / "include" / f"weights_{size}.c", - (f"v{iter:03d}, val_corr={corr:.4f}",), + (f"v{iter:03d}, val_corr={corr:.4f}, rate={rate:.4f}",), ) print(f"== candidate v{iter:03d} PROMOTED (include/weights_{size}.c) ==") return cand @@ -513,23 +527,23 @@ def main() -> None: ) _ = p.add_argument("--iters", type=int, default=10, help="max loop iterations") _ = p.add_argument( - "--games", type=int, default=2000, help="selfplay games per iteration" + "--games", type=int, default=100, help="selfplay games per iteration" ) _ = p.add_argument( "--replay-iters", type=int, - default=4, + default=0, help="number of previous self-play instances to mix in with current dataset during training", ) _ = p.add_argument( "--eps-start", type=float, default=0.15, - help="initial self-play epsilon (random-move probability); kept close " - "to --tour-eps so the value net trains on the policy it is deployed " - "under", + help="initial self-play epsilon: in asymmetric self-play one side (chosen at random per game) plays a uniform random move with this probability while the greedy side has its plies recorded", + ) + _ = p.add_argument( + "--eps-min", type=float, default=0.05, help="self-play epsilon floor" ) - _ = p.add_argument("--eps-min", type=float, default=0.05, help="epsilon floor") _ = p.add_argument( "--eps-decay", type=float, default=0.9, help="per-iteration epsilon decay" ) @@ -548,20 +562,20 @@ def main() -> None: _ = p.add_argument( "--tournament-eps", type=float, - default=0.05, + default=0.01, help="tournament epsilon (random-move probability)", ) _ = p.add_argument( "--tournament-games", type=int, default=None, - help="tournament games (10/tour_eps if unset)", + help="tournament games (1/tournament-eps if unset)", ) _ = p.add_argument( "--promote", type=float, - default=0.57, - help="candidate win rate among non-drawn tournament games needed to promote (~p<0.03 one-sided binomial at the default 200 games)", + default=0.0, + help="candidate win rate among non-drawn tournament games needed to promote", ) _ = p.add_argument( "--procs", @@ -582,7 +596,7 @@ def main() -> None: args = p.parse_args() if args.tournament_games is None: - args.tournament_games = max(20, int(round(10 / args.tournament_eps))) + args.tournament_games = max(100, int(round(1 / args.tournament_eps))) if args.procs is None: args.procs = max(1, (os.cpu_count() or 1) // 2) 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 . + along with ctak. If not, see . */ #include @@ -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 \n\ -Plays a single game of x. 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 onwards is written to stdout as one CSV row:\n\ -\n\ - parity,white_flats,black_flats,,game_id,ply,R\n\ +Plays a single asymmetric game of x 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 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,,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; -- cgit v1.3.1