ProbCut

Milestone M5, after stage 20 · on main, no stage tag · code in crates/engine/src/search.rs

Null-move pruning (chapter 12) cuts a node off when passing keeps the score at or above beta, in a search a few plies shallower. ProbCut makes a bet of the same shape with a real move: if some capture beats beta by a clear margin, even in a search four plies shallower, then the full-depth search would almost surely beat beta too, and the node is cut off.

The bet rests on a fact about search scores: a shallow search’s score and a deep search’s score of the same position are closely related (Buro measured it, for Othello). So a shallow score well above beta says, with high probability, that the deep score is above beta as well. The name is short for probabilistic cut. Like chapter 14.1’s techniques, it came after stage 20, so no stage tag contains it. It measured weaker, so it is off by default; set probcut on switches it on.

The test

        // ProbCut: if a good capture beats beta by a margin even in a shallower search, the
        // full-depth search would almost surely beat beta too, so the node is cut off. Not if
        // the hash table already says that a search about as deep fell short of the margin.
        let probcut_beta = beta + p.probcut_margin;
        if self.techniques.probcut
            && self.techniques.quiescence
            && selective
            && excluded.is_none()
            && depth >= p.probcut_min_depth
            && beta.abs() + p.probcut_margin < MATE - MAX_PLY as i32
            && !tt_entry.is_some_and(|entry| {
                entry.bound != Bound::Lower
                    && u32::from(entry.depth) + p.probcut_reduction > depth
                    && score_from_tt(entry.score, ply) < probcut_beta
            })
        {
            self.note(Note::ProbCut);
            let probcut_depth = depth.saturating_sub(p.probcut_reduction);
            let captures: Vec<Move> = moves.iter().copied().filter(|&mv| is_noisy(mv)).collect();
            let previous = self.previous();
            let picker = MovePicker::new(
                pos,
                &captures,
                tt_move,
                ply,
                &previous,
                self.ordering,
                &self.techniques,
            );
            let mut cutoff = None;
            let mut probcut_pv = Vec::new();
            self.keys.push(pos.hash());
            for mv in picker {
                // Only captures that win, by static exchange, at least what the static
                // evaluation is short of the margin.
                if see(pos, mv) < probcut_beta - static_eval {
                    continue;
                }
                let mut child = pos.clone();
                child.make_move(mv);
                self.push_move(pos, Some(mv));
                self.update_accumulator(pos, Some(mv), ply);
                // The quiescence search first: it is cheap, and if even it can't reach the
                // margin, the shallower search seldom does.
                let mut score = -self.quiescence(
                    &child,
                    ply + 1,
                    -probcut_beta,
                    -probcut_beta + 1,
                    &mut probcut_pv,
                );
                if score >= probcut_beta && probcut_depth > 0 && !self.aborted {
                    score = self.search_child(
                        &child,
                        probcut_depth,
                        probcut_beta - 1,
                        probcut_beta,
                        !cut_node,
                        &mut probcut_pv,
                    );
                }
                self.pop_move();
                if self.aborted {
                    break;
                }
                if score >= probcut_beta {
                    cutoff = Some((mv, score));
                    break;
                }
            }
            self.keys.pop();
            if self.aborted {
                return 0;
            }
            if let Some((mv, score)) = cutoff {
                self.note(Note::ProbCutCutoff(mv));
                // What ProbCut found is a lower bound from its shallower search.
                if self.techniques.tt {
                    let stored = score_to_tt(score, ply);
                    self.tt.store(
                        pos.hash(),
                        Some(mv),
                        stored,
                        probcut_depth + 1,
                        Bound::Lower,
                        tt_pv,
                    );
                }
                return score;
            }
        }

ProbCut asks about probcut_beta, beta plus probcut_margin (100 centipawns), and it keeps the cost down three ways:

• Captures only. A move that beats beta by a pawn in a shallow search is usually one that wins material. Quiet moves are left to the full search.
• Only captures that could make it. A capture’s static exchange evaluation (chapter 14) has to make up what the static evaluation is short of probcut_beta. In a position evaluated at beta, that is a capture winning a pawn or more. Ten points below, it has to win 110.
• The quiescence search first. Each capture gets a quiescence search against probcut_beta, which costs little. Only if that reaches the margin does the capture get the real test, a null-window search probcut_reduction (4) plies shallower than the node.

A capture that passes the test cuts the node off. The cutoff is stored in the transposition table as a lower bound, at the depth of ProbCut’s search plus one: one ply more because the capture was made before that search.

The conditions

• Off the principal variation and out of check, like the pruning of chapters 12 to 14.
• From depth 5 (probcut_min_depth). At depth 4, ProbCut’s own search would be only the quiescence search.
• Not near a mate score. A margin added to a mate score is no longer a score.
• Not when the hash table already knows better. If the table holds an exact score or an upper bound for this position, from a search at least as deep as ProbCut’s own, and that score is below probcut_beta, ProbCut’s search would probably fail too, so it isn’t tried. A lower bound below probcut_beta doesn’t say the true score is below it, so it doesn’t stop the test.
• Not in a singular extension’s search, which leaves the hash move out and asks a different question.

Where it comes from

Michael Buro invented ProbCut for Othello, in his thesis (1994) and in “ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm” (ICCA Journal, 1995). His version is statistical. It measures, over many positions, how a deep search’s score relates to a shallow one’s, and sets the margin from the spread, so that a cut is wrong with a chosen, small probability. It worked very well in Othello. In chess, attempts in Crafty in 2003 and 2004 found it no better, or worse.

The version that works in chess is Gary Linscott’s for Stockfish (GPL-3.0, 2013): a fixed margin, captures only, and a search a few plies shallower. cb2026’s follows that form and adds the quiescence search first and the hash table check, as later Stockfish versions do. The code is cb2026’s own. The three numbers, 5, 100 and 4, were set by hand, not tuned.

What it changes

The bench is 9.6% smaller with it: 963,637 nodes instead of 1,065,754. With set probcut off it is main’s exactly. Three alternating bench runs gave 1.55 to 1.62 million nodes a second for main and 1.63 to 1.65 million with ProbCut.

The stats command shows how often it fires. After a search to depth 12:

On those three, ProbCut cuts off hundreds or thousands of nodes, yet the tree comes out about the same size. Presumably its own searches cost about what its cutoffs save there; on the bench positions it saves 9.6%. The games (below) found it weaker all the same.

Pitfalls

• The margin is a bet. Too small, and ProbCut cuts nodes whose deep score would have fallen below beta. Too large, and it seldom fires and only costs time. The right size depends on the evaluation: a pawn here, on cb2026’s centipawn scale.
• Cost at nodes that don’t cut off. Each capture tried costs a quiescence search, and some a shallower search too. Where no capture reaches the margin, that work is wasted. The static exchange filter and the quiescence search first keep it small.
• Mate scores. A margin added to a score near mate makes no sense, so ProbCut isn’t tried there. A mate it finds through the capture is a real one, so it is returned as it is.
• The hash table. A ProbCut result is a lower bound from a shallower search, stored at that depth, so a later search that needs more depth searches the node again.

What it’s worth

Like capture history (chapter 10.2), it made the bench smaller and the engine weaker. Why isn’t measured: the cutoffs it makes may be wrong too often at a margin of a pawn, or the searches it spends where no capture reaches the margin may cost more in games than in the bench. The switch and the three parameters stay. Untested candidates for another try:

• A larger margin, 150 or 200 centipawns: fewer cutoffs, and fewer wrong ones.
• A deeper start, probcut_min_depth 6 or 7, so that ProbCut’s own search is deeper and its score closer to the full search’s.
• The long time control, 40+0.4, where searches are deeper and more nodes are at the depths ProbCut works at.

Further reading

• Chess Programming Wiki: ProbCut, with Multi-ProbCut and the Crafty experiments.
• Michael Buro, “ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm”, ICCA Journal 18(2), 1995.
• Stockfish’s source (GPL-3.0), search.cpp, “ProbCut”.