Compact state encoding

Deep dive

How it works

In: a position (board, side to move, castling, en passant) · Out: 24 bytes, or the lexicographically smallest of k symmetric encodings · State: none · Cost: O(pieces) per encode or decode.

Occupancy + nibbles (24 bytes, fixed size)

1. occ: bit s set iff square s holds a piece (8 bytes).
2. For each set bit in ascending order, one 4-bit code: 0-11 = piece kind and colour.
3. Spare codes carry the remaining state:
   • 12 = a pawn that just made a double push; the en-passant square is behind it, and its colour follows from the rank (4th rank: white).
   • 13 / 14 = white / black rook that still has its castling right (castling side follows from the square).
   • 15 = black king and black to move; a plain black king (11) means white to move.
4. Halfmove clock and move number, if needed, go in 1-2 extra bytes.

Huffman board (variable, ≤ 32 bytes): side to move (1 bit), both king squares (6 bits each), then per non-king square a prefix code: empty 0, pawn 001, knight 011, bishop 101, rook 111 (+1 colour bit each), queen 1001 + colour; then castling (4 bits), en passant (1 or 7 bits), counters. Shorter on average than 24 bytes, but variable length and bit-serial to decode.

Canonical forms: generate each symmetric variant, encode, keep the lexicographically smallest bytes. Chess: identity and colour flip (ranks mirrored, colours and side to move swapped, castling bits swapped); add the a↔h file mirror when no castling rights remain. Pawnless endgames: all 8 rotations/reflections of the square; tablebases then place the white king in the a1-d1-d4 triangle (10 squares), and the two kings together have 462 placements. Go: 8 board symmetries; a 19×19 board is 361 points × 2 bits = 91 bytes raw.

occupancy (8 B) │ nibbles in square order (≤ 16 B)
1111111111111111 0000…0000 1111111111111111   start position: 32 bits set
 WR* WN WB WQ WK WB WN WR* WP×8 … BP×8 BR* BN BB BQ BK BB BN BR*   (* = rook with castling right)

Code

// Square 0 = a1, 7 = h1, 63 = h8. Piece codes 0..=11: WP BP WN BN WB BB WR BR WQ BQ WK BK
// (even = white, code ^ 1 swaps colour). EMPTY marks an empty square.
pub const EMPTY: u8 = 0xFF;
const WP: u8 = 0; const BP: u8 = 1; const WR: u8 = 6; const BR: u8 = 7; const BK: u8 = 11;
// Spare nibble values, each folding one bit of state into a piece:
const EP_PAWN: u8 = 12;     // pawn that just double-pushed (ep square is behind it)
const WR_CASTLE: u8 = 13;   // white rook that still has its castling right
const BR_CASTLE: u8 = 14;   // black rook that still has its castling right
const BK_TO_MOVE: u8 = 15;  // black king, and black is to move

#[derive(Clone, PartialEq, Debug)]
pub struct Pos {
    pub board: [u8; 64],
    pub black_to_move: bool,
    pub castling: u8,       // bit 0 = white h1 rook (K), 1 = white a1 (Q), 2 = black h8 (k), 3 = black a8 (q)
    pub ep: Option<u8>,     // en-passant target square; store only if a capture is legal
}

const CASTLE_SQ: [u8; 4] = [7, 0, 63, 56];

/// 24 bytes: 8-byte occupancy + 32 nibbles in ascending square order.
pub fn encode(p: &Pos) -> [u8; 24] {
    let mut out = [0u8; 24];
    let mut occ = 0u64;
    for sq in 0..64 { if p.board[sq] != EMPTY { occ |= 1 << sq; } }
    out[..8].copy_from_slice(&occ.to_le_bytes());
    let (mut bits, mut n) = (occ, 0usize);
    while bits != 0 {
        let sq = bits.trailing_zeros() as u8;
        bits &= bits - 1;
        let pc = p.board[sq as usize];
        let mut code = pc;
        if let Some(ep) = p.ep { // pawn on the square in front of the ep target
            if (pc == WP && sq == ep + 8) || (pc == BP && sq + 8 == ep) { code = EP_PAWN; }
        }
        for (bit, &csq) in CASTLE_SQ.iter().enumerate() {
            if p.castling & (1 << bit) != 0 && sq == csq {
                code = if pc == WR { WR_CASTLE } else if pc == BR { BR_CASTLE } else { code };
            }
        }
        if pc == BK && p.black_to_move { code = BK_TO_MOVE; }
        out[8 + n / 2] |= code << ((n & 1) * 4); // first nibble in the low bits
        n += 1;
    }
    assert!(n <= 32, "more than 32 pieces");
    out
}

pub fn decode(b: &[u8; 24]) -> Pos {
    let mut p = Pos { board: [EMPTY; 64], black_to_move: false, castling: 0, ep: None };
    let mut bits = u64::from_le_bytes(b[..8].try_into().unwrap());
    let mut n = 0usize;
    while bits != 0 {
        let sq = bits.trailing_zeros() as u8;
        bits &= bits - 1;
        let code = (b[8 + n / 2] >> ((n & 1) * 4)) & 0xF;
        n += 1;
        p.board[sq as usize] = match code {
            EP_PAWN if sq < 32 => { p.ep = Some(sq - 8); WP } // 4th rank: white just pushed
            EP_PAWN => { p.ep = Some(sq + 8); BP }            // 5th rank: black just pushed
            WR_CASTLE | BR_CASTLE => {
                let bit = CASTLE_SQ.iter().position(|&c| c == sq).expect("castling rook off its square");
                p.castling |= 1 << bit;
                if code == WR_CASTLE { WR } else { BR }
            }
            BK_TO_MOVE => { p.black_to_move = true; BK }
            c => c,
        };
    }
    p
}

/// Colour flip: mirror ranks, swap colours and side to move. Equivalent position for a
/// side-to-move-relative evaluator; use min(encode(p), encode(flip(p))) as a canonical key.
pub fn flip(p: &Pos) -> Pos {
    let mut q = Pos { board: [EMPTY; 64], black_to_move: !p.black_to_move, castling: 0, ep: None };
    for sq in 0..64 {
        let pc = p.board[sq];
        if pc != EMPTY { q.board[sq ^ 56] = pc ^ 1; }
    }
    q.castling = ((p.castling & 0b0011) << 2) | ((p.castling & 0b1100) >> 2);
    q.ep = p.ep.map(|s| s ^ 56);
    q
}

/// File mirror (a <-> h): only a symmetry when no castling rights remain.
pub fn mirror_files(p: &Pos) -> Option<Pos> {
    if p.castling != 0 { return None; }
    let mut q = p.clone();
    for sq in 0..64 { q.board[sq ^ 7] = p.board[sq]; }
    q.ep = p.ep.map(|s| s ^ 7);
    Some(q)
}

Complexity and constants

• Encode/decode: one pass over set bits, tzcnt + blsr per piece; order of tens of ns per position, dominated by memory traffic when streaming.
• Size: 24 bytes fixed vs 32 for PackedSfen; Stockfish's older .bin training format stores 40 bytes per position (32-byte PackedSfen + score, move, ply, result, padding).
• Fixed size means random access by index (offset = 24 · i) and trivially parallel decoding; variable Huffman codes need an offset index or sequential reads.
• General-purpose compressors on top (zstd) still help a lot on game-ordered data, since consecutive positions share most bytes.

Efficiency

• Cost: encode or decode is one pass over the set bits (tzcnt + blsr per piece), order of tens of ns per position, bound by memory traffic when streaming. Size: 24 bytes fixed; PackedSfen 32; the older .bin record 40 bytes.
• Levers:
  • fixed-size records — random access by index, parallel decode — large flat files
  • move-chain storage (binpack) — one 24-byte position per chain, then a move index and score delta per position — game-ordered data
  • zstd on top — consecutive positions share most bytes — game-ordered data
  • canonical form before dedupe — roughly halves distinct positions with the colour flip — side-to-move-relative evaluators
  • 128-bit hash or exact key — avoids the birthday bound at about 2³² states — billions of keys
• Naive → standard → state of the art:
  • FEN text · tens of bytes per position
  • occupancy + nibbles · 24 bytes fixed
  • binpack chains · fewer bytes per position than 24 (positions follow each other as moves); lower bound 149 bits per arbitrary position (Tromp)

Implementation notes

• Byte order: fix the bitboard's byte order in the file format (little-endian above); Stockfish's binpack writes it big-endian. Never transmute structs into files.
• Nibble order: first square in the low nibble here; whichever you choose, document it, and zero the unused high nibble when the piece count is odd so equal positions give equal bytes.
• Canonical en passant: record the ep square only if an en-passant capture is actually legal. FEN always records it after a double push, so two identical positions would otherwise get different keys (repetition detection has the same rule).
• Chess960 castling: the rook-with-rights trick still works (rooks on any file), but decoding must infer the castling side from the rook's file relative to the king, not from a1/h1.
• Symmetry for training: if your network sees positions from the side to move, store the colour-flipped canonical form and halve the dataset's distinct positions; if it sees absolute colours, do not flip.
• Sort keys: canonical bytes compare with memcmp, so they double as sort keys for dedupe (external sort or a hash set of 24-byte keys).

Pitfalls

• Encoding castling as 4 separate flags and allowing rooks off their squares: decoders accept impossible states; validate on decode (rook on its square, king on its start square).
• Forgetting the side-to-move bit when no black king exists (custom variants, invalid positions): code 15 cannot express it; reject positions without exactly one king per side.
• Promoted pieces: 9 queens are legal; any scheme that assumes at most 8 pawns + original pieces per kind breaks. Occupancy + nibbles has no such limit (only ≤ 32 pieces).
• Mirroring files with castling rights present: the position changes meaning (O-O becomes O-O-O).
• Using a 64-bit hash as a "unique" key for billions of positions: collisions become likely past about 2³² positions (birthday bound); use the exact encoding or a 128-bit hash.

Variants and alternatives

In production

• Games: Stockfish NNUE training data (binpack CompressedPosition, 24 bytes; older PackedSfen 32 bytes), Syzygy and Nalimov tablebase indexes (symmetry-reduced king placements), Lc0 and KataGo training pipelines (board planes, symmetry augmentation).
• Chemistry: canonical SMILES gives one string per molecule for duplicate removal and database keys (Weininger 1989); implemented in RDKit.
• Formal verification: the Murphi verifier collapses symmetric states to one canonical representative (Ip and Dill 1996).

Implementations

Sources

• Stockfish tools branch, src/extra/nnue_data_binpack_format.h (CompressedPosition) and src/tools/sfen_packer.cpp (PackedSfen).
• John Tromp, ChessPositionRanking, GitHub, 2021 (estimate of 4.8 × 10⁴⁴ legal positions). code
• David Weininger, Arthur Weininger, Joseph L. Weininger, SMILES. 2. Algorithm for generation of unique SMILES notation, J. Chem. Inf. Comput. Sci. 29(2), 1989. paper
• C. Norris Ip, David L. Dill, Better verification through symmetry, Formal Methods in System Design 9, 1996. paper