From 241156da6f35cb888253e6b8814e7b61a76b4fc7 Mon Sep 17 00:00:00 2001 From: tslil Date: Sun, 30 Aug 2026 19:46:07 +0100 Subject: TD(lambda), and a big rework NOTE: 6x6 weights are as-yet untrained On the performance side: * switch from linked-list chaining hash table to direct mapping * cache check_win by hash * persist transposition tables across plies (this was a big deal and difficult to puzzle out) * add align directives to the network floats * prepare_nn_input gained a small LUT to avoid branching (i suppose you might call this 1D embedding) * apply mtune=native for the native builds On the correctness side: * Zobrist has now includes the ply parity * the network now predicts something in [-1, 1] using tanh (approximated by polynomials) * the training object is now MSE because we're learning a value estimate * use .clangd instead of compile_commands.json On the training side: * completely forgo human-derived data set * implement td(lambda), self-play, tournaments --- include/negamax.c | 67 ++++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 51 insertions(+), 16 deletions(-) (limited to 'include/negamax.c') 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 . + along with ctak. If not, see . */ #include "negamax.h" @@ -28,6 +28,26 @@ uint8_t negamax_search_depth = 3; 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; -- cgit v1.3.1