Networks Inside Search

01A network guesses, a search checks

A policy network looks at a position once and gives a probability for every move. One pass is fast, about a millisecond for Pduhard's Back Track King network on CodinGame's machine, but it checks nothing: if the favourite move walks into a trap two turns away, nothing in that pass notices.^[1] A search can notice, because it plays moves forward in a simulator and looks at what happens. What a search lacks is judgment: which of hundreds of moves are worth looking at, and how good a position is when it stops looking.

A network trained by self-play, games against itself and its earlier versions, brings both. Its policy head, the part of the network that outputs those move probabilities, tells the search which moves to try first, and its value head, which predicts the result from a position, scores the positions where the search stops. Self-Play Reinforcement Learning trains exactly this kind of two-headed network.

reCurse won Fall Challenge 2023 with a policy network and no search. In the next bot contest, Summer Challenge 2024, he wrote that "even a very good policy network could not be as competitive on its own anymore," added a search around his network, and finished 2nd.^[2] In chess, AlphaZero looked at 60,000 positions a second where Stockfish, then an alpha-beta engine with a hand-written evaluation, looked at 60 million, and AlphaZero won. Its authors suggest the network made up for the difference by focusing the search on the most promising lines.^[3]

Three ways to combine them come up on CodinGame, and this page takes them one at a time. In PUCT the network's probabilities steer a Monte Carlo tree search. In a one-turn search the policy proposes a few whole-turn plans and a simulator checks them. And NNUE is a network built to be cheap enough to call at every position of an alpha-beta search.

02PUCT: the network picks what to search

Plain Monte Carlo tree search, often called UCT, picks which move to try next with UCB1, a rule that scores each move by its average result plus a bonus for being tried rarely (Monte Carlo Tree Search builds it). UCB1 gives every untried move one visit before it repeats any. With 9 moves that costs little. With hundreds of moves the search can spend its whole turn on first visits to moves no decent player would make.

AlphaGo Zero, DeepMind's 2017 Go program, selects moves with a rule its paper calls a variant of PUCT. Every move gets a prior, its probability from the policy head. The search then picks the move with the highest score: the move's average value so far plus an exploration bonus that is large when the prior is large and shrinks each time the move is visited.^[4] A move the network likes is tried early. If it keeps disappointing, its average drops and its bonus shrinks, so the visits move elsewhere. A move with a small prior gets a small bonus that grows slowly as its parent collects visits, so it gets its turn late, once the favoured moves have stopped looking good.

The selection rule, as AlphaGo Zero states it, scores every move a in position s and follows the best:

In words: a move's score is its average value so far plus a bonus. The bonus grows with the network's prior for the move and with the square root of how often the position has been visited, and it shrinks as the move itself gets visits. c_puct sets how much the bonus counts against the average.

Two more things change from plain MCTS. AlphaGo Zero plays no random games at all: when the search reaches a new position, the network's value head scores it, and that number is backed up the path.^[4] It chooses the move to play by visit count, as plain MCTS does. During self-play it also mixes random noise into the root's priors so that "all moves may be tried, but the search may still overrule bad moves". Without it, a network that has learned to ignore a move might never find out it was wrong.

So the priors cut both ways. Good priors put most of the visits on the right move within the first 200 simulations; misleading ones starve it, and the search does worse than plain UCT with no network at all. Tuning c_puct doesn't fix a bad network. In this widget, every c_puct from 0.25 to 4 left cell 0 between 20% and 46% of the visits at quality 0, all below plain UCT's 61%, while at quality 0.5 c_puct = 1 reached 97% and the extremes 86 to 87%.

On CodinGame, reCurse's Summer Challenge 2024 bot plugged his network, trained with PPO, into decoupled UCT, the simultaneous-move form of MCTS, with PUCT selection, "following the footsteps of AlphaZero." With the network in the loop he could afford 1,000 to 3,000 iterations a turn. He found that about seven shorter searches a turn, each with its own fixed random seed and voting at the end, beat one long search, and that a little uniform noise in the policy helped against real opponents even though it always looked worse locally.^[2] marchete's CGZero, an AlphaZero-style bot for Oware Abapa with a network of about 80 KB, reached the top 6 of that game; its author reports that going from 5,000 to 10,000 simulations a turn improved the win rate noticeably.^[5]

03PUCT in code

These complete programs implement PUCT on plain tic-tac-toe. The search calls an evaluator, the stand-in for a network, which returns a prior for every legal move and the value of the position for the player to move; the search never looks inside it. Selection follows the highest PUCT score, a new position is expanded with the evaluator's priors, and the evaluator's value is backed up the path, flipping sides at each level. The move played is the most visited.

The test in main checks the worked example's two scores, then runs the widget's position (only cell 0 wins) with three sets of priors at the root: 0.6 on the winning move, even, and 0.6 on cell 8, which doesn't win. Below the root every prior is even, and the stand-in's value is the result of one random game, so the root priors are the only knowledge it adds. Over 20 seeded runs of 800 simulations each, both programs print the same numbers: cell 0 gets 93.9% of the visits with the good priors and is played in all 20 runs, 64.1% and 17 runs with even priors, and 37.1% and 10 runs with the misleading ones. The test asserts all 20 good runs play cell 0, that the visit shares fall in that order, and that the misleading priors pick the winner less often than the even ones.

// PUCT, the move-selection rule of AlphaZero-style search, on tic-tac-toe.
// The search asks an evaluator, standing in for a network, for a prior
// probability on each move and a value for each new position.
#include <array>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <functional>
#include <vector>

// Cells 0..8 row by row; 0 empty, 1 X, 2 O. X moves first.
struct Board {
    std::array<int, 9> cells{};
    int toMove = 1;
};

constexpr int kLines[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6},
                              {1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6}};

// 1 or 2 when that player has three in a row, 3 for a full board, 0 otherwise.
int result(const Board& board) {
    for (const auto& line : kLines) {
        const int mark = board.cells[line[0]];
        if (mark != 0 && mark == board.cells[line[1]] && mark == board.cells[line[2]]) return mark;
    }
    for (int cell : board.cells)
        if (cell == 0) return 0;
    return 3;
}

std::vector<int> legalMoves(const Board& board) {
    std::vector<int> moves;
    if (result(board) != 0) return moves;
    for (int cell = 0; cell < 9; ++cell)
        if (board.cells[cell] == 0) moves.push_back(cell);
    return moves;
}

void play(Board& board, int cell) {
    board.cells[cell] = board.toMove;
    board.toMove = 3 - board.toMove;
}

// What a network gives the search for one position: a prior probability for
// each legal move (in legalMoves order) and the chance that the player to
// move wins, with a draw counted as 0.5.
struct Evaluation {
    std::vector<double> priors;
    double value;
};
using Evaluator = std::function<Evaluation(const Board&)>;

struct Node {
    int cell = -1;              // the move that led here
    double prior = 0.0;         // P(s, a): the network's probability for that move
    int visits = 0;             // N(s, a)
    double valueSum = 0.0;      // summed values, seen by the player who made the move
    std::vector<int> children;  // indices into the node pool
};

// The PUCT score of a child: its average value so far, plus a bonus that is
// large for moves the network likes and shrinks as the move collects visits.
double puctScore(const Node& child, int parentVisits, double cPuct, double unvisitedValue) {
    const double average = child.visits > 0 ? child.valueSum / child.visits : unvisitedValue;
    const double bonus = cPuct * child.prior * std::sqrt(static_cast<double>(parentVisits)) /
                         (1.0 + child.visits);
    return average + bonus;
}

class Search {
public:
    Search(const Board& root, Evaluator evaluator, double cPuct)
        : rootBoard_(root), evaluate_(std::move(evaluator)), cPuct_(cPuct), nodes_(1) {}

    // One simulation: walk down by PUCT, evaluate the new position, back the value up.
    void simulate() {
        Board board = rootBoard_;
        std::vector<int> path{0};
        int current = 0;
        // Selection: follow the best-scoring child until a node with no children.
        // AlphaGo Zero puts the sum of the children's visits under the square
        // root; the parent's own count, one more, is a common variant.
        while (!nodes_[current].children.empty()) {
            int best = nodes_[current].children.front();
            double bestScore = -1e9;
            for (int child : nodes_[current].children) {
                // An untried move counts as a draw, 0.5; AlphaGo Zero starts it at 0
                // on its -1..1 scale, which is the same value.
                const double score = puctScore(nodes_[child], nodes_[current].visits, cPuct_, 0.5);
                if (score > bestScore) { bestScore = score; best = child; }
            }
            current = best;
            play(board, nodes_[current].cell);
            path.push_back(current);
        }
        // Expansion and evaluation: the rules score a finished game; otherwise the
        // evaluator gives the value and the priors for the new children.
        double valueForMover;  // the chance that the player to move here wins
        const int outcome = result(board);
        if (outcome == 3) valueForMover = 0.5;
        else if (outcome != 0) valueForMover = 0.0;  // the move into this node won
        else {
            const Evaluation evaluation = evaluate_(board);
            const std::vector<int> moves = legalMoves(board);
            for (std::size_t i = 0; i < moves.size(); ++i) {
                Node child;
                child.cell = moves[i];
                child.prior = evaluation.priors[i];
                nodes_.push_back(child);
                nodes_[current].children.push_back(static_cast<int>(nodes_.size()) - 1);
            }
            valueForMover = evaluation.value;
        }
        // Backup: a node keeps values seen by the player who moved into it, so
        // the value flips at every level on the way back to the root.
        double value = 1.0 - valueForMover;
        for (auto step = path.rbegin(); step != path.rend(); ++step) {
            nodes_[*step].visits += 1;
            nodes_[*step].valueSum += value;
            value = 1.0 - value;
        }
    }

    // Play the most visited move; visit counts are steadier than averages.
    int bestMove() const {
        int best = -1, mostVisits = -1;
        for (int child : nodes_[0].children)
            if (nodes_[child].visits > mostVisits) {
                mostVisits = nodes_[child].visits;
                best = nodes_[child].cell;
            }
        return best;
    }

    // The share of the root's simulations that went to one move.
    double visitShare(int cell) const {
        for (int child : nodes_[0].children)
            if (nodes_[child].cell == cell)
                return static_cast<double>(nodes_[child].visits) / (nodes_[0].visits - 1);
        return 0.0;
    }

private:
    Board rootBoard_;
    Evaluator evaluate_;
    double cPuct_;
    std::vector<Node> nodes_;  // node 0 is the root
};

// SplitMix64, a small seeded generator for the stand-in's random playouts.
struct SplitMix64 {
    std::uint64_t state;
    std::uint64_t next() {
        state += 0x9E3779B97F4A7C15ull;
        std::uint64_t mixed = state;
        mixed = (mixed ^ (mixed >> 30)) * 0xBF58476D1CE4E5B9ull;
        mixed = (mixed ^ (mixed >> 27)) * 0x94D049BB133111EBull;
        return mixed ^ (mixed >> 31);
    }
    int below(int count) { return static_cast<int>(next() % static_cast<std::uint64_t>(count)); }
};

// A stand-in network: the given priors at the root, even priors elsewhere,
// and as its value the result of one random game played from the position.
// The root priors are the only knowledge it adds.
Evaluator standIn(const Board& root, std::vector<double> rootPriors, std::uint64_t seed) {
    return [root, rootPriors, random = SplitMix64{seed}](const Board& board) mutable {
        const std::vector<int> moves = legalMoves(board);
        Evaluation evaluation;
        if (board.cells == root.cells) evaluation.priors = rootPriors;
        else evaluation.priors.assign(moves.size(), 1.0 / static_cast<double>(moves.size()));
        Board playout = board;
        while (result(playout) == 0) {
            const std::vector<int> options = legalMoves(playout);
            play(playout, options[random.below(static_cast<int>(options.size()))]);
        }
        const int outcome = result(playout);
        evaluation.value = outcome == 3 ? 0.5 : outcome == board.toMove ? 1.0 : 0.0;
        return evaluation;
    };
}

int main() {
    // The worked example: a parent with 100 visits and c_puct = 1.
    Node liked;
    liked.prior = 0.6;
    liked.visits = 10;
    liked.valueSum = 5.0;
    Node untried;
    untried.prior = 0.05;
    assert(std::abs(puctScore(liked, 100, 1.0, 0.5) - 1.0454545454545454) < 1e-12);
    assert(std::abs(puctScore(untried, 100, 1.0, 0.5) - 1.0) < 1e-12);

    // X to move; only cell 0 wins (O must block at 6, then X takes 4 and
    // threatens two lines). The free cells, in order, are 0 1 4 5 6 7 8.
    Board root;
    root.cells[3] = 1;
    root.cells[2] = 2;
    const double rest = 0.4 / 6;
    const std::vector<std::vector<double>> priors{
        {0.6, rest, rest, rest, rest, rest, rest},  // the winning move first
        std::vector<double>(7, 1.0 / 7),            // no opinion
        {rest, rest, rest, rest, rest, rest, 0.6},  // a non-winning move first
    };
    const char* names[] = {"good", "even", "misleading"};
    double meanShare[3] = {0, 0, 0};
    int picksWinner[3] = {0, 0, 0};
    for (int setting = 0; setting < 3; ++setting) {
        for (std::uint64_t seed = 1; seed <= 20; ++seed) {
            Search search(root, standIn(root, priors[setting], seed), 1.0);
            for (int simulation = 0; simulation < 800; ++simulation) search.simulate();
            meanShare[setting] += search.visitShare(0) / 20;
            if (search.bestMove() == 0) picksWinner[setting] += 1;
        }
        std::printf("%-10s priors: %4.1f%% of visits on cell 0, plays it in %d of 20 runs\n",
                    names[setting], 100 * meanShare[setting], picksWinner[setting]);
    }
    assert(picksWinner[0] == 20);
    assert(meanShare[0] > meanShare[1] && meanShare[1] > meanShare[2]);
    assert(picksWinner[2] < picksWinner[1]);
}

// PUCT, the move-selection rule of AlphaZero-style search, on tic-tac-toe.
// The search asks an evaluator, standing in for a network, for a prior
// probability on each move and a value for each new position.

// Cells 0..8 row by row; 0 empty, 1 X, 2 O. X moves first.
#[derive(Clone, Copy, PartialEq)]
struct Board {
    cells: [u8; 9],
    to_move: u8,
}

const LINES: [[usize; 3]; 8] = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6],
                                [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]];

// 1 or 2 when that player has three in a row, 3 for a full board, 0 otherwise.
fn result(board: &Board) -> u8 {
    for line in LINES.iter() {
        let mark = board.cells[line[0]];
        if mark != 0 && mark == board.cells[line[1]] && mark == board.cells[line[2]] {
            return mark;
        }
    }
    if board.cells.iter().any(|&cell| cell == 0) { 0 } else { 3 }
}

fn legal_moves(board: &Board) -> Vec<usize> {
    if result(board) != 0 {
        return Vec::new();
    }
    (0..9).filter(|&cell| board.cells[cell] == 0).collect()
}

fn play(board: &mut Board, cell: usize) {
    board.cells[cell] = board.to_move;
    board.to_move = 3 - board.to_move;
}

// What a network gives the search for one position: a prior probability for
// each legal move (in legal_moves order) and the chance that the player to
// move wins, with a draw counted as 0.5.
struct Evaluation {
    priors: Vec<f64>,
    value: f64,
}
type Evaluator = Box<dyn FnMut(&Board) -> Evaluation>;

#[derive(Clone, Default)]
struct Node {
    cell: usize,          // the move that led here
    prior: f64,           // P(s, a): the network's probability for that move
    visits: u32,          // N(s, a)
    value_sum: f64,       // summed values, seen by the player who made the move
    children: Vec<usize>, // indices into the node pool
}

// The PUCT score of a child: its average value so far, plus a bonus that is
// large for moves the network likes and shrinks as the move collects visits.
fn puct_score(child: &Node, parent_visits: u32, c_puct: f64, unvisited_value: f64) -> f64 {
    let average = if child.visits > 0 { child.value_sum / f64::from(child.visits) } else { unvisited_value };
    let bonus = c_puct * child.prior * f64::from(parent_visits).sqrt() / (1.0 + f64::from(child.visits));
    average + bonus
}

struct Search {
    root_board: Board,
    evaluate: Evaluator,
    c_puct: f64,
    nodes: Vec<Node>, // node 0 is the root
}

impl Search {
    fn new(root: Board, evaluator: Evaluator, c_puct: f64) -> Search {
        Search { root_board: root, evaluate: evaluator, c_puct, nodes: vec![Node::default()] }
    }

    // One simulation: walk down by PUCT, evaluate the new position, back the value up.
    fn simulate(&mut self) {
        let mut board = self.root_board;
        let mut path = vec![0];
        let mut current = 0;
        // Selection: follow the best-scoring child until a node with no children.
        // AlphaGo Zero puts the sum of the children's visits under the square
        // root; the parent's own count, one more, is a common variant.
        while !self.nodes[current].children.is_empty() {
            let mut best = self.nodes[current].children[0];
            let mut best_score = -1e9;
            for &child in &self.nodes[current].children {
                // An untried move counts as a draw, 0.5; AlphaGo Zero starts it at 0
                // on its -1..1 scale, which is the same value.
                let score = puct_score(&self.nodes[child], self.nodes[current].visits, self.c_puct, 0.5);
                if score > best_score {
                    best_score = score;
                    best = child;
                }
            }
            current = best;
            play(&mut board, self.nodes[current].cell);
            path.push(current);
        }
        // Expansion and evaluation: the rules score a finished game; otherwise the
        // evaluator gives the value and the priors for the new children.
        let outcome = result(&board);
        let value_for_mover = if outcome == 3 {
            0.5
        } else if outcome != 0 {
            0.0 // the move into this node won
        } else {
            let evaluation = (self.evaluate)(&board);
            for (i, cell) in legal_moves(&board).into_iter().enumerate() {
                self.nodes.push(Node { cell, prior: evaluation.priors[i], ..Node::default() });
                let index = self.nodes.len() - 1;
                self.nodes[current].children.push(index);
            }
            evaluation.value
        };
        // Backup: a node keeps values seen by the player who moved into it, so
        // the value flips at every level on the way back to the root.
        let mut value = 1.0 - value_for_mover;
        for &step in path.iter().rev() {
            self.nodes[step].visits += 1;
            self.nodes[step].value_sum += value;
            value = 1.0 - value;
        }
    }

    // Play the most visited move; visit counts are steadier than averages.
    fn best_move(&self) -> usize {
        let mut best = 9;
        let mut most_visits = 0;
        for &child in &self.nodes[0].children {
            if best == 9 || self.nodes[child].visits > most_visits {
                most_visits = self.nodes[child].visits;
                best = self.nodes[child].cell;
            }
        }
        best
    }

    // The share of the root's simulations that went to one move.
    fn visit_share(&self, cell: usize) -> f64 {
        for &child in &self.nodes[0].children {
            if self.nodes[child].cell == cell {
                return f64::from(self.nodes[child].visits) / f64::from(self.nodes[0].visits - 1);
            }
        }
        0.0
    }
}

// SplitMix64, a small seeded generator for the stand-in's random playouts.
struct SplitMix64 {
    state: u64,
}

impl SplitMix64 {
    fn next(&mut self) -> u64 {
        self.state = self.state.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut mixed = self.state;
        mixed = (mixed ^ (mixed >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        mixed = (mixed ^ (mixed >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        mixed ^ (mixed >> 31)
    }
    fn below(&mut self, count: usize) -> usize {
        (self.next() % count as u64) as usize
    }
}

// A stand-in network: the given priors at the root, even priors elsewhere,
// and as its value the result of one random game played from the position.
// The root priors are the only knowledge it adds.
fn stand_in(root: Board, root_priors: Vec<f64>, seed: u64) -> Evaluator {
    let mut random = SplitMix64 { state: seed };
    Box::new(move |board: &Board| {
        let moves = legal_moves(board);
        let priors = if board.cells == root.cells {
            root_priors.clone()
        } else {
            vec![1.0 / moves.len() as f64; moves.len()]
        };
        let mut playout = *board;
        while result(&playout) == 0 {
            let options = legal_moves(&playout);
            play(&mut playout, options[random.below(options.len())]);
        }
        let outcome = result(&playout);
        let value = if outcome == 3 { 0.5 } else if outcome == board.to_move { 1.0 } else { 0.0 };
        Evaluation { priors, value }
    })
}

fn main() {
    // The worked example: a parent with 100 visits and c_puct = 1.
    let liked = Node { prior: 0.6, visits: 10, value_sum: 5.0, ..Node::default() };
    let untried = Node { prior: 0.05, ..Node::default() };
    assert!((puct_score(&liked, 100, 1.0, 0.5) - 1.0454545454545454).abs() < 1e-12);
    assert!((puct_score(&untried, 100, 1.0, 0.5) - 1.0).abs() < 1e-12);

    // X to move; only cell 0 wins (O must block at 6, then X takes 4 and
    // threatens two lines). The free cells, in order, are 0 1 4 5 6 7 8.
    let mut root = Board { cells: [0; 9], to_move: 1 };
    root.cells[3] = 1;
    root.cells[2] = 2;
    let rest = 0.4 / 6.0;
    let priors = [
        vec![0.6, rest, rest, rest, rest, rest, rest], // the winning move first
        vec![1.0 / 7.0; 7],                            // no opinion
        vec![rest, rest, rest, rest, rest, rest, 0.6], // a non-winning move first
    ];
    let names = ["good", "even", "misleading"];
    let mut mean_share = [0.0; 3];
    let mut picks_winner = [0; 3];
    for setting in 0..3 {
        for seed in 1..=20u64 {
            let mut search = Search::new(root, stand_in(root, priors[setting].clone(), seed), 1.0);
            for _simulation in 0..800 {
                search.simulate();
            }
            mean_share[setting] += search.visit_share(0) / 20.0;
            if search.best_move() == 0 {
                picks_winner[setting] += 1;
            }
        }
        println!(
            "{:<10} priors: {:4.1}% of visits on cell 0, plays it in {} of 20 runs",
            names[setting], 100.0 * mean_share[setting], picks_winner[setting]
        );
    }
    assert!(picks_winner[0] == 20);
    assert!(mean_share[0] > mean_share[1] && mean_share[1] > mean_share[2]);
    assert!(picks_winner[2] < picks_winner[1]);
}

04One turn ahead when both players move at once

In Back Track King both players choose their whole turn at the same time, and a turn has about 253 million options (When to Use Machine Learning counts them). A tree that branches on every option can't get past its root. A search can still check a handful of plans, if the network says which plans are worth checking and what the opponent is likely to do.

A one-turn search does exactly that much:

1. Take candidates from the policy: the network's favourite plan for the turn, plus a few variations built from its second and third choices.
2. Predict the opponent by running your own network from the opponent's seat on the same board and taking its favourite move.
3. Simulate one turn for each candidate against that predicted move, with your exact simulator.
4. Score each result with something you can trust after one turn, such as the score margin, plus the network's value of the new position.
5. Play the best candidate the clock allowed you to score; if time runs out first, play the policy's own choice.

A strong local result and a flat live one is the pattern RamzaBeoulve, 4th in that contest, warned about. Locally his search looked like a +20 point improvement over his plain network, but his first ladder results suggested the plain network was better: his search "was extremely good at predicting" his own network.^[7] A search that predicts the opponent with your network is tested unfairly against that same network: the prediction is exactly right whenever the opponent plays its favourite move. He fixed most of it by playing the search against exploiters and tuning the exploration constant for the opponent's moves. After that the search was worth a lot: without it, he writes, his network ranked around 7th or 8th, and with it the bot spent about a day at #1. Pduhard's search scored a few candidate plans with the value head two turns ahead and won .839 against the same network without it.^[1] That's the same kind of matchup, so only the ladder settles how much of it carries over.

The favourite-move predictor is right 52% of the time, above the break-even, yet the search using it loses. The break-even line assumes a wrong guess lands on any other move at random. A predictor that always names the favourite is wrong in a particular way: it misses most often when the opponent's choice is close to a coin flip. The policy ranks moves by their average over the opponent's whole mix, so it hedges, while the search bets everything on one reply, and in exactly those situations the bet loses more than it wins.

reCurse handled simultaneous moves differently in Winter Challenge 2024, which he won. He let the policy pick 4 candidate moves for each player, ordered the moves of an alpha-beta search by the policy, and assumed the opponent moves knowing your move, a pessimistic rule that needs no prediction at all.^[8]

05Update, don't recompute: NNUE

Alpha-beta search (Minimax and Alpha-Beta) moves through thousands of positions that differ by one move and evaluates each. A network's first layer multiplies every input by every weight: with 190 inputs and 256 hidden units that's 48,640 multiply-adds per position, before the rest of the network runs. Most of that work repeats what was computed one move earlier.

The fix starts with the inputs. Make each one an on-or-off fact, a one-hot input such as "X has a mark on this cell", "O has won this small board" or "the next move must be played in board 4". Then the first layer's output is just the bias plus the weight columns of the inputs that are on. A move changes only a few of them: in Ultimate Tic-Tac-Toe it switches on the new mark and the board the opponent is now sent to, sometimes a board won, and switches off the board the mover was sent to. Add the new columns, subtract the old ones, and the sums are current again. The stored sums are called the accumulator.

The update rule:

In words: keep last position's sums; for every input the move switched on, add its weight column, and for every input it switched off, subtract its column. The cost is the number of changed inputs times the number of hidden units, however many inputs the network has.

This is the core of NNUE, the efficiently updatable network Yu Nasu designed in 2018 for computer shogi, to run fast on a CPU "using various acceleration techniques, including incremental computation."^[9] It was later ported to chess in Stockfish. The nnue-pytorch documentation, from the Stockfish project, lists the conditions: few inputs on at once, inputs that change little from one position to the next, and a network simple enough to run in low-precision integers. In chess with a simple piece-on-square encoding, a move changes at most 4 inputs (castling) and fewer than 3 on average.^[10]

The sums stay exact because the weights are integers. With floating point, every add and subtract rounds a little, and the error grows move after move; the nnue-pytorch documentation recommends keeping a copy of the sums for each position on the search's stack, so undoing a move restores them instead of subtracting, and notes that a quantized integer layer is consistent however the sums were reached.^[10]

The update fits alpha-beta, which walks from a position to its neighbours and back, better than MCTS, which jumps between distant parts of its tree. Tom Alard, 2nd in the Ultimate Tic-Tac-Toe arena at the time of his 2026 write-up, describes the mismatch: the way MCTS explores its tree rules out incremental accumulator updates. His workaround, jacekmax, popularized on CodinGame by jacek, expands all the children of a leaf at once, so the accumulator is built once at the leaf and updated for each child. His network has about 215,000 parameters, was trained on over 300 million self-play positions, and plays inside that MCTS variant; he names MrSubZero's alpha-beta search with an NNUE among the top three.^[11] A related saving needs no stored sums at all. With one-hot inputs, a full recompute only has to add the columns of the inputs that are on, which the widget's amber line counts; marchete lists it among CGZero's speedups.^[5]

06How many network calls fit in a turn

Every network call spends turn time that the search could have spent on more positions. Before choosing a search, count how many calls fit.

The arithmetic is one line:

In words: the time you can safely spend, divided by what one network call costs, measured on the machine that will run it. That count decides which kind of search fits.

The rows come from each author's write-up.^{[1][8][2][7][5]} reCurse's Winter Challenge 2024 network was a convolutional one, "a real CPU killer" in his words, and about 100 evaluations was too few for MCTS in a game "full of traps", so he chose alpha-beta, with the policy ordering the moves. Smaller networks would have allowed more calls, but they "had a sharp decrease in quality that was not compensated by being able to do more search."^[8] CGZero's author measured the other side of that trade: his bot spent 70% of its time inside the network, and every saving there turned into more simulations and a higher win rate.^[5]

Spend the first turn too. Many CodinGame games allow far more time on the first turn (1,000 ms in Back Track King), and reCurse kept a cache of network evaluations partly to make use of it.^[8]

07Teaching the search back to the network

If the search finds better moves than the network, why not train the network to make them directly? The bot would get the search's judgment without spending its time.

AlphaGo Zero builds this into training. Its paper calls the search "a powerful policy improvement operator" and trains the policy head toward the search's visit counts, from 1,600 simulations per move in its self-play games, so the policy keeps learning the choices of a search stronger than itself.^[4] Training one model to copy another's outputs is distillation. Pduhard used it to make his search affordable: a network that ran once per turn learned to give the same moves as one that ran four times, "one quarter of the work, and that is what paid for the search."^[1]

AlphaGo Zero's version differs in ways that may matter: it trains on the search's whole spread of visits, not only the move it chose, and it repeats the cycle on every round of self-play, while the lab ran one round of copying chosen plans in a game where both players move at once. reCurse also tried bringing search into training in Summer Challenge 2024 and set it aside after unconvincing first attempts.^[2] One failed round in one game doesn't rule the idea out. The bar is the same as for any change: the result has to win against fixed opponents, then on the ladder.

08Where network search goes wrong

No fallback move. Network calls take longer on a slower machine; reCurse saw his iteration count change with the CodinGame machine his bot landed on. Keep the policy's own move ready from the start of the turn and check the clock between calls.

Trusting priors that never get checked. A network that has learned to ignore a move keeps ignoring it, because the search rarely visits it. Self-play needs noise at the root, as AlphaGo Zero adds, or training may never find out the move was good.

Floating-point accumulators that drift. Adding and subtracting floats move after move collects rounding error. Use integer first-layer weights, or restore saved sums when you undo a move.

A local gain inside the live noise. In the author's lab, a search that won clearly in local matches landed live inside the 1.62-point spread that the plain network's identical resubmissions produced. Compare a live result with that spread before calling it a gain.

09What's next

Case Study: Back Track King tells the whole story behind the lab results on this page, in order: the hand-written contest bot and its Gold finish, the learning attempts that failed and the measuring mistake that hid it, the rebuild from the top players' post-mortems, the 917,630 games to the first Legend network, the plateau, and the decision to stop.

10Sources

Players' numbers and quotes are from their own write-ups. Numbers marked as the author's lab are first-hand records from one lab and aren't general results. Widget readouts are computed in the page from seeded games and stand-in networks.

1. Pduhard, 2026. Summer Challenge 2026, Back Track King: 3rd, README. About a millisecond per network pass on CodinGame, two to four plans scored per turn, the small search's 0.839 against the same network without it, and the distilled one-pass student that paid for the search.
2. reCurse, 2024. Summer Challenge 2024 post-mortem (2nd place). A PPO network plugged into decoupled UCT with PUCT selection, 1,000 to 3,000 iterations a turn, several short searches voting, noise added to the policy, and an unconvincing first try at search inside training.
3. David Silver et al., 2018. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play, Science 362(6419), doi:10.1126/science.aar6404. AlphaZero's 60,000 positions a second against Stockfish's 60 million, and 800 simulations per move in training.
4. David Silver et al., 2017. Mastering the game of Go without human knowledge (authors' manuscript), Nature 550, doi:10.1038/nature24270. The PUCT selection rule, leaf evaluation by the network with no rollouts, root noise in self-play, and search probabilities as training targets.
5. marchete, 2021 to 2023. CGZero: AlphaZero-like implementation for Oware Abapa, README and the playground notes in markdowns/. An 80 KB network inside MCTS, top 6 in Oware Abapa, and a higher win rate from 10,000 simulations a turn instead of 5,000.
6. Author's lab records, 2026 (private repository). The one-turn search, its local and live results and the opponent-prediction study: experiments/runs/search-check-20261025/manifest.json; six live runs of identical plain-network code and the October 25 and 26 entries: AGENTS.md; the search distillation: experiments/runs/search-distill-20261026/manifest.json.
7. RamzaBeoulve, 2026. 4th place solution, CodinGame forum, Summer Challenge 2026 feedback and strategies, post 10. Smitsimax with network priors, about 1,700 iterations a turn, and the warning that a search tested against its own network overstates its gain.
8. reCurse, 2025. Winter Challenge 2024 post-mortem (1st place). About 100 network evaluations a turn, alpha-beta with the policy for move ordering and 4 candidates per player, depth 2, and the trade between network size and search.
9. Yu Nasu, 2018. NNUE: Efficiently Updatable Neural-Network-based Evaluation Functions for Computer Shogi (in Japanese, English abstract). The original NNUE, built for incremental computation on a CPU.
10. Official Stockfish project, 2026. NNUE, nnue-pytorch documentation (file last changed 2026-09-30). The accumulator's add and subtract rule, at most 4 changed inputs per chess move, and why quantized integers keep incremental sums exact.
11. Tom Alard, 2026. Fighting for #1 in the Ultimate Tic-Tac-Toe Arena (archived copy). Three inputs updated per move, why NNUE fits alpha-beta better than MCTS, and his 215,000-parameter network inside an MCTS variant.