在国际象棋引擎、在线对弈平台与棋局数据库系统中，高效存储棋盘状态是一个基础而关键的工程挑战。传统的 FEN（Forsyth-Edwards Notation）格式需要约 70 字节，而通过精妙的 bitboard 优化与约束编码，我们可以将单个棋盘位置压缩至仅 26 字节。这不仅大幅减少了存储开销，更为实时对弈、棋局分析与分布式系统提供了高效的数据交换格式。
基础表示：从 24 字节开始
国际象棋棋盘有 64 个方格，初始状态下包含 32 个棋子。最直观的编码方案是为每个棋子分配一个 6 位整数（2^6=64），表示其在棋盘上的位置。32 个棋子 × 6 位 = 192 位 = 24 字节。这是我们的起点，但仅包含棋子位置信息，忽略了游戏状态的关键要素。
完整的棋盘状态还需要编码以下信息：
- 被吃棋子：哪些棋子已被移出棋盘
- 王车易位权限：双方国王与车是否仍可进行王车易位
- 吃过路兵目标：当前回合是否存在可吃过路兵的方格
- 升变棋子：哪些兵已升变为其他棋子
如果为每个需求单独分配比特位，我们需要：
- 被吃棋子：32 位（每个棋子 1 位）
- 王车易位：4 位（每方国王侧与后翼各 1 位）
- 吃过路兵：16 位（每个兵 1 位，最多一个目标）
- 升变信息：48 位（16 个兵 × 3 位：1 位是否升变 + 2 位升变类型）
总计 100 位 ≈ 12 字节，加上基础的 24 字节，总计约 36 字节。但通过巧妙的约束利用，我们可以将这些额外信息 "免费" 编码。
约束优化：免费编码的数学原理
1. 被吃棋子的位置复用
国际象棋的基本规则是：没有两个棋子可以占据同一方格。这一约束为我们提供了编码机会。当某个棋子被吃时，我们可以用对方国王的位置来表示该棋子已被移除。
为什么可行？因为被吃的棋子不可能与对方国王占据同一方格（否则国王已被将死，游戏结束）。因此，如果某个棋子的位置编码与对方国王的位置相同，我们可以推断该棋子已被吃。这一技巧完全消除了对被吃棋子单独编码的需求。
2. 王车易位的隐含位置
王车易位仅在国王与相应的车都未移动过时才允许。这意味着，如果王车易位权限存在，那么车必然位于其初始位置（a1/h1 或 a8/h8）。我们可以利用这一事实：当需要编码王车易位权限时，我们只需将车的位置替换为己方国王的位置。
解码时，如果发现车的位置与己方国王相同，且该位置是合法的王车易位初始位置，我们就可以恢复原始的车位置与易位权限信息。
3. 吃过路兵的目标推断
吃过路兵规则规定：只有当对方兵在前一回合向前移动两格时，己方兵可以斜向移动一格吃掉该兵。这意味着可吃过路兵的兵必然位于特定位置：
- 白兵：第 4 横线（rank 4）
- 黑兵：第 5 横线（rank 5）
而且，该兵必须位于其初始纵线（file）上。因此，我们可以用己方国王的位置来编码吃过路兵的目标。解码时，如果某个兵的位置与己方国王相同，且该位置符合吃过路兵的约束条件，我们就可以恢复原始信息。
通过这三个技巧，我们完全消除了对被吃棋子、王车易位和吃过路兵的显式编码需求，将额外开销从 12 字节降至 0 字节。
升变编码：弱递增序列的数学之美
升变编码是本方案中最精妙的部分。每个兵有 5 种可能状态：未升变，或升变为骑士、主教、车、皇后。如果为每个兵分配 3 位（1 位是否升变 + 2 位升变类型），16 个兵需要 48 位。
但我们可以做得更好。观察发现：升变棋子的排序可以唯一确定其升变类型。
弱递增序列编码
假设我们有 8 个白兵，其中一些已升变。我们可以为每个兵分配一个数字：
- 0：未升变
- 1：升变为骑士
- 2：升变为主教
- 3：升变为车
- 4：升变为皇后
然后，我们将这些数字按升序排列，并相应调整兵的位置顺序。例如，如果两个兵分别升变为皇后和车，其他未升变，我们可能得到序列 "00000034"。
关键洞察是：不同的升变模式会产生不同的弱递增序列。通过组合数学计算，8 个兵的所有可能升变模式对应的弱递增序列数量为 495 种。这恰好可以用 9 位编码（2^9=512 > 495）。
因此，白方 8 个兵的升变信息只需 9 位，黑方同样需要 9 位，总计 18 位 ≈ 2 字节。相比原始的 48 位，压缩率达到 62.5%。
组合数学证明
为什么是 495？这是一个经典的 "球与隔板"（balls and urns）问题。我们有 8 个位置（兵），每个位置可以放置 0-4 的数字，且序列必须是非递减的。这等价于在 8+4=12 个位置中选择 4 个隔板位置，即组合数 C (12,4)=495。
更一般地，对于 n 个兵，每个兵有 k 种可能状态（包括未升变），弱递增序列的数量为 C (n+k-1, k-1)。当 n=8，k=5 时，C (12,4)=495。
工程实现：26 字节编码方案
综合以上优化，我们得到完整的 26 字节编码方案：
- 基础位置编码（24 字节）：32 个棋子 × 6 位，按固定顺序排列
- 升变信息编码（2 字节）：18 位弱递增序列编码，白方 9 位 + 黑方 9 位
- 约束隐含信息（0 字节）：被吃棋子、王车易位、吃过路兵通过位置复用编码
编码流程
def encode_position(board_state):
# 1. 编码32个棋子的位置（192位）
positions = encode_piece_positions(board_state)
# 2. 应用约束优化
# - 被吃棋子：用对方国王位置标记
# - 王车易位：用己方国王位置标记车
# - 吃过路兵：用己方国王位置标记兵
# 3. 编码升变信息
promotions = encode_promotions(board_state) # 18位
# 4. 组合输出
return positions + promotions # 210位 = 26.25字节，实际26字节
解码流程
解码是编码的逆过程，但需要特别注意约束检查：
- 首先解码 32 个棋子的位置
- 识别位置冲突（棋子与国王位置相同）
- 根据冲突类型恢复被吃棋子、王车易位或吃过路兵信息
- 解码升变序列，恢复兵的实际升变状态
性能考量与限制
优势
- 确定性编码：无需概率模型或训练数据
- 快速编解码：仅涉及位操作和简单算术
- 完全可逆：无信息损失，完美重建原始状态
- 兼容性强：适用于所有合法可达的棋盘位置
限制
- 仅限合法位置：不能编码任意棋盘配置（如多个国王）
- 升变数量限制：最多支持 4 个升变棋子（每方），超过需要特殊处理
- 依赖游戏规则：编码假设标准国际象棋规则
实际应用场景
- 在线对弈平台：减少棋局传输带宽，提升实时性
- 棋局数据库：压缩存储数百万棋局，降低存储成本
- 分布式分析：高效序列化棋盘状态，便于并行计算
- 移动端应用：减少内存占用，提升响应速度
扩展与优化方向
1. 游戏序列压缩
如 Hacker News 讨论中提到的，存储整个游戏序列可能比存储单个位置更高效。每个回合的着法可以用 1 字节编码（少于 255 种可能着法），结合 Huffman 编码可进一步压缩。
2. 增量更新
对于连续的位置变化，可以只编码差异部分（delta encoding），大幅减少传输数据量。
3. 概率模型增强
结合棋局统计信息，为常见着法分配更短的编码，实现基于上下文的压缩。
4. 硬件加速
利用现代 CPU 的位操作指令（如 POPCNT、BMI2）加速编解码过程。
结语
26 字节的国际象棋位置编码展示了约束优化与组合数学在数据压缩中的强大力量。通过深入理解问题域的特有约束，我们可以设计出远超通用压缩算法的专用编码方案。
这一技术不仅适用于国际象棋，其核心思想 —— 利用领域特定约束消除冗余信息 —— 可以推广到其他游戏状态编码、配置存储乃至通用数据结构优化中。在数据密集型应用日益普及的今天，这类精妙的编码技术为系统性能优化提供了宝贵思路。
资料来源：Ezzeri Esa 的《How to store a chess position in 26 bytes using bit-level magic》及相关 Hacker News 讨论。