Compressing chess moves for fun and profit

Original Article ↗ Hacker News Discussion ↗

Overall focus

  • Discussion centers on how far you can compress chess games beyond PGN by exploiting game structure, non‑uniform move distributions, and engine predictions.
  • There’s a recurring tension between “maximal compression” vs “simplicity, speed, and queryability.”

Generic vs domain‑specific compression

  • Several suggest trying standard compressors (gzip, zstd, LZW, trained dictionaries) on move lists or sorted game lists as a baseline.
  • Others argue general compressors can’t exploit chess‑specific structure (legal moves, board state) as well as custom encodings.
  • Some think a good zstd dictionary or columnar formats over positions might get close “for free,” but this remains untested in the thread.

Move- and game-level encodings

  • Many propose simple fixed‑width encodings:
    • 12–16 bits: source + destination squares (6+6 bits), with promotions/castling inferred or signaled via “impossible” destinations or extra bits.
    • Piece-index + relative move pattern, exploiting that each side has at most 16 pieces; schemes reaching ~6–9 bits/move are discussed.
  • More advanced schemes:
    • Index the chosen move among all legal moves in the current position; with ~n legal moves, you need ~log₂(n) bits; practical estimates are ≲6–8 bits/move.
    • Use variable‑length codes (Huffman, arithmetic coding, ANS/rANS, CABAC) with per‑position probability distributions.
    • Engine‑guided probabilities (from Stockfish or weaker engines) could, in theory, reach ~3–4 bits/move, possibly lower, but at high CPU cost and with tight coupling to specific engine versions.
  • A follow‑up by the article’s author (linked repeatedly) reports ~3.7 bits/move using arithmetic coding and fast move generation.

Positions, indexing, and search

  • Several point out that in real databases, storage is often dominated by search indexes, not raw game data.
  • Ideas for indexing:
    • Zobrist hashing and transposition‑table–style structures.
    • Bloom filters or partitioned Bloom filters for existence checks vs full hash tables for O(1) lookup.
    • Columnar storage of board states (per‑square “columns”) with standard compression and then referencing positions by offset.
    • Techniques for “fuzzy” position search (e.g., Hamming distance on bitboards, MinHash‑like ideas), though practical solutions remain unclear.

Tradeoffs and practical concerns

  • Many emphasize that extreme compression can hurt:
    • Decoding speed (full move generation, engine calls).
    • Random access and complex queries (e.g., opening explorers, endgame pattern search).
    • Maintainability; very dense, clever schemes may be hard for future developers to understand.
  • Some note that PGN is wasteful but human‑readable; in many real‑world cases, I/O latency and querying strategy matter more than squeezing the last bits out of move storage.