Futility, razoring and SEE pruning

Stage 14 · tag stage-14-pruning · code in crates/engine/src/search.rs and see.rs

Chapters 12 and 13 cut whole subtrees (null move) and searched late moves less deeply (LMR). This chapter adds the last family of selective techniques in cb2026’s hand-crafted search: pruning near the leaves, decided by how far the static evaluation is from the window. Each one is a small, cheap guess. Together they make the tree nearly five times smaller.

They all share the same ground rules. None of them applies on the principal variation, in check, or (for the move-level ones) before a move has been found that doesn’t lose to a mate.

Static exchange evaluation

Several of these techniques need to know whether a move loses material, so first a tool: static exchange evaluation (SEE). It plays out every capture and recapture on one square, each side using its least valuable piece first and free to stop when continuing would lose more. It runs without any search, so it is cheap enough to call on every capture.

/// The material `mv` wins (or loses, if negative) for the side making it, once the exchange
/// on its destination square is played out. A quiet move scores 0 or less: less if the piece
/// can be taken for free or for less than it is worth.
pub fn see(pos: &Position, mv: Move) -> i32 {
    let to = mv.to();
    let from = mv.from();
    let value = |pt: PieceType| SEE_VALUES[pt.index()];

    // What the first move captures, and the piece that will stand on the square after it.
    let mut occupied = pos.occupied().without(from);
    let first_gain = match mv.kind() {
        MoveKind::EnPassant => {
            let captured = Square::new(to.file(), from.rank());
            occupied = occupied.without(captured);
            value(PieceType::Pawn)
        }
        MoveKind::Castle => return 0,
        _ => pos.piece_at(to).map_or(0, |p| value(p.piece_type)),
    };
    let mover = pos.piece_at(from).expect("a piece on the from-square");
    let mut on_square = match mv.promotion() {
        Some(pt) => pt,
        None => mover.piece_type,
    };
    let promotion_gain = mv
        .promotion()
        .map_or(0, |pt| value(pt) - value(PieceType::Pawn));

    // gains[i]: material for the side that made capture i, if capture i is the last one.
    let mut gains = vec![first_gain + promotion_gain];
    let mut side = !mover.color;
    let mut attackers = pos.attackers_to(to, occupied) & occupied;
    loop {
        let ours = attackers & pos.pieces_of_color(side);
        let Some((piece_type, square)) = least_valuable(pos, ours) else {
            break;
        };
        // This side captures the piece standing on the square.
        let previous = *gains.last().expect("at least one entry");
        gains.push(value(on_square) - previous);
        on_square = piece_type;
        occupied = occupied.without(square);
        // Recompute, so sliders behind the piece that just moved join in (x-rays).
        attackers = pos.attackers_to(to, occupied) & occupied;
        side = !side;
        // A king can't capture into an attacked square: if it just did and the other side
        // has an attacker left, the king's capture was illegal. Drop it and stop.
        if piece_type == PieceType::King && !(attackers & pos.pieces_of_color(side)).is_empty() {
            gains.pop();
            break;
        }
    }

    // Work backwards: each side may decline to continue the exchange.
    while gains.len() > 1 {
        let last = gains.pop().expect("more than one entry");
        let before = gains.last_mut().expect("at least one entry");
        *before = (*before).min(-last);
    }
    gains[0]
}

The gains list records, after each capture, what the capturing side would have gained if the exchange stopped there. Walking it backwards lets each side choose between stopping and going on. When a piece leaves the square’s line, the attackers are recomputed with it removed from the occupancy, which reveals x-ray attackers: the rook behind a rook, the bishop behind a queen.

SEE improves ordering too. MVV-LVA put QxP before every quiet move even when the pawn is defended. Now captures that lose material are searched last, after the quiet moves.

Reverse futility pruning

If the static evaluation is above beta by a margin that grows with depth (80 centipawns per ply, up to depth 7), the side to move is probably doing so well that the opponent can’t bring the score back down within the remaining depth. The node returns the static evaluation straight away. This is also called the static null move: it is null-move pruning (chapter 12) without the search.

        // Reverse futility pruning: far enough above beta, assume a search would stay there.
        // An improving side gets a smaller margin, but never none at all.
        let rfp_margin = p.rfp_margin * depth as i32 - if improving { p.rfp_improving } else { 0 };
        if self.techniques.reverse_futility
            && selective
            && depth <= p.rfp_max_depth
            && static_eval - rfp_margin >= beta
        {
            self.note(Note::ReverseFutility);
            return static_eval;
        }

The improving part of the margin came later, in chapter 14.1.

Razoring

The mirror image: at depth 1 or 2, if the static evaluation is far below alpha (300 centipawns per ply), quiet moves are unlikely to rescue the position. Only a capture could, so the node asks the quiescence search. If even the captures can’t reach alpha, the node is abandoned.

        // Razoring: far below alpha near the leaves, only captures could save the node.
        if self.techniques.razoring
            && self.techniques.quiescence
            && selective
            && depth <= p.razor_max_depth
            && static_eval + p.razor_margin * (depth as i32) < alpha
        {
            let score = self.quiescence(pos, ply, alpha, alpha + 1, pv);
            if score <= alpha {
                self.note(Note::Razoring);
                return score;
            }
            pv.clear();
        }

Futility pruning

The same idea per move. Within 6 plies of the horizon, if the static evaluation plus a generous margin (100 + 100 per ply) still doesn’t reach alpha, a quiet move is “futile”. It changes no material, so it can hardly gain that much, and it is skipped without being searched. Captures and checks are still searched.

            // Futility pruning: a quiet move can't lift a hopeless static evaluation to alpha.
            if self.techniques.futility
                && ordinary
                && !pv_node
                && depth <= p.futility_max_depth
                && best > -MATE + MAX_PLY as i32
                && static_eval + p.futility_base + p.futility_per_depth * depth as i32 <= alpha
            {
                self.note(Note::Futility(mv));
                continue;
            }

SEE pruning

Within 6 plies of the horizon, moves that lose material by SEE are skipped: quiet moves that put a piece where it can be taken for more than 60 centipawns per ply of depth, and captures that lose more than 100 per ply. In the quiescence search every losing capture is skipped: captures there are meant to resolve the position, and a capture that loses material can’t improve on standing pat.

            // SEE pruning: near the leaves, skip moves that lose material outright.
            if self.techniques.see_pruning
                && selective
                && index > 0
                && !gives_check
                && depth <= p.see_max_depth
                && best > -MATE + MAX_PLY as i32
            {
                let margin = if quiet {
                    p.see_quiet_margin
                } else {
                    p.see_capture_margin
                };
                if see(pos, mv) < -margin * (depth as i32) {
                    self.note(Note::SeePruning(mv));
                    continue;
                }
            }

Delta pruning

In the quiescence search, a capture is skipped if even winning the captured piece for free, plus a 200-centipawn safety margin, would leave the score at or below alpha. A side that is a rook down won’t be saved by winning a pawn.

What it saves

The six positions at depth 8, as in the earlier chapters:

SEE pruning, mostly in the quiescence search, does the most. Ordering losing captures last costs nodes on these six positions. Moving a losing capture behind the quiet moves isn’t always right: some of those captures are sacrifices that work. Whether it’s worth keeping is for the SPRT to say, not a node count.

The bench now searches to depth 10 instead of 4: at depth 4 the pruning left too little of the tree to be a useful fingerprint.

Pitfalls

• Margins. Every technique here trades accuracy for depth through a margin. Too small, and the engine prunes good moves; too large, and it prunes nothing. The values here are common starting points, and stage 16 and later tuning will revisit them.
• Mates. Pruning by static evaluation is blind to mating attacks. That’s why none of it applies in check, and the move-level pruning waits until a move has been found that doesn’t lose to a mate.
• SEE’s blind spots. SEE ignores pins and checks, and it only looks at one square. A capture it calls losing can win if the recapturing piece is pinned.
• Interactions. These techniques overlap with each other and with null move and LMR: turning one off shows only what it adds on top of the others.

What it’s worth

Further reading

• Chess Programming Wiki: Static Exchange Evaluation, Reverse Futility Pruning, Razoring, Futility Pruning, Delta Pruning.
• Ernst Heinz, “Extended Futility Pruning”, ICCA Journal 21 (1998).