Alpha-beta search

Deep dive

How it works

Parts:

• negamax recursion — one function; value of a node = best of the negated child values
• window [α, β] — passed down; narrows as bounds are proven
• move generator with ordering hooks — decides how early a cutoff happens
• quiescence search — extends the leaves through unstable (tactical) moves
• driver — iterative deepening with aspiration windows, clock checks

Operations (steps below): search a node, cut off, re-search on a window miss, deepen one level.

1. Negamax form. Scores are always from the side to move: score(child) = -search(child, -β, -α).
2. Fail-soft. Return the best score found even outside [α, β]; it gives tighter bounds for the transposition table and aspiration re-searches.
3. Leaves → quiescence. At depth 0, don't evaluate a position in the middle of a capture sequence. Search captures (and promotions) only, with stand-pat: the side to move may decline all captures, so eval is a lower bound.
4. Terminal nodes. No legal moves: checkmated → -MATE + ply (prefer faster mates), stalemate → 0. Repetitions and the 50-move rule → 0 (draw score) before searching.
5. PVS. First move with the full window; later moves with (α, α+1). A null-window search only answers "better than α or not" and cuts off much more. If it says "better", re-search with (α, β).
6. Iterative deepening. Search depth 1, 2, 3 … until the time is up; the previous PV move (via TT) is searched first.
7. Aspiration windows. From depth ~4, search [prev − δ, prev + δ]. On fail low/high, widen that side and re-search; grow δ geometrically.

        α=-inf β=+inf               root (max)
        /         \
     a: 3       b: ≤ 2  ← first reply of b scores 2 ≤ α=3:
                          the remaining replies of b are cut

Code

use std::time::{Duration, Instant};

pub const INF: i32 = 32_000;
pub const MATE: i32 = 31_000; // |score| > MATE - MAX_PLY means a forced mate
pub const MAX_PLY: usize = 128;

pub trait Game: Clone {
    type Move: Copy + PartialEq;
    fn moves(&self, out: &mut Vec<Self::Move>);    // legal moves, best guess first
    fn captures(&self, out: &mut Vec<Self::Move>); // tactical moves for quiescence
    fn play(&self, m: Self::Move) -> Self;         // copy-make
    fn in_check(&self) -> bool;
    fn eval(&self) -> i32;                         // from the side to move
    fn is_draw(&self) -> bool;                     // repetition, 50-move rule, ...
}

pub struct Search<G: Game> {
    pub nodes: u64,
    pub stop: bool,
    deadline: Instant,
    pv: Vec<Vec<G::Move>>, // triangular PV: pv[ply] = best line from ply
}

impl<G: Game> Search<G> {
    pub fn new() -> Self {
        Search { nodes: 0, stop: false, deadline: Instant::now(), pv: vec![Vec::new(); MAX_PLY + 1] }
    }

    pub fn think(&mut self, root: &G, max_depth: i32, budget: Duration) -> (Option<G::Move>, i32) {
        self.deadline = Instant::now() + budget;
        self.stop = false;
        let (mut best, mut score) = (None, 0);
        for depth in 1..=max_depth {
            let mut delta = 25;
            let (mut lo, mut hi) = if depth >= 4 { (score - delta, score + delta) } else { (-INF, INF) };
            let s = loop {
                let s = self.negamax(root, depth, lo, hi, 0);
                if self.stop { break s; }
                if s <= lo { lo = (lo - delta).max(-INF); }      // fail low: lower alpha
                else if s >= hi { hi = (hi + delta).min(INF); } // fail high: raise beta
                else { break s; }
                delta = (delta * 2).min(INF);
            };
            if self.stop { break; } // keep the last completed iteration
            score = s;
            best = self.pv[0].first().copied();
            if score.abs() > MATE - MAX_PLY as i32 { break; } // forced mate found
        }
        (best, score)
    }

    fn tick(&mut self) {
        self.nodes += 1;
        if self.nodes & 2047 == 0 && Instant::now() >= self.deadline { self.stop = true; }
    }

    fn negamax(&mut self, g: &G, depth: i32, mut alpha: i32, mut beta: i32, ply: usize) -> i32 {
        self.pv[ply].clear();
        if depth <= 0 { return self.qsearch(g, alpha, beta, ply); }
        self.tick();
        if ply > 0 {
            if g.is_draw() { return 0; }
            alpha = alpha.max(-MATE + ply as i32); // mate-distance pruning
            beta = beta.min(MATE - ply as i32 - 1);
            if alpha >= beta { return alpha; }
        }
        if ply >= MAX_PLY - 1 { return g.eval(); }
        let mut moves = Vec::with_capacity(64);
        g.moves(&mut moves);
        if moves.is_empty() { return if g.in_check() { -MATE + ply as i32 } else { 0 }; }
        let mut best = -INF;
        for (i, &m) in moves.iter().enumerate() {
            let child = g.play(m);
            let mut s;
            if i == 0 {
                s = -self.negamax(&child, depth - 1, -beta, -alpha, ply + 1);
            } else {
                s = -self.negamax(&child, depth - 1, -alpha - 1, -alpha, ply + 1); // null window
                if s > alpha && s < beta {
                    s = -self.negamax(&child, depth - 1, -beta, -alpha, ply + 1); // re-search
                }
            }
            if self.stop { return 0; }
            if s > best {
                best = s;
                if s > alpha {
                    alpha = s;
                    let tail = std::mem::take(&mut self.pv[ply + 1]);
                    self.pv[ply].clear();
                    self.pv[ply].push(m);
                    self.pv[ply].extend_from_slice(&tail);
                    self.pv[ply + 1] = tail;
                    if s >= beta { break; } // cutoff
                }
            }
        }
        best
    }

    fn qsearch(&mut self, g: &G, mut alpha: i32, beta: i32, ply: usize) -> i32 {
        if g.in_check() { return self.negamax(g, 1, alpha, beta, ply); } // must answer the check
        self.tick();
        let stand_pat = g.eval();
        if stand_pat >= beta || ply >= MAX_PLY - 1 { return stand_pat; }
        alpha = alpha.max(stand_pat);
        let mut best = stand_pat;
        let mut caps = Vec::with_capacity(16);
        g.captures(&mut caps);
        for m in caps {
            let s = -self.qsearch(&g.play(m), -beta, -alpha, ply + 1);
            if self.stop { return 0; }
            if s > best {
                best = s;
                if s > alpha { alpha = s; if s >= beta { break; } }
            }
        }
        best
    }
}

Complexity and constants

• Minimal tree (Knuth-Moore): b^⌈d/2⌉ + b^⌊d/2⌋ − 1 leaves. b = 35, d = 10: 2·35⁵ ≈ 1.05·10⁸ instead of 35¹⁰ ≈ 2.8·10¹⁵.
• Quiescence nodes are often more than half of all nodes; keep captures() cheap and ordered (MVV-LVA, SEE).
• Iterative deepening with effective branching factor B costs a factor of about B/(B−1) over the last iteration alone: 2× for B = 2, less for larger B, and it is repaid by better ordering.
• Node rates: order of 10⁶-10⁷ nodes/s per core for bitboard engines with a handcrafted or small NNUE evaluation.

Efficiency

• Cost: one node is move generation plus a recursive call; bitboard engines with a small evaluation reach order of 10⁶-10⁷ nodes/s per core. Tree size is the bound: minimax visits b^d leaves, alpha-beta with perfect ordering b^⌈d/2⌉ + b^⌊d/2⌋ − 1 (Knuth and Moore 1975). Bound: branch mispredictions and cache misses in the TT, not arithmetic.
• Levers:
  • best move first (TT move, captures, killers) — tree moves toward b^(d/2), about twice the depth (Knuth and Moore 1975) — any search
  • null-window PVS — most later moves answer only "better than α?" (Marsland and Campbell 1982) — good ordering
  • transposition table — shared sub-results across move orders — graphs, not trees
  • aspiration windows — narrower windows cut more; costs re-searches on a miss — stable scores
  • clock check every 2,048 nodes — no Instant::now() per node — all engines
• Naive → standard → state of the art:
  • plain minimax · b^d leaves
  • alpha-beta, fixed depth, unordered · between b^(d/2) and b^d, depending on ordering
  • ID + TT + PVS + aspiration + Lazy SMP · effective branching factor of order 1.5-2

Implementation notes

• Score range. Use i32 (or i16 in the TT) with INF > MATE > MATE − MAX_PLY > any eval. Clamp evaluations so they never reach the mate band.
• Mate scores in the TT. Stored mate scores are relative to the root; convert to "mate in n from this node" on store and back on probe (see transposition table).
• Time control. Check the clock every 1-4 k nodes, not every node. Keep a soft limit (don't start a new iteration past ~50 % of the budget) and a hard limit (abort mid-iteration). An aborted iteration's best move may still be used if it was fully searched and beat the previous one.
• No allocation in the hot path. Production engines use fixed arrays per ply (move lists of 256, PV arrays), not Vec.
• Ordering hooks belong in moves(): TT move, good captures, killers, history. See move ordering and pruning.
• Parallel search. Lazy SMP: N threads search the same root, share only the TT, and differ slightly in depth; simple and scales well to tens of cores. Older schemes (YBWC, PVS splitting) split the tree explicitly.
• Aspiration δ. Start small (order of 10-30 centipawns, or derive it from score volatility) and widen geometrically; an initial window that is too narrow causes repeated re-searches.

Pitfalls

• Fail-hard returns mixed with fail-soft TT bounds: subtle inconsistencies and search instability.
• Returning a draw score at the root: the engine then has no move. Skip draw checks at ply 0.
• Quiescence without in-check handling: stand-pat while in check hides mates.
• Using the PV of an aborted iteration whose first move was searched only partially.
• Not negating the window correctly in negamax: (-β, -α) and the null window (-α−1, -α).
• Aspiration re-search loops that never terminate because δ overflows or bounds are not clamped to ±INF.

Variants and alternatives

In production

• Games: Stockfish (PVS, aspiration windows, iterative deepening, Lazy SMP), Komodo Dragon, Ethereal, Berserk, Chinook (checkers), Fairy-Stockfish (chess variants, shogi), Edax (othello).
• Learned-model verification: lower bounds on a network's robustness computed by alpha-beta over a two-player game (Wu et al. 2020).
• Search theory: branch-and-bound formulation of AND/OR tree and game-tree search (Kumar and Kanal 1983).

Implementations

Sources

• Donald E. Knuth, Ronald W. Moore, An Analysis of Alpha-Beta Pruning, Artificial Intelligence 6(4), 1975. paper
• T. Anthony Marsland, Murray Campbell, Parallel Search of Strongly Ordered Game Trees, ACM Computing Surveys 14(4), 1982. paper
• Alexander Reinefeld, An Improvement to the Scout Tree Search Algorithm, ICCA Journal 6(4), 1983.
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin, Best-First Fixed-Depth Minimax Algorithms, Artificial Intelligence 87, 1996. paper
• Vipin Kumar, Laveen N. Kanal, A General Branch and Bound Formulation for Understanding and Synthesizing And/Or Tree Search Procedures, Artificial Intelligence 21, 1983. paper
• Min Wu, Matthew Wicker, Wenjie Ruan, Xiaowei Huang, Marta Kwiatkowska, A Game-Based Approximate Verification of Deep Neural Networks with Provable Guarantees, Theoretical Computer Science 807, 2020. paper · arXiv
• Chess Programming Wiki, entries Principal Variation Search, Aspiration Windows, Quiescence Search (chessprogramming.org).