压缩棋位
Compression of chess position
我开发了一个大约 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 位用于白皇后等。
请注意，这里的 pawn 需要 8*(6+3) 位，因为 pawns 可以提升为其他需要在 3 位内编码的部分。有问题的是编码缺少一块。
- 有一些压缩技术，如霍夫曼树，但我还需要对棋盘上的棋子进行一些快速计算。
那么 fastest/best 存储国际象棋位置的压缩技术是什么？
您好
芬恩
哈夫曼码在这里工作得很好，而且它们可能比您想象的要快。
每个方块由可变位数表示。第一位为空 (0)，或已占用 (1)。如果为 0，则下一位用于下一个方块。如果为 1，则下一位为白色 (0) 或黑色 (1)。接下来的一到四位是棋子的类型：兵（0）、马（100）、象（101）、车（110）、王（1110）、王（1111）。
平均用16.9字节编码一块板子。 （运行超过一百万场比赛。）一个完整的棋盘代码最大为20.5字节。
通过 table 查找可以非常快速地完成解码。最长的代码是六位。抓住接下来的六位并在 64 条目 table 中查找。 table 中的每个条目都是正方形的内容（例如黑主教、白王、空），以及代码中的位数 (1..6)。删除那么多位，获取更多位来填充剩下的六位，然后重复。
您可以使用它来转换为简单的 64 字节表示以进行快速操作，如果需要，结果可以快速转换回压缩形式。
如果需要，可以剃掉更多。将空或占用表示为八列（文件），每列为八位。霍夫曼编码那些八位符号。它们平均可以编码为 6.6 位，将 16.9 字节减少到 15.5 字节。
您可以用文件的四个代码再减少 2.2 个字节，而不是文件的一个代码：一个用于 a/h，一个用于 b/g，一个用于 c/f ，还有一个用于 d/e。这使平均值下降到 13.3 字节。
我开发了一个大约 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 位用于白皇后等。 请注意，这里的 pawn 需要 8*(6+3) 位，因为 pawns 可以提升为其他需要在 3 位内编码的部分。有问题的是编码缺少一块。
- 有一些压缩技术，如霍夫曼树，但我还需要对棋盘上的棋子进行一些快速计算。
那么 fastest/best 存储国际象棋位置的压缩技术是什么？
您好 芬恩
哈夫曼码在这里工作得很好，而且它们可能比您想象的要快。
每个方块由可变位数表示。第一位为空 (0)，或已占用 (1)。如果为 0，则下一位用于下一个方块。如果为 1，则下一位为白色 (0) 或黑色 (1)。接下来的一到四位是棋子的类型：兵（0）、马（100）、象（101）、车（110）、王（1110）、王（1111）。
平均用16.9字节编码一块板子。 （运行超过一百万场比赛。）一个完整的棋盘代码最大为20.5字节。
通过 table 查找可以非常快速地完成解码。最长的代码是六位。抓住接下来的六位并在 64 条目 table 中查找。 table 中的每个条目都是正方形的内容（例如黑主教、白王、空），以及代码中的位数 (1..6)。删除那么多位，获取更多位来填充剩下的六位，然后重复。
您可以使用它来转换为简单的 64 字节表示以进行快速操作，如果需要，结果可以快速转换回压缩形式。
如果需要，可以剃掉更多。将空或占用表示为八列（文件），每列为八位。霍夫曼编码那些八位符号。它们平均可以编码为 6.6 位，将 16.9 字节减少到 15.5 字节。
您可以用文件的四个代码再减少 2.2 个字节，而不是文件的一个代码：一个用于 a/h，一个用于 b/g，一个用于 c/f ，还有一个用于 d/e。这使平均值下降到 13.3 字节。