Legal move generation

Deep dive

How it works

Builds on: Bitboards for the board representation and shift/mask idioms; Zobrist hashing for the position key that make/unmake maintains.

Parts:

• board — one bitboard per piece type, one occupancy per colour, a square-to-piece array, side to move, castling rights, en-passant square, hash
• leaper tables — knight and king target masks, 64 entries each, precomputed
• slider lookup — rook, bishop and queen attacks from the square and the blockers: magic bitboards (multiply, shift, index) or PEXT (extract the blocker bits as the index)
• generator — pseudo-legal list, or fully legal using pin and check masks
• legality test — king not attacked after the move
• make/unmake — updates bitboards, rights, en-passant square and hash incrementally
• perft — recursive leaf counter that tests everything above

Operations: attacks, generate, filter, make, unmake, verify (steps below).

1. Attacks. Leaper: table[sq] & !own. Slider: table[index(sq, occupancy)]. Pawn pushes and captures are shifts of the pawn bitboard.
2. Generate (pseudo-legal). For each own piece take its attack set minus own pieces. Pawns add single and double pushes, captures, en passant, and four moves per promotion. Castling needs the right, empty squares between, and the king neither in check nor crossing an attacked square.
3. Filter (two ways). (a) Test after make: play the move on a copy, reject it if the own king is attacked. (b) Masks: compute the checkers; with two checkers only king moves exist; with one, every other piece may only capture the checker or block on the ray between; a pinned piece may only move along the pin ray; king targets are checked against the enemy attack map computed with the king removed from the occupancy.
4. Make. XOR the moving piece out and in, remove the captured piece (for en passant the pawn behind the target), move the rook when castling, clear castling rights with a per-square mask applied to both from and to, set the en-passant square after a double push, flip the side, and XOR the changed Zobrist keys into the hash.
5. Unmake. Either restore a saved copy of the board (copy-make) or reverse the XORs and pop the irreversible state (captured piece, rights, en-passant square, hash) from a per-ply stack.
6. Verify. perft(d) = sum of perft(d−1) over legal moves, with the legal count at depth 1 ("bulk counting"). Compare to the published tables; on a mismatch, diff per-move counts against a reference engine to find the position.

position ─► piece loop ─► attack tables ─► pseudo-legal list ─► legality filter ─► legal moves
                              ▲                                      │ make copy, king attacked?
                  magic / PEXT index(sq, blockers)                   ▼
                                                              make ─► new board + hash ─► recurse (perft/search)

Code

const P: usize = 0; const N: usize = 1; const B: usize = 2;
const R: usize = 3; const Q: usize = 4; const K: usize = 5;

const fn step_table(d: [(i8, i8); 8]) -> [u64; 64] {
    let mut t = [0u64; 64];
    let mut s = 0;
    while s < 64 {
        let mut i = 0;
        while i < 8 {
            let (f, r) = ((s % 8) as i8 + d[i].0, (s / 8) as i8 + d[i].1);
            if f >= 0 && f < 8 && r >= 0 && r < 8 { t[s] |= 1u64 << (r * 8 + f); }
            i += 1;
        }
        s += 1;
    }
    t
}
static KNIGHT: [u64; 64] = step_table([(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]);
static KING: [u64; 64] = step_table([(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]);

/// Sliding attacks by walking each ray until the first blocker (included).
fn slide(sq: usize, occ: u64, dirs: &[(i8, i8)]) -> u64 {
    let mut a = 0;
    for &(df, dr) in dirs {
        let (mut f, mut r) = ((sq % 8) as i8 + df, (sq / 8) as i8 + dr);
        while (0..8).contains(&f) && (0..8).contains(&r) {
            let b = 1u64 << (r * 8 + f);
            a |= b;
            if occ & b != 0 { break; }
            f += df; r += dr;
        }
    }
    a
}
const DIAG: [(i8, i8); 4] = [(1, 1), (1, -1), (-1, 1), (-1, -1)];
const ORTH: [(i8, i8); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];

const fn splitmix(mut x: u64) -> u64 {
    x = x.wrapping_add(0x9E3779B97F4A7C15);
    x = (x ^ (x >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
    x = (x ^ (x >> 27)).wrapping_mul(0x94D049BB133111EB);
    x ^ (x >> 31)
}
const fn keys() -> [u64; 793] {
    let mut k = [0u64; 793];
    let mut i = 0;
    while i < 793 { k[i] = splitmix(i as u64 + 1); i += 1; }
    k
}
// layout: [0,768) piece*64+sq (piece = color*6+type), [768,784) castling, [784,792) ep file, 792 side
static Z: [u64; 793] = keys();

#[derive(Clone, Copy, PartialEq, Debug)]
pub struct Move { pub from: u8, pub to: u8, pub promo: u8, pub flag: u8 } // promo: piece type or 0; flag: 0 normal, 1 double push, 2 en passant, 3 castle

#[derive(Clone, Copy)]
pub struct Board {
    pc: [u64; 6], occ: [u64; 2], mail: [u8; 64], // mail: 0 empty, else piece type + 1
    pub stm: usize, castle: u8, ep: i8, pub hash: u64,
}

impl Board {
    fn put(&mut self, c: usize, t: usize, s: usize) {
        self.pc[t] ^= 1 << s; self.occ[c] ^= 1 << s; self.mail[s] = t as u8 + 1;
        self.hash ^= Z[(c * 6 + t) * 64 + s];
    }
    fn take(&mut self, c: usize, t: usize, s: usize) {
        self.pc[t] ^= 1 << s; self.occ[c] ^= 1 << s; self.mail[s] = 0;
        self.hash ^= Z[(c * 6 + t) * 64 + s];
    }
    fn rights_hash(&self) -> u64 {
        Z[768 + self.castle as usize] ^ if self.ep >= 0 { Z[784 + (self.ep % 8) as usize] } else { 0 }
    }
    pub fn from_fen(fen: &str) -> Board {
        let mut b = Board { pc: [0; 6], occ: [0; 2], mail: [0; 64], stm: 0, castle: 0, ep: -1, hash: 0 };
        let f: Vec<&str> = fen.split_whitespace().collect();
        for (i, row) in f[0].split('/').enumerate() {
            let mut file = 0;
            for ch in row.chars() {
                if let Some(d) = ch.to_digit(10) { file += d as usize; continue; }
                let t = "pnbrqk".find(ch.to_ascii_lowercase()).unwrap();
                b.put(ch.is_ascii_lowercase() as usize, t, (7 - i) * 8 + file);
                file += 1;
            }
        }
        b.stm = (f[1] == "b") as usize;
        for ch in f[2].chars() { b.castle |= match ch { 'K' => 1, 'Q' => 2, 'k' => 4, 'q' => 8, _ => 0 }; }
        if f[3] != "-" { let v = f[3].as_bytes(); b.ep = ((v[1] - b'1') * 8 + (v[0] - b'a')) as i8; }
        b.hash ^= b.rights_hash() ^ if b.stm == 1 { Z[792] } else { 0 };
        b
    }
    pub fn startpos() -> Board { Board::from_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1") }

    /// Hash recomputed from scratch, to test the incremental updates.
    pub fn hash_from_scratch(&self) -> u64 {
        let mut h = self.rights_hash() ^ if self.stm == 1 { Z[792] } else { 0 };
        for s in 0..64 {
            if self.mail[s] != 0 { h ^= Z[(((self.occ[1] >> s) & 1) as usize * 6 + self.mail[s] as usize - 1) * 64 + s]; }
        }
        h
    }

    fn attacked(&self, s: usize, by: usize) -> bool {
        let all = self.occ[0] | self.occ[1];
        let mine = self.occ[by];
        let (f, r) = (s % 8, s / 8);
        // pawns of colour `by` attack upward (white) or downward (black): look one rank back
        let pr = if by == 0 { r.wrapping_sub(1) } else { r + 1 };
        let mut pawn = false;
        if pr < 8 {
            for pf in [f.wrapping_sub(1), f + 1] {
                if pf < 8 { pawn |= (self.pc[P] & mine) >> (pr * 8 + pf) & 1 != 0; }
            }
        }
        pawn
            || KNIGHT[s] & self.pc[N] & mine != 0
            || KING[s] & self.pc[K] & mine != 0
            || slide(s, all, &DIAG) & (self.pc[B] | self.pc[Q]) & mine != 0
            || slide(s, all, &ORTH) & (self.pc[R] | self.pc[Q]) & mine != 0
    }

    fn pseudo_legal(&self, out: &mut Vec<Move>) {
        let us = self.stm; let them = 1 - us;
        let all = self.occ[0] | self.occ[1];
        let add = |from: usize, mut targets: u64, out: &mut Vec<Move>| {
            while targets != 0 {
                let to = targets.trailing_zeros() as u8; targets &= targets - 1;
                out.push(Move { from: from as u8, to, promo: 0, flag: 0 });
            }
        };
        for t in N..=K {
            let mut bb = self.pc[t] & self.occ[us];
            while bb != 0 {
                let s = bb.trailing_zeros() as usize; bb &= bb - 1;
                let a = match t {
                    N => KNIGHT[s], K => KING[s],
                    B => slide(s, all, &DIAG), R => slide(s, all, &ORTH),
                    _ => slide(s, all, &DIAG) | slide(s, all, &ORTH),
                };
                add(s, a & !self.occ[us], out);
            }
        }
        let (up, start, last): (i8, usize, usize) = if us == 0 { (8, 1, 7) } else { (-8, 6, 0) };
        let mut bb = self.pc[P] & self.occ[us];
        while bb != 0 {
            let s = bb.trailing_zeros() as usize; bb &= bb - 1;
            let one = (s as i8 + up) as usize;
            let push = |to: usize, flag: u8, out: &mut Vec<Move>| {
                if to / 8 == last { for p in [N, B, R, Q] { out.push(Move { from: s as u8, to: to as u8, promo: p as u8, flag }); } }
                else { out.push(Move { from: s as u8, to: to as u8, promo: 0, flag }); }
            };
            if all >> one & 1 == 0 {
                push(one, 0, out);
                let two = (s as i8 + 2 * up) as usize;
                if s / 8 == start && all >> two & 1 == 0 { push(two, 1, out); }
            }
            for df in [-1i8, 1] {
                let f = (s % 8) as i8 + df;
                if !(0..8).contains(&f) { continue; }
                let to = (one / 8) * 8 + f as usize;
                if self.occ[them] >> to & 1 != 0 { push(to, 0, out); }
                else if to as i8 == self.ep { push(to, 2, out); }
            }
        }
        // castling: rights, empty squares between, king not in check and not crossing an attacked square
        let (ks, k_bit, q_bit) = if us == 0 { (4, 1, 2) } else { (60, 4, 8) };
        if (self.pc[K] & self.occ[us]) >> ks & 1 != 0 && !self.attacked(ks, them) {
            if self.castle & k_bit != 0 && all >> (ks + 1) & 3 == 0 && !self.attacked(ks + 1, them) {
                out.push(Move { from: ks as u8, to: ks as u8 + 2, promo: 0, flag: 3 });
            }
            if self.castle & q_bit != 0 && all >> (ks - 3) & 7 == 0 && !self.attacked(ks - 1, them) {
                out.push(Move { from: ks as u8, to: ks as u8 - 2, promo: 0, flag: 3 });
            }
        }
    }

    pub fn make(&self, m: Move) -> Board {
        let mut b = *self;
        let (us, them) = (self.stm, 1 - self.stm);
        let (f, t) = (m.from as usize, m.to as usize);
        b.hash ^= b.rights_hash();
        let piece = b.mail[f] as usize - 1;
        let cap_sq = if m.flag == 2 { if us == 0 { t - 8 } else { t + 8 } } else { t };
        if b.mail[cap_sq] != 0 { let ct = b.mail[cap_sq] as usize - 1; b.take(them, ct, cap_sq); }
        b.take(us, piece, f);
        b.put(us, if m.promo != 0 { m.promo as usize } else { piece }, t);
        if m.flag == 3 {
            let (rf, rt) = if t > f { (f + 3, f + 1) } else { (f - 4, f - 1) };
            b.take(us, R, rf); b.put(us, R, rt);
        }
        let mask = |s: usize| match s { 0 => 2, 7 => 1, 4 => 3, 56 => 8, 63 => 4, 60 => 12, _ => 0 };
        b.castle &= !(mask(f) | mask(t));
        b.ep = if m.flag == 1 { ((f + t) / 2) as i8 } else { -1 };
        b.stm = them;
        b.hash ^= b.rights_hash() ^ Z[792];
        b
    }

    /// Fully legal moves: pseudo-legal, then reject those that leave the own king attacked.
    pub fn legal_moves(&self) -> Vec<Move> {
        let mut v = Vec::with_capacity(48);
        self.pseudo_legal(&mut v);
        v.retain(|&m| {
            let n = self.make(m);
            let k = (n.pc[K] & n.occ[self.stm]).trailing_zeros() as usize;
            !n.attacked(k, n.stm)
        });
        v
    }
}

pub fn perft(b: &Board, depth: u32) -> u64 {
    if depth == 0 { return 1; }
    debug_assert_eq!(b.hash, b.hash_from_scratch());
    let moves = b.legal_moves();
    if depth == 1 { return moves.len() as u64; }
    moves.iter().map(|&m| perft(&b.make(m), depth - 1)).sum()
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn start_position() {
        let b = Board::startpos();
        assert_eq!(perft(&b, 1), 20);
        assert_eq!(perft(&b, 3), 8_902);
        assert_eq!(perft(&b, 4), 197_281);
    }
    #[test]
    fn kiwipete() {
        let b = Board::from_fen("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1");
        assert_eq!(perft(&b, 1), 48);
        assert_eq!(perft(&b, 2), 2_039);
        assert_eq!(perft(&b, 3), 97_862);
    }
}

Measured with this code: perft(5) of Kiwipete (193,690,690 leaves) in about 4 s on one Apple-silicon core in a release build, order of 5×10^7 leaves per second. Sliding attacks use a plain ray walk, so a magic or PEXT table is the first speed-up; the Board is a 150-byte Copy value, so copy-make needs no unmake.

Complexity and constants

• Generation per node: O(pieces + moves). With table lookups each slider costs one multiply, shift and load (magic) or one pext and load.
• Tables (Chess Programming Wiki): plain magics about 2 MiB for rooks and 256 KiB for bishops; fancy (per-square sized) magics about 800 KiB and 38 KiB; a fancy PEXT layout about 840 KB for both. Order of 1 MiB total keeps them in L2.
• Board state: order of 150 bytes (6 piece masks, 2 colour masks, 64-byte mailbox, flags, hash); copy-make copies that much per node.
• Move: 4 bytes here (from, to, promotion, flag); 16 bits suffice (6+6+4).

Efficiency

• Cost: order of 20 ns per leaf in the code above (measured: 193.7 M leaves in 4.2 s on one Apple-silicon core, ray-walk sliders, test-after-make); the bound is branchy code and one board copy per move, not memory.
• Levers:
  • magic or PEXT slider tables — replaces the ray loop with one load per slider — in any engine; PEXT only where the instruction is fast
  • legal-by-construction masks — skips the copy and attack test per move — generators inside a search
  • bulk counting at depth 1 — perft saves a make per leaf — perft only
  • staged generation (captures, then quiets) — never builds moves that a cutoff skips — alpha-beta search with move ordering
  • incremental hash — O(changed squares) per move instead of O(pieces) — whenever a transposition table is used
• Naive → standard → state of the art:
  • array board scan with ray loops, copy-make · slowest; fine for tools
  • bitboards, leaper tables, ray-walk sliders, pseudo-legal plus test · the code above, about 20 ns per leaf
  • bitboards, magic or PEXT sliders, pin/check masks, staged lists, unmake · what engines ship

Implementation notes

• Index squares a1 = 0 … h8 = 63 (rank × 8 + file); trailing_zeros pops the lowest piece, bb &= bb - 1 clears it.
• Castling-rights update by a per-square mask (a1, e1, h1, a8, e8, h8) applied to both from and to handles king moves, rook moves and rook captures with one rule.
• Hash only an en-passant file when a pawn can actually capture; hashing it after every double push (as above) is simpler but gives two different keys for the same position.
• Keep the mailbox (square → piece) beside the bitboards: captures and make/unmake then need no bitboard scan.
• Run perft in a debug build with debug_assert_eq!(hash, hash_from_scratch()) at every node; incremental-hash bugs show up there first.
• Use u64 shifts with file masks (& !FILE_A) for pawn captures; a shift without the mask wraps around the board edge.

Pitfalls

• En passant exposing the own king along the rank (both pawns leave it at once): a mask-based generator needs a special check, test-after-make gets it free.
• Castling out of, through or into check; losing rights when a rook is captured on its home square.
• Promotions yield four moves; counting one gives a wrong perft only at depths where promotions occur, which is why perft needs the tricky positions, not just the start position.
• Generating the king's escape squares with the king still on the board: the king "shields" squares behind it from a checking slider.
• Trusting game playing instead of perft: bugs in rare rules survive thousands of games.

Variants and alternatives

In production

• Chess engines such as Stockfish; the generator is tested against published perft counts.
• Rust rules libraries used by chess servers and tools: shakmaty, chess.
• Self-play and search code calls a generator at every tree expansion and to mask a policy head.

Implementations

Sources

• Chess Programming Wiki, Move Generation. page
• Chess Programming Wiki, Perft and Perft Results. Perft · results
• Chess Programming Wiki, Magic Bitboards. page
• Chess Programming Wiki, BMI2 (PEXT bitboards). page
• Chess Programming Wiki, Make Move. page
• Chess Programming Wiki, Pin. page
• Chess Programming Wiki, Zobrist Hashing. page