Candidate ordering and pruning

Deep dive

How it works

In: node (depth, window, static eval, move list) · Out: a move order and a skip/reduce decision per move · State: killer, history and counter-move tables, kept across nodes · Cost: O(n) scoring plus lazy selection, tables of about 40 KiB.

Order of operations in a non-root node of depth d:

1. Probe TT; cut if the stored bound allows it (non-PV nodes).
2. Static eval e. improving = e is higher than two plies ago (same side).
3. Reverse futility (static null move): non-PV, not in check, d ≤ ~8, e − margin·d ≥ β → return e.
4. Null move: non-PV, not in check, has non-pawn material, e ≥ β, previous move not null. Make a null move, search to d − 1 − R with window (−β, −β+1). Score ≥ β → return it (don't return unproven mate scores).
5. Generate and order: TT move → captures with SEE ≥ 0 by MVV-LVA → killer 1, killer 2 → counter-move → quiets by history → captures with SEE < 0.
6. Per move: late move pruning (skip quiets after (3 + d²)/(2 − improving) moves at low depth), futility (skip quiets if e + margin(d) ≤ α), SEE pruning (skip captures that lose material beyond a depth-scaled threshold). Never prune before one move is searched, and never moves that give check or escape check.
7. LMR: for quiet moves after the first 1-3 at d ≥ 3, search at d − 1 − r with a null window; if the score beats α, re-search at d − 1 (and then with the full window if PV).
8. On a β cutoff by a quiet move: store killer and counter-move, raise its history, lower history of quiets tried before it.

Code

pub type Move = u16; // bits 0-5 from, 6-11 to, 12-15 flags; 0 = none
const fn from_sq(m: Move) -> usize { (m & 63) as usize }
const fn to_sq(m: Move) -> usize { (m >> 6 & 63) as usize }
pub const MAX_PLY: usize = 128;
pub const HIST_MAX: i32 = 16_384;

#[derive(Clone, Copy)]
pub struct MoveInfo { pub m: Move, pub victim: Option<u8>, pub attacker: u8, pub see_ok: bool } // kinds 0..6 = P N B R Q K

pub struct Heuristics {
    pub killers: [[Move; 2]; MAX_PLY],
    pub history: [[[i32; 64]; 64]; 2], // [side][from][to]
    pub counter: [[Move; 64]; 64],     // [prev from][prev to] -> refutation
    lmr: [[i32; 64]; 64],
}

/// History "gravity": entries saturate smoothly at ±HIST_MAX instead of overflowing.
fn gravity(e: &mut i32, bonus: i32) {
    let b = bonus.clamp(-HIST_MAX, HIST_MAX);
    *e += b - *e * b.abs() / HIST_MAX;
}

impl Heuristics {
    pub fn new() -> Box<Self> {
        let mut h = Box::new(Heuristics {
            killers: [[0; 2]; MAX_PLY], history: [[[0; 64]; 64]; 2], counter: [[0; 64]; 64], lmr: [[0; 64]; 64],
        });
        for d in 1..64 {
            for n in 1..64 { h.lmr[d][n] = (0.75 + (d as f64).ln() * (n as f64).ln() / 2.25) as i32; }
        }
        h
    }

    pub fn score(&self, mi: &MoveInfo, tt: Move, ply: usize, side: usize, prev: Move) -> i32 {
        let mvv_lva = |v: u8| 64 * v as i32 - mi.attacker as i32; // most valuable victim, least valuable attacker
        if mi.m == tt { return i32::MAX; }
        match mi.victim {
            Some(v) if mi.see_ok => 2_000_000 + mvv_lva(v),
            Some(v) => -2_000_000 + mvv_lva(v), // losing captures go last
            None if mi.m == self.killers[ply][0] => 1_000_002,
            None if mi.m == self.killers[ply][1] => 1_000_001,
            None if prev != 0 && mi.m == self.counter[from_sq(prev)][to_sq(prev)] => 1_000_000,
            None => self.history[side][from_sq(mi.m)][to_sq(mi.m)],
        }
    }

    /// Quiet `best` failed high; `tried` are the quiets searched before it at this node.
    pub fn on_cutoff(&mut self, best: Move, tried: &[Move], depth: i32, ply: usize, side: usize, prev: Move) {
        if self.killers[ply][0] != best {
            self.killers[ply][1] = self.killers[ply][0];
            self.killers[ply][0] = best;
        }
        if prev != 0 { self.counter[from_sq(prev)][to_sq(prev)] = best; }
        let bonus = (16 * depth * depth).min(1200);
        gravity(&mut self.history[side][from_sq(best)][to_sq(best)], bonus);
        for &m in tried { gravity(&mut self.history[side][from_sq(m)][to_sq(m)], -bonus); }
    }

    pub fn reduction(&self, depth: i32, move_no: usize, pv: bool, improving: bool, hist: i32) -> i32 {
        let mut r = self.lmr[depth.clamp(0, 63) as usize][move_no.min(63)];
        r += !pv as i32 + !improving as i32;
        r -= hist / 8192; // well-scored quiets are reduced less
        r.min(depth - 2).max(0) // reduced depth stays >= 1
    }
}

/// Lazy selection sort: most nodes cut after 1-3 moves, so a full sort is wasted work.
pub struct Picker { moves: Vec<(MoveInfo, i32)>, next: usize }

impl Picker {
    pub fn new(h: &Heuristics, list: &[MoveInfo], tt: Move, ply: usize, side: usize, prev: Move) -> Self {
        Picker { moves: list.iter().map(|mi| (*mi, h.score(mi, tt, ply, side, prev))).collect(), next: 0 }
    }
    pub fn next(&mut self) -> Option<MoveInfo> {
        let rest = &mut self.moves[self.next..];
        let best = (0..rest.len()).max_by_key(|&i| rest[i].1)?;
        rest.swap(0, best);
        self.next += 1;
        Some(self.moves[self.next - 1].0)
    }
}

pub struct NodeInfo {
    pub depth: i32, pub pv: bool, pub in_check: bool, pub eval: i32, pub beta: i32,
    pub improving: bool, pub non_pawn_material: bool, pub prev_was_null: bool,
}

pub fn reverse_futility(n: &NodeInfo) -> bool {
    !n.pv && !n.in_check && n.depth <= 8 && n.eval - 90 * (n.depth - n.improving as i32) >= n.beta
}

/// Some(R) if a null-move search should be tried, searched to depth - 1 - R.
pub fn null_move_r(n: &NodeInfo) -> Option<i32> {
    let ok = !n.pv && !n.in_check && !n.prev_was_null && n.non_pawn_material && n.depth >= 3 && n.eval >= n.beta;
    ok.then(|| 3 + n.depth / 3 + ((n.eval - n.beta) / 200).min(3))
}

pub fn lmp_limit(depth: i32, improving: bool) -> usize { ((3 + depth * depth) / (2 - improving as i32)) as usize }

Complexity and constants

• Ordering cost: scoring is O(n) per node; lazy selection is O(k·n) for the k moves actually searched, usually k ≤ 3 at cut nodes.
• History, counter-move and killer tables: 32 KiB + 8 KiB + 512 B, L1/L2 resident.
• A null-move search at depth d − 1 − R costs about B^R less than a normal move at d − 1, where B is the effective branching factor.
• The constants above (90 cp per ply, 200 cp per R step, 16·d² bonus, 8192 history divisor) are reasonable starting points, not tuned values. Every engine tunes them with self-play tests.

Efficiency

• Cost: scoring is O(n) per node and lazy selection O(k·n) for the k moves searched, usually k ≤ 3 at cut nodes; the tables (history 32 KiB, counter-move 8 KiB, killers 512 B) stay in L1/L2. A null-move search costs about B^R less than a normal move (B = effective branching factor). Bound: node count, not ordering cost.
• Levers:
  • TT move first, tried before generating anything — most cut nodes end here — all alpha-beta engines
  • lazy selection sort and staged generation — skips sorting and generating moves that are never searched — nodes cut after 1-3 moves
  • null move and reverse futility — whole subtrees dropped at non-PV nodes — non-PV nodes, not in check
  • LMR with re-search — late quiets searched shallower; errors caught by the re-search — good ordering
  • self-play tuning (SPRT) of margins — fixed-depth tests mislead — every constant
• Naive → standard → state of the art:
  • plain alpha-beta, unordered · effective branching factor about √35 ≈ 6 in chess
  • TT move, MVV-LVA, killers, history · closer to the b^(d/2) bound
  • plus null move, LMR, futility, continuation history · effective branching factor of order 1.5-2

Implementation notes

• SEE (static exchange evaluation): swap-list over attackers of the target square, cheapest attacker first, including X-rays revealed by removed sliders; return see(m) ≥ threshold as a bool so it can stop early.
• Generate in stages. Try the TT move before generating anything; generate captures, then quiets, only if needed. Saves generation work at the many nodes that cut on the TT move.
• More history tables. Continuation history [prev piece][prev to][piece][to] (1-2 plies back) and capture history [piece][to][victim] add most of the remaining ordering gain in modern engines.
• Mate scores. Don't return a null-move score that claims mate; clamp to β.
• Zugzwang. Pawn-only endgames break the null-move assumption; disable it there or verify with a reduced normal search at high depth.
• Extensions. Check extensions (+1 when giving check) and singular extensions (TT move much better than all others at reduced depth → +1) counterbalance reductions in forcing lines.
• Internal iterative reduction. At PV/cut nodes without a TT move, reduce depth by 1 instead of running a separate shallow search.
• Test every change by self-play with an SPRT; see Elo rating. Fixed-depth tests lie, because pruning trades depth for speed.

Pitfalls

• Pruning or reducing while in check, or pruning moves that give check: misses mates.
• Futility pruning at PV nodes or before any move was searched: the node can return −∞.
• Updating history for captures in the quiet table, or with unbounded += d*d: overflow and stale dominance. Use gravity or periodic halving.
• Killers not cleared for ply + 2 at the start of a search iteration (or kept from a different game phase): harmless but noisy.
• LMR reducing to depth ≤ 0 (forgetting the clamp) turns real moves into quiescence calls.
• Null move after null move: two passes return to the same position at lower depth, wasting time and corrupting the TT.

Variants and alternatives

In production

• Games: Stockfish (staged MovePicker, butterfly/continuation/capture history, null move with verification, LMR, singular extensions, ProbCut), Ethereal, Berserk, Koivisto, Fairy-Stockfish, Edax (othello, ProbCut).
• Mixed-integer programming: SCIP selects branching variables by scores such as reliability branching (Achterberg et al. 2005).
• Planning: FF restricts successors to helpful actions (Hoffmann and Nebel 2001); Fast Downward searches preferred operators first (Helmert 2006).

Implementations

Sources

• Jonathan Schaeffer, The History Heuristic and Alpha-Beta Search Enhancements in Practice, IEEE TPAMI 11(11), 1989. paper
• Selim G. Akl, Monroe M. Newborn, The Principal Continuation and the Killer Heuristic, ACM Annual Conference, 1977.
• Chrilly Donninger, Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs, ICCA Journal 16(3), 1993.
• Ernst A. Heinz, Adaptive Null-Move Pruning, ICCA Journal 22(3), 1999.
• Thomas Anantharaman, Murray Campbell, Feng-hsiung Hsu, Singular Extensions: Adding Selectivity to Brute-Force Searching, Artificial Intelligence 43(1), 1990.
• Michael Buro, ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm, ICCA Journal 18(2), 1995.
• Chess Programming Wiki, entries Late Move Reductions, Null Move Pruning, Static Exchange Evaluation (chessprogramming.org).
• Tobias Achterberg, Thorsten Koch, Alexander Martin, Branching rules revisited, Operations Research Letters 33(1), 2005. paper
• Jörg Hoffmann, Bernhard Nebel, The FF Planning System: Fast Plan Generation Through Heuristic Search, JAIR 14, 2001. paper
• Malte Helmert, The Fast Downward Planning System, JAIR 26, 2006. paper · code