Bitboards

Deep dive

How it works

In: occupancy and piece sets as u64 + a square index · Out: attack, move or neighbor sets as u64 · State: pieces[color][kind], occupied, attack tables (about 841 KiB with fancy magics) · Cost: O(1) per ray query (mask, multiply, shift, load), O(n) to iterate n set bits.

1. Layout. Keep pieces[color][kind]: u64, plus occupied[color] and all kept in sync on make/unmake. Also keep board[64]: Piece (mailbox) to answer "what is on e4" in O(1).
2. Shifts. One step in a direction is a shift; horizontal shifts must mask off the wrap-around file. Pawn pushes for all white pawns at once: north(pawns) & empty; double pushes: north(single & RANK_3) & empty.
3. Leapers. Knight, king and pawn attacks per square are 64-entry tables built at startup.
4. Sliders (magic). For a rook on sq, only blockers on its rays excluding the board edge matter (a piece on the edge cannot hide anything behind it). That "relevant mask" has bits ≤ 12 set. For every subset of the mask, the attack set is precomputed. A 64-bit constant magic is found by random search such that (subset * magic) >> (64 - bits) maps all 2^bits subsets to distinct slots, or to slots whose attack sets are equal (constructive collision).
5. Iterate pieces. sq = b.trailing_zeros(); b &= b - 1; visits each set bit once.
6. Generate moves. targets = attacks(sq, all) & !own; captures = targets & enemy, quiets = targets & !all. Pin and check masks (between[ksq][checker]) make the generator legal instead of pseudo-legal.

rank 8  56 57 58 59 60 61 62 63      north  = << 8     south = >> 8
...                                   east   = (b << 1) & !FILE_A
rank 1   0  1  2  3  4  5  6  7      west   = (b >> 1) & !FILE_H
         a  b  c  d  e  f  g  h

Code

pub type Bb = u64;
pub const FILE_A: Bb = 0x0101_0101_0101_0101;
pub const FILE_H: Bb = FILE_A << 7;
#[inline] pub fn north(b: Bb) -> Bb { b << 8 }
#[inline] pub fn south(b: Bb) -> Bb { b >> 8 }
#[inline] pub fn east(b: Bb) -> Bb { (b << 1) & !FILE_A }
#[inline] pub fn west(b: Bb) -> Bb { (b >> 1) & !FILE_H }
pub fn knight_attacks(sq: u32) -> Bb {
    let b = 1u64 << sq;
    let h1 = ((b >> 1) & !FILE_H) | ((b << 1) & !FILE_A);
    let h2 = ((b >> 2) & !(FILE_H | FILE_H >> 1)) | ((b << 2) & !(FILE_A | FILE_A << 1));
    (h1 << 16) | (h1 >> 16) | (h2 << 8) | (h2 >> 8)
}
pub fn king_attacks(sq: u32) -> Bb {
    let b = 1u64 << sq;
    let row = b | east(b) | west(b);
    (row | north(row) | south(row)) & !b
}
pub fn white_pawn_attacks(pawns: Bb) -> Bb { north(east(pawns) | west(pawns)) }

pub fn squares(mut b: Bb) -> impl Iterator<Item = u32> {
    std::iter::from_fn(move || {
        if b == 0 { return None; }
        let s = b.trailing_zeros();
        b &= b - 1; // clear lowest set bit
        Some(s)
    })
}
pub const ROOK_DIRS: [(i32, i32); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];
pub const BISHOP_DIRS: [(i32, i32); 4] = [(1, 1), (1, -1), (-1, 1), (-1, -1)];

/// Slow ray walk: only for building tables and for tests.
pub fn slide(sq: u32, occ: Bb, dirs: &[(i32, i32); 4]) -> Bb {
    let (f0, r0) = ((sq % 8) as i32, (sq / 8) as i32);
    let mut att = 0;
    for &(df, dr) in dirs {
        let (mut f, mut r) = (f0 + df, r0 + dr);
        while (0..8).contains(&f) && (0..8).contains(&r) {
            let s = 1u64 << (r * 8 + f);
            att |= s;
            if occ & s != 0 { break; }
            (f, r) = (f + df, r + dr);
        }
    }
    att
}

/// Ray squares that can block, i.e. without the last square on each ray.
fn relevant_mask(sq: u32, dirs: &[(i32, i32); 4]) -> Bb {
    let (f0, r0) = ((sq % 8) as i32, (sq / 8) as i32);
    let mut m = 0;
    for &(df, dr) in dirs {
        let (mut f, mut r) = (f0 + df, r0 + dr);
        while (0..8).contains(&(f + df)) && (0..8).contains(&(r + dr)) {
            m |= 1u64 << (r * 8 + f);
            (f, r) = (f + df, r + dr);
        }
    }
    m
}

#[derive(Clone, Copy, Default)]
pub struct Magic { mask: Bb, magic: u64, shift: u32, offset: usize }

pub struct Sliders { rook: [Magic; 64], bishop: [Magic; 64], table: Vec<Bb> }

impl Sliders {
    #[inline]
    fn index(m: &Magic, occ: Bb) -> usize {
        m.offset + ((occ & m.mask).wrapping_mul(m.magic) >> m.shift) as usize
    }
    #[inline] pub fn rook(&self, sq: u32, occ: Bb) -> Bb { self.table[Self::index(&self.rook[sq as usize], occ)] }
    #[inline] pub fn bishop(&self, sq: u32, occ: Bb) -> Bb { self.table[Self::index(&self.bishop[sq as usize], occ)] }
    #[inline] pub fn queen(&self, sq: u32, occ: Bb) -> Bb { self.rook(sq, occ) | self.bishop(sq, occ) }

    pub fn new() -> Self {
        let mut s = Sliders { rook: [Magic::default(); 64], bishop: [Magic::default(); 64], table: Vec::new() };
        let mut rng = 0x9E37_79B9_7F4A_7C15u64;
        for sq in 0..64u32 {
            s.rook[sq as usize] = find_magic(sq, &ROOK_DIRS, &mut s.table, &mut rng);
            s.bishop[sq as usize] = find_magic(sq, &BISHOP_DIRS, &mut s.table, &mut rng);
        }
        s
    }
}

fn find_magic(sq: u32, dirs: &[(i32, i32); 4], table: &mut Vec<Bb>, rng: &mut u64) -> Magic {
    let mask = relevant_mask(sq, dirs);
    let bits = mask.count_ones();
    let (mut occs, mut atts) = (Vec::new(), Vec::new());
    let mut sub = 0u64;
    loop {
        occs.push(sub);
        atts.push(slide(sq, sub, dirs));
        sub = sub.wrapping_sub(mask) & mask; // Carry-Rippler: next subset of mask
        if sub == 0 { break; }
    }
    let offset = table.len();
    table.resize(offset + (1 << bits), 0);
    let mut epoch = vec![0u32; 1 << bits]; // attempt that last wrote each slot, avoids clearing
    for attempt in 1u32.. {
        let magic = xorshift(rng) & xorshift(rng) & xorshift(rng); // sparse candidates work better
        if (mask.wrapping_mul(magic) >> 56).count_ones() < 6 { continue; }
        let m = Magic { mask, magic, shift: 64 - bits, offset };
        let ok = occs.iter().zip(&atts).all(|(&o, &a)| {
            let i = Sliders::index(&m, o);
            if epoch[i - offset] != attempt {
                epoch[i - offset] = attempt;
                table[i] = a;
                true
            } else {
                table[i] == a // constructive collision is allowed
            }
        });
        if ok { return m; }
    }
    unreachable!()
}

fn xorshift(s: &mut u64) -> u64 { *s ^= *s << 13; *s ^= *s >> 7; *s ^= *s << 17; *s }

Complexity and constants

• Magic lookup: AND, MUL (3-cycle latency on current x86 and Apple cores), SHR, ADD, one load. Latency is dominated by the load: L1 hit ≈ 4-5 cycles, L2 ≈ 12-16. The 841 KiB table (plain magics) does not fit L1; hot squares stay in L2.
• Startup magic search with the code above: order of 0.2 s in an optimized build. Engines ship precomputed magics.
• Popcount and tzcnt: 1 instruction each if enabled. Rust's count_ones on x86-64 baseline compiles to a bit-twiddling sequence; build with -C target-cpu=native or x86-64-v2/-v3 (v2 has POPCNT, v3 adds BMI1/BMI2 incl. TZCNT and PEXT).
• Perft (node count of legal moves) from the start position: depth 5 = 4,865,609, depth 6 = 119,060,324. Bitboard generators with bulk counting at the leaves reach order of 10⁸-10⁹ nodes/s per core.

Efficiency

• Cost: a ray query is AND, MUL (3-cycle latency), SHR, ADD and one load: order of 1-3 ns when cached, bounded by the load (L1 ≈ 4-5 cycles; the 841 KiB table lives in L2). Memory is 8 bytes per set plus the tables. Bulk-counting perft generators reach order of 10⁸-10⁹ nodes/s per core.
• Levers:
  • PEXT index instead of multiply — drops the magic search and one multiply — Intel Haswell+, AMD Zen 3+ only (microcoded before)
  • fancy magics (shared table, 2^bits slots per square) — 841 KiB instead of about 2.3 MiB for plain magics — cache-sensitive code
  • build with POPCNT/BMI (-C target-cpu=native, x86-64-v2/v3) — one-instruction popcount and tzcnt instead of a bit-twiddling sequence — x86-64 builds
  • set-wise generation (pawns, Kogge-Stone fills) — all pieces of a kind in a few operations — bulk move generation
  • precomputed between and line tables, 32 KiB each — pins and check blocks in one AND — legal move generation
• Naive → standard → state of the art:
  • per-ray loop over squares · O(ray length) branches per slider
  • rotated bitboards · several shifts plus lookups per ray (superseded)
  • magic or PEXT bitboards · order of 1-3 ns per ray

Implementation notes

• Fancy vs plain magics. The code above is "fancy": each square uses exactly 2^bits slots in one shared table with a per-square offset. Plain magics use 4096/512 slots per square (2 MiB + 256 KiB).
• PEXT. With BMI2, _pext_u64(occ, mask) is the perfect index; no magic, same table. Use it only on Intel Haswell+ and AMD Zen 3+; on Zen 1/2 it is microcoded with latency that grows with the mask popcount, slower than the multiply.
• Struct layout. mask, magic, shift, offset in one 32-byte struct per square, as in Stockfish's Magic.
• Precompute between[a][b] and line[a][b] (64×64×8 B = 32 KiB each): pin rays and check-block masks in one AND.
• Struct layout. Put mask, magic, shift, offset in one 32-byte struct per square (Stockfish's Magic struct does this), so one lookup touches one cache line for metadata and one for the table.
• Precompute between[a][b] (squares strictly between) and line[a][b] (full line through both): 64×64×8 B = 32 KiB each. They give pin rays, check-block masks and castling-path tests in one AND.
• Pawns in bulk. Generate all pawn moves with set-wise shifts, then extract target squares and recover the origin by subtracting the shift. Promotions: & RANK_8.
• Mailbox alongside. Bitboards answer "where are the knights"; an array answers "what is on e4". Keep both; update both in make/unmake.
• Flips. b.swap_bytes() mirrors ranks (white↔black view); b.reverse_bits() rotates 180°. Hyperbola quintessence uses swap_bytes for files and diagonals.

Pitfalls

• Forgetting the wrap mask on east/west shifts: an h-file piece "attacks" the a-file of the next rank.
• 1 << sq with an i32 literal: overflow for sq ≥ 31. Always 1u64 << sq.
• Validate move generation with perft against published numbers, including tricky positions (castling through check, en-passant discovered check along the rank).
• Including the board edge in the relevant mask: still correct, but every square needs one or two more bits, quadrupling table size.
• Shifting by 64 (b >> (64 - 0)) is undefined in C and panics in debug Rust; it happens if a mask is empty. Masks are never empty for real squares, but guard generic code.
• Building without POPCNT/BMI and wondering why evaluation is 2× slower.

Variants and alternatives

In production

• Games: Stockfish (bitboard.cpp: fancy magics, PEXT in BMI2 builds), Ethereal, Berserk, Leela Chess Zero's move generator, Crafty (originally rotated bitboards); checkers and othello engines use the same set-wise shifts.
• Combinatorial optimisation: BBMC, an exact maximum-clique solver that stores vertex sets as bit strings (San Segundo et al. 2011).
• Text and bioinformatics: Myers' bit-vector algorithm for approximate string matching, a column of the dynamic-programming matrix held in machine words.
• Databases and search engines: compressed bitmap indexes with the Roaring library (CRoaring, roaring-rs).

Implementations

Sources

• Pradyumna Kannan, Magic Move-Bitboard Generation in Computer Chess, 2007.
• Pablo San Segundo, Diego Rodríguez-Losada, Agustín Jiménez, An exact bit-parallel algorithm for the maximum clique problem, Computers & Operations Research 38(2), 2011. paper
• Gene Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, Journal of the ACM 46(3), 1999. paper
• Daniel Lemire et al., Roaring bitmaps: Implementation of an optimized software library, Software: Practice and Experience 48(4), 2018. paper · code
• Robert Hyatt, Rotated Bitmaps, a New Twist on an Old Idea, ICCA Journal 22(4), 1999.
• Chess Programming Wiki, entries Magic Bitboards, Perft Results, Hyperbola Quintessence (chessprogramming.org).
• Stockfish source, src/bitboard.h and src/bitboard.cpp.