为乐趣和利润压缩棋步

原文 ↗ Hacker News 讨论 ↗

总体关注点

  • 讨论集中在如何通过利用棋局结构、不均匀的着法分布以及引擎预测，把国际象棋对局压缩到比 PGN 更小的程度。
  • 反复出现的一种张力是：“极限压缩” 与 “简单性、速度和可查询性” 之间的权衡。

通用压缩 vs 领域特定压缩

  • 有几位建议先对着法列表或排序后的对局列表尝试标准压缩器（gzip、zstd、LZW、训练过的字典）作为基线。
  • 也有人认为，通用压缩器无法像自定义编码那样利用国际象棋特有的结构（合法着法、局面状态）。
  • 有人认为，一个好的 zstd 字典或基于列式格式存储局面，可能“免费”地接近理想效果，但这一点在讨论串中尚未经过测试。

着法级和对局级编码

  • 许多人提出简单的定长编码：
    • 12–16 位：起点 + 终点格（6+6 位），通过“不可能”的终点或额外位来推断或标记升变/王车易位。
    • 子力索引 + 相对着法模式，利用每方最多只有 16 个棋子；讨论中提到可达到约 6–9 位/步的方案。
  • 更高级的方案：
    • 将当前局面下所有合法着法中的所选着法进行索引；若有约 n 个合法着法，则需要约 log₂(n) 位；实际估计通常是 ≲6–8 位/步。
    • 使用变长编码（Huffman、算术编码、ANS/rANS、CABAC），并结合每个局面的概率分布。
    • 由引擎（如 Stockfish 或较弱引擎）给出的概率在理论上可达到约 3–4 位/步，甚至更低，但 CPU 成本很高，而且会紧密耦合到特定引擎版本。
  • 文章作者的后续更新（在讨论中被反复链接）报告称，使用算术编码和快速着法生成可达到约 3.7 位/步。

局面、索引与检索

  • 有几位指出，在真实数据库中，存储往往主要被检索索引占用，而不是原始对局数据。
  • 索引方面的想法包括：
    • Zobrist 哈希和类似转置表的结构。
    • 用 Bloom filter 或分区 Bloom filter 做存在性检查，或用完整哈希表实现 O(1) 查找。
    • 对棋盘状态进行列式存储（按每个格子的“列”）并使用标准压缩，然后通过偏移量引用局面。
    • 用于“模糊”局面搜索的技术（例如在 bitboard 上做汉明距离，或类似 MinHash 的想法），但实际可行方案仍不清楚。

权衡与实际顾虑

  • 许多人强调，极端压缩可能带来代价：
    • 解码速度（完整着法生成、引擎调用）。
    • 随机访问和复杂查询（例如开局浏览器、残局模式搜索）。
    • 可维护性；过于密集、巧妙的方案可能会让未来的开发者难以理解。
  • 也有人指出，PGN 虽然浪费空间，但可读性强；在许多现实场景里，I/O 延迟和查询策略比把着法存储再挤出最后几比特更重要。