Move ordering

Stage 10 · tag stage-10-ordering · code in crates/engine/src/ordering.rs

Alpha-beta’s speed depends on searching the best move first. With perfect ordering it visits about the square root of the positions minimax does; with bad ordering it saves almost nothing. The stages so far order moves like this:

• the transposition table’s move first (chapter 8);
• then captures, by MVV-LVA (chapter 7);
• then quiet moves, in whatever order the generator produced them.

Most moves are quiet, and at many nodes none of the captures is any good, so that last category matters. This chapter adds three heuristics that learn, from the search itself, which quiet moves tend to be good. It also changes how moves are ordered, so the work isn’t wasted at nodes that cut off early.

Killer moves

Say White threatens mate with Qh7. At ply 3 the search tries Black’s first move, finds that Qh7# refutes it, and cuts off. Then it tries Black’s second move, and Qh7# probably refutes that too. A quiet move that caused a cutoff at a given ply is a killer, and it is tried early at the same ply in other branches. cb2026 keeps two per ply. When a new killer arrives, the older one is dropped.

Countermoves

Many moves have a natural reply: …a6 is often met by a4, and Bb5 by …a6. The countermove table remembers, for each opponent move (the piece that moved and the square it went to), the quiet move that last refuted it, and tries that reply early.

The history heuristic

Killers and countermoves remember a handful of moves. The history table scores every quiet move, by side, from-square and to-square. When a quiet move causes a cutoff with depth plies left, its score rises by depth², since cutoffs deep in the tree save the most work. The quiet moves searched before it at that node, which failed to cut off, lose the same amount. Quiet moves are then searched in order of their history score.

    /// Records that the quiet move `best` caused a beta cutoff at `ply` with `depth` left,
    /// after the quiet moves in `tried` failed to. `previous` are the moves that led here.
    pub fn record_cutoff(
        &mut self,
        pos: &Position,
        best: Move,
        tried: &[Move],
        ply: u32,
        depth: u32,
        previous: &Previous,
    ) {
        let killers = &mut self.killers[ply as usize];
        if killers[0] != Some(best) {
            killers[1] = killers[0];
            killers[0] = Some(best);
        }
        if let Some(prev) = previous.mv
            && let Some(slot) = piece_slot(pos, prev)
        {
            self.countermoves[slot][prev.to().index()] = Some(best);
        }
        let side = pos.side_to_move().index();
        let bonus = cutoff_bonus(depth);
        let mut update = |mv: Move, change: i32| {
            gravity(
                &mut self.history[side][mv.from().index()][mv.to().index()],
                change,
            );
            // Continuation history: the same change, after each earlier move.
            let Some(this) = PieceTo::new(pos, mv) else {
                return;
            };
            for (back, earlier) in previous.moved.iter().enumerate() {
                if let Some(earlier) = *earlier {
                    let index = continuation_index(back, earlier, this);
                    gravity(&mut self.continuation[index], change);
                }
            }
        };
        update(best, bonus);
        for &mv in tried {
            update(mv, -bonus);
        }
    }

(The previous argument and the continuation history lines came later, in chapter 10.1.) The bonus and the update are two small functions, which chapter 10.2’s capture history shares:

/// The history bonus for a cutoff with `depth` plies left (and the penalty for the moves that
/// failed before it): `depth²`, since cutoffs deep in the tree save the most work.
fn cutoff_bonus(depth: u32) -> i32 {
    (depth * depth).min(HISTORY_MAX as u32) as i32
}

/// Adds `change` to a history score with gravity: the nearer the cap, the smaller the change,
/// so scores stay within ±[`HISTORY_MAX`].
fn gravity(entry: &mut i32, change: i32) {
    *entry += change - *entry * change.abs() / HISTORY_MAX;
}

The update uses gravity: change − score × |change| / MAX. A bonus to a score near the maximum hardly moves it, while a penalty to it moves it a lot. Scores stay within ±16,384, and the table keeps adapting instead of saturating. Between searches every score is halved, so old knowledge fades.

The order, and picking moves lazily

The full order is:

1. the transposition table move;
2. captures and queen promotions, by MVV-LVA;
3. the first killer, the second killer, the countermove;
4. the remaining quiet moves, by history.

Sorting the whole list at every node would waste time: most nodes that cut off do so on the first or second move, and the order of the rest never matters. So a move picker computes each move’s key, then on each request picks the best remaining move. That is one pass of a selection sort, done only as far as the search actually goes:

/// Hands out moves best first, choosing each one only when it is asked for.
pub struct MovePicker {
    moves: Vec<(Move, i32)>,
    next: usize,
}

impl MovePicker {
    /// Orders `moves` in `pos` for the search at `ply`. `tt_move` comes first; `previous` are
    /// the moves that led here (for the countermove and continuation history).
    pub fn new(
        pos: &Position,
        moves: &[Move],
        tt_move: Option<Move>,
        ply: u32,
        previous: &Previous,
        tables: &OrderingTables,
        techniques: &Techniques,
    ) -> MovePicker {
        let killers = if techniques.killers {
            tables.killers(ply)
        } else {
            [None; 2]
        };
        let countermove = if techniques.countermoves {
            tables.countermove(pos, previous.mv)
        } else {
            None
        };
        let key = |mv: Move| {
            if Some(mv) == tt_move {
                TT_MOVE_KEY
            } else if techniques.mvv_lva && is_noisy(mv) {
                let score = tables.noisy_score(pos, mv, techniques);
                // Captures that lose material in the exchange go after the quiet moves.
                if techniques.see_ordering && see(pos, mv) < 0 {
                    BAD_CAPTURE_KEY + score
                } else {
                    NOISY_KEY + score
                }
            } else if Some(mv) == killers[0] {
                KILLER_KEYS[0]
            } else if Some(mv) == killers[1] {
                KILLER_KEYS[1]
            } else if Some(mv) == countermove {
                COUNTERMOVE_KEY
            } else {
                tables.quiet_score(pos, mv, previous, techniques)
            }
        };
        MovePicker {
            moves: moves.iter().map(|&mv| (mv, key(mv))).collect(),
            next: 0,
        }
    }
}

impl Iterator for MovePicker {
    type Item = Move;

    /// The best move not yet handed out: one pass of a selection sort. Ties go to the move
    /// generated first, so the order is deterministic.
    fn next(&mut self) -> Option<Move> {
        let rest = self.moves.get(self.next..)?;
        let mut best = 0;
        for (i, &(_, key)) in rest.iter().enumerate() {
            if key > rest[best].1 {
                best = i;
            }
        }
        let (mv, _) = *rest.get(best)?;
        // Move the chosen one to the front; keep the others in their order.
        self.moves[self.next..=self.next + best].rotate_right(1);
        self.next += 1;
        Some(mv)
    }
}

The quiescence search takes the same idea further, with staged generation. Unless the side to move is in check, it only wants captures and promotions, so the move generator now has a mode that generates only those (Position::noisy_moves). The pieces’ target squares are restricted to enemy pieces, and pawns only generate captures and promoting pushes. Most of the positions a search visits are quiescence nodes, so this is where the cheaper generation pays off. A test checks that this mode generates exactly the captures and promotions among the legal moves, in every position within two plies of each perft position.

What it saves

Total nodes to search six positions (openings, middlegames, Kiwipete and an endgame) to depth 7:

Together they cut the tree by 42%. Each one adds little on top of the others, because they often agree on the same move: with history and countermoves on, killers even cost a few percent here. These numbers are from one small set of positions. The real test is games, below. Later stages (late move reductions, above all) lean on good quiet-move ordering even more, because they search the late moves less deeply.

Pitfalls

• Killers that aren’t quiet. A capture that cuts off is already ordered by MVV-LVA. Storing it as a killer would waste the slot, so only quiet moves are recorded.
• Stale killers. Killers belong to a ply of one search tree. They are cleared at the start of each search, while history is only halved.
• Unbounded history. Adding bonuses without gravity or a cap lets a few moves’ scores run away, and the table stops reflecting recent results.
• Determinism. Ties keep generation order, so the search, and the bench count, are reproducible.

What it’s worth

Further reading

• Chess Programming Wiki: Move Ordering, Killer Heuristic, Countermove Heuristic, History Heuristic, Move Generation: staged.
• Jonathan Schaeffer, “The History Heuristic and Alpha-Beta Search Enhancements in Practice”, IEEE Transactions on Pattern Analysis and Machine Intelligence 11 (1989).
• Jos Uiterwijk, “The Countermove Heuristic”, ICCA Journal 15 (1992).