Correction history

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

Chapters 12 to 14 prune by guessing from the static evaluation. Reverse futility pruning returns when the evaluation is far above beta, razoring gives up when it is far below alpha, null-move pruning needs it at beta or above, and futility pruning skips quiet moves that can’t lift it to alpha. The quiescence search stands pat on it at every leaf. All of them are only as good as that one number.

Chapter 15’s evaluation is hand-crafted, and it is wrong in patterns. In some pawn structures it is too optimistic, in others too pessimistic, by much the same amount each time the structure comes up: a weakness it doesn’t know about, or a pawn chain it overrates. The search finds out as it goes. A node’s searched score is a better estimate than its static evaluation, and the difference between them is the evaluation’s error in that position.

Correction history remembers those errors. It keeps a running average of the difference in a table indexed by the side to move and the pawn structure, and adds the average to every later static evaluation of a position with the same pawns. Two more tables do the same by each side’s pieces (below): averaged with the pawn table they measured weaker, and added to it they made no difference, so they are off by default. Like chapter 14.1’s techniques, it came after stage 20, so no stage tag contains it. Switch it with set correction on|off, and the piece tables with set corrpieces on|off.

The table

A pawn structure is two bitboards, White’s pawns and Black’s. There are far too many structures to give each its own entry, so the two bitboards are mixed into one number, and its low bits pick one of 16,384 entries per side:

/// The pawn structure as one number: both sides' pawn bitboards, mixed so that every bit of
/// them affects every bit of the result. Black's are mixed first, so a white pawn and a black
/// pawn on the same square don't count as the same structure.
pub fn pawn_key(pos: &Position) -> u64 {
    let white = pos.pieces(Color::White, PieceType::Pawn).0;
    let black = pos.pieces(Color::Black, PieceType::Pawn).0;
    mix(white ^ mix(black))
}

/// SplitMix64's finaliser (Steele, Lea and Flood, 2014): a cheap, thorough bit mixer.
fn mix(mut x: u64) -> u64 {
    x ^= x >> 30;
    x = x.wrapping_mul(0xBF58_476D_1CE4_E5B9);
    x ^= x >> 27;
    x = x.wrapping_mul(0x94D0_49BB_1331_11EB);
    x ^ (x >> 31)
}

Black’s pawns are mixed before they are combined with White’s, so that a white pawn on a2 and a black pawn on a2 don’t count as the same structure. The mixer is SplitMix64’s finaliser, a few shifts and multiplications that make every bit of the input affect every bit of the output, so similar structures land far apart. Engines usually keep a pawn hash key up to date move by move, as the position’s Zobrist key is (chapter 4). Computing it from the bitboards instead costs much less than the evaluation it corrects and leaves the position as it is.

The entries are kept in 256ths of a centipawn:

/// How far the static evaluation tends to be off, by side to move and pawn structure, and by
/// side to move and each side's other pieces.
#[derive(Clone, Debug)]
pub struct CorrectionHistory {
    /// `2 × CORRECTION_ENTRIES` corrections in 256ths of a centipawn, by pawn structure: White
    /// to move's, then Black to move's.
    pawn: Vec<i32>,
    /// The same, by White's pieces other than pawns, then by Black's.
    non_pawn: [Vec<i32>; 2],
}

Correcting

Every node in the main search computes its static evaluation, then corrects it:

        // The static evaluation, for the pruning decisions (meaningless in check), corrected by
        // what the search has learnt about positions with these pawns.
        let raw_eval = if in_check {
            -INFINITY
        } else {
            self.evaluate(pos, ply)
        };
        let static_eval = if in_check {
            -INFINITY
        } else {
            self.corrected_eval(pos, raw_eval)
        };

    /// `raw_eval`, the static evaluation of `pos`, corrected (see [`Self::correction`]), and
    /// kept clear of the mate scores.
    pub fn corrected(&self, pos: &Position, raw_eval: i32, settings: &CorrectionSettings) -> i32 {
        let highest = MATE - MAX_PLY as i32 - 1;
        (raw_eval + self.correction(pos, settings)).clamp(-highest, highest)
    }

The quiescence search corrects its stand pat the same way. The uncorrected evaluation is kept too, because that is what the table learns about.

Learning

When a node’s search is done, its result says something about the evaluation, but not always:

        // Correction history learns how far the static evaluation was off: not in check (there
        // is none), not in a singular extension's search (its score leaves the best move out),
        // and not when the best move is a capture or promotion (its gain is material the static
        // evaluation isn't meant to see).
        let settings = self.correction_settings();
        if self.techniques.correction_history
            && !self.aborted
            && !in_check
            && excluded.is_none()
            && !best_move.is_some_and(is_noisy)
            && let Some(correction) = self.correction.as_deref_mut()
        {
            correction.update(pos, depth, raw_eval, best, bound, &settings);
        }

    /// Learns from a search of `pos` to `depth` that scored `score` as a `bound`, where the
    /// uncorrected static evaluation was `raw_eval`: the pawn table, and the piece tables too
    /// if they are on. The caller has already left out the nodes that can't say anything about
    /// the evaluation (see the module documentation); this leaves out mate scores and bounds on
    /// the wrong side of the evaluation.
    pub fn update(
        &mut self,
        pos: &Position,
        depth: u32,
        raw_eval: i32,
        score: i32,
        bound: Bound,
        settings: &CorrectionSettings,
    ) {
        if score.abs() >= MATE - MAX_PLY as i32 {
            return;
        }
        // A fail high shows the evaluation too low, a fail low shows it too high; nothing else.
        let informative = match bound {
            Bound::Exact => true,
            Bound::Lower => score > raw_eval,
            Bound::Upper => score < raw_eval,
        };
        if !informative {
            return;
        }
        let weight = (depth as i32 + 1).min(settings.max_weight);
        let limit = settings.limit * GRAIN;
        let target = ((score - raw_eval) * GRAIN).clamp(-limit, limit);
        let learn = |entry: &mut i32| {
            *entry = (*entry * (WEIGHT_SCALE - weight) + target * weight) / WEIGHT_SCALE;
        };
        learn(&mut self.pawn[index(pos, pawn_key(pos))]);
        if settings.non_pawn_share > 0 {
            for color in Color::ALL {
                learn(&mut self.non_pawn[color.index()][index(pos, non_pawn_key(pos, color))]);
            }
        }
    }

• Captures and promotions. If the best move wins material, the score is higher than the evaluation because of the capture. The evaluation of a position isn’t meant to include material that is about to change hands; the quiescence search is there for that.
• Bounds. A fail high is a lower bound: the true score is at least score. If that is above the evaluation, the evaluation was too low by at least the difference; if it is below, the true score could be anything, and the node says nothing. A fail low is the mirror image.
• Mate scores are about a forced line, not the position’s evaluation.
• No static evaluation in check, and a singular extension’s search leaves the best move out on purpose, so neither counts.

An entry then moves towards the new difference by a fraction of the way: min(depth + 1, 16) 256ths. A deep search’s result is worth more than a shallow one’s, but even the deepest moves the entry only a sixteenth of the way, so the entry is an average over many nodes and no single surprising result dominates. No entry goes past 64 centipawns either way. Both numbers are search parameters, correction_max_weight and correction_limit.

What it changes

The bench, which starts every position with an empty table, is 3.0% smaller with it: 1,065,754 nodes instead of 1,098,926. The speed is unchanged: computing the pawn key at every node costs nothing measurable.

The corrections themselves are small. After searching the 14 bench positions to depth 13 one after another, without clearing the table, 2,111 of the 32,768 entries were in use. Their average correction was 3.5 centipawns, 90% were within 8 and 99% within 25, and none reached the limit of 64. Reverse futility pruning, razoring and futility pruning have margins of 80 centipawns a ply or more, so a typical correction changes few of their decisions. Null-move pruning, which only needs the evaluation at beta, and the stand pat feel it more directly.

Even so, it gained about as much as singular extensions and multi-cut (+29.5, chapter 14.1), among the largest of the changes made after stage 20. The numbers above don’t explain that on their own, and two things they leave out probably do. In a game the table carries over from move to move and the same structures come up again and again, so its entries learn from far more nodes than in that measurement. And most of the gain may come from the few structures where the evaluation is consistently wrong by more, the 1% beyond 25 centipawns, which are also where a wrong evaluation costs the most. Neither is measured.

More tables

The pawns aren’t the only part of a position whose errors repeat. A knight stuck on the rim, a king in an awkward spot, a bishop pair that the evaluation over- or underrates: those are about the pieces. Two more tables, indexed the same way by the side to move and a key, use each side’s pieces other than pawns as the key, White’s knights, bishops, rooks, queens and king in one and Black’s in the other:

/// `color`'s pieces other than pawns as one number, made like [`pawn_key`]: each piece type's
/// bitboard is mixed into the key in turn, so a knight and a bishop on the same square differ.
pub fn non_pawn_key(pos: &Position, color: Color) -> u64 {
    NON_PAWN_PIECES
        .iter()
        .fold(0, |key, &piece| mix(key ^ pos.pieces(color, piece).0))
}

Every update teaches all three tables the same difference. A move changes one side’s pieces at most, or both sides’ with a capture, so the positions a search visits share their piece keys with many others nearby: after a White move, Black’s key is the one it was. The piece tables learn from the positions the search is in.

Stockfish (GPL-3.0) keeps tables like these, one keyed by each side’s pieces other than pawns, among others. The code here is cb2026’s own. With set corrpieces off, the pawn table corrects alone, as before.

The first version: an average

The first version’s correction was the tables’ weighted average: half the pawn table’s, and a quarter each piece table’s (correction_pawn_share 128 and correction_non_pawn_share 64, of 256). An average, not a sum, because each table learns the whole error: summed, three tables that agree would correct three times over.

The bench was 4.3% smaller with it, 1,019,663 nodes instead of 1,065,754, and the search ran about 2.5% fewer nodes a second: each lookup computes two more keys, of five bitboards each, and the two tables add 256 KB that compete for the cache. It lost in games (below).

The piece tables weren’t silent. Over the 14 bench positions searched to depth 13 one after another, the corrections applied at lookups averaged 2.4 centipawns from the pawn table and 2.4 from the piece tables’ average, and 2.25 combined. So the piece tables replaced half of the pawn table’s correction with corrections as large and, by the result, worse. Why isn’t measured. A side’s piece key changes whenever one of its pieces moves, the king included, so each entry may learn from fewer and more varied positions than a pawn entry, and average more noise than error.

The second version: added

The second version keeps the pawn table’s correction whole and adds an eighth of each piece table’s (correction_pawn_share 256, correction_non_pawn_share 32), keeping the sum within correction_limit:

    /// The correction for `pos`'s static evaluation, in centipawns. With the piece tables off
    /// it is the pawn table's; on, the pawn table's counts `pawn_share` 256ths and each side's
    /// piece table's `non_pawn_share` 256ths, added up and kept within the limit.
    pub fn correction(&self, pos: &Position, settings: &CorrectionSettings) -> i32 {
        let pawn = self.pawn[index(pos, pawn_key(pos))];
        let non_pawn_share = settings.non_pawn_share;
        if non_pawn_share == 0 {
            return pawn / GRAIN;
        }
        let pieces: i32 = Color::ALL
            .iter()
            .map(|&color| self.non_pawn[color.index()][index(pos, non_pawn_key(pos, color))])
            .sum();
        let sum = pawn * settings.pawn_share + pieces * non_pawn_share;
        (sum / (SHARE_SCALE * GRAIN)).clamp(-settings.limit, settings.limit)
    }

Where the pawn table alone knows the position, it corrects as before. Where all three agree, the correction is a quarter bigger. A piece table that is wrong can move the evaluation by an eighth of its error at most, where in the first version it moved it by a quarter and took half of the pawn table’s say away.

The bench is 2.7% bigger with it: 1,094,228 nodes instead of 1,065,754, and with set corrpieces off it is main’s exactly. The search runs about 1% fewer nodes a second (two sets of five alternating pairs of bench runs, one sample left out as an outlier).

It made no difference in games (below): −0.4 ± 4.3 Elo after 11,433. Kept small, the piece tables did no harm, and showed no gain either. So the pawn table corrects alone, as before, and the piece tables are off by default.

Pitfalls

• Learning from the correction itself. The searched score comes from a tree whose leaves were corrected. If the table learnt the difference from the corrected evaluation, each correction would build on the last. Measured against the raw evaluation, an entry is an average of how far the raw evaluation was off, and it settles.
• Averaging dilutes. In the first version the pawn table counted half as much as it did alone, so where only it had learnt something, the correction was half as big. Adding keeps it whole, at the cost of correcting by more than any one table where they agree; the limit still holds.
• Collisions. Every pawn structure the search meets shares 16,384 entries per side, so unrelated structures can share an average. A bigger table collides less, but each entry learns more slowly.
• The mate range. A corrected evaluation is clamped short of the mate scores, so that a correction can never make a large evaluation look like a forced mate.
• Helper threads (chapter 17) start every search with an empty table of their own; only the main thread’s table carries over from one move to the next. What they find still reaches the main thread through the shared transposition table.
• Comparisons at equal scores. Correction history changes the static evaluation, so it changes scores, not only node counts. Techniques::sound(), which keeps only the techniques that don’t change the result, switches it off.

What it’s worth

That second test took 11,433 games, about 9 hours: an SPRT needs many games to tell a change worth about nothing from one worth a few Elo.

Other candidates, untested:

• Keys without the king, which moves often and makes a side’s key change more than its pieces do.
• Fewer pieces per key, for example knights and bishops in one key and rooks and queens in another, so that each entry is shared by more positions.

Further reading

• Chess Programming Wiki: Static Evaluation Correction History.
• The idea comes from Caissa (MIT licence, 2023), and Stockfish (GPL-3.0) and most strong engines have adopted it, several with more tables than the pawn one. The code here is cb2026’s own.
• Guy L. Steele, Doug Lea and Christine H. Flood, “Fast Splittable Pseudorandom Number Generators”, OOPSLA 2014: SplitMix64, whose finaliser mixes the pawn key.