Move generation and perft
Stage 2 · tag stage-02-movegen · code in crates/chess
An engine spends much of its time asking “what are the legal moves here?”. Getting the answer exactly right is the first hard part of writing one, and perft is how we prove we did.
Attacks
Everything starts with attacks: which squares does each piece attack?
Leaping pieces: tables
A knight on g1 attacks e2, f3 and h3 whatever else is on the board. So the attacks of knights, kings and pawns are computed once, at compile time, into 64-entry tables:
/// `KNIGHT_ATTACKS[sq]`: the squares a knight on `sq` attacks.
pub const KNIGHT_ATTACKS: [Bitboard; 64] = leaper_table(&KNIGHT_STEPS);
/// `KING_ATTACKS[sq]`: the squares a king on `sq` attacks.
pub const KING_ATTACKS: [Bitboard; 64] = leaper_table(&KING_STEPS);Sliding pieces: walking rays
Bishops, rooks and queens slide until they hit something, so their attacks depend on the occupied squares. Stage 2 computes them the obvious way: step out in each direction and stop after the first occupied square (which is attacked either way: an enemy piece can be captured, an own piece is defended).
/// Slides from `square` in each direction until the edge or the first occupied square
/// (included, since a piece there can be captured or is defended).
fn slider_attacks(square: Square, occupied: Bitboard, directions: &[(i8, i8)]) -> Bitboard {
let mut attacks = Bitboard::EMPTY;
for &direction in directions {
let mut index = square.index();
while let Some(next) = step(index, direction) {
let next_square = Square::from_index(next).expect("step stays on the board");
attacks = attacks.with(next_square);
if occupied.contains(next_square) {
break;
}
index = next;
}
}
attacks
}This is simple and clearly correct, which makes it the reference that stage 3’s much faster magic bitboards are tested against.
Who attacks a square?
A neat trick turns “what does this piece attack?” around into “what attacks this square?”: put each kind of piece on the square and see which enemy pieces of that kind it would attack. A knight on e4 attacks exactly the squares from which a knight attacks e4.
/// All pieces, of both colours, that attack `square`, if the occupied squares were
/// `occupied`.
///
/// The trick: put each kind of piece on `square` and see what it would attack. A knight on
/// `square` attacks exactly the squares from which a knight attacks `square`, and the same
/// holds for every piece (with the pawn directions swapped).
pub fn attackers_to(&self, square: Square, occupied: Bitboard) -> Bitboard {
let rooks = self.pieces_of_type(PieceType::Rook) | self.pieces_of_type(PieceType::Queen);
let bishops =
self.pieces_of_type(PieceType::Bishop) | self.pieces_of_type(PieceType::Queen);
(pawn_attacks(Color::White, square) & self.pieces(Color::Black, PieceType::Pawn))
| (pawn_attacks(Color::Black, square) & self.pieces(Color::White, PieceType::Pawn))
| (knight_attacks(square) & self.pieces_of_type(PieceType::Knight))
| (king_attacks(square) & self.pieces_of_type(PieceType::King))
| (rook_attacks(square, occupied) & rooks)
| (bishop_attacks(square, occupied) & bishops)
}Legal moves, directly
The simplest generator makes pseudo-legal moves (each piece’s moves, ignoring checks), plays each one and throws away those that leave the king in check. cb2026 instead generates only legal moves, using two facts about the position:
- Checkers. In double check only the king can move. In single check, every other move must capture the checker or block between it and the king: a check mask of allowed destinations.
- Pins. A piece standing alone between its king and an enemy slider may only move along that line.
fn generate(&self, list: &mut MoveList, gen_kind: Gen) {
let us = self.side_to_move();
let them = !us;
let own = self.pieces_of_color(us);
let enemy = self.pieces_of_color(them);
let occupied = self.occupied();
let king = self.king_square(us);
let checkers = self.checkers();
// Where pieces may move: any square not holding one of ours, or only enemy pieces.
let targets = match gen_kind {
Gen::All => !own,
Gen::Noisy => enemy,
};
// King moves: never onto a square the enemy attacks. Lift the king off the board
// first, or it would seem to block a slider's attack on the square behind it.
let without_king = occupied.without(king);
for to in king_attacks(king) & targets {
if (self.attackers_to(to, without_king) & enemy).is_empty() {
list.push(Move::new(king, to, capture_or_quiet(enemy, to)));
}
}
// In double check, only the king can move.
if checkers.count() > 1 {
return;
}
// With one checker, other moves must capture it or block the check.
let check_mask = match checkers.first() {
Some(checker) => between(king, checker).with(checker),
None => Bitboard::ALL,
};
let pinned = self.pinned();
// A pinned piece may only move along the line through its king and itself.
let pin_mask = |from: Square| {
if pinned.contains(from) {
line(king, from)
} else {
Bitboard::ALL
}
};Note the line that lifts the king off the board before testing its destination squares. Without it, a king in check from a rook on the same rank could “escape” one square further along the rank, because the king itself would seem to block the rook.
The awkward cases
Two moves are rare and subtle, so cb2026 checks them by playing them on a copy and looking at the king:
- En passant removes two pawns from one rank, which can expose the king to a rook on that rank even though neither pawn was pinned on its own.
- Castling in Chess960, where the castling rook itself might be what shields the king.
Castling gets one more idea: the move is stored as “king takes own rook” (e1h1). That
describes Chess960 castling unambiguously, even when the king doesn’t move at all, and the
same code then handles standard chess.
/// Castling moves, for standard chess and Chess960 alike.
///
/// Castling needs: the right still held; every square the king and rook travel over or
/// land on empty (apart from the king and rook themselves); and no square the king stands
/// on, crosses or lands on attacked. The attack test runs with the king and castling rook
/// lifted off the board, which catches the Chess960 case where the rook was shielding the
/// king from an enemy rook or queen on the back rank.
fn generate_castling(&self, list: &mut MoveList) {
let us = self.side_to_move();
let king = self.king_square(us);
for side in CastlingSide::ALL {
let Some(rook_file) = self.castling().rook_file(us, side) else {
continue;
};
let rook = Square::new(rook_file, king.rank());
let (king_to, rook_to) = castling_destinations(us, side);
let king_path = between(king, king_to).with(king_to).with(king);
let rook_path = between(rook, rook_to).with(rook_to);
let movers = Bitboard::from_square(king).with(rook);
if !((king_path | rook_path) & self.occupied() & !movers).is_empty() {
continue;
}
let lifted = self.occupied() & !movers;
let enemy = self.pieces_of_color(!us);
let safe = king_path
.squares()
.all(|square| (self.attackers_to(square, lifted) & enemy).is_empty());
if safe {
list.push(Move::new(king, rook, MoveKind::Castle));
}
}
}Making moves
make_move updates the board and everything that depends on the move:
- captures, including en passant;
- promotions;
- castling rights, which are lost when a king or castling rook moves or a castling rook is captured;
- the en passant square;
- both clocks.
/// Plays `mv`, which must be legal in this position (for example one from
/// [`Position::legal_moves`]).
pub fn make_move(&mut self, mv: Move) {
let us = self.side_to_move();
let them = !us;
let from = mv.from();
let to = mv.to();
let mut halfmove_clock = self.halfmove_clock() + 1;
let mut en_passant = None;
if mv.kind() == MoveKind::Castle {
// `to` is the castling rook. Lift both pieces, then put them on their destinations
// (in Chess960 a destination may be the other piece's starting square).
let side = if to.file() > from.file() {
CastlingSide::KingSide
} else {
CastlingSide::QueenSide
};
let (king_to, rook_to) = castling_destinations(us, side);
let king = self.remove_piece(from).expect("castling king");
let rook = self.remove_piece(to).expect("castling rook");
self.put_piece(king_to, king);
self.put_piece(rook_to, rook);
self.remove_castling_color(us);
} else {
let piece = self.remove_piece(from).expect("a piece on the from-square");
if mv.is_capture() {
// En passant captures the pawn beside the destination, not on it.
let captured_square = match mv.kind() {
MoveKind::EnPassant => Square::new(to.file(), from.rank()),
_ => to,
};
self.remove_piece(captured_square)
.expect("a piece to capture");
// Capturing a castling rook removes that castling right.
self.remove_rook_right(them, captured_square);
halfmove_clock = 0;
}
let landing = match mv.promotion() {
Some(piece_type) => Piece::new(us, piece_type),
None => piece,
};
self.put_piece(to, landing);
match piece.piece_type {
PieceType::Pawn => {
halfmove_clock = 0;
if mv.kind() == MoveKind::DoublePawnPush {
// Record the skipped square only if an enemy pawn could capture there,
// so equal positions always look equal.
let skipped = Square::new(from.file(), middle_rank(from.rank(), to.rank()));
if !(pawn_attacks(us, skipped) & self.pieces(them, PieceType::Pawn))
.is_empty()
{
en_passant = Some(skipped);
}
}
}
PieceType::King => self.remove_castling_color(us),
PieceType::Rook => self.remove_rook_right(us, from),
_ => {}
}
}
let fullmove_number = self.fullmove_number() + u32::from(us == Color::Black);
self.set_clocks(halfmove_clock, fullmove_number);
self.set_en_passant(en_passant);
self.set_side_to_move(them);
}To try a move and come back, cb2026 copies the position first (“copy-make”). A position is a few hundred bytes, so copying is cheap and there’s no undo code to get wrong.
One detail: the en passant square is recorded only when an enemy pawn could actually capture there. Then two positions that are really the same always look the same, which matters once positions are compared and hashed (stage 4).
Perft: proving it
Perft counts the leaf positions of the full game tree to a given depth: every legal move, every reply, and so on.
/// The number of leaf positions `depth` plies below `pos`.
pub fn perft(pos: &Position, depth: u32) -> u64 {
if depth == 0 {
return 1;
}
let moves = pos.legal_moves();
if depth == 1 {
// Bulk counting: each legal move leads to exactly one leaf.
return moves.len() as u64;
}
moves
.iter()
.map(|&mv| {
let mut child = pos.clone();
child.make_move(mv);
perft(&child, depth - 1)
})
.sum()
}The counts for standard test positions have been reproduced by many independent programs.
A move generator that matches them exactly at every depth is almost certainly right, because
any bug changes the count. When a count is wrong, divide splits it by first move, which
points straight at the move whose subtree is wrong.
cb2026’s suites live in tests/data/:
perft.epd: the Chess Programming Wiki positions, including “Kiwipete”, plus small positions aimed at classic bugs. Those bugs include an illegal en passant, castling that gives check, and underpromotion.perft960.epd: Chess960 start and middlegame positions.
The unit tests run every depth up to a million nodes. Every change is also checked at every
depth in a release build (cargo run --release -p cb2026-tools --bin perft-suite), about 666
million positions.
Bulk counting. At depth 1 the count is just the number of legal moves, so they need not be played. That shortcut alone makes perft several times faster.
Try it
> perft 5
Depth 5: 4865609 nodes in 0.030 s (160.0 million nodes/s) # speed varies by machine
> e2e4
> legal
> divide 2
> fen r3k2r/8/8/8/2b5/8/8/R3K2R w KQkq - 0 1
> legal # no e1g1: the bishop on c4 covers f1
> bb pinned
> attackers f1
What it’s worth
Still nothing in Elo: there’s no search yet. But every later stage relies on this code being exactly right.
Further reading
- Chess Programming Wiki: Move Generation, Pin, Classical Approach, Perft, Perft Results, Chess960 Perft Results.