压缩棋局

Question

我开发了一个国际象棋引擎，其运行速度约为 3300 Elo。 我需要处理和调整我用引擎生成的一组位置。 为此，最好在 RAM 中存储大约 1B 以上的位置。 我正在尝试找出存储纯位置象棋数据的最有效方法。

易位、过路等信息可以忽略。

想法

---

1. 天真的方法是使用位板，这需要 12 个位板(每 block ) 最终结果为 12*8=96 字节。
2. 或者，我只能使用 8 个位板，其中 6 个用于不同的部分，另外 2 个用于不同的颜色 =64 字节。
3. 理论上，我可以使用上述方法使用 7 个位板。我不需要 2 个位板来处理颜色。只要有白色的就足够了，我可以很容易地判断一件作品是白色还是黑色。 = 56 字节
4. 我可以使用位板进一步压缩，这将在 48 字节 中解析，但我无法使用位板低于该值。
5. 人们还可以存储每件作品的纯位置信息。例如使用前 6 位表示白王，接下来的 6 位表示黑王，接下来的 6 位表示白后，依此类推。 请注意，这里的 pawn 需要 8*(6+3) 位，因为 pawn 可能会升级为需要在 3 位内编码的其他棋子。问题在于编码缺少一 block 。
6. 有一些压缩技术，例如霍夫曼树，但我还需要对棋盘上的棋子进行一些快速计算。

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

问候 芬恩

Answer 1

霍夫曼代码在这里运行良好，而且它们可能比您想象的要快。

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

这对一 block 板的编码平均为 16.9 字节。 (运行超过一百万个游戏。)完整的棋盘代码最大为 20.5 字节。

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

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

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

您可以使用四个文件代码来节省另外 2.2 个字节，而不是使用一个文件代码:一个用于 a/h，一个用于 b/g，一个用于 c/f，一个用于 d/e。这使得平均值下降到 13.3 字节。