Compressing chess moves for fun and profit

Original Article ↗ Hacker News Discussion ↗

Efforts to compress chess games far beyond human-readable PGN spark a range of ideas, from simple fixed-width encodings of source–destination squares to sophisticated schemes using engines, probability models, Huffman or arithmetic coding, and even ANS. Commenters debate theoretical limits of bits per move, the practicality of engine‑based predictors at scale, and how custom formats compare to generic tools like gzip or zstd. Many conclude that for large databases the harder and more important problem is efficient indexing and fuzzy search of positions, with compression useful mainly insofar as it reduces I/O without making querying too complex.

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.