如何将含全部棋子的国际象棋状态编码至18字节以内？

我希望最小化存储包含全部棋子的国际象棋状态所需的字节数，目前我通过组合数编码白王及其他棋子的可能位置，需要约18字节来存储完整棋盘，具体实现代码如下：

BigInteger big1 = ZERO;
BigInteger small1 = ONE;


big1 = big1.add(small1.multiply(tn.binomialCache(64,1, cache).subtract(ONE))); // White K
small1 = small1.multiply(tn.binomialCache(64,1, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(63,1, cache).subtract(ONE))); // White Q
small1 = small1.multiply(tn.binomialCache(63,1, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(62,1, cache).subtract(ONE))); // Black K
small1 = small1.multiply(tn.binomialCache(62,1, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(61,1, cache).subtract(ONE))); // Black Q
small1 = small1.multiply(tn.binomialCache(61,1, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(60,2, cache).subtract(ONE))); // White T
small1 = small1.multiply(tn.binomialCache(60,2, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(58,2, cache).subtract(ONE))); // Black T
small1 = small1.multiply(tn.binomialCache(58,2, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(56,2, cache).subtract(ONE))); // White H
small1 = small1.multiply(tn.binomialCache(56,2, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(54,2, cache).subtract(ONE))); // Black H
small1 = small1.multiply(tn.binomialCache(54,2, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(52,2, cache).subtract(ONE))); // White R
small1 = small1.multiply(tn.binomialCache(52,2, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(50,2, cache).subtract(ONE))); // Black R 
small1 = small1.multiply(tn.binomialCache(50,2, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(48,8, cache).subtract(ONE))); // White P
small1 = small1.multiply(tn.binomialCache(48,8, cache));
big1 = big1.add(small1.multiply(tn.binomialCache(40,8, cache).subtract(ONE))); // Black P

// nummber of states which a full chessboard can have
// big1 = 4634726695587809641192045982323285670400000

请问是否可以将含全部棋子的国际象棋棋盘状态编码/解码至18字节以内？

可以，不仅能压缩到18字节以内，甚至可以优化到16字节，完全满足需求。

理论依据 #

你计算出的全棋子状态总数为4634726695587809641192045982323285670400000，对其取以2为底的对数可得：
log2(4.6347×10^37) ≈ 125.5位。
1字节=8位，125.5÷8≈15.7，因此理论上最少需要16字节（128位）即可存储所有状态（15字节仅120位，不足以覆盖全部状态；16字节的无符号整数最大值为3.4×10^38，远大于你的状态数）。

优化实现思路 #

你的组合数编码逻辑是正确的，最终生成的big1就是唯一对应棋盘状态的整数编码，只需将这个整数转换为固定长度的字节数组即可：

1. 直接将big1转换为16字节的大端序数组（前面补0填充），无需额外冗余存储。
2. 解码时从16字节数组恢复BigInteger，再逆向执行编码逻辑即可还原棋盘状态。

示例代码（Java）：

// 编码：将big1压缩为16字节数组
byte[] compactState = new byte[16];
byte[] bigBytes = big1.toByteArray();
// 复制到16字节数组的末尾，前面补0
System.arraycopy(bigBytes, 0, compactState, 16 - bigBytes.length, bigBytes.length);

// 解码：从16字节数组恢复BigInteger
BigInteger decodedState = new BigInteger(1, compactState);

额外优化空间 #

如果只考虑合法的国际象棋全棋子状态（比如王不能互相攻击、兵不能在底线等），状态总数会进一步减少，甚至可以尝试压缩到15字节，但即使不做合法性过滤，16字节已经能满足你的需求，且实现简单可靠。

内容的提问来源于stack exchange，提问作者TTho Einthausend