Principal variation search and aspiration windows

Stage 11 · tag stage-11-pvs · code in crates/engine/src/search.rs

Chapters 7 to 10 made the first move searched at a node very likely to be the best one. This chapter puts that to work. Both ideas here change the window [alpha, beta] a search is given, and both rest on the same fact: the narrower the window, the more alpha-beta can prune.

Null-window searches

What does a search with the window [alpha, alpha + 1] do? No integer score fits strictly between alpha and alpha + 1, so it can’t compute an exact score. It can only answer a yes/no question, is this position worth more than alpha?, and it answers with a bound. That is enough to prune almost everything: every move that is clearly worse fails low at once, and the first move that is better fails high and ends the search.

Principal variation search

At a node where move ordering has done its job, the first move is the best and every other move only needs to be proven worse than it, not given an exact score. Principal variation search (PVS) does exactly that:

1. Search the first move with the full window [alpha, beta].
2. Search every later move with the null window [alpha, alpha + 1].
3. If a later move unexpectedly scores above alpha, the bet failed: search that move again with the full window to get its real score.

    /// The score of the move that led to `child` (the last move on the path), from the
    /// mover's side, searched to `depth`.
    ///
    /// The first move gets the full window. With PVS on, a later move gets a null window
    /// first, at a reduced depth if LMR chose a reduction; if it beats `alpha` it is searched
    /// again at full depth, and then with the full window if it is inside it.
    ///
    /// `cut_node` is the parent's flag. The child of a null-window search is an expected cut
    /// node if its parent is an expected all-node, and the other way round; a child with the
    /// full window is a principal variation node, never a cut node. A late move's reduced
    /// search counts as a cut node whatever the parent, as in Stockfish (GPL-3.0).
    #[allow(clippy::too_many_arguments)]
    fn search_move(
        &mut self,
        child: &Position,
        depth: u32,
        alpha: i32,
        beta: i32,
        how: MoveSearch,
        cut_node: bool,
        pv: &mut Vec<Move>,
    ) -> i32 {
        let pvs = self.techniques.pvs && self.techniques.alpha_beta;
        let null_window = beta - alpha == 1;
        let reduction = match how {
            MoveSearch::Later { reduction } if pvs => reduction,
            _ => return self.search_child(child, depth, alpha, beta, null_window && !cut_node, pv),
        };
        let mv = self.path.last().copied().flatten();
        if reduction > 0
            && let Some(mv) = mv
        {
            self.note(Note::Reduced(mv, reduction));
        }
        let mut score = self.search_child(
            child,
            depth - reduction,
            alpha,
            alpha + 1,
            reduction > 0 || !cut_node,
            pv,
        );
        if score > alpha && reduction > 0 && !self.aborted {
            if let Some(mv) = mv {
                self.note(Note::ReductionResearch(mv));
            }
            score = self.search_child(child, depth, alpha, alpha + 1, !cut_node, pv);
        }
        if score > alpha && score < beta && !self.aborted {
            if let Some(mv) = mv {
                self.note(Note::PvsResearch(mv));
                self.follow_better(mv);
            }
            score = self.search_child(child, depth, alpha, beta, false, pv);
        }
        score
    }

    /// The score of `child` for the side that moved there, searched to `depth` within the
    /// mover's window `[alpha, beta]`.
    fn search_child(
        &mut self,
        child: &Position,
        depth: u32,
        alpha: i32,
        beta: i32,
        cut_node: bool,
        pv: &mut Vec<Move>,
    ) -> i32 {
        let ply = self.path.len() as u32;
        let score = -self.negamax(child, depth, ply, -beta, -alpha, cut_node, pv);
        self.note(Note::Exit { score: -score });
        score
    }

The re-searches cost something, but with good ordering they are rare, and the null-window searches are much cheaper than full ones. The name comes from the principal variation: the line both sides are expected to play, which is the only one that gets full-window searches.

Aspiration windows

At the root, iterative deepening gives a good guess before each depth starts: the previous depth’s score. Scores usually move by a few centipawns from one depth to the next. So instead of the infinite window, each depth from 5 on starts with aspiration window [previous − 25, previous + 25].

• If the score lands inside, the search was cheaper than with the full window, and the answer is exact.
• If it fails low (the position is worse than thought) or fails high (better), the window is widened on that side, the margin doubled, and the depth searched again. After a fail high, the move that failed high goes first in the re-search. Past a margin of 800 the search gives up on guessing and uses the full window.

    /// Searches the root to `depth`, using an aspiration window around `previous` (the last
    /// depth's score) when there is one. Fail-high moves are moved to the front of
    /// `root_moves` for the re-search.
    pub(crate) fn search_depth(
        &mut self,
        pos: &Position,
        root_moves: &mut Vec<Move>,
        depth: u32,
        previous: Option<i32>,
    ) -> RootResult {
        let p = self.search_params;
        let center = previous.filter(|score| {
            self.techniques.aspiration
                && self.techniques.alpha_beta
                && depth >= p.aspiration_min_depth
                && score.abs() < MATE - MAX_PLY as i32
        });
        let Some(center) = center else {
            return self.search_root(pos, root_moves, depth, -INFINITY, INFINITY);
        };
        let mut delta = p.aspiration_delta;
        let (mut alpha, mut beta) = (center - delta, center + delta);
        let mut fail_high: Option<RootResult> = None;
        loop {
            let result = self.search_root(pos, root_moves, depth, alpha, beta);
            if !result.complete {
                // Stopped during a re-search before any move finished: the move that failed
                // high is still the best information there is.
                return match fail_high {
                    Some(high) if result.score == -INFINITY => RootResult {
                        complete: false,
                        nodes: result.nodes,
                        seldepth: result.seldepth,
                        ..high
                    },
                    _ => result,
                };
            }
            if result.score <= alpha {
                alpha = (result.score - delta).max(-INFINITY);
                self.follow_research(root_moves, RootResearch::FailLow(to_score(result.score)));
            } else if result.score >= beta {
                beta = (result.score + delta).min(INFINITY);
                if let Some(mv) = result.best_move {
                    root_moves.retain(|&m| m != mv);
                    root_moves.insert(0, mv);
                }
                self.follow_research(root_moves, RootResearch::FailHigh(to_score(result.score)));
                fail_high = Some(result);
            } else {
                return result;
            }
            delta *= 2;
            if delta > p.aspiration_max_delta {
                (alpha, beta) = (-INFINITY, INFINITY);
            }
        }
    }

/// The search's tunable numbers.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct SearchParams {
    /// Aspiration windows start at the previous score ± this many centipawns.
    pub aspiration_delta: i32,
    /// Aspiration windows are used from this depth on (shallow scores jump around too much).
    pub aspiration_min_depth: u32,
    /// Once the margin grows past this, the full window is used.
    pub aspiration_max_delta: i32,
    /// Null moves are tried with at least this much depth left.
    pub null_min_depth: u32,
    /// The null move's search is reduced by this many plies...
    pub null_reduction: u32,
    /// ...plus one more per this many plies of depth.
    pub null_depth_divisor: u32,
    /// Late move reductions start at this depth...
    pub lmr_min_depth: u32,
    /// ...for moves after this many have been searched.
    pub lmr_min_moves: u32,
    /// The reduction's constant part, in hundredths of a ply.
    pub lmr_base: u32,
    /// The divisor of `ln(depth) × ln(move number)`, in hundredths.
    pub lmr_divisor: u32,
    /// A quiet move's reduction shrinks by a ply for each this much history score it has
    /// (and grows by a ply for each this much below zero)...
    pub lmr_history_divisor: i32,
    /// ...by at most this many plies either way.
    pub lmr_history_max: i32,
    /// Late move reductions are this many plies larger at an expected cut node.
    pub lmr_cut_node: i32,
    /// Late move reductions are this many plies smaller at an expected all-node.
    pub lmr_all_node: i32,
    /// Late move reductions are this many plies smaller at a node that is or has been on the
    /// principal variation (but isn't a PV node now, which has its own ply off).
    pub lmr_tt_pv: i32,
    /// A node that fails low takes its parent's "is or has been on the PV" flag only above
    /// this depth.
    pub tt_pv_fail_low_depth: u32,
    /// Late move reductions are `lmr_cutoff_plies` larger when the next ply has counted more
    /// than this many fail highs (see [`Techniques::cutoff_reductions`])...
    pub lmr_cutoff_count: u32,
    /// ...this many (and `lmr_cutoff_all_node_plies` more at an expected all-node).
    pub lmr_cutoff_plies: i32,
    /// After many fail highs, late move reductions at an expected all-node are this many plies
    /// larger again (see `lmr_cutoff_plies`).
    pub lmr_cutoff_all_node_plies: i32,
    /// What a fail high by a doubly extended move adds to its ply's count of fail highs, besides
    /// the one more for a node without a hash move (any other move adds 1).
    pub cutoff_count_double_extended: u32,
    /// Late move reductions are this many plies larger when the hash move is a capture (see
    /// [`Techniques::tt_capture_reductions`])...
    pub lmr_tt_capture: i32,
    /// ...but this many at a PV node.
    pub lmr_tt_capture_pv: i32,
    /// Late move pruning applies up to this depth...
    pub lmp_max_depth: u32,
    /// ...once `lmp_base + depth²` quiet moves have been tried...
    pub lmp_base: u32,
    /// ...times this when the side to move is improving (1: no change).
    pub lmp_improving: u32,
    /// History pruning applies up to this depth...
    pub history_pruning_max_depth: u32,
    /// ...to a quiet move whose quiet-move score is below minus this much per ply of depth.
    pub history_pruning_margin: i32,
    /// Reverse futility pruning applies up to this depth...
    pub rfp_max_depth: u32,
    /// ...when the static evaluation beats beta by this much per ply of depth...
    pub rfp_margin: i32,
    /// ...less this much when the side to move is improving. Keep it below `rfp_margin`, so
    /// the margin never reaches zero.
    pub rfp_improving: i32,
    /// Razoring applies up to this depth...
    pub razor_max_depth: u32,
    /// ...when the static evaluation is below alpha by this much per ply of depth.
    pub razor_margin: i32,
    /// Futility pruning applies up to this depth...
    pub futility_max_depth: u32,
    /// ...when the static evaluation plus this...
    pub futility_base: i32,
    /// ...plus this much per ply of depth is still at or below alpha.
    pub futility_per_depth: i32,
    /// SEE pruning applies up to this depth...
    pub see_max_depth: u32,
    /// ...to quiet moves losing more than this much per ply of depth...
    pub see_quiet_margin: i32,
    /// ...and to captures losing more than this much per ply of depth.
    pub see_capture_margin: i32,
    /// Delta pruning: a capture is skipped if winning the piece plus this margin still
    /// leaves the score at or below alpha.
    pub delta_margin: i32,
    /// Internal iterative reductions apply from this depth on.
    pub iir_min_depth: u32,
    /// Singular extensions apply from this depth on...
    pub singular_min_depth: u32,
    /// ...when the hash move's entry is at most this many plies shallower than the node...
    pub singular_tt_depth_margin: u32,
    /// ...and no other move comes within this many centipawns per ply of depth of its score.
    pub singular_margin: i32,
    /// A singular hash move is searched two plies deeper if no other move comes within this
    /// many centipawns of `singular_beta` either (a double extension)...
    pub double_extension_margin: i32,
    /// ...at most this many times along a line.
    pub double_extension_limit: u32,
    /// A hash move that isn't singular but whose hash score beats beta is searched this many
    /// plies shallower (a negative extension).
    pub negative_extension_plies: u32,
    /// Correction history moves an entry towards a node's error by at most this many 256ths of
    /// the way (`depth + 1` below it)...
    pub correction_max_weight: i32,
    /// ...and no entry corrects by more than this many centipawns either way.
    pub correction_limit: i32,
    /// With the piece tables on, the pawn table's correction counts this many 256ths...
    pub correction_pawn_share: i32,
    /// ...and each side's piece table's this many, added to it.
    pub correction_non_pawn_share: i32,
    /// ProbCut applies from this depth on...
    pub probcut_min_depth: u32,
    /// ...and asks whether a capture beats beta by this many centipawns...
    pub probcut_margin: i32,
    /// ...in a search this many plies shallower.
    pub probcut_reduction: u32,
}

impl Default for SearchParams {
    fn default() -> SearchParams {
        SearchParams {
            aspiration_delta: 25,
            aspiration_min_depth: 5,
            aspiration_max_delta: 800,
            null_min_depth: 3,
            null_reduction: 3,
            null_depth_divisor: 6,
            lmr_min_depth: 3,
            lmr_min_moves: 3,
            lmr_base: 75,
            lmr_divisor: 225,
            // About one reduced move in seven has a quiet-move score of at least 128 either way
            // (measured over a self-play game; see the module documentation). The first
            // version used 256 and history alone, and changed about one in ten.
            lmr_history_divisor: 128,
            lmr_history_max: 2,
            // 1 gained +11.6 ± 7.7 against none (cjus/chessengine#145); 2, as in Stockfish
            // (GPL-3.0), gained +8.7 ± 6.4 against 1 (cjus/chessengine#155). Stockfish adds
            // them alongside reductions that cb2026 doesn't have. Not tuned further.
            lmr_cut_node: 2,
            // Set by hand, not tuned; it failed at 1 (cjus/chessengine#158).
            lmr_all_node: 1,
            // Set by hand, not tuned; no verdict at 1 (cjus/chessengine#160). Stockfish
            // (GPL-3.0) takes off 1 to 3 plies, depending on the hash entry.
            lmr_tt_pv: 1,
            // As in Stockfish 16 (GPL-3.0): above depth 3.
            tt_pv_fail_low_depth: 3,
            // As in Stockfish 16 (GPL-3.0); passed at these values (cjus/chessengine#165), not
            // tuned.
            lmr_cutoff_count: 3,
            lmr_cutoff_plies: 1,
            // Stockfish 17's version (GPL-3.0), which passed against Stockfish 16's, +13.7 ± 8.5
            // (cjus/chessengine#167); 0 and 1 give Stockfish 16's (cjus/chessengine#165).
            lmr_cutoff_all_node_plies: 1,
            cutoff_count_double_extended: 0,
            // As in Stockfish 16 and 17 (GPL-3.0), which apply it at every node. With 1 at PV
            // nodes too it failed (cjus/chessengine#171), and with 0 there too
            // (cjus/chessengine#179).
            lmr_tt_capture: 1,
            lmr_tt_capture_pv: 0,
            lmp_max_depth: 3,
            lmp_base: 3,
            // Doubling it when improving was part of both failed versions (#60, #63).
            lmp_improving: 1,
            // Below one depth-4 cutoff's penalty (16) per ply of depth, up to depth 4: set from
            // measurements over a game's positions, not tuned (see chapter 13.1).
            history_pruning_max_depth: 4,
            history_pruning_margin: 16,
            rfp_max_depth: 7,
            rfp_margin: 80,
            rfp_improving: 40,
            razor_max_depth: 2,
            razor_margin: 300,
            futility_max_depth: 6,
            futility_base: 100,
            futility_per_depth: 100,
            see_max_depth: 6,
            see_quiet_margin: 60,
            see_capture_margin: 100,
            delta_margin: 200,
            iir_min_depth: 4,
            // The first version started at 8 (cjus/chessengine#71); 6 gained +5.0 ± 4.1
            // (cjus/chessengine#78); 4 gained +6.1 ± 4.8 more (cjus/chessengine#80).
            singular_min_depth: 4,
            // 3, as in Stockfish (GPL-3.0); 4 failed, −7.4 ± 8.0 against 3
            // (cjus/chessengine#123).
            singular_tt_depth_margin: 3,
            // 2 until 4 became the start depth; 3 gained +5.2 ± 4.2 (cjus/chessengine#82); 4
            // failed, −1.8 ± 5.3 against 3 (cjus/chessengine#84).
            singular_margin: 3,
            // 20 at first, as in Stockfish (GPL-3.0), had no verdict (cjus/chessengine#96); 50
            // gained +13.0 ± 8.3 (cjus/chessengine#125); 100 failed, −7.3 ± 8.0 against 50
            // (cjus/chessengine#127); 70 failed too, −20.5 ± 12.2 against 50
            // (cjus/chessengine#138).
            double_extension_margin: 50,
            double_extension_limit: 6,
            negative_extension_plies: 1,
            correction_max_weight: 16,
            correction_limit: 64,
            // All of the pawn table's and an eighth of each piece table's, added: set by hand,
            // not tuned. The first version averaged them, 128 and 64, and measured weaker
            // (cjus/chessengine#119).
            correction_pawn_share: 256,
            correction_non_pawn_share: 32,
            // Set by hand, not tuned: a pawn above beta, four plies shallower.
            probcut_min_depth: 5,
            probcut_margin: 100,
            probcut_reduction: 4,
        }
    }
}

What it saves

Total nodes over six positions at depth 8 (the same positions as chapter 10):

PVS does most of the work. Aspiration windows hardly change the totals on their own, but they and PVS help each other: the narrower root window makes PVS’s re-searches rarer. Aspiration windows matter more in long searches, where every saved node at the root multiplies down a deep tree.

Pitfalls

• Search instability. With a transposition table, a re-search doesn’t always reproduce the result that triggered it: a move fails high on the null window, then scores below alpha on the full one. The search must cope (cb2026 simply keeps the result of the re-search), not loop forever.
• Mate scores and aspiration. A window around a mate score makes no sense, since mate scores jump by large amounts between depths. Aspiration is skipped when the previous score was a mate.
• Fail-soft bounds. When a root search fails, the returned score (beyond the window) is used to place the next window, which wastes fewer re-searches than widening blindly.
• Stopping mid-re-search. If time runs out while re-searching after a fail high, the move that failed high is still the best information there is, so it is kept.

What it’s worth

PVS and aspiration windows are worth much less than the early stages, so proving the gain took two thousand games: the first stage whose test ran on the faster test Mac. The cloud run’s estimate (+18 ± 20) and the Mac’s (+28.5 ± 13.1) agree within their margins.

Further reading

• Chess Programming Wiki: Principal Variation Search, Null Window, Aspiration Windows, Search Instability.
• Tony Marsland and Murray Campbell, “Parallel Search of Strongly Ordered Game Trees”, ACM Computing Surveys 14 (1982): the principal variation idea.