我开发了一个国际象棋引擎，大约在 3300 Elo 下棋。我需要处理和调整我用我的引擎生成的一组位置。为此，在我的 RAM 中存储大约超过 1B 个位置将是理想的。我试图找出存储纯位置国际象棋数据的最有效方法。

castling、en passant 等信息可以忽略不计。

想法

幼稚的方法是使用位板，这将需要恰好 12 个位板（每块），最终会以12*8=96 byte.
或者，我只能使用 8 个位板，其中 6 个用于不同的部件，2 个用于不同的颜色=64 byte。
从理论上讲，我可以使用上面的方法摆脱 7 个位板。我不需要 2 个用于颜色的位板。只要有白色的就足够了，我可以很容易地断定一件是白色还是黑色。= 56 byte
我可以使用可以解决的位板进行进一步的压缩，48 byte但是我无法使用位板来降低压缩率。
还可以存储每一块的纯位置信息。例如，将前 6 位用于白国王，接下来的 6 位用于黑国王，接下来的 6 位用于白皇后等。请注意，这里的棋子需要 8*(6+3) 位，因为棋子可以提升到需要在 3 位内编码的其他部分。有问题的是编码没有一块。
有一些压缩技术，如霍夫曼树，但我还需要对板上的部分进行一些快速计算。

那么存储国际象棋位置的最快/最佳压缩技术是什么？

问候芬恩

标签： compressionchess

霍夫曼代码在这里工作得很好，而且它们可能比你想象的要快。

每个方块由可变数量的位表示。第一位为空 (0)，或被占用 (1)。如果为 0，则下一位用于下一个方块。如果为 1，则下一位是白色 (0) 或黑色 (1)。接下来的一到四位是棋子的类型：卒 (0)、马 (100)、象 (101)、车 (110)、后 (1110)、国王 (1111)。

这平均用 16.9 个字节对一块板进行编码。（运行超过一百万场比赛。）一个完整的棋盘代码，最大为 20.5 字节。

使用表查找可以非常快速地完成解码。最长的代码是六位。获取接下来的 6 位并在 64 条目表中查找。表中的每一项都是方格的内容（例如黑主教、白国王、空），以及代码中的位数（1..6）。丢弃那么多位，获取更多位来填充剩下的六位，然后重复。

您可以使用它转换为简单的 64 字节表示以进行快速操作，并且如果需要，可以将结果快速转换回压缩形式。

如果需要，可以剃掉更多。将空或占用表示为八列（文件），每列八位。霍夫曼对这些八位符号进行编码。它们平均可以编码为 6.6 位，将 16.9 字节减少到 15.5 字节。

代替文件的一个代码，您可以用四个文件代码削减另外 2.2 个字节：一个用于 a/h，一个用于 b/g，一个用于 c/f，一个用于 d/e。这使平均值降至 13.3 字节。

compression - 棋位压缩