这篇文章介绍了一种用26字节存储国际象棋棋局状态的巧妙方法。通过将32个棋子的位置编码为6位数字(共192位/24字节)，并额外使用2位记录王车易位和吃过路兵等特殊规则，最终实现了高效压缩存储。这种方法利用了位级操作技术，在保证信息完整性的同时大幅减少了存储空间需求。

如何用26字节存储国际象棋棋局：位运算的魔法

作者注：本文改编自在Recurse Center的演讲内容。

基础存储需求

• 棋盘上有32个棋子，每个棋子占据64个方格之一
• 用6位二进制数（2^6=64）表示每个棋子的位置
• 32个棋子 × 6位 = 192位（即24字节）

额外需要记录的信息

1. 吃子情况：用32位位图表示哪些棋子被吃
2. 王车易位：用4位记录（每方两个车各1位）
3. 过路兵：用16位记录（每方8个兵各1位）
4. 兵升变：
   • 每个兵需要3位：1位标记是否升变，2位记录升变后的棋子类型
   • 16个兵共需48位

优化技巧

关键发现：任何两个棋子不能占据同一方格

1. 吃子优化：

   • 用对方王的位置表示被吃的棋子
   • 用己方王的位置表示特殊状态

2. 王车易位优化：

   • 用车初始位置替代实际位置（因为只有未移动的车才能易位）

3. 过路兵优化：

   • 过路兵必定位于初始列和特定行（白方第4行/黑方第5行）
   • 用己方王的位置替代过路兵位置

通过这些技巧，可以免费存储吃子、易位和过路兵信息！

兵升变的优化

• 通过建立唯一排序的升变序列
• 使用9位二进制数即可表示所有可能的升变组合（共495种情况）
• 每方各需9位，共18位（约2.25字节）

最终存储方案

• 基础位置信息：24字节
• 升变信息：2.25字节
• 总计约26字节

延伸阅读

国际象棋编码是深度有趣的话题，Lichess博客介绍了使用霍夫曼编码高效存储棋局的方法。

（注：原文中的数学推导和代码链接等细节已适当简化，保留核心思路）

评论总结

1. 编码效率与实用性

• 支持高效编码：pklausler指出26字节（208位）足够编码棋局，并分享了自己90年代用96位编码的经验。
  "26 bytes is 208 bits, about twice what you really need for a minimal encoding..."
• 反对过度优化：notthefda认为代码可读性比节省字节更重要。
  "With a few bytes more you can create an implementation that is a lot easier to understand. Bytes are cheap, developer time isn't."
  jcalvinowens补充说密集结构可能导致指令膨胀。
  "Absolute minimalism is rarely the right choice, the size of .text matters too."

2. 棋局状态完整性争议

• 遗漏规则信息：btilly指出当前编码无法处理“50回合和棋”或“重复局面”规则，需额外存储历史信息。
  "Either we have to say that the position does not dictate the possible moves, or that this does not fully capture the position."
• 王车易位漏洞：efitz和4rt质疑仅通过棋子位置判断易权是否可靠。
  "There’s a logic error from assuming that because the rook is in its original position that the rook has not moved."

3. 数学与压缩技术

• 状态数计算：jmward01通过26字节推算棋局状态上限为4.1×10⁶²，并引用研究证实。
  "26 bytes works out to chess being no more than 4.113761393×10⁶² possible states."
• 优化建议：bonzini提出主教编码可省2位，精确达到26字节。
  "Bishops only need 5 bits instead of 6... reaching exactly 26 bytes."
  billforsternz提出两种24字节编码方法，强调平均比特效率。
  "Method 1: Lichess method; 64 bit header... worst case 24 bytes!"

4. 替代方案与批评

• 简化编码：Smalltalker-80建议用14字节数组存储棋子位置。
  "Create an array with 16 elements... 112 bits = 14 bytes."
• 二进制编码争议：01092026批评当前方法混淆整数与比特流，声称可实现真实二进制编码。
  "A true bit-level approach would encode positions as pure binary streams... Ask and I will show you how to do it in 24 BYTES."
• 历史压缩：kibwen和untech推荐基于移动序列的压缩（如Lichess的3.7比特/步）。
  "Compressing Chess Moves Even Further, To 3.7 Bits Per Move."

5. 其他观点

• 应用场景：jfaat分享了一个棋局分析平台，强调实战优化价值。
  "It’s been really useful for me to identify weaknesses and have a ‘coach’."
• 边缘优化：RiverCrochet指出国王捕获位可复用。
  "The king can’t be captured, so the capture bit for the kings can be used for something else."