Late move reductions and pruning

Stage 13 · tag stage-13-lmr · code in crates/engine/src/search.rs

Good move ordering (chapter 10) means a cutoff almost always comes from one of the first few moves searched. So most of the effort at a node goes into proving that the other moves are no better, and those moves are usually poor. This chapter spends less on them. It is the single biggest step in depth an engine takes.

Late move reductions

Late move reductions (LMR) search the late moves at a reduced depth. The later a move comes in the ordering and the deeper the search, the bigger the reduction:

reduction = 0.75 + ln(depth) × ln(move number) / 2.25      (rounded down)

At depth 10, the 20th move is searched 3 plies less deep. At depth 3, the third move loses 1 ply. The table is computed once:

/// The late move reduction for each depth and move number:
/// `base + ln(depth) × ln(move number) / divisor`, rounded down.
fn lmr_table(p: &SearchParams) -> Vec<[u8; LMR_TABLE_SIZE]> {
    let base = f64::from(p.lmr_base) / 100.0;
    let divisor = f64::from(p.lmr_divisor) / 100.0;
    (0..LMR_TABLE_SIZE)
        .map(|depth| {
            let mut row = [0; LMR_TABLE_SIZE];
            for (index, r) in row.iter_mut().enumerate().skip(1) {
                if depth > 0 {
                    let value = base + (depth as f64).ln() * (index as f64).ln() / divisor;
                    *r = value.max(0.0) as u8;
                }
            }
            row
        })
        .collect()
}

A reduced search is a guess, so it has a safety net. If the reduced, null-window search says the move beats alpha after all, the move is searched again at full depth. If it still beats alpha and lies within the window, PVS searches it once more with the full window:

    /// 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
    }

Some moves are never reduced, because they are too often important:

• the first move (usually the TT move);
• captures and promotions;
• moves that give check, and every move when in check;
• moves at depths below 3, or among the first 3 moves.

On the principal variation, where the exact score matters, reductions are one ply smaller.

            let how = if index == 0 {
                MoveSearch::First
            } else if self.techniques.lmr
                && ordinary
                && depth >= p.lmr_min_depth
                && index as u32 >= p.lmr_min_moves
            {
                let row = &self.lmr[(depth as usize).min(LMR_TABLE_SIZE - 1)];
                let mut reduction = i32::from(row[index.min(LMR_TABLE_SIZE - 1)]);
                // Reduce the principal variation less: its exact score matters.
                if pv_node {
                    reduction -= 1;
                }
                // Reduce more at an expected cut node: one move should refute it, and the late
                // ones seldom matter.
                if self.techniques.cut_node_reductions && cut_node {
                    reduction += p.lmr_cut_node;
                }
                // Reduce more when many moves at this ply have been refuted: this node is
                // probably failing low, and its late moves along with it.
                if self.techniques.cutoff_reductions
                    && self.cutoffs[ply as usize + 1] > p.lmr_cutoff_count
                {
                    reduction += p.lmr_cutoff_plies;
                    // More at an expected all-node, as in Stockfish 17.
                    if !pv_node && !cut_node {
                        reduction += p.lmr_cutoff_all_node_plies;
                    }
                }
                // Reduce more when the hash move is a capture: it is probably the best move,
                // and a quiet move this late seldom beats it. Less (by default not at all) on
                // the principal variation, whose exact score matters.
                if self.techniques.tt_capture_reductions && tt_move.is_some_and(is_noisy) {
                    reduction += if pv_node {
                        p.lmr_tt_capture_pv
                    } else {
                        p.lmr_tt_capture
                    };
                }
                // Reduce less at an expected all-node: every move has to fail low for its
                // score to hold, so a late move that is wrongly reduced into failing low
                // makes the parent's move a refutation it isn't.
                if self.techniques.all_node_reductions && !pv_node && !cut_node {
                    reduction -= p.lmr_all_node;
                }
                // Reduce less at a node that has been on the principal variation: it may be
                // again.
                if self.techniques.tt_pv && tt_pv && !pv_node {
                    reduction -= p.lmr_tt_pv;
                }
                // Reduce a move with a good history less: it has caused cutoffs elsewhere. And
                // one with a bad history more.
                if self.techniques.history_lmr {
                    let score = self
                        .ordering
                        .quiet_score(pos, mv, &previous, &self.techniques);
                    reduction -= p.lmr_history_adjustment(score);
                }
                MoveSearch::Later {
                    // Never reduce into the quiescence search.
                    reduction: reduction.clamp(0, depth as i32 - 2) as u32,
                }
            } else {
                MoveSearch::Later { reduction: 0 }
            };

(The history adjustment came later, in chapter 14.1.)

Late move pruning

Near the leaves, LMR’s reductions would leave little depth to search. Late move pruning (LMP) goes one step further. At depth 3 or less, outside the principal variation, once 3 + depth² quiet moves have been tried, the remaining quiet moves are skipped entirely: 4 at depth 1, 7 at depth 2, 12 at depth 3.

            // Late move pruning: near the leaves, after enough quiet moves, skip the rest
            // (once a move has shown we aren't simply getting mated).
            if self.techniques.late_move_pruning
                && ordinary
                && !pv_node
                && depth <= p.lmp_max_depth
                && best > -MATE + MAX_PLY as i32
                && quiets_tried.len() as u32
                    >= (p.lmp_base + depth * depth) * if improving { p.lmp_improving } else { 1 }
            {
                self.note(Note::LateMovePruning(mv));
                continue;
            }

Pruning only starts once some move has been found that doesn’t lose to a mate. Otherwise a side that is under a mating attack could prune the one quiet move that defends.

What it saves

Six positions to depth 8, as in chapters 10 to 12:

The tree is seven times smaller. From the starting position cb2026 now reaches depth 16 in about two seconds. At stage 9 the same time bought depth 9. The depth numbers are no longer comparable with the early stages: a “depth 16” search with LMR has many lines searched far less deeply than 16 plies.

Pitfalls

• Reductions that are never verified. Without the full-depth re-search, LMR would silently miss every late move that turns out to be good. The re-search is what makes it safe enough.
• Reducing the wrong moves. Captures, checks and evasions often change the evaluation sharply. Reducing them hides tactics.
• Ordering matters more than ever. A good move ordered late now gets a shallower search. Every improvement to ordering (chapter 10, and better history in later stages) pays off twice.
• Tuning. The 0.75 and 2.25 in the formula, the 3 move and depth thresholds and LMP’s 3 + depth² are reasonable starting values, not measured optima. Each is a named parameter in SearchParams, ready for tuning.

What it’s worth

Further reading

• Chess Programming Wiki: Late Move Reductions, Futility Pruning: Move Count Based Pruning, Reductions.
• Tord Romstad, “An Introduction to Late Move Reductions” (2006): the article that made LMR widely known.