Minimax and Alpha-Beta

01Look ahead: the game tree

The greedy bot from Evaluation Functions scores each of its own moves and takes the best. It never asks what the opponent does next. Picture a corridor with a big open area at the far end. Driving in looks good for one turn, because every cell beyond the corridor counts as yours. Then the opponent seals the far end, and you're left with the corridor. To see that coming, a bot has to consider the opponent's reply, and its own answer to that reply.

Written out, those possibilities form a game tree. Each position is a node, each legal move is a branch to the position it leads to, and the positions where the look-ahead stops are leaves. The number of moves from a position is its branching factor: at most 3 for a moving light cycle, since it can't turn back into its own trail. Depth is counted in plies, one move by one player each.

Minimax values the tree from the bottom up. The evaluation from page 4 scores every leaf from your side. Where it's your move, a position is worth its best child, because you'll pick that one. Where it's the opponent's move, a position is worth its worst child for you, because you assume the opponent picks that one. Your levels are called MAX and the opponent's MIN.

In formula form, minimax uses the evaluation at the leaves and alternates max and min above them:

In words: score the positions at the bottom with the evaluation. Going up, take the largest value on levels where you move and the smallest where the opponent moves. The root's best child is the move to play.

Writing a max function and a min function doubles the code. Light cycles between two players is zero-sum: anything good for one player is exactly as bad for the other. So score every position from the side of the player to move, and one rule covers both levels. This form is called negamax, and it's how Knuth and Moore wrote the algorithm in their 1975 analysis.^[1]

In words: a position is worth the best of its children, where each child's value is negated because it was computed for the other player. At a leaf, return the evaluation for the player to move.

02Skip what can't matter: alpha-beta

A full tree grows fast. With 3 moves per position, eight plies hold up to 3⁸ = 6,561 leaves, and each leaf costs two breadth-first searches. Most of that work can't change the answer.

Alpha-beta pruning applies that test at every level of the tree, carrying two numbers down as it goes. Alpha is the score the player to move is already sure of from moves searched so far. Beta is the score the opponent can already hold it to through some other line. As soon as a move's value reaches beta, the opponent would never allow the position, so the remaining replies there are skipped. That skip is a cutoff. Knuth and Moore put it in game terms: once a move has been refuted, "we need not search for the best possible refutation."^[1]

Skipping never changes the result. Alpha-beta returns exactly the value plain minimax would, and Knuth and Moore proved it.^[1] What changes is the number of leaves it reads, and that depends on the order it tries moves in.

How much can pruning save at best? If the best move is always searched first, alpha-beta reads exactly this many leaves of a tree where every position has the same number of moves:

In words: with perfect ordering, the work grows with half the depth instead of the full depth, so alpha-beta reads roughly the square root of the b^d leaves minimax reads. Plain minimax reads all b^d.

03Best move first

The formula has a catch. It assumes the best move is always searched first, and if you knew the best move you wouldn't need to search. In the worst order alpha-beta prunes nothing and reads every leaf.^[1] Real searches land in between, and how close they get to the best case depends on how good their first guesses are.

Where do good first guesses come from? Light-cycle bots and chess programs use the same few sources:

• The previous search's best line. Section 05 searches depth 1, then depth 2, and so on. The line of play each search expects is its principal variation, and it's usually close to right one depth later, so it goes first.
• Killer moves. Often most moves in a position are refuted by the same reply. A reply that keeps causing cutoffs is a killer move, and the killer heuristic remembers, for each depth, the one or two that have been causing cutoffs and tries them early at the other positions at that depth.^[3]
• The history heuristic. Keep a score for every move, raise it whenever that move causes a cutoff or turns out best anywhere in the tree, and sort by it. Schaeffer notes that the killer heuristic is a special case of it. In his chess program, history scores and transposition tables (section 06) together gave over 99% of the possible tree-size reduction at depths up to 8.^[3]
• A quick estimate. Score each child with something cheap, such as one evaluation, and search the best-looking first.

The light-cycle widgets on this page try the previous best line first, then the latest killer move for that depth, then straight, right and left.

04Alpha-beta plays light cycles

On a real game the question is what depth buys. The widget below runs an alpha-beta bot with page 4's Voronoi evaluation at depths 1 to 8, 50 games per depth, against two opponents. The board is 15×10 and players move in turn, as in CodinGame's version.

Against a bot that ignores the opponent, one ply of a good evaluation is nearly enough. Against a bot with the same evaluation, three plies lift the score from about half to about 70%, and the deeper searches add less than 50 games can measure on this board. A likely reason is that every leaf uses the same evaluation, so its blind spots, such as the one-cell doors from page 4, survive at any depth. a1k0n, who won the 2010 Google AI Challenge with an alpha-beta Tron bot, put it bluntly: "a better evaluation heuristic will always beat deeper minimax searches, because a deep minimax search using a flawed evaluation heuristic is self-deluded about what its opponent is actually going to do."^[4] That's one winner's view from one contest, and the widget's numbers are consistent with it.

For a sense of real depths: Janzert's alpha-beta bot from the same contest usually saw about 7 moves ahead with 30,000 nodes per turn at the start of an open 15×15 map on his machine, about 20 near the end of the open game, and about 40 once the players were separated.^[5]

05Answer before the deadline

Tron Battle gives each move less than 100 ms, and a bot that answers late loses the game.^[6] A fixed search depth can't promise that. The node count depends on how many moves each position has and how often pruning succeeds, so the same depth can take a millisecond on one turn and blow the budget on the next.

Iterative deepening sidesteps the problem. Search to depth 1, then depth 2, then 3, until the clock says stop, and answer with the deepest search that finished. Throw away the search that was cut off: it has looked at some moves and not others, so its favorite proves nothing. a1k0n described finally realizing "that when time runs out on a minimax search, you have to throw away the ply you're in the middle of searching and use the best move from the previous ply".^[4]

With alpha-beta the repeats can even pay for themselves. Each finished depth's principal variation goes first in the next search, and better ordering means more cutoffs. In the widget below, iterative deepening reaches depth 8 after 985 nodes in all, while a single depth-8 search from scratch needs 1,579.

Iterative deepening is older than its best-known analysis. Korf's 1985 paper proved it asymptotically optimal among brute-force tree searches in time, space and solution length, and named Slate and Atkin's chess program Chess 4.5 as its first documented use. He also explained why game programs use it: it reaches the deepest search a fixed time allows, the last complete search is there to fall back on when time runs out, and its results order the next search.^[7] Graph Traversal shows the same idea for finding paths.

1. Start timing when the turn's input starts arriving. Reading input, searching and printing all count against the same limit.
2. Leave a margin. Aim to finish well inside the limit, because the operating system can pause your program between two clock checks, and the output still has to be written.
3. Read the clock every few dozen nodes. Reading it costs time too. The code on this page checks every 64 nodes.
4. Don't start a depth that can't finish. Each depth costs several times the previous one, so if much of the budget is already gone, answer now.
5. Always hold a legal move. Until a search finishes, answer with the first legal move.

06Remember positions: transposition tables

The same position can turn up more than once in a search, reached by different orders of moves. In chess, developing a knight and then a bishop reaches the same position as the bishop and then the knight, with the same replies in between. Each repeat is a whole subtree searched again. In light cycles, a trail records the exact route, so repeats are rarer in the open game. After separation they're common: a one-player fill reaches the same filled area and head by many different routes.

A transposition table is a hash table keyed by position that stores what the search learned there: the value, how deep the search below it went, and the best move it found. On a repeat, a value from a search at least as deep can be reused outright; otherwise the stored best move is tried first, which helps the ordering.^[3] One detail matters for correctness: a value found after a cutoff is only a bound, so each entry also records whether it's exact, a lower bound or an upper bound.^[9] Janzert's 2010 Tron bot used a transposition table with two entries per slot, and also cached its chamber evaluations by a hash of the area.^[5]

The table needs a fast fingerprint of each position. Zobrist hashing, from Albert Zobrist's 1970 report, gives every possible occupant of every square its own random number and XORs together the numbers for everything on the board. XOR undoes itself, so a move updates the key with one or two XORs instead of a recount, and the key doesn't depend on the order of the moves.^[10]

Two different positions can still share a table slot, a hash collision, and a search that trusts the wrong entry plays from a position it never reached. Zobrist's fix is to store a second, independent code with each entry and compare it on every lookup. For a 32K-entry table he estimated a 3% error rate with 20-bit check codes and 0.1% with 25 bits.^[10]

07Three or four players: paranoid and maxⁿ

Tron Battle's arena runs battles of two to four cycles, and when a player crashes its trail disappears and frees space for everyone left.^[6] Minimax assumes a single opponent who wants exactly what you don't. With three players, one opponent gaining doesn't have to mean you losing; the third player may be the one who pays.

The direct extension is maxⁿ, from Luckhardt and Irani in 1986. Each leaf gets a list of scores, one per player. At each node, the player to move picks the child with the best score for itself, and the whole list is carried up. It assumes every player plays for itself.^[11] The cost is pruning: with independent goals there's little a search can rule out, and Sturtevant and Korf showed that only a limited "shallow" form of alpha-beta pruning applies to maxⁿ.^[12]

The other option is paranoid search. Sturtevant and Korf describe it as "making the 'paranoid' assumption that all our opponents have formed a coalition against us." The game becomes you against one combined opponent, so ordinary alpha-beta works. They add that "this is not a realistic assumption and can lead to suboptimal play," and that the speed it gains "will not, however, guarantee an increase in play quality."^[12]

With four cycles, each opponent's move is its own ply, so a depth of 4 is one move each. On CodinGame, one Tron Battle player, dolmen1234, wrote in 2018 that extending his minimax to every player, with all of them assumed to be fighting him, "seemed to improve my results and get me to legend", while calling it "somehow pessimistic".^[13] Another player reached Legend with no search at all (page 4), so paranoid search is one reported route among several. In The Great Escape contest of 2015, the winner, Recar, and the third-placed Romka both picked a single main rival in three-player games, usually the next player in turn order.^[14]

A common question: if everyone runs the same alpha-beta, shouldn't the bots end up the same? The search loop is the shared part, a few dozen lines. Everything around it differs: the evaluation at the leaves (page 4), the move ordering that decides how deep a turn's budget reaches, raw speed, the clock rules, the endgame, and with three or four players the model of what the opponents want. In the Great Escape tests above, changing only the opponent model moved the score by several points.

08After separation: a race to fill

Once the trails wall the players apart, nothing either one does can affect the other. The game becomes two separate one-player puzzles: make as many moves as possible inside your own region. A search over the opponent's moves is wasted from here on.

Filling well is harder than it looks. On page 4's Chamber board the one-ply bot trapped itself after 20 moves in a 30-cell room, and the number of possible routes through a region grows very fast with its size. Strong light-cycle bots combine a rule with a bounded search:

• A filling rule. a1k0n's: "always choose the move that removes the least number of edges from the graph. In other words, go towards the space with the most walls for neighbors. But! Avoid cut vertices (AKA articulation points), and if you have to enter a cut vertex, then always choose the largest space left over."^[4]
• A search on top of it. a1k0n's endgame tried every short sequence of moves with iterative deepening and finished each one with the filling rule, keeping the sequence that filled the most. Janzert's searched only his own moves after a separation, about 40 moves deep at first, and found the longest path 70 to 150 moves away.^[4][5]
• A bound to stop early. The checkerboard count from page 4 gives the most cells a region can possibly yield, so a search that finds a path that long can stop: nothing longer exists.

09Negamax with a deadline in code

These complete programs search turn-based light cycles on a 7×5 board, small enough that plain minimax is quick to compare against. The evaluation is page 4's territory margin for the player to move. negamax prunes with alpha-beta and reads the clock every 64 nodes; minimax is the same search without pruning, kept as the reference answer; chooseMove deepens one ply at a time, puts the last best move first, and keeps the answer of the deepest finished depth.

main plays 1,000 random positions, the same ones in both languages, and checks four things in each. Alpha-beta at depth 6 returns exactly the minimax value; over all 1,000 positions minimax reads 83,282 leaves and alpha-beta 38,103, 46% as many. With time to spare, iterative deepening plays a move that minimax rates best. A 2 ms budget comes back with a legal move inside Tron Battle's 100 ms limit; on this small board the search solves many positions outright within 2 ms, and in many others the clock cuts it off first. And with no time at all, there's still a move to send. The slowest of the 2 ms answers shows why bots keep a margin: in eleven runs on a heavily loaded 16-core machine it ranged from 2.4 ms to 54 ms, because the operating system can pause a program between two clock checks.

// Negamax with alpha-beta, iterative deepening and a deadline, on turn-based light cycles.
#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstdlib>

using Clock = std::chrono::steady_clock;
constexpr int kWidth = 7, kHeight = 5, kCells = kWidth * kHeight;
constexpr int kWin = 1'000'000;  // bigger than any territory margin on this board
constexpr int kInfinity = 2 * kWin;
constexpr int kUnreached = -1;

struct Board {
    std::array<bool, kCells> blocked{};  // trails and both heads
    std::array<int, 2> head{};           // each player's head cell (y * kWidth + x)
    int toMove = 0;                      // whose turn it is
};

// The cell one step away in direction 0..3 (up, right, down, left), or -1 off the board.
int neighbor(int cell, int direction) {
    const int x = cell % kWidth + std::array{0, 1, 0, -1}[direction];
    const int y = cell / kWidth + std::array{-1, 0, 1, 0}[direction];
    return (x < 0 || y < 0 || x >= kWidth || y >= kHeight) ? -1 : y * kWidth + x;
}

struct MoveList { std::array<int, 4> direction{}; int count = 0; };  // no allocation per node

MoveList legalMoves(const Board& board) {
    MoveList moves;
    for (int direction = 0; direction < 4; ++direction) {
        const int cell = neighbor(board.head[board.toMove], direction);
        if (cell >= 0 && !board.blocked[cell]) moves.direction[moves.count++] = direction;
    }
    return moves;
}

void play(Board& board, int direction) {  // move the player to move, then pass the turn
    const int cell = neighbor(board.head[board.toMove], direction);
    board.blocked[cell] = true;
    board.head[board.toMove] = cell;
    board.toMove = 1 - board.toMove;
}

void undo(Board& board, int oldHead) {  // take back the last move
    board.toMove = 1 - board.toMove;
    board.blocked[board.head[board.toMove]] = false;
    board.head[board.toMove] = oldHead;
}

std::array<int, kCells> distancesFrom(const Board& board, int start) {  // breadth-first search
    std::array<int, kCells> distance;
    distance.fill(kUnreached);
    std::array<int, kCells> queue{};
    int read = 0, write = 0;
    distance[start] = 0;
    queue[write++] = start;
    while (read < write) {
        const int cell = queue[read++];
        for (int direction = 0; direction < 4; ++direction) {
            const int next = neighbor(cell, direction);
            if (next < 0 || board.blocked[next] || distance[next] != kUnreached) continue;
            distance[next] = distance[cell] + 1;
            queue[write++] = next;
        }
    }
    return distance;
}

// Page 4's evaluation, for the player to move: cells it reaches first minus cells the other reaches first.
int evaluate(const Board& board) {
    const auto mine = distancesFrom(board, board.head[board.toMove]);
    const auto theirs = distancesFrom(board, board.head[1 - board.toMove]);
    int margin = 0;
    for (int cell = 0; cell < kCells; ++cell) {
        if (board.blocked[cell]) continue;
        const bool iReach = mine[cell] != kUnreached, theyReach = theirs[cell] != kUnreached;
        if (iReach && (!theyReach || mine[cell] < theirs[cell])) ++margin;
        else if (theyReach && (!iReach || theirs[cell] < mine[cell])) --margin;
    }
    return margin;
}

struct Search {
    Clock::time_point deadline;
    std::int64_t nodes = 0, leaves = 0;
    bool outOfTime = false;
};

// Negamax: the value of the position for the player to move. A result that is good for one player
// is exactly as bad for the other, so one function serves both: score each reply, flip its sign.
int negamax(Board& board, int depth, int alpha, int beta, int ply, Search& search) {
    // Reading the clock costs time too, so look at it once every 64 nodes.
    if (++search.nodes % 64 == 0 && Clock::now() >= search.deadline) search.outOfTime = true;
    if (search.outOfTime) return 0;               // the caller throws this result away
    const MoveList moves = legalMoves(board);
    if (moves.count == 0) return -(kWin - ply);   // a crash: the later the loss, the better
    if (depth == 0) { ++search.leaves; return evaluate(board); }
    int best = -kInfinity;
    for (int i = 0; i < moves.count; ++i) {
        const int oldHead = board.head[board.toMove];
        play(board, moves.direction[i]);
        const int value = -negamax(board, depth - 1, -beta, -alpha, ply + 1, search);
        undo(board, oldHead);
        best = std::max(best, value);
        alpha = std::max(alpha, value);
        if (alpha >= beta) break;  // the opponent has a better choice elsewhere: skip the rest
    }
    return best;
}

// Plain minimax in the same negamax form, with no pruning: the reference answer.
int minimax(Board& board, int depth, int ply, std::int64_t& leaves) {
    const MoveList moves = legalMoves(board);
    if (moves.count == 0) return -(kWin - ply);
    if (depth == 0) { ++leaves; return evaluate(board); }
    int best = -kInfinity;
    for (int i = 0; i < moves.count; ++i) {
        const int oldHead = board.head[board.toMove];
        play(board, moves.direction[i]);
        best = std::max(best, -minimax(board, depth - 1, ply + 1, leaves));
        undo(board, oldHead);
    }
    return best;
}

struct Answer { int bestMove = -1, depth = 0, value = 0; };

// Iterative deepening: search depth 1, then 2, then 3... and answer with the deepest search that
// finished. Until the first one finishes, the answer is the first legal move.
Answer chooseMove(Board board, Clock::duration budget, int maxDepth) {
    Search search{Clock::now() + budget};
    MoveList moves = legalMoves(board);
    Answer answer;
    if (moves.count == 0) return answer;  // every move crashes: nothing to choose
    answer.bestMove = moves.direction[0];
    for (int depth = 1; depth <= maxDepth; ++depth) {
        int alpha = -kInfinity, bestIndex = 0;
        for (int i = 0; i < moves.count; ++i) {
            const int oldHead = board.head[board.toMove];
            play(board, moves.direction[i]);
            const int value = -negamax(board, depth - 1, -kInfinity, -alpha, 1, search);
            undo(board, oldHead);
            if (search.outOfTime) break;
            if (value > alpha) { alpha = value; bestIndex = i; }
        }
        if (search.outOfTime) break;  // an unfinished depth proves nothing: keep the last full one
        answer = {moves.direction[bestIndex], depth, alpha};
        // Search this depth's best move first next time: alpha-beta prunes most when it comes first.
        std::rotate(moves.direction.begin(), moves.direction.begin() + bestIndex,
                    moves.direction.begin() + bestIndex + 1);
        if (alpha >= kWin / 2 || alpha <= -kWin / 2) break;  // a forced win or loss won't change
    }
    return answer;
}

// A tiny random generator, the same in the C++ and Rust programs, so both test the same positions.
struct Random {
    std::uint64_t state;
    std::uint64_t next() { state ^= state << 13; state ^= state >> 7; state ^= state << 17; return state; }
    int below(int n) { return static_cast<int>(next() % static_cast<std::uint64_t>(n)); }
};

// Two random start cells, then up to 12 random legal moves; the player to move can still move.
Board randomPosition(Random& random) {
    for (;;) {
        Board board;
        board.head[0] = random.below(kCells);
        do board.head[1] = random.below(kCells); while (board.head[1] == board.head[0]);
        board.blocked[board.head[0]] = board.blocked[board.head[1]] = true;
        const int plies = random.below(13);
        for (int ply = 0; ply < plies && legalMoves(board).count > 0; ++ply) {
            const MoveList moves = legalMoves(board);
            play(board, moves.direction[random.below(moves.count)]);
        }
        if (legalMoves(board).count > 0) return board;
    }
}

bool isLegal(const Board& board, int direction) {
    const MoveList moves = legalMoves(board);
    return std::find(moves.direction.begin(), moves.direction.begin() + moves.count, direction)
           != moves.direction.begin() + moves.count;
}

int main() {
    Random random{0x9E3779B97F4A7C15ULL};
    constexpr int kPositions = 1000, kDepth = 6;
    std::int64_t minimaxLeaves = 0, alphaBetaLeaves = 0;
    Clock::duration slowest{};
    for (int i = 0; i < kPositions; ++i) {
        Board board = randomPosition(random);
        // 1. Pruning never changes the answer: the same value as plain minimax at the same depth.
        const int reference = minimax(board, kDepth, 0, minimaxLeaves);
        Search unlimited{Clock::time_point::max()};
        assert(negamax(board, kDepth, -kInfinity, kInfinity, 0, unlimited) == reference);
        alphaBetaLeaves += unlimited.leaves;
        // 2. With time to spare, iterative deepening plays a move plain minimax rates best.
        const Answer full = chooseMove(board, std::chrono::hours(1), kDepth);
        assert(full.value == reference && isLegal(board, full.bestMove));
        assert(full.depth == kDepth || std::abs(full.value) >= kWin / 2);  // or it proved the result sooner
        std::int64_t ignored = 0;
        Board after = board;
        play(after, full.bestMove);
        assert(-minimax(after, kDepth - 1, 1, ignored) == reference);
        // 3. A 2 ms budget answers with a legal move, far inside Tron Battle's 100 ms limit.
        const Clock::time_point start = Clock::now();
        const Answer quick = chooseMove(board, std::chrono::milliseconds(2), 64);
        const Clock::duration elapsed = Clock::now() - start;
        assert(isLegal(board, quick.bestMove) && elapsed < std::chrono::milliseconds(100));
        slowest = std::max(slowest, elapsed);
        // 4. With no time at all there is still a move to send.
        assert(isLegal(board, chooseMove(board, Clock::duration::zero(), 64).bestMove));
    }
    std::printf("%d positions at depth %d: minimax read %lld leaves, alpha-beta %lld\n", kPositions,
                kDepth, static_cast<long long>(minimaxLeaves), static_cast<long long>(alphaBetaLeaves));
    std::printf("slowest 2 ms answer: %.2f ms\n",
                std::chrono::duration<double, std::milli>(slowest).count());
}

// Negamax with alpha-beta, iterative deepening and a deadline, on turn-based light cycles.
use std::time::{Duration, Instant};

const WIDTH: i32 = 7;
const HEIGHT: i32 = 5;
const CELLS: usize = (WIDTH * HEIGHT) as usize;
const WIN: i32 = 1_000_000; // bigger than any territory margin on this board
const INFINITY: i32 = 2 * WIN;
const UNREACHED: i32 = -1;

#[derive(Clone)]
struct Board {
    blocked: [bool; CELLS], // trails and both heads
    head: [usize; 2],       // each player's head cell (y * WIDTH + x)
    to_move: usize,         // whose turn it is
}

// The cell one step away in direction 0..3 (up, right, down, left), or None off the board.
fn neighbor(cell: usize, direction: usize) -> Option<usize> {
    let x = cell as i32 % WIDTH + [0, 1, 0, -1][direction];
    let y = cell as i32 / WIDTH + [-1, 0, 1, 0][direction];
    if x < 0 || y < 0 || x >= WIDTH || y >= HEIGHT { None } else { Some((y * WIDTH + x) as usize) }
}

struct MoveList { direction: [usize; 4], count: usize } // no allocation per node

fn legal_moves(board: &Board) -> MoveList {
    let mut moves = MoveList { direction: [0; 4], count: 0 };
    for direction in 0..4 {
        if let Some(cell) = neighbor(board.head[board.to_move], direction) {
            if !board.blocked[cell] { moves.direction[moves.count] = direction; moves.count += 1; }
        }
    }
    moves
}

fn play(board: &mut Board, direction: usize) { // move the player to move, then pass the turn
    let cell = neighbor(board.head[board.to_move], direction).expect("only legal moves are played");
    board.blocked[cell] = true;
    board.head[board.to_move] = cell;
    board.to_move = 1 - board.to_move;
}

fn undo(board: &mut Board, old_head: usize) { // take back the last move
    board.to_move = 1 - board.to_move;
    board.blocked[board.head[board.to_move]] = false;
    board.head[board.to_move] = old_head;
}

fn distances_from(board: &Board, start: usize) -> [i32; CELLS] { // breadth-first search
    let mut distance = [UNREACHED; CELLS];
    let mut queue = [0usize; CELLS];
    let (mut read, mut write) = (0, 0);
    distance[start] = 0;
    queue[write] = start;
    write += 1;
    while read < write {
        let cell = queue[read];
        read += 1;
        for direction in 0..4 {
            let Some(next) = neighbor(cell, direction) else { continue };
            if board.blocked[next] || distance[next] != UNREACHED { continue; }
            distance[next] = distance[cell] + 1;
            queue[write] = next;
            write += 1;
        }
    }
    distance
}

// Page 4's evaluation, for the player to move: cells it reaches first minus cells the other reaches first.
fn evaluate(board: &Board) -> i32 {
    let mine = distances_from(board, board.head[board.to_move]);
    let theirs = distances_from(board, board.head[1 - board.to_move]);
    let mut margin = 0;
    for cell in 0..CELLS {
        if board.blocked[cell] { continue; }
        let (i_reach, they_reach) = (mine[cell] != UNREACHED, theirs[cell] != UNREACHED);
        if i_reach && (!they_reach || mine[cell] < theirs[cell]) { margin += 1; }
        else if they_reach && (!i_reach || theirs[cell] < mine[cell]) { margin -= 1; }
    }
    margin
}

struct Search { deadline: Instant, nodes: i64, leaves: i64, out_of_time: bool }

// Negamax: the value of the position for the player to move. A result that is good for one player
// is exactly as bad for the other, so one function serves both: score each reply, flip its sign.
fn negamax(board: &mut Board, depth: i32, mut alpha: i32, beta: i32, ply: i32, search: &mut Search) -> i32 {
    // Reading the clock costs time too, so look at it once every 64 nodes.
    search.nodes += 1;
    if search.nodes % 64 == 0 && Instant::now() >= search.deadline { search.out_of_time = true; }
    if search.out_of_time { return 0; }           // the caller throws this result away
    let moves = legal_moves(board);
    if moves.count == 0 { return -(WIN - ply); }  // a crash: the later the loss, the better
    if depth == 0 { search.leaves += 1; return evaluate(board); }
    let mut best = -INFINITY;
    for &direction in &moves.direction[..moves.count] {
        let old_head = board.head[board.to_move];
        play(board, direction);
        let value = -negamax(board, depth - 1, -beta, -alpha, ply + 1, search);
        undo(board, old_head);
        best = best.max(value);
        alpha = alpha.max(value);
        if alpha >= beta { break; } // the opponent has a better choice elsewhere: skip the rest
    }
    best
}

// Plain minimax in the same negamax form, with no pruning: the reference answer.
fn minimax(board: &mut Board, depth: i32, ply: i32, leaves: &mut i64) -> i32 {
    let moves = legal_moves(board);
    if moves.count == 0 { return -(WIN - ply); }
    if depth == 0 { *leaves += 1; return evaluate(board); }
    let mut best = -INFINITY;
    for &direction in &moves.direction[..moves.count] {
        let old_head = board.head[board.to_move];
        play(board, direction);
        best = best.max(-minimax(board, depth - 1, ply + 1, leaves));
        undo(board, old_head);
    }
    best
}

struct Answer { best_move: Option<usize>, depth: i32, value: i32 }

// Iterative deepening: search depth 1, then 2, then 3... and answer with the deepest search that
// finished. Until the first one finishes, the answer is the first legal move.
fn choose_move(board: &Board, budget: Duration, max_depth: i32) -> Answer {
    let mut board = board.clone();
    let mut search = Search { deadline: Instant::now() + budget, nodes: 0, leaves: 0, out_of_time: false };
    let mut moves = legal_moves(&board);
    let mut answer = Answer { best_move: None, depth: 0, value: 0 };
    if moves.count == 0 { return answer; } // every move crashes: nothing to choose
    answer.best_move = Some(moves.direction[0]);
    for depth in 1..=max_depth {
        let (mut alpha, mut best_index) = (-INFINITY, 0);
        for i in 0..moves.count {
            let old_head = board.head[board.to_move];
            play(&mut board, moves.direction[i]);
            let value = -negamax(&mut board, depth - 1, -INFINITY, -alpha, 1, &mut search);
            undo(&mut board, old_head);
            if search.out_of_time { break; }
            if value > alpha { alpha = value; best_index = i; }
        }
        if search.out_of_time { break; } // an unfinished depth proves nothing: keep the last full one
        answer = Answer { best_move: Some(moves.direction[best_index]), depth, value: alpha };
        // Search this depth's best move first next time: alpha-beta prunes most when it comes first.
        moves.direction[..=best_index].rotate_right(1);
        if alpha >= WIN / 2 || alpha <= -WIN / 2 { break; } // a forced win or loss won't change
    }
    answer
}

// A tiny random generator, the same in the C++ and Rust programs, so both test the same positions.
struct Random { state: u64 }
impl Random {
    fn next(&mut self) -> u64 { self.state ^= self.state << 13; self.state ^= self.state >> 7; self.state ^= self.state << 17; self.state }
    fn below(&mut self, n: usize) -> usize { (self.next() % n as u64) as usize }
}

// Two random start cells, then up to 12 random legal moves; the player to move can still move.
fn random_position(random: &mut Random) -> Board {
    loop {
        let mut board = Board { blocked: [false; CELLS], head: [0; 2], to_move: 0 };
        board.head[0] = random.below(CELLS);
        board.head[1] = random.below(CELLS);
        while board.head[1] == board.head[0] { board.head[1] = random.below(CELLS); }
        board.blocked[board.head[0]] = true;
        board.blocked[board.head[1]] = true;
        let plies = random.below(13);
        let mut ply = 0;
        while ply < plies && legal_moves(&board).count > 0 {
            let moves = legal_moves(&board);
            play(&mut board, moves.direction[random.below(moves.count)]);
            ply += 1;
        }
        if legal_moves(&board).count > 0 { return board; }
    }
}

fn is_legal(board: &Board, direction: Option<usize>) -> bool {
    let moves = legal_moves(board);
    direction.map_or(false, |direction| moves.direction[..moves.count].contains(&direction))
}

fn main() {
    let mut random = Random { state: 0x9E3779B97F4A7C15 };
    const POSITIONS: i32 = 1000;
    const DEPTH: i32 = 6;
    let (mut minimax_leaves, mut alpha_beta_leaves) = (0i64, 0i64);
    let mut slowest = Duration::ZERO;
    for _ in 0..POSITIONS {
        let mut board = random_position(&mut random);
        // 1. Pruning never changes the answer: the same value as plain minimax at the same depth.
        let reference = minimax(&mut board, DEPTH, 0, &mut minimax_leaves);
        let mut unlimited = Search { deadline: Instant::now() + Duration::from_secs(3600), nodes: 0, leaves: 0, out_of_time: false };
        assert_eq!(negamax(&mut board, DEPTH, -INFINITY, INFINITY, 0, &mut unlimited), reference);
        alpha_beta_leaves += unlimited.leaves;
        // 2. With time to spare, iterative deepening plays a move plain minimax rates best.
        let full = choose_move(&board, Duration::from_secs(3600), DEPTH);
        assert!(full.value == reference && is_legal(&board, full.best_move));
        assert!(full.depth == DEPTH || full.value.abs() >= WIN / 2); // or it proved the result sooner
        let mut after = board.clone();
        play(&mut after, full.best_move.unwrap());
        assert_eq!(-minimax(&mut after, DEPTH - 1, 1, &mut 0), reference);
        // 3. A 2 ms budget answers with a legal move, far inside Tron Battle's 100 ms limit.
        let start = Instant::now();
        let quick = choose_move(&board, Duration::from_millis(2), 64);
        let elapsed = start.elapsed();
        assert!(is_legal(&board, quick.best_move) && elapsed < Duration::from_millis(100));
        slowest = slowest.max(elapsed);
        // 4. With no time at all there is still a move to send.
        assert!(is_legal(&board, choose_move(&board, Duration::ZERO, 64).best_move));
    }
    println!("{POSITIONS} positions at depth {DEPTH}: minimax read {minimax_leaves} leaves, alpha-beta {alpha_beta_leaves}");
    println!("slowest 2 ms answer: {:.2} ms", slowest.as_secs_f64() * 1000.0);
}

10Where searches go wrong

A sign in the wrong place. Negamax only works if every value is from the side of the player to move. An evaluation that scores for a fixed player, or a missing minus sign on one return path, makes the bot play for the opponent on alternate plies.

Trusting a half-finished depth. The best move found so far in an interrupted search is only the best of the moves it reached. Keep the last finished depth's answer.

A move that isn't undone. Searches make and undo moves on one shared board. One branch that forgets to undo corrupts every branch after it. Check after each search that the board is back where it started.

Counting rounds instead of plies. With four players, depth 4 is one move each, and depth 1 sees only your own move. Budgets and depth limits need the same unit everywhere.

The horizon. A search that stops at depth 6 can't see a trap that closes at ply 7, and it will happily walk into one if the evaluation looks good at ply 6. More depth only moves the horizon further out. A better evaluation, like the chamber counts of page 4, sees some traps without searching to them.

11What's next

Alpha-beta needs an evaluation that knows who's winning. In Ultimate Tic-Tac-Toe the obvious hand-written ones mislead: TomAlard, second on its leaderboard in September 2026, notes that a player regularly leads two small boards to none while having a completely lost position.^[16] A turn can also offer up to 81 moves. Monte Carlo Tree Search values positions by playing random games to the end instead, and spends more of those games on the moves that look promising.

12Sources

Widget readouts are computed in the page from seeded trees and seeded games on small boards; they are not CodinGame results. First-hand results from the author's lab are marked as such.

1. Donald E. Knuth and Ronald W. Moore, 1975. An Analysis of Alpha-Beta Pruning, Artificial Intelligence 6(4): 293–326 (scan). Negamax form, alpha-beta returning the minimax value, the best case and its optimality (Corollaries 1 and 3), the worst case, Figure 4, and the history of the method.
2. Chess Programming Wiki. Alpha-Beta. The b = 40, depth 4 example: 2,560,000 leaves for minimax against 3,199 with the best move first.
3. Jonathan Schaeffer, 1989. The History Heuristic and Alpha-Beta Search Enhancements in Practice, IEEE Transactions on Pattern Analysis and Machine Intelligence 11(11): 1203–1212 (author's preprint). Killer moves, the history heuristic, transposition tables, and their combined effect in his chess program at depths up to 8.
4. Andy Sloane (a1k0n), 2010. Google AI Challenge post-mortem. Evaluation over search depth in his view, discarding the unfinished ply, and his endgame filling rule and search.
5. Brian Haskin (Janzert), 2010. Janzert's Tron Bots, Information Page. Search depths of his alpha-beta bot, its transposition table and chamber cache, and its separated-endgame search.
6. CodinGame. Tron Battle, puzzle statement (first league), read 2026-10-30. Battles of 2 to 4 cycles, the 100 ms limit per turn, losing on a late or invalid answer, and a defeated player's trail disappearing.
7. Richard E. Korf, 1985. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search, Artificial Intelligence 27(1): 97–109 (scan). Its optimality, Chess 4.5 as the first documented use, and why game programs deepen iteratively.
8. Author's lab records, 2026 (private repository). games/tronbattle/README.md and games/tronbattle/bots/search/ (budget, clock checks, reply times, local match, fill solver); games/greatescape/bots/escape/ and prompts/results/greatescape-legend-20261029.json (node budget, CodinGame node counts, wall census, opponent-model tests); experiments/live-submissions/tron-battle/ and experiments/live-submissions/great-escape/, submitted.jsonl and rankings.jsonl (submissions, Gold rankings and promotions).
9. Chess Programming Wiki. Transposition Table. What an entry stores, including whether its score is exact, a lower bound or an upper bound.
10. Albert L. Zobrist, 1970. A New Hashing Method with Application for Game Playing, Technical Report 88, Computer Sciences Department, University of Wisconsin. XOR keys updated per move, and check codes against collisions with his error estimates.
11. Carol A. Luckhardt and Keki B. Irani, 1986. An Algorithmic Solution of N-Person Games, Proceedings of AAAI-86: 158–162. The maxⁿ procedure.
12. Nathan R. Sturtevant and Richard E. Korf, 2000. On Pruning Techniques for Multi-Player Games, Proceedings of AAAI-2000: 201–207. Shallow pruning for maxⁿ, and the paranoid reduction with its caveats.
13. dolmen1234, 2018. Post #36 in "Tron Battle (aka Line Racing) multiplayer challenge discussion", CodinGame forum, 13 February 2018. Reaching Legend after searching over all players, each assumed to play against him.
14. CodinGame, 2015. The Great Escape: Top CodinGamers Code Reviews (Internet Archive copy). Recar (1st) and Romka (3rd) on choosing a rival in three-player games.
15. dimkadimon, 2015. Post #9 in "The Great Escape - Strategies", CodinGame forum, 28 February 2015. Laochao's fixed opening that walls off a passage around the edge, and dimkadimon's own variant.
16. Tom Alard (TomAlard), 2026. Fighting for #1 in the Ultimate Tic-Tac-Toe Arena, blog post, 20 September 2026. Why hand-written Ultimate Tic-Tac-Toe evaluations misjudge positions, and his place on the leaderboard at the time.