Capture history

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

Chapter 7 orders captures by MVV-LVA: the biggest victim first and, among captures of the same piece, the smallest attacker first. It is a good rule, and a fixed one. Bxf7 comes before Rxf7 in every position, whether or not the bishop’s capture works there, and a capture of a pawn always waits behind every capture of a knight, even where taking the pawn is what refutes the opponent’s last move.

Chapter 10 had the same problem with quiet moves and solved it with the history table, which learns from the search which moves cause cutoffs. Capture history does the same for captures. Its table is indexed by the piece that captures, the square it captures on and the piece it takes, and it learns the way history does. Like chapter 14.1’s techniques, it came after stage 20, so no stage tag contains it. Its three versions all measured weaker, the second in Stockfish’s form and the third the second in the main search only, so it is off by default. set capthist on switches the third version on; set capthistq on with it gives the second.

The table

/// Where `mv`, a capture or queen promotion in `pos`, is in the capture history table: by the
/// piece that moves, its destination and what it captures. `None` if no piece stands on its
/// from-square, which a legal move never does.
fn capture_index(pos: &Position, mv: Move) -> Option<usize> {
    let victim = match mv.kind() {
        MoveKind::EnPassant => PieceType::Pawn.index(),
        _ => pos
            .piece_at(mv.to())
            .map_or(NO_VICTIM, |p| p.piece_type.index()),
    };
    Some(PieceTo::new(pos, mv)?.index() * VICTIMS + victim)
}

Twelve pieces, 64 squares and six victims make 4,608 scores, 18 KB. The victim keeps apart moves that mean different things: a rook arriving on d5 to take a pawn and one arriving to take a knight. The sixth victim is nothing, for a queen promotion that captures nothing, which the ordering treats as a capture (chapter 7). A king is never captured, so its slot is free for it. An en passant capture takes a pawn that isn’t on the destination square, so its victim is set by hand.

Ordering

A capture starts from what it wins, by the piece values of static exchange evaluation (chapter 14): the victim’s value, and a queen less a pawn for a queen promotion.

/// What `mv`, a capture or queen promotion in `pos`, wins in material if nothing is taken back,
/// by static exchange evaluation's piece values: the victim's value, plus a queen less a pawn
/// for a queen promotion. Capture history's ordering starts from this.
pub fn capture_value(pos: &Position, mv: Move) -> i32 {
    let value = |pt: PieceType| SEE_VALUES[pt.index()];
    let mut gain = 0;
    if mv.is_capture() {
        let victim = match mv.kind() {
            MoveKind::EnPassant => PieceType::Pawn,
            _ => pos
                .piece_at(mv.to())
                .map_or(PieceType::Pawn, |p| p.piece_type),
        };
        gain += value(victim);
    }
    if mv.promotion() == Some(PieceType::Queen) {
        gain += value(PieceType::Queen) - value(PieceType::Pawn);
    }
    gain
}

Its ordering key is that value times 32, plus its capture history score:

    /// The score that orders `mv`, a capture or queen promotion in `pos`, among the others:
    /// its MVV-LVA key, or with capture history on, the material it wins scaled up plus its
    /// capture history score, less the attacker's rank (pawn 1 … king 6) to break ties.
    pub fn noisy_score(&self, pos: &Position, mv: Move, techniques: &Techniques) -> i32 {
        if techniques.capture_history {
            // The attacker's rank is smaller than any history update from depth 3 on (a bonus
            // of 9), so it only decides between captures that history can't tell apart, at
            // first all of them: then the smaller attacker goes first, as in MVV-LVA.
            let attacker = pos
                .piece_at(mv.from())
                .map_or(1, |p| p.piece_type.index() as i32 + 1);
            capture_value(pos, mv) * CAPTURE_VALUE_SCALE + self.capture_history(pos, mv) - attacker
        } else {
            mvv_lva(pos, mv)
        }
    }

Times 32, a pawn is worth 3,200, a fifth of the 16,384 that a history score can reach; a knight 10,240, a rook 16,000 and a queen 28,800. So:

• Among captures of the same piece, capture history decides. The attacker is left out, as in Stockfish, except to break ties: its rank, 1 to 6, is less than one cutoff’s bonus from depth 3 on. At a node the table knows nothing about, every capture of the same piece ties, and the smaller attacker goes first, as in MVV-LVA.
• Across victims it can move a capture a long way, but not all the way. A capture of a pawn with the best history there is (3,200 + 16,384) comes before a capture of a rook with none (16,000), but never before a capture of a queen. A knight and a bishop are only 320 points apart (10 centipawns), so between them history decides soon.
• The static exchange split stays. Captures that lose material by SEE still come after the quiet moves, in this same order among themselves.

Stockfish 16 (GPL-3.0) adds 7 times the victim’s middlegame value to a capture history limited to 10,692. That puts a queen at 1.66 times the limit, where cb2026’s scale puts it at 1.76. Its pawn is worth less (126 against a knight’s 781, where SEE’s values give 100 and 320), so a pawn’s capture moves further on its history there.

The first version

The first version kept MVV-LVA’s attacker term. Its key was the MVV-LVA key times 1,024 plus capture history. MVV-LVA’s key rises by 8 for each rank of victim and falls by 1 for each rank of attacker, so a victim rank was worth 8,192, half of what a history score can reach, and an attacker rank 1,024. Among captures of the same piece, history decided only once it disagreed with MVV-LVA by more than the attackers’ difference (3,072 between a pawn and a rook), and across victims it moved a capture two ranks at most. It took 11.5% off the bench and lost about 19 Elo (see “What it’s worth”).

The main search only

The quiescence search doesn’t teach the table: its nodes have no depth left, and the bonus is depth². The first two versions let it order its captures by the table all the same. The third doesn’t, unless capture_history_quiescence is on (set capthistq on): the quiescence search keeps MVV-LVA’s order, and the table orders only the captures of the search that teaches it.

        // Capture history is taught by the main search only, since a cutoff's bonus is depth².
        // Unless `capture_history_quiescence` is on, the quiescence search keeps MVV-LVA's order.
        let techniques = Techniques {
            capture_history: self.techniques.capture_history
                && self.techniques.capture_history_quiescence,
            ..self.techniques
        };

The quiescence search is more than half of the nodes, 55% to 58% over the six positions of chapters 10 to 14 (bench positions 2 to 7) at depths 9 to 11. Stockfish (GPL-3.0) orders its quiescence search’s captures by capture history too, so this third version departs from it.

Learning

When a move causes a beta cutoff, the captures searched before it at that node get a penalty, and the move gets a bonus if it is a capture:

            // Beta cutoff: the opponent won't allow this position, so stop looking.
            if self.techniques.alpha_beta && alpha >= beta {
                self.note(Note::BetaCutoff(mv, searched));
                // Counted for the node above: once more without a hash move, and less for a
                // doubly extended move, as in Stockfish 17.
                let counts = if doubled {
                    p.cutoff_count_double_extended
                } else {
                    1
                };
                self.cutoffs[ply as usize] += counts + u32::from(tt_move.is_none());
                if quiet {
                    self.ordering
                        .record_cutoff(pos, mv, &quiets_tried, ply, depth, &previous);
                }
                // The captures tried before it failed, whichever kind of move cut off.
                let noisy_best = (!quiet).then_some(mv);
                self.ordering
                    .record_captures(pos, noisy_best, &noisy_tried, depth);
                break;
            }
            if quiet {
                quiets_tried.push(mv);
            } else {
                noisy_tried.push(mv);
            }

    /// Records a beta cutoff with `depth` left in capture history: `best` is the move that
    /// caused it if that was a capture or queen promotion (`None` if it was quiet), and `tried`
    /// are the captures and queen promotions searched before it, which failed to.
    pub fn record_captures(
        &mut self,
        pos: &Position,
        best: Option<Move>,
        tried: &[Move],
        depth: u32,
    ) {
        let bonus = cutoff_bonus(depth);
        let mut update = |mv: Move, change: i32| {
            if let Some(index) = capture_index(pos, mv) {
                gravity(&mut self.captures[index], change);
            }
        };
        if let Some(best) = best {
            update(best, bonus);
        }
        for &mv in tried {
            update(mv, -bonus);
        }
    }

The penalty goes to the captures tried before a quiet move’s cutoff too. Every capture that doesn’t lose material is searched before the killers and the other quiet moves, so when a quiet move cuts off, those captures all failed, and that is worth knowing. Without the penalties, scores could only rise. The bonus is chapter 10’s depth², with the same gravity, and the table is halved between searches like the others.

Credit

The Chess Programming Wiki credits capture history to Stefan Geschwentner (2016) and describes it as replacing MVV-LVA’s attacker term with the history score. Stockfish (GPL-3.0) does that: it scores a capture by its victim’s value and its capture history. The second version follows it. The first kept the attacker term as a large part of the key; the second keeps it only to break ties. Stockfish generates pawn captures first, then the knights’, bishops’, rooks’ and queens’, so its ties tend to go to the smaller attacker too. The code here is cb2026’s own.

What it changes

The first version made the bench 11.5% smaller: 943,210 nodes instead of 1,065,754. The second makes it 12.1% smaller, 998,700 instead of 1,136,500 (main by then had double extensions, chapter 14.1). With set capthist off it is main’s exactly, so the change does nothing when switched off. The speed is unchanged: over four alternating pairs of bench runs, the second version’s speed was 0.996 to 1.004 times main’s. The table is small enough to stay in the cache.

The bench is one depth. Over the six positions of chapters 10 to 14 (bench positions 2 to 7), the second version’s trees:

So the trees shrink at one depth and grow at the next, and the share of cutoffs made by the first move searched hardly moves. Nothing here says whether the order is better.

The third version, in the main search only, makes the bench 11.7% smaller (1,003,431 nodes), and its trees are close to the second version’s: 363,572 nodes at depth 9 (−19% against set capthist off), 581,326 at depth 10 (−17%) and 1,015,664 at depth 11 (+15%), with 89.5% to 90.0% of cutoffs by the first move. The speed is the same as main’s.

Chapter 10.1 warned that with late move reductions and pruning, a smaller tree doesn’t prove better ordering: a worse order can push good moves into the reductions and shrink the tree by missing them. The warning seemed to apply less here. Captures are never reduced or pruned for coming late, so a capture moved later is still searched in full, and the 11.5% looked like cutoffs found sooner. The games said otherwise (below): the tree shrank and the engine got weaker. Why isn’t measured. One candidate: at a principal variation node, the order decides which capture gets the first move’s full window, while the others get null windows, where null-move pruning and the rest are allowed and a good capture can be missed.

Pitfalls

• Swamping the victim’s value. With too large a history score, a capture of a pawn that happened to cut off a few times would be searched before a free queen. The scale keeps a queen out of history’s reach, and lets it move a pawn’s capture past a rook’s.
• Ties are most of the table at first. Without the tie-break, the second version made the bench 6.5% bigger (1,210,252 nodes), not 12.1% smaller: at a node the table knows nothing about, captures of the same piece tied, and the order fell back to the order the moves were generated in, rooks before pawns. A rule that only breaks ties can still change the tree a lot.
• Bad captures. History doesn’t move a capture across the static exchange split, so a losing capture with a good history still waits behind the quiet moves.
• Under-promotions are quiet moves to the ordering (chapter 7), so their history is in the quiet tables, not here.

What it’s worth

Like switching history off in chapter 10.1, the first version made the tree smaller and the engine weaker. The switch and the table stayed for a second version, in Stockfish’s form: the victim’s value plus capture history, with the attacker only breaking ties. It lost too, by less: about −7 Elo (cjus/chessengine#129), again with a smaller bench. The third version left the quiescence search on MVV-LVA’s order and lost by less again: about −3 Elo over 6,301 games (cjus/chessengine#134). That is close to zero, but the SPRT settled on no gain rather than the 5 Elo it tested for. The second and third versions differ by 4 ± 10 Elo, so the games don’t show that the quiescence search’s order was what cost the second. All three made the bench about 12% smaller and the engine no stronger; why isn’t measured. Still untested:

• History only among captures of the same piece: a scale large enough that a victim rank outweighs any history score, so history only reorders the attackers.
• No penalty for the captures tried before a quiet move’s cutoff, so that a capture is marked down only when another capture did better.

Further reading

• Chess Programming Wiki: History Heuristic, section “Capture History”.
• Stockfish’s source (GPL-3.0), movepick.cpp and search.cpp: how captures are scored, and the capture history updates.