严格来说不是一个问题，更像是一个谜......
多年来，我参与了一些新员工的技术面试。除了问标准的“你知道 X 技术吗”问题之外，我还试图了解他们如何处理问题。通常，我会在面试前一天通过电子邮件将问题发送给他们，并期望他们在第二天提出解决方案。
通常结果会非常有趣——错误但有趣——如果他们能解释为什么他们采取特定方法，他们仍然会得到我的推荐。
所以我想我会向 Stack Overflow 的观众提出我的一个问题。
问题：您能想到的对国际象棋游戏（或其子集）状态进行编码的最节省空间的方式是什么？也就是说，给定一个棋盘，棋子是合法排列的，对这个初始状态和玩家在游戏中采取的所有后续合法移动进行编码。
答案不需要代码，只需描述您将使用的算法。
编辑：正如其中一位海报指出的那样，我没有考虑移动之间的时间间隔。也可以随意将其作为可选的额外内容:)
EDIT2：只是为了进一步澄清......请记住，编码器/解码器是规则感知的。唯一真正需要存储的是玩家的选择 - 可以假设编码器/解码器知道其他任何内容。
EDIT3：在这里很难选出赢家:) 很多很棒的答案！
更新：我非常喜欢这个主题，我写了Programming Puzzles, Chess Positions 和 Huffman Coding。如果您通读本文，我已经确定存储完整游戏状态的唯一方法是存储完整的移动列表。请继续阅读以了解原因。因此，我使用问题的略微简化版本来进行拼图布局。
此图说明了国际象棋的起始位置。国际象棋发生在一个 8x8 棋盘上，每个玩家从一组相同的 16 个棋子开始，包括 8 个棋子、2 个车、2 个马、2 个象、1 个皇后和 1 个国王，如下所示：
位置通常记录为列的字母，后跟行的数字，因此白方的皇后在 d1。移动通常以代数符号存储，这是明确的，通常只指定必要的最少信息。考虑这个开口：
翻译为：
董事会看起来像这样：
任何程序员的一项重要能力是能够正确且明确地指定问题。
那么有什么遗漏或模棱两可的呢？事实证明很多。
您需要确定的第一件事是存储游戏的状态还是棋盘上棋子的位置。简单地编码棋子的位置是一回事，但问题是“所有后续的合法动作”。这个问题也没有说明知道到目前为止的动作。正如我将解释的那样，这实际上是一个问题。
比赛进行如下：
该板如下所示：
白有易位的选择。对此的部分要求是国王和相关的车永远不会移动，因此需要存储国王或双方的任何一个车是否移动。显然，如果他们不在他们的起始位置，他们已经移动，否则需要指定。
有几种策略可用于处理此问题。
首先，我们可以存储额外的 6 位信息（每个 rook 和 king 1 个）来指示该棋子是否已经移动。如果正确的部分恰好在其中，我们可以通过只为这六个正方形之一存储一点来简化这一点。或者，我们可以将每个未移动的棋子视为另一种棋子类型，而不是每边的 6 个棋子类型（棋子、车、马、主教、皇后和国王）有 8 个（添加未移动的车和未移动的国王）。
国际象棋中另一个特殊且经常被忽视的规则是En Passant。
比赛进行了。
黑方在 b4 上的兵现在可以选择将他在 b4 上的兵移动到 c3 上，然后将白方在 c4 上的兵。这仅在第一次机会时发生，这意味着如果黑方现在放弃该选项，他将无法采取下一步行动。所以我们需要存储它。
如果我们知道上一步，我们肯定可以回答 En Passant 是否可行。或者，我们可以存储其第 4 级的每个棋子是否刚刚移动到那里并向前移动。或者我们可以查看棋盘上每个可能的 En Passant 位置，并有一个标志来指示它是否可能。
这是白棋的一步。如果白方将他的棋子从 h7 移到 h8，它可以升级为任何其他棋子（但不能升级为国王）。99% 的情况下它会被提升为女王，但有时不会，通常是因为这可能会迫使您陷入僵局，否则您会获胜。这写成：
这在我们的问题中很重要，因为这意味着我们不能指望每边都有固定数量的棋子。如果所有 8 个棋子都得到提升，那么一方完全有可能（但极不可能）最终得到 9 个皇后、10 个车、10 个象或 10 个骑士。
当处于你无法取胜的位置时，你最好的策略是尝试相持。最可能的变体是您无法进行合法的移动（通常是因为在控制您的国王时任何移动）。在这种情况下，您可以要求平局。这个很容易满足。
第二种变体是三重重复。如果相同的棋盘位置在一场比赛中出现了 3 次（或将在下一步出现第 3 次），则可以主张平局。这些位置不需要以任何特定的顺序出现（这意味着它不必重复三次相同的移动顺序）。这使问题变得非常复杂，因为您必须记住以前的每一个棋盘位置。如果这是问题的要求，则问题的唯一可能解决方案是存储以前的每一步。
最后，还有五十步规则。如果在前 50 次连续移动中没有棋子移动并且没有棋子被拿走，玩家可以声称平局，因此我们需要存储自从棋子被移动或拿走棋子以来的移动数（两者中的最新一次。这需要6 位 (0-63)。
当然，我们还需要知道轮到谁了，这只是一点点信息。
由于僵局的情况，存储游戏状态的唯一可行或明智的方法是存储导致该位置的所有移动。我会解决这个问题。棋盘状态问题将简化为：存储棋盘上所有棋子的当前位置，忽略易位、过路、相持条件以及轮到谁。
棋子布局可以通过以下两种方式之一进行广泛处理：通过存储每个方格的内容或通过存储每个棋子的位置。
有六种棋子类型（棋子、车、马、主教、皇后和国王）。每个棋子可以是白色或黑色，因此一个正方形可能包含 12 个可能的棋子之一，或者它可能是空的，因此有 13 种可能性。13可以存储4位（0-15）所以最简单的解决方案是每个平方存储4位乘以64个平方或256位信息。
这种方法的优点是操作非常容易和快速。这甚至可以通过在不增加存储要求的情况下增加 3 种可能性来扩展：在最后一回合移动了 2 个空格的棋子、没有移动的国王和没有移动的车，这将满足很多需求前面提到的问题。
但我们可以做得更好。
Base 13 编码
将董事会职位视为一个非常大的数字通常会有所帮助。这通常在计算机科学中完成。例如，停机问题（正确地）将计算机程序视为一个大数。
第一个解决方案将位置视为 64 位以 16 为基数的数字，但正如所证明的那样，此信息中存在冗余（每个“数字”有 3 个未使用的可能性），因此我们可以将数字空间减少到 64 个以 13 为基数的数字。当然，这不能像 base 16 那样高效，但它会节省存储需求（并且最小化存储空间是我们的目标）。
以 10 为底，数字 234 等价于 2 x 10 2 + 3 x 10 1 + 4 x 10 0。
在基数 16 中，数字 0xA50 等价于 10 x 16 2 + 5 x 16 1 + 0 x 16 0 = 2640（十进制）。
所以我们可以将我们的位置编码为 p 0 x 13 63 + p 1 x 13 62 + ... + p 63 x 13 0其中 p i代表正方形i的内容。
2 256大约等于 1.16e77。13 64大约等于 1.96e71，需要 237 位存储空间。仅节省 7.5% 的代价就是显着增加了操作成本。
在法律板上，某些棋子不能出现在某些方格中。例如，棋子不能出现在第一排或第八排，从而将这些方格的可能性减少到 11。这将可能的棋盘减少到 11 16 x 13 48 = 1.35e70（大约），需要 233 位存储空间。
实际上，在十进制（或二进制）之间编码和解码这些值有点复杂，但它可以可靠地完成，并留给读者作为练习。
前两种方法都可以描述为定宽字母编码。字母表的 11、13 或 16 个成员中的每一个都替换为另一个值。每个“字符”的宽度相同，但是当您考虑每个字符的可能性不相等时，效率可以提高。
考虑摩尔斯电码（如上图所示）。消息中的字符被编码为一系列破折号和点。这些破折号和圆点通过无线电传输（通常），它们之间有一个暂停来分隔它们。
请注意字母 E（英语中最常见的字母）是一个单点，是可能的最短序列，而 Z（最不常见）是两个破折号和两个哔哔声。
这种方案可以显着减小预期消息的大小，但代价是增加了随机字符序列的大小。
应该注意的是，摩尔斯电码还有另一个内置功能：破折号长达三个点，因此在创建上述代码时考虑到这一点，以尽量减少破折号的使用。由于 1 和 0（我们的构建块）没有这个问题，所以我们不需要复制它。
最后，摩尔斯电码中有两种休止符。短休止符（点的长度）用于区分点和破折号。较长的间隙（破折号的长度）用于分隔字符。
那么这如何适用于我们的问题呢？
有一种处理可变长度代码的算法称为霍夫曼编码。霍夫曼编码创建可变长度代码替换，通常使用符号的预期频率来为更常见的符号分配较短的值。
在上面的树中，字母 E 被编码为 000（或 left-left-left），S 为 1011。应该清楚的是，这种编码方案是明确的。
这是与摩尔斯电码的一个重要区别。摩尔斯电码具有字符分隔符，因此它可以进行其他不明确的替换（例如，4 个点可以是 H 或 2 个 Is），但我们只有 1 和 0，因此我们选择了明确的替换。
下面是一个简单的实现：
private static class Node {
private final Node left;
private final Node right;
private final String label;
private final int weight;
private Node(String label, int weight) {
this.left = null;
this.right = null;
this.label = label;
this.weight = weight;
}
public Node(Node left, Node right) {
this.left = left;
this.right = right;
label = "";
weight = left.weight + right.weight;
}
public boolean isLeaf() { return left == null && right == null; }
public Node getLeft() { return left; }
public Node getRight() { return right; }
public String getLabel() { return label; }
public int getWeight() { return weight; }
}
使用静态数据：
private final static List<string> COLOURS;
private final static Map<string, integer> WEIGHTS;
static {
List<string> list = new ArrayList<string>();
list.add("White");
list.add("Black");
COLOURS = Collections.unmodifiableList(list);
Map<string, integer> map = new HashMap<string, integer>();
for (String colour : COLOURS) {
map.put(colour + " " + "King", 1);
map.put(colour + " " + "Queen";, 1);
map.put(colour + " " + "Rook", 2);
map.put(colour + " " + "Knight", 2);
map.put(colour + " " + "Bishop";, 2);
map.put(colour + " " + "Pawn", 8);
}
map.put("Empty", 32);
WEIGHTS = Collections.unmodifiableMap(map);
}
和：
private static class WeightComparator implements Comparator<node> {
@Override
public int compare(Node o1, Node o2) {
if (o1.getWeight() == o2.getWeight()) {
return 0;
} else {
return o1.getWeight() < o2.getWeight() ? -1 : 1;
}
}
}
private static class PathComparator implements Comparator<string> {
@Override
public int compare(String o1, String o2) {
if (o1 == null) {
return o2 == null ? 0 : -1;
} else if (o2 == null) {
return 1;
} else {
int length1 = o1.length();
int length2 = o2.length();
if (length1 == length2) {
return o1.compareTo(o2);
} else {
return length1 < length2 ? -1 : 1;
}
}
}
}
public static void main(String args[]) {
PriorityQueue<node> queue = new PriorityQueue<node>(WEIGHTS.size(),
new WeightComparator());
for (Map.Entry<string, integer> entry : WEIGHTS.entrySet()) {
queue.add(new Node(entry.getKey(), entry.getValue()));
}
while (queue.size() > 1) {
Node first = queue.poll();
Node second = queue.poll();
queue.add(new Node(first, second));
}
Map<string, node> nodes = new TreeMap<string, node>(new PathComparator());
addLeaves(nodes, queue.peek(), "");
for (Map.Entry<string, node> entry : nodes.entrySet()) {
System.out.printf("%s %s%n", entry.getKey(), entry.getValue().getLabel());
}
}
public static void addLeaves(Map<string, node> nodes, Node node, String prefix) {
if (node != null) {
addLeaves(nodes, node.getLeft(), prefix + "0");
addLeaves(nodes, node.getRight(), prefix + "1");
if (node.isLeaf()) {
nodes.put(prefix, node);
}
}
}
一种可能的输出是：
White Black
Empty 0
Pawn 110 100
Rook 11111 11110
Knight 10110 10101
Bishop 10100 11100
Queen 111010 111011
King 101110 101111
对于起始位置，这等于 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 位。
另一种可能的方法是将第一种方法与霍夫曼编码相结合。这是基于这样的假设，即大多数预期的棋盘（而不是随机生成的棋盘）更有可能（至少部分地）类似于起始位置。
因此，您要做的是将 256 位当前板位置与 256 位起始位置进行异或，然后对其进行编码（使用 Huffman 编码，或者说，某种运行长度编码方法）。显然，这将非常有效（64 个 0 可能对应于 64 位），但随着游戏的进行需要增加存储空间。
如前所述，解决此问题的另一种方法是存储玩家拥有的每个棋子的位置。这特别适用于大多数方格为空的残局位置（但在霍夫曼编码方法中，空方格无论如何只使用 1 位）。
每一方都有一个国王和0-15个其他棋子。由于促销，这些部分的确切组成可能会发生很大变化，以至于您不能假设基于起始位置的数字是最大值。
划分它的逻辑方法是存储一个由两条边（白色和黑色）组成的位置。每一方都有：
至于棋子的位置，棋子只能在 48 个可能的方格上（而不是像其他方格一样的 64 个）。因此，最好不要浪费每个 pawn 使用 6 位会使用的额外 16 个值。因此，如果您有 8 个棋子，则有 48 8个可能性，等于 28,179,280,429,056。您需要 45 位来编码那么多值。
这是每边 105 位或总共 210 位。然而，对于这种方法来说，起始位置是最坏的情况，当你移除碎片时它会变得更好。
需要指出的是，少于 48 的可能性有8个，因为棋子不可能都在同一个方格中。第一个有 48 个可能性，第二个有 47 个，依此类推。48 x 47 x … x 41 = 1.52e13 = 44 位存储。
您可以通过消除其他棋子（包括另一边）占据的方格来进一步改善这一点，这样您就可以先放置白色非棋子，然后放置黑色非棋子，然后放置白色棋子，最后放置黑色棋子。在起始位置，这将白色的存储要求降低到 44 位，黑色的存储要求降低到 42 位。
另一种可能的优化是这些方法中的每一种都有其优点和缺点。比如说，你可以选择最好的 4 个，然后在前两位编码一个方案选择器，然后再编码方案特定的存储。
由于开销很小，这将是迄今为止最好的方法。
我回到存储游戏而不是位置的问题。由于三重重复，我们必须存储到目前为止发生的移动列表。
您必须确定的一件事是您只是存储移动列表还是注释游戏？国际象棋游戏经常被注释，例如：
白棋以两个感叹号标记为绝妙，而黑棋则被视为错误。请参阅国际象棋标点符号。
此外，您可能还需要在描述移动时存储自由文本。
我假设这些动作已经足够了，所以不会有注释。
我们可以简单地将移动的文本存储在这里（“e4”、“Bxb5”等）。包括一个终止字节，每次移动大约需要 6 个字节（48 位）（最坏情况）。这不是特别有效。
要尝试的第二件事是存储起始位置（6 位）和结束位置（6 位），因此每次移动 12 位。那要好得多。
或者，我们可以以可预测和确定的方式确定当前位置的所有合法移动，并说明我们选择的状态。然后回到上面提到的可变基编码。白方和黑方在他们的第一步中各有 20 种可能的步法，第二步则更多，以此类推。
这个问题没有绝对正确的答案。有许多可能的方法，以上只是其中的一小部分。
我喜欢这个问题和类似问题的地方在于，它需要对任何程序员都很重要的能力，比如考虑使用模式、准确确定需求和考虑极端情况。
国际象棋位置作为国际象棋位置训练器的屏幕截图。
最好以人类可读的标准格式存储国际象棋游戏。
Portable Game Notation假定一个标准的起始位置（尽管它不是必须的），并且只是逐个列出动作。一种紧凑的、人类可读的标准格式。
例如
[Event "F/S Return Match"]
[Site "Belgrade, Serbia Yugoslavia|JUG"]
[Date "1992.11.04"]
[Round "29"]
[White "Fischer, Robert J."]
[Black "Spassky, Boris V."]
[Result "1/2-1/2"]
1. e4 e5 2. Nf3 Nc6 3. Bb5 {This opening is called the Ruy Lopez.} 3... a6
4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8 10. d4 Nbd7
11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5
Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6
23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5
hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5
35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6
Nf2 42. g4 Bd3 43. Re6 1/2-1/2
如果你想让它更小，那就把它拉上拉链。任务完成！
大拼图！
我看到大多数人都在存储每一块的位置。采用更简单的方法，并存储每个方格的内容如何？这会自动处理促销和捕获的作品。
它允许霍夫曼编码。实际上，棋盘上棋子的初始频率几乎是完美的：一半的方格是空的，剩下的一半方格是棋子，等等。
考虑到每篇文章的频率，我在纸上构建了一棵霍夫曼树，这里不再赘述。结果，其中c代表颜色（白色 = 0，黑色 = 1）：
对于初始状态下的整个董事会，我们有
总计：初始板状态为164 位。明显少于当前最高投票答案的 235 位。而且它只会随着游戏的进行而变得更小（升级后除外）。
我只看棋子在棋盘上的位置；额外的状态（谁的回合，谁已经城堡，过路，重复动作等）必须单独编码。也许最多还有 16 位，因此整个游戏状态为180 位。可能的优化：
c位的额外符号进行编码，然后可以从主教所在的方格中推断出。（提升为主教的棋子破坏了这个计划......）位置- 18 字节
合法位置的估计数量为10 43
只需将它们全部枚举出来，位置就可以存储在 143 位中。需要多 1 位来指示接下来要播放哪一方
枚举当然不实用，但这表明至少需要 144 位。
Moves - 1 字节
每个位置通常有大约 30-40 个合法移动，但数量可能高达 218 让我们列举每个位置的所有合法移动。现在每一步都可以编码成一个字节。
我们仍然有足够的空间让特殊动作，例如 0xFF 来代表辞职。
昨晚我看到了这个问题，这让我很感兴趣，所以我坐在床上思考解决方案。我的最终答案实际上与 int3 非常相似。
假设一个标准的国际象棋游戏并且你不编码规则（就像白总是先走），那么你可以通过只编码每个棋子的移动来节省很多。
总共有 32 个棋子，但每次移动你都知道什么颜色在移动，所以只有 16 个方格需要担心，即本回合移动哪一个棋子需要4 位。
每件作品只有一个有限的移动集，你可以以某种方式列举出来。
对于促销，有 4 个棋子可供选择（Rook、Bishop、Knight、Queen），因此我们将添加2 个位来指定。我认为所有其他规则都会自动涵盖（例如，通过者）。
首先，在一种颜色捕获 8 块后，可以将块编码减少到 3 位，然后 2 位为 4 块，依此类推。
不过，主要的优化是仅枚举游戏中每个点的可能动作。假设我们将 Pawn 的移动{00, 01, 10, 11}分别存储为向前 1 步、向前 2 步、对角线左和对角线右。如果某些动作是不可能的，我们可以将它们从本回合的编码中删除。
我们知道每个阶段的游戏状态（从跟随所有的移动），所以在读取了哪个棋子将移动之后，我们总是可以确定我们需要读取多少位。如果我们意识到一个棋子此时的唯一移动是对角向右捕获或向前移动一个，我们知道只读取 1 位。
简而言之，上面列出的每件的位存储只是最大值。几乎每一步都会有更少的选择，通常也会更少。
在每个位置获取所有可能移动的数量。
下一步动作生成为
index_current_move =n % num_of_moves //this is best space efficiency
n=n/num_of_moves
可证明是存储随机生成游戏的最佳空间效率，平均需要大约 5 位/移动，因为您有 30-40 个可能的移动。组装存储只是以相反的顺序生成 n 。
由于大量冗余，存储位置更难破解。（一个站点最多可以有 9 个皇后在棋盘上，但在这种情况下，没有棋子，如果棋盘上的象在相反颜色的方格上），但通常就像在剩余方格上存储相同棋子的组合。）
编辑：
保存招式的要点是只存储招式的索引。我们应该只添加从确定性 movegenerator(position) 生成的移动索引，而不是存储 Kc1-c2 并尝试减少此信息
在每一步我们添加大小信息
num_of_moves = get_number_of_possible_moves(postion) ;
在池中，这个数字不能减少
生成信息池是
n=n*num_of_moves+ index_current_move
额外的
如果最终位置只有一个可用的移动，则保存为先前完成的强制移动的数量。示例：如果起始位置每边有 1 次强制移动（2 次移动），并且我们想将其保存为一个移动游戏，则将 1 存储在池 n 中。
存储到信息池的示例
假设我们已经知道起始位置并且我们做了 3 次移动。
第一步有 5 个可用步数，我们采用步数索引 4。在第二步中，有 6 个可用步数，我们采用位置索引 3，而在第三步中，该方有 7 个步数可用，他选择了步数索引2.
向量形式；索引=[4,3,2] n_moves=[5,6,7]
我们正在向后编码此信息，因此 n= 4+5*(3+6*(2))=79 （不需要乘以 7）
如何解开这个？首先我们有位置，我们发现有 5 个动作可用。所以
index=79%5=4
n=79/5=15; //no remainder
我们采用移动索引 4 并再次检查位置，从这一点我们发现有 6 种可能的移动。
index=15%6=3
n=15/6=2
我们采用移动索引 3，它使我们到达一个有 7 个可能移动的位置。
index=2%7=2
n=2/7=0
我们执行最后一步索引 2 并到达最终位置。
如您所见，时间复杂度为 O(n)，空间复杂度为 O(n)。编辑：时间复杂度实际上是 O(n^2)，因为你乘以的数字会增加，但是存储多达 10,000 个动作的游戏应该没有问题。
储蓄头寸
可以做到接近最优。
当我们了解信息和存储信息时，让我再谈一谈。一般的想法是减少冗余（我稍后会谈到）。让我们假设没有升职，也没有接受，所以每边有 8 个棋子、2 个车、2 个骑士、2 个主教、1 个国王和 1 个皇后。
我们需要保存什么： 1. 每个和平的位置 2. 易位的可能性 3. 过路人的可能性 4. 有移动可用的一方
让我们假设每一块都可以放在任何地方，但不能两块放在同一个地方。8个相同颜色的棋子可以排列在板上的方式数是C（64/8）（二项式），即32位，然后2个车2R-> C（56/2），2B-> C（54/2） , 2N->C(52/2), 1Q->C(50/1), 1K -> C(49/1) 和其他站点相同，但从 8P -> C(48/8) 等开始.
将这两个站点的数字相乘得到我们的数字 4634726695587809641192045982323285670400000 大约 142 位，我们必须为一个可能的过路人加 8（过路兵可以在 8 个地方之一），16（4 位）用于易位限制和一位已移动的网站。我们最终得到 142+3+4+1= 150bits
但是现在让我们继续在 32 块棋盘上寻找冗余，并且不带走。
黑白棋子都在同一列并且彼此面对。每个棋子都面对另一个棋子，这意味着白棋子最多可以排在第 6 位。这给我们带来了 8*C(6/2) 而不是 C(64/8)*C(48/8) ，它将信息减少了 56 位。
易位的可能性也是多余的。如果车不在起始位置，则该车没有易位可能性。所以我们可以想象在船上添加 4 个方格来获取额外的信息，如果可以用这辆小车进行易位并移除 4 个易位位。因此，我们有 C(58/2)*C(42/2) 而不是 C(56/2)*C(40/2)*16 并且我们丢失了 3.76 位（几乎全部 4 位）
en-passant：当我们存储 8 个 en passant 可能性之一时，我们知道黑兵的位置并减少信息冗余（如果它是白棋并且有 3th pawn en-passant，这意味着黑兵在 c5 上，而白兵在 c5 上） c2,c3 或 c4) 如此插入 C(6/2) 我们有 3 并且我们丢失了 2.3 位。如果我们在可以完成的一侧（3 种可能性-> 左，右，两者）存储白色的过路数，我们会减少一些冗余，并且我们知道可以采取过路的典当的位置。（例如，从 c5 上的前一个示例中的白色黑色可以在左侧，右侧或两者中。如果它在一个站点上，我们有 2*3（3 个用于存储 psissibilites 和 2 个可能的移动用于第 7 或第 6 级的黑色典当) 由 C(6/2) 插入，我们减少 1.3 位，如果两边都减少 4.2 位。这样我们可以减少 2.3+1.3=3。
bishops：bisops只能在opostite squares上，这将每个站点的冗余减少1位。
如果我们总结我们需要 150-56-4-3.6-2= 85bits 来存储国际象棋位置，如果没有收入
如果考虑到收入和晋升，可能不会更多（但如果有人会发现这篇长帖子有用，我稍后会写这个）
对于人类玩的典型游戏，而不是最坏的情况，优化平均情况大小会增加兴趣。（问题陈述没有说明是哪一个；大多数回答都假设最坏的情况。）
对于移动序列，有一个好的国际象棋引擎从每个位置生成移动；它将生成一个 k 可能移动的列表，按其质量排名排序。人们通常比随机动作更频繁地选择好的动作，因此我们需要学习从列表中的每个位置到人们选择“好”动作的概率的映射。使用这些概率（基于来自一些互联网国际象棋数据库的游戏语料库），用算术编码对移动进行编码。（解码器必须使用相同的国际象棋引擎和映射。）
对于起始位置，ralu 的方法会奏效。如果我们有某种方法可以通过概率对选择进行加权，我们也可以在那里用算术编码来改进它——例如，棋子经常出现在相互保护的配置中，而不是随机出现。很难找到一种简单的方法来整合这些知识。一个想法：转而使用上述移动编码，从标准开局位置开始，找到一个以所需棋盘结束的序列。（您可以尝试使用启发式距离进行 A* 搜索，该启发式距离等于棋子与其最终位置的距离之和，或类似的东西。）这会因过度指定移动顺序而导致效率低下，而因利用国际象棋而导致效率低下。知识。
如果不从实际的语料库中收集一些统计数据，也很难估计在平均情况复杂度下这将为您节省多少。但是我认为所有移动的起点都一样可能已经超过了这里的大多数建议：算术编码不需要每次移动的整数位数。
在对初始位置进行编码后，攻击对步骤进行编码的子问题。该方法是创建步骤的“链接列表”。
游戏中的每一步都被编码为“旧位置->新位置”对。你知道棋局开始时的初始位置；通过遍历步的链表，可以到达 X 移动后的状态。
对于每个步骤的编码，您需要 64 个值来编码起始位置（板上 64 个方格的 6 位 - 8x8 方格），以及结束位置的 6 位。每侧 1 次移动 16 位。
编码给定游戏所需的空间量与移动次数成正比：
10 x（白棋步数 + 黑棋步数）位。
更新：提升棋子的潜在并发症。需要能够说明典当被提升到什么 - 可能需要特殊位（将为此使用格雷码以节省空间，因为典当提升极为罕见）。
更新 2：您不必编码结束位置的完整坐标。在大多数情况下，被移动的棋子最多只能移动 X 个位置。例如，一个棋子在任何给定点最多可以有 3 个移动选项。通过实现每种棋子类型的最大移动次数，我们可以节省“目标”的编码位。
Pawn:
- 2 options for movement (e2e3 or e2e4) + 2 options for taking = 4 options to encode
- 12 options for promotions - 4 promotions (knight, biship, rook, queen) times 3 squares (because you can take a piece on the last row and promote the pawn at the same time)
- Total of 16 options, 4 bits
Knight: 8 options, 3 bits
Bishop: 4 bits
Rook: 4 bits
King: 3 bits
Queen: 5 bits
因此，每次移动黑色或白色的空间复杂度变为
6 位用于初始位置 +（基于移动物体的类型的可变位数）。
问题是给出对典型国际象棋游戏最有效的编码，还是给出最短最坏情况编码的编码？
对于后者，最有效的方法也是最不透明的：创建所有可能对的枚举（初始棋盘，合法的移动顺序），其中，重复三次重复位置和不超过-fifty-moves since last-pawn-move-or-capture 规则，是递归的。然后，这个有限序列中的位置索引给出了最短的最坏情况编码，但也给出了典型情况下同样长的编码，而且我预计计算起来非常昂贵。可能最长的国际象棋游戏应该超过 5000 步，每个玩家通常在每个位置有 20-30 步可用（尽管当剩下的棋子很少时更少）——这提供了这种编码所需的 40000 位。
如 Henk Holterman 对上述编码移动的建议所述，可以应用枚举的想法来提供更易于处理的解决方案。我的建议：不是最小的，但比我看过的上面的例子要短，并且合理易处理：
64 位表示哪些方格被占用（占用矩阵），加上每个被占用方格中有哪些棋子的列表（棋子可以有 3 位，其他棋子可以有 4 位）：这给出了 190 位作为起始位置。由于板上不能超过 32 块，占用矩阵的编码是多余的，因此可以对常见板位置之类的东西进行编码，例如 33 个设置位加上常见板列表中的板索引。
1 位说谁先行动
根据 Henk 的建议编码移动：通常每对白/黑移动 10 位，尽管当玩家没有其他移动时，有些移动将占用 0 位。
这建议使用 490 位来编码典型的 30 步游戏，并且对于典型游戏来说是一种相当有效的表示。
关于自上次典当移动或捕获规则以来的三次重复位置和不超过五十步的编码：如果您将过去的移动编码回最后的典当移动或捕获，那么您有足够的信息来决定这些规则是否适用：不需要整个游戏历史。
板上的位置可以用 7 位定义（0-63 和 1 个值指定它不再在板上）。因此，为板上的每一块指定它的位置。
32 件 * 7 位 = 224 位
编辑：正如 Cadrian 指出的那样……我们也有“提升典当到王后”的案例。我建议我们在最后添加额外的位来指示哪个棋子被提升了。
所以对于每一个被提升的pawn，我们跟随224位和5位表示已经提升的pawn的索引，如果它是列表的末尾则为11111。
所以最小的情况（没有促销）是 224 位 + 5（没有促销）。对于每个提升的棋子，添加 5 位。
编辑：正如毛茸茸的青蛙指出的那样，我们需要在最后再一点来表明轮到谁了 ;^)
大多数人一直在对棋盘状态进行编码，但关于移动本身.. 这是一个位编码描述。
每件位数：
假设所有棋子都在棋盘上，这些是每步棋的位数：典当 - 第一次走棋时 6 位棋子，随后是 5 位棋子。7 如果晋升。主教：9 位（最大），骑士：7，车：9，国王：7，皇后：11（最大）。
大多数答案都忽略了 3 次重复。不幸的是，对于 3 次重复，您必须存储到目前为止播放的所有位置...
这个问题要求我们以节省空间的方式存储，所以我们真的不需要存储位置，只要我们可以从移动列表中构建它（假设我们有标准的起始位置）。我们可以优化 PGN，我们就完成了。贝娄是一个简单的方案。
棋盘上有 64 个方格，64 = 2^6。如果我们只存储每次移动的初始和最后一个方格，这将占用 12 位（稍后会解决促销问题）。请注意，该方案已经涵盖了玩家移动、强调、捕获棋子、易位等；这些可以通过仅重播移动列表来构建。
为了提升，我们可以保留一个单独的向量数组，上面写着“在移动 N 提升到片 XYZ”。我们可以保留一个 (int, byte) 的向量。
优化 (To,From) 向量也很诱人，因为许多 (To,From) 向量在国际象棋中是不可能的。例如。不会有从 e1 到 d8 等的移动。但我想不出任何方案。任何进一步的想法都非常受欢迎。
如果计算时间不是问题，那么您可以使用确定性的可能位置生成器将唯一 ID 分配给给定位置。
首先从给定位置生成确定性庄园中的多个可能位置，例如从左下角开始移动到右上角。这决定了下一步需要多少位，在某些情况下可能只有一个。然后，当进行移动时，只存储该移动的唯一 ID。
升级和其他规则只要以确定的方式处理，就可以简单地算作有效的移动，例如，对后、对白车、对象的每一个都算作一个单独的移动。
初始位置是最难的，可能会产生大约 2.5 亿个可能的位置（我认为），这需要大约 28 位加上一个额外的位来确定它是谁的移动。
假设我们知道轮到谁了（每一轮都从白色变为黑色），确定性生成器看起来像：
for each row
for each column
add to list ( get list of possible moves( current piece, players turn) )
“获取可能移动的列表”会执行以下操作：
if current piece is not null
if current piece color is the same as the players turn
switch( current piece type )
king - return list of possible king moves( current piece )
queen - return list of possible queen moves( current piece )
rook - return list of possible rook moves( current piece )
etc.
如果国王处于检查状态，则每个“可能的 xxx 移动列表”仅返回改变检查情况的有效移动。
有 64 个可能的板位置，因此每个位置需要 6 位。有 32 个初始片段，所以到目前为止我们总共有 192 位，其中每 6 位表示给定片段的位置。我们可以预先确定碎片出现的顺序，所以我们不必说哪个是哪个。
如果一块棋子不在棋盘上怎么办？好吧，我们可以将一块与另一块放在同一位置以表明它不在棋盘上，否则那将是非法的。但我们也不知道第一块是否会出现在棋盘上。因此，我们添加 5 位来指示哪一块是第一块（32 种可能性 = 5 位来表示第一块）。然后我们可以将该位置用于后续的棋盘上的棋子。这使我们总共有 197 位。板上必须至少有一块，这样才能奏效。
然后我们需要一个位来轮到谁 - 将我们带到198 位。
典当推广呢？我们可以通过将每个棋子添加 3 位，添加 42 位来做到这一点。但是我们可以注意到，大多数时候，棋子没有被提升。
因此，对于棋盘上的每个棋子，位“0”表示它没有被提升。如果棋子不在棋盘上，那么我们根本不需要一点棋子。然后我们可以使用他有促销的可变长度位串。最常见的是女王，所以“10”可能意味着女王。那么“110”表示车，“1110”表示主教，“1111”表示骑士。
初始状态将占用 198 + 16 = 214 位，因为所有 16 个棋子都在棋盘上且未升级。一个有两个升级的典当皇后的最终游戏可能需要像 198 + 4 + 4 之类的东西，这意味着 4 个活着但没有被提升的典当和 2 个皇后典当，总共206 位。看起来很健壮！
===
正如其他人所指出的那样，霍夫曼编码将是下一步。如果你观察几百万场比赛，你会发现每一个棋子更有可能出现在某些格子上。例如，大多数时候，棋子保持在一条直线上，或者一个在左边/一个在右边。国王通常会留在本垒附近。
因此，为每个单独的位置设计一个霍夫曼编码方案。棋子可能平均只占用 3-4 位而不是 6 位。国王也应该占用少量位。
同样在此方案中，将“采取”作为可能的位置。这也可以非常有效地处理易位 - 每个 rook 和 king 将有一个额外的“原始位置，移动”状态。您也可以通过这种方式在 pawn 中编码 en passant - “原始位置，可以 en passant”。
有了足够的数据，这种方法应该会产生非常好的结果。
就像他们在书本和纸上编码游戏一样：每一件作品都有一个符号；因为这是一个“合法”的游戏，所以先走白色 - 无需单独编码白色或黑色，只需计算移动的数量即可确定谁移动了。此外，每一步都被编码为（片，结束位置），其中“结束位置”减少到允许辨别歧义的最少符号数量（可以为零）。游戏的长度决定了移动的数量。还可以在每一步对时间进行编码（自上次移动以来）。
可以通过为每个（总共 32 个）分配一个符号或通过为类分配一个符号来完成片段的编码，并使用结束位置来了解哪个片段被移动。例如，一个棋子有 6 个可能的结束位置；但平均而言，每次只有一对夫妇可用。因此，从统计上讲，按结束位置编码可能最适合这种情况。
类似的编码用于计算神经科学 (AER) 中的脉冲序列。
缺点：需要重玩整个游戏才能到达当前状态并生成一个子集，很像遍历链表。
我会尝试使用Huffman encoding。这背后的理论是——在每场国际象棋比赛中，都会有一些棋子会移动很多，而一些棋子不会移动太多或被提前淘汰。如果起始位置已经移除了一些部分 - 那就更好了。方块也是如此 - 有些方块可以看到所有动作，而有些则不会受到太多影响。
因此，我有两张 Huffman 桌子——一张用于拼块，另一张用于正方形。它们将通过查看实际游戏来生成。我可以为每对棋子设置一张大桌子，但我认为这将非常低效，因为没有多少相同棋子的实例再次在同一个正方形上移动。
每件作品都有一个分配的 ID。由于有 32 个不同的片段，因此片段 ID 只需要 5 位。棋子 ID 不会因游戏而异。方形 ID 也是如此，我需要 6 位。
霍夫曼树将通过按顺序遍历每个节点来编码（即，首先输出节点，然后从左到右输出其子节点）。对于每个节点，都会有一位指定它是叶节点还是分支节点。如果它是一个叶节点，它后面会跟着给出 ID 的位。
起始位置将简单地由一系列工件位置对给出。之后，每一步都会有一个棋子位置对。只需找到提到两次的第一个片段，您就可以找到起始位置描述符的结尾（以及移动描述符的开头）。如果一个棋子被提升，将有 2 个额外的位指定它变成什么，但棋子 ID 不会改变。
考虑到棋子在游戏开始时被提升的可能性，在霍夫曼树和数据之间也会有一个“提升表”。首先将有 4 位指定升级了多少棋子。然后对于每个 pawn，将有其霍夫曼编码的 ID 和 2 位指定它变成了什么。
哈夫曼树将通过考虑所有数据（包括起始位置和移动）和升级表来生成。虽然通常促销表是空的或只有几个条目。
用图形术语总结一下：
<Game> := <Pieces huffman tree> <squares huffman tree> <promotion table> <initial position> (<moves> | <1 bit for next move - see Added 2 below>)
<Pieces huffman tree> := <pieces entry 1> <pieces entry 2> ... <pieces entry N>
<pieces entry> := "0" | "1" <5 bits with piece ID>
<squares huffman tree> := <squares entry 1> <squares entry 2> ... <squares entry N>
<Squares entry> := "0" | "1" <6 bits with square ID>
<promotion table> := <4 bits with count of promotions> <promotion 1> <promotion 2> ... <promotion N>
<promotion> := <huffman-encoded piece ID> <2 bits with what it becomes>
<initial position> := <position entry 1> <position entry 2> ... <position entry N>
<moves> := <position entry 1> <position entry 2> ... <position entry N>
<position entry> := <huffman-encoded piece ID> <huffman-encoded squre ID> (<2 bits specifying the upgrade - optional>)
补充：这仍然可以优化。每件作品只有几个合法的动作。不是简单地对目标方块进行编码，而是可以为每个棋子的可能移动提供基于 0 的 ID。每个棋子都会重复使用相同的 ID，因此总共不会有超过 21 个不同的 ID（女王最多可以有 21 个不同的可能移动选项）。把它放在一个霍夫曼表而不是字段中。
然而，这将难以代表原始状态。一个人可能会产生一系列动作来将每一块放在它的位置上。在这种情况下，有必要以某种方式标记初始状态的结束和移动的开始。
或者，可以使用未压缩的 6 位方形 ID 来放置它们。
这是否会导致整体尺寸减小 - 我不知道。可能，但应该尝试一下。
补充2：另一种特殊情况。如果游戏状态没有移动，那么区分接下来谁移动就变得很重要。为此在最后添加一位。:)
我已经考虑了很长时间（+ - 2小时）。而且没有明显的答案。
假设：
...所以它是最新的现代规则。首先不管重复和移动重复限制。
-C 25 字节四舍五入（64b+32*4b+5b=325b）
=64 位（有/无）+32*4 位 [ 1bit=color{black/withe} +3bit=棋子类型{King,Queen,Bishop,kNight,Rook,Pawn,MovedPawn} 注意：移动的棋子...例如，如果它是前一回合中最后移动的棋子，则表明“过路人”是可行的。] +5bit 表示实际状态（轮到谁，过路人，两边是否有可能出现问题）
到目前为止，一切都很好。可能可以增强，但会考虑到可变长度和提升！？
现在，以下规则仅适用于玩家申请平局时，这不是自动的！因此，如果没有玩家要求平局，那么考虑这 90 步没有捕获或棋子的移动是可行的！这意味着所有的动作都需要被记录……并且可用。
-D 重复位置...例如上面提到的棋盘状态（见 C）与否...（见下文关于 FIDE 规则） -E 这留下了 50 移动允许的复杂问题，没有捕获或典当移动到那里计数器是必要的......但是。
那么你如何处理呢？......好吧，真的没有办法。因为两个玩家都可能不想画，或者意识到它已经发生了。现在，如果 E 计数器可能就足够了......但这是诀窍，甚至阅读 FIDE 规则（http://www.fide.com/component/handbook/?id=124&view=article）我找不到回答... 失去发车能力怎么办。那是重复吗？我认为不是，但这是一个模糊的主题，没有解决，没有澄清。
所以这里有两个规则是两个复杂的或未定义的，甚至试图编码......干杯。
因此，真正编码游戏的唯一方法是从一开始就记录所有内容……然后与“棋盘状态”问题发生冲突（或不冲突？）。
希望这能有所帮助......不要过多的数学:-) 只是为了表明某些问题并不那么容易，对于解释或预先知识来说太开放而无法正确和有效。我不会考虑接受采访，因为它打开了太多的蠕虫罐头。
我会使用运行长度编码。有些片段是独一无二的（或者只存在两次），所以我可以省略它们后面的长度。像 cletus 一样，我需要 13 个独特的状态，所以我可以使用一个半字节（4 位）来对片段进行编码。初始板将如下所示：
White Rook, W. Knight, W. Bishop, W. Queen, W. King, W. Bishop, W. Knight, W. Rook,
W. Pawn, 8,
Empty, 16, Empty, 16
B. Pawn, 8,
B. Rook, B. Knight, B. Bishop, B. Queen, B. King, B. Bishop, B. Knight, B. Rook
这给我留下了 8+2+4+2+8 半字节 = 24 半字节 = 96 位。我不能用半字节对 16 进行编码，但由于“空，0”没有意义，我可以将“0”视为“16”。
如果棋盘是空的，但左上角只有一个棋子，我会得到“Pawn, 1, Empty, 16, Empty, 16, Empty 16, Empty, 15” = 10 个半字节 = 40 位。
最坏的情况是当我在每块之间有一个空方格时。但是对于片段的编码，我只需要 16 个值中的 13 个，所以也许我可以用另一个来说“Empty1”。然后，我需要 64 个半字节 == 128 位。
对于运动，我需要 3 位用于棋子（颜色由白色总是先移动的事实给出）加上 5 位 (0..63) 用于新位置 = 每个运动一个字节。大多数时候，我不需要旧位置，因为范围内只有一块。对于奇怪的情况，我必须使用单个未使用的代码（我只需要 7 个代码来编码该片段），然后 5 位用于旧位置，5 位用于新位置。
这使我可以在 13 口中编码易位（我可以将国王移向 Rook，这足以说明我的意图）。
[编辑] 如果您允许使用智能编码器，那么我需要 0 位进行初始设置（因为它不必以任何方式编码：它是静态的）加上每次移动一个字节。
[EDIT2] 留下了典当转换。如果一个棋子到达最后一行，我可以将它移动到适当的位置说“变形”，然后为它替换的棋子添加 3 位（你不必使用皇后；你可以用任何东西替换棋子但国王）。
[正确阅读问题后编辑]如果您假设每个合法位置都可以从初始位置到达（这是“合法”的可能定义），那么任何位置都可以表示为从一开始的移动顺序。从非标准位置开始的游戏片段可以表示为到达起点所需的一系列动作，打开相机的开关，然后是后续动作。
因此，我们将初始板状态称为单个位“0”。
任何位置的移动都可以通过对方格编号并按（开始，结束）排序移动来枚举，传统的 2 格跳跃表示易位。不需要对非法移动进行编码，因为棋盘位置和规则总是已知的。打开相机的标志可以表示为特殊的带内移动，或者更明智地表示为带外移动编号。
两边各有 24 个开局动作，每个动作可容纳 5 个位。随后的移动可能需要更多或更少的位，但合法的移动始终是可枚举的，因此每个移动的宽度可以愉快地增长或扩展。我没有计算过，但我想 7 位位置会很少见。
使用这个系统，一个 100 个半步游戏可以被编码为大约 500 位。但是，使用打开的书可能是明智的。假设它包含一百万个序列。那么，初始的 0 表示从标准板开始，而后跟 20 位数字的 1 表示从该打开序列开始。有一些传统开局的游戏可能会缩短 20 个半步或 100 位。
这不是最大可能的压缩，但是（没有开本）如果您已经有一个国际象棋模型（问题假设），它会很容易实现。
为了进一步压缩，您希望根据可能性而不是任意顺序对移动进行排序，并将可能的序列编码为更少的位（使用例如人们提到的霍夫曼标记）。
Yacoby 解决方案中起始位置的可能改进
没有一个合法位置的每种颜色超过 16 件。在 64 个方格上放置多达 16 个黑色和 16 个白色棋子的方法数量约为 3.63e27。对数2（3.63e27）=91.55。这意味着您可以将所有片段的位置和颜色编码为 92 位。这比 Yacoby 的解决方案所需的 64 位位置 + 最多 32 位颜色要少。您可以在最坏的情况下节省 4 位，但代价是编码相当复杂。
另一方面，它会增加缺少 5 件或更多件的位置的大小。这些位置仅占所有位置的 <4%，但它们可能是您想要记录不同于初始位置的起始位置的大多数情况。
这导致了完整的解决方案
算法应该在每次移动时确定性地枚举所有可能的目的地。目的地数量：
在最坏的（枚举方式）情况下，8 个爪子都可能成为皇后，从而使最大数量的可能目的地成为 9*27+26+28+16+8=321。因此，任何移动的所有目标都可以用 9 位数字枚举。
双方的最大移动数为 100（如果我没记错的话，不是棋手）。因此，任何游戏都可以以 900 位记录。加上每块的初始位置可以用6位数字记录，总计32*6 =192位。再加上“谁先走”的记录。因此，任何游戏都可以使用 900+192+1=1093 位来记录。
存储板状态
我想到的最简单的方法是首先有一个 8*8 位的数组，表示每个棋子的位置（如果那里有棋子，则为 1，如果没有棋子，则为 0）。由于这是一个固定长度，我们不需要任何终止符。
接下来按位置顺序表示每个棋子。每片使用 4 位，这需要 32*4 位（总共 128 位）。这真的很浪费。
使用二叉树，我们可以用一个字节表示一个棋子，用 3 表示马、车和主教，用 4 表示国王和王后。因为我们还需要存储棋子的颜色，这需要一个额外的字节如（如果这是错误的，请原谅我，我以前从未详细看过霍夫曼编码）：
鉴于总数：
2*16 + 4*4 + 4*4 + 4*4 + 2*5 + 2*5 = 100
这比使用固定大小的位组高出 28 位。
所以我发现的最好的方法是将它存储在一个 8 2 + 100 位数组中
8*8 + 100 = 164
存储移动
我们需要知道的第一件事是哪一块移动到哪里。鉴于棋盘上最多有 32 个棋子，并且我们知道每个棋子是什么，而不是一个整数表示正方形，我们可以有一个整数表示棋子偏移量，这意味着我们只需要拟合 32 个可能的值来表示一个片。
不幸的是，有各种各样的特殊规则，比如易位或推翻国王并组建共和国（特里普拉切特参考），所以在我们存储要移动的棋子之前，我们需要一个位来指示它是否是一个特殊的移动。
因此，对于每个正常的移动，我们都有必要的1 + 5 = 6位。（1位类型，5位为一块）
在解码棋子编号后，我们就知道棋子的类型，并且每个棋子都应该以最有效的方式代表它的移动。例如（如果我的国际象棋规则符合规定）一个棋子总共有 4 种可能的走法（向左走、向右走、向前走一走、向前走两走）。
所以为了表示一个棋子，我们需要'6 + 2 = 8'位。（6 位用于初始移动标头，2 位用于移动）
为皇后移动会更复杂，因为最好有一个方向（8 个可能的方向，所以 3 位）和每个方向总共移动 8 个可能的方格（所以另外 3 位）。因此，要表示移动皇后，它需要6 + 3 + 3 = 12位。
对我来说发生的最后一件事是我们需要存储轮到哪些玩家。这应该是一个位（下一个移动的白色或黑色）
结果格式
所以文件格式看起来像这样
[64 位] 初始棋子位置
[最大 100 位] 初始棋子 [1 位] 玩家回合
[n 位] 移动
其中移动是
[1 位] 移动类型（特殊或正常）
[n 位] 移动详细信息
如果移动是正常移动，则移动细节看起来像
[5 位] 块
[n 位] 特定块移动（通常在 2 到 6 位的范围内）
如果它是一个特殊的移动
它应该有一个整数类型，然后是任何附加信息（比如它是否是castling）。我不记得必杀技的数量了，所以可能只是表明它是必杀技（如果只有一个）就可以了
每个棋子可以用 4 位表示（兵到王，6 种），黑/白 = 12 个值
棋盘上的每个方格可以用 6 位（x 坐标，y 坐标）表示。
初始位置最多需要 320 位（32 件，4 + 6 位）
每个后续移动都可以用 16 位（从位置、到位置、块）表示。
Castling 需要额外的 16 位，因为它是双重移动。
皇后棋子可以由 4 位中的 4 个备用值之一表示。
在不详细计算的情况下，与存储 32 * 7 位（预定义的块数组）或 64 * 4 位（预定义的正方形分配）相比，这在第一次移动后开始节省空间
两边移动10次后，需要的最大空间为640位
...但话又说回来，如果我们唯一地标识每个棋子（5 位）并添加第六位来标记皇后棋子，那么我们只需要每一步的棋子 ID + 到位置。这将计算更改为...
初始位置 = 最大 384 位（32 件，6 + 6 位）每次移动 = 12 位（到位置，件 ID）
然后每边移动 10 次后，所需的最大空间为 624 位
一块棋盘有 64 个方格，可以用 64 位表示，显示方格是否为空。如果正方形有棋子，我们只需要棋子信息。由于玩家 + 棋子需要 4 位（如前所示），我们可以得到 64 + 4 * 32 = 192 位的当前状态。投入当前回合，您有 193 位。
然而，我们还需要对每一个棋子的合法走法进行编码。首先，我们计算每个棋子的合法移动数，并在一个完整方格的棋子标识符之后附加那么多位。我计算如下：
Pawn：前锋，先转二前锋，en passant * 2，promotion = 7 bits。您可以将第一轮前进和升级合并为一个位，因为它们不可能从同一位置发生，所以您有 6 个。车：7 个垂直方块，7 个水平方块 = 14 位骑士：8 个方块 = 8 位主教：2 个对角线* 7 = 14 位皇后：7 垂直，7 水平，7 对角线，7 对角线 = 28 位国王：8 个周围的正方形
这仍然意味着您需要根据当前位置映射目标方格，但它（应该）是一个简单的计算。
因为我们有 16 个棋子、4 个车/骑士/象和 2 个皇后/国王，所以这是 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = 312 位，带来总共为 505 位。
至于每件可能移动所需的位数，可以添加一些优化，并且位数可能会减少，我只是使用简单的数字来处理。例如，对于滑动件，您可以存储它们可以移动的距离，但这需要额外的计算。
长话短说：仅在方格被占用时存储额外数据（棋子等），并且仅存储每个棋子的最小位数以表示其合法移动。
EDIT1：忘记了对任何棋子的易位和典当促销。这可以使具有明确位置的总数达到 557 步（棋子多 3 位，国王多 2 位）
像 Robert G 一样，我倾向于使用 PGN，因为它是标准的并且可以被多种工具使用。
但是，如果我正在玩一个在遥远太空探测器上的国际象棋 AI，因此每一点都是宝贵的，这就是我会为这些动作做的事情。稍后我将重新编码初始状态。
动作不需要记录状态；解码器可以跟踪状态以及在任何给定点哪些移动是合法的。所有需要记录的移动是选择了各种合法替代方案中的哪一个。由于玩家交替，移动不需要记录玩家颜色。由于玩家只能移动自己的颜色棋子，因此首先选择的是玩家移动的棋子（稍后我会回到使用另一种选择的替代方案）。最多 16 件，这最多需要 4 位。当玩家失去棋子时，选择的数量会减少。此外，特定的游戏状态可能会限制棋子的选择。如果国王在不检查自己的情况下无法移动，则选择的数量减少一。如果一个国王被控制，任何不能让国王摆脱控制的棋子都不是一个可行的选择。
一旦指定了作品，它将只有一定数量的合法目的地。确切的数字在很大程度上取决于棋盘布局和游戏历史，但我们可以计算出某些最大值和预期值。除了骑士和在易位期间，一个棋子不能穿过另一个棋子。这将是移动限制的重要来源，但很难量化。一块不能移出棋盘，这也将在很大程度上限制目的地的数量。
我们通过按以下顺序沿线对正方形进行编号来编码大多数棋子的目的地：W、NW、N、NE（黑边是 N）。一条线从给定方向上最远的方格开始，合法移动到该方向并继续前进。对于无阻碍的国王，移动列表是 W、E、NW、SE、N、S、NE、SW。对于骑士，我们从 2W1N 开始，顺时针前进；目的地 0 是此顺序中的第一个有效目的地。
由于选择的数量并不总是 2 的幂，因此上面仍然浪费位。假设选择的数量是C并且特定的选择编号为c，并且n = ceil(lg( C )) （编码选择所需的位数）。我们通过检查下一个选择的第一位来利用这些否则会浪费的值。如果为 0，则什么也不做。如果是 1 且c + C < 2 n，则将C添加到c。解码一个数字会反转这个：如果接收到的c >= C，减去C并将下一个数字的第一位设置为 1。如果c< 2 n - C，然后将下一个数字的第一位设置为 0。如果 2 n - C <= c < C，则什么也不做。将此方案称为“饱和”。
另一种可能缩短编码的潜在选择类型是选择要捕获的对手棋子。这增加了移动的第一部分的选择数量，选择一块，最多增加一点（确切的数字取决于当前玩家可以移动多少块）。这个选择之后是选择捕获棋子，这可能比任何给定玩家棋子的移动数要小得多。一个棋子只能被任意主要方向的一个棋子加上骑士攻击，总共最多10个攻击棋子；这为捕获移动提供了最多 9 位，尽管我预计平均 7 位。这对于女王的捕获特别有利，因为它通常会有很多合法的目的地。
由于饱和，捕获编码可能无法提供优势。我们可以允许这两个选项，指定使用的初始状态。如果不使用饱和度，游戏编码还可以使用未使用的选项编号 ( C <= c < 2 n ) 在游戏期间更改选项。任何时候C是 2 的幂，我们都无法更改选项。
在初始棋盘加上后续移动的基本情况下，请考虑以下内容。
使用国际象棋程序为所有可能的移动分配概率。例如，e2-e4 为 40%，d2-d4 为 20%，以此类推。如果某些动作是合法的，但该程序没有考虑，则给它们一些低概率。使用算术编码来保存所采取的选择，对于第一步，它将是 0 到 0.4 之间的某个数字，第二步是 0.4 和 0.6 之间的某个数字，依此类推。
对另一侧做同样的事情。例如，如果 e7-e5 有 50% 的机会作为对 e2-e4 的响应，则编码数字将介于 0 和 0.2 之间。重复直到游戏结束。结果是一个潜在的非常小的范围。找到适合该范围的最小基数的二进制分数。那是算术编码。
这比霍夫曼要好，因为它可以被认为是小数位编码（在游戏结束时加上一些以四舍五入）。
结果应该比霍夫曼更紧凑，并且没有特殊情况进行升级，过路，50规则移动和其他细节，因为它们是由国际象棋评估程序处理的。
要重播，再次使用国际象棋程序评估棋盘并将所有概率分配给每一步。使用算术编码值来确定实际播放的是哪个动作。重复直到完成。
如果您的国际象棋程序足够好，您可以使用双态编码器获得更好的压缩，其中概率是基于黑白移动定义的。在大约 200 多个状态的最极端情况下，这编码了所有可能的国际象棋游戏的整个集合，因此是不可行的。
这与 Darius 已经写过的内容完全不同，只是举了一些算术编码如何工作的例子，以及一个使用现有国际象棋程序来帮助评估下一步行动概率的真实例子。
这就是我对游戏步骤进行编码的方式。对于一个有 40 步的游戏，这将需要大约 180 位左右。
首先，使用了解所有国际象棋规则的引擎创建所有选项的列表。每一步，执行以下操作：
这将为您提供如下列表：
[[10, 3], # choose white pawn at index #3
[2, 0], # move it one step forward
[10, 2], # choose black pawn #2
[2, 1], # move it two steps forward
...
]
等等。要对其进行编码，您只需要存储选择，而不是可能的移动次数。存储它的一种方法是找出每个选择需要多少位：
[[10, 3], # 10 choices => 4 bits
[2, 0], # 2 choices => 1 bit
[10, 2], # 10 choices => 4 bits
[2, 1], # 2 choices => 1 bit
...
]
前两次移动的总位数4+1+4+1=10。但是浪费了一些位，使用 4 位进行 10 个选择会浪费 6 个可能的选择。
可以做得更好：反转列表，并根据可能的选择和所采取的选择计算一个数字：
n = 0 # last position
n = n*2 + 1 # from [2, 1] n=1
n = n*10 + 2 # from [10, 2] n=12
n = n*2 + 0 # from [2, 0] n=24
n = n*10 + 3 # from [10, 3] n=243
现在我们有了数字243binary 11110011，它将上述所有步骤编码为 8 位。
要解码，我们知道初始开仓有 10 种可能的选择。计算
n = 243
choice = n % 10 # we know there are 10 moveable pieces. => choice=3
n /= 10 # n=24
choice = n % 2 # we know 2 possible moves for selected pawn => choice=0
n /= 2 # n=12
choice = n % 10 # 10 moveable pieces for black player. => choice=2
n /= 10 # n=1
choice = n % 2 # 2 possible moves for pawn => choice=1
n /= 2 # n=0, finished decoding
编码非常有效，尤其是在最后阶段，因为剩下的可能选择不多。此外，当您只剩下一个可能的移动时，您根本不需要任何存储来进行移动。
棋盘上有 32 个棋子。每个棋子都有一个位置（64 个方格中的一个）。所以你只需要 32 个正整数。
我知道 64 个位置保存在 6 位中，但我不会那样做。我会为几面旗帜保留最后一点（掉落的一块，女王的典当）
cletus的回答很好，但他忘了也编码轮到谁了。它是当前状态的一部分，如果您使用该状态来驱动搜索算法（如 alpha-beta 导数），则它是必需的。
我不是国际象棋棋手，但我相信还有一个极端情况：重复了多少步。一旦每个玩家进行相同的动作3次，游戏就是平局，不是吗？如果是这样，那么您需要将该信息保存在状态中，因为在第三次重复之后，状态现在是终端。
正如其他几个人提到的那样，您可以为 32 个棋子中的每一个存储它们在哪个方格上，以及它们是否在棋盘上，这给出 32 * (log2(64) + 1) = 224 位。
然而，主教只能占据黑色或白色方块，因此对于这些，您只需要 log2(32) 位作为位置，即 28 * 7 + 4 * 6 = 220 位。
而且由于pawns不是从后面开始，只能向前移动，它们只能在56上，应该可以使用这个限制来减少pawns所需的位数。
Thomas 有正确的方法来对电路板进行编码。然而，这应该与 ralu 存储移动的方法相结合。列出所有可能的移动，写出表达这个数字所需的位数。由于解码器正在执行相同的计算，它知道有多少是可能的，并且可以知道要读取多少位，因此不需要长度代码。
因此，我们得到 164 位用于棋子，4 位用于易位信息（假设我们正在存储游戏的片段，否则可以重建），3 位用于通过行人资格信息 - 只需存储发生移动的列（如果 en passant 不可能，则在不可能的地方存储一列 - 这样的列必须存在）和 1 表示要移动的人。
移动通常需要 5 或 6 位，但可以从 1 到 8 不等。
一个额外的捷径——如果编码以 12 个 1 位开始（一种无效的情况——甚至一个片段都不会在一侧有两个国王），你中止解码，擦板并设置一个新游戏。下一位将是移动位。