程序员谜题：在整个游戏中编写一个棋盘状态

不是严格的问题，更多的是一个难题

多年来，我参与了一些新员工的技术面试。 除了问标准“你知道X技术”这个问题之外，我还试图去了解他们如何解决问题。 通常情况下，我会在面试的前一天通过电子邮件向他们发送问题，并期待他们在第二天提出解决scheme。

结果往往是相当有趣的 – 错误的，但有趣的 – 如果他们能解释为什么他们采取了特定的方法，那么他仍然会得到我的build议。

所以我想我会为Stack Overflow观众提出我的一个问题。

问题： 如何编码国际象棋游戏（或其子集）的时候，可以考虑的最节省空间的方法是什么？ 也就是说，如果棋盘上有合法排列的棋子，则编码这个初始状态以及游戏中玩家采取的所有后续合法行为。

答案不需要代码，只需要描述你将要使用的algorithm。

编辑：正如其中一个海报已经指出，我没有考虑到移动之间的时间间隔。 随意作为一个可选的额外的:)

编辑2：只是为了进一步澄清…请记住，编码器/解码器是规则感知。 真正需要存储的唯一东西是播放器的select – 编码器/解码器可以假定其他任何东西。

编辑3：这里将很难挑选一个胜利者:)很多伟大的答案！

更新：我非常喜欢这个话题，我写了编程难题，象棋位置和哈夫曼编码 。 如果你通读了这个，我已经确定存储一个完整的游戏状态的唯一方法是存储一个完整的移动列表。 阅读为什么。 所以我使用一个稍微简化的版本来解决这个问题。

问题

这张图片说明了国际象棋的起始位置。 国际象棋发生在一个8×8的棋盘上，每个棋手都有16个棋子，包括8个棋子，2个骑手，2个骑士，2个主教，1个皇后和1个国王，如下图所示：

开始象棋位置http://img222.imageshack.us/img222/5970/chess.png

职位通常logging为列的字母，然后是该行的编号，所以White的女王在d1。 移动通常以代数符号存储，这是明确的，通常只指定必要的最小信息。 考虑这个开放：

  1. e4 e5
  2. Nf3 Nc6
  3. …

这意味着：

  1. 白棋从e2到e4移动国王的棋子（这是唯一可以到达e4的棋子，因此是“e4”）;
  2. 黑棋将国王的棋子从e7移到e5;
  3. 白棋将骑士（N）移至f3;
  4. 黑色将骑士移至c6。
  5. …

董事会看起来像这样：

早期开放http://img222.imageshack.us/img222/371/chessx.png

对于任何程序员来说，一个重要的能力是能够正确无误地指定问题 。

那么有什么缺失或含糊？ 结果很多。

董事会状态与游戏状态

你需要确定的第一件事是你是否正在存储游戏的状态或棋盘上棋子的位置。 编码简单的块的位置是一回事，但问题说“所有后续的法律行动”。 这个问题也没有说明到目前为止的情况。 这是我会解释的一个问题。

易位

游戏进行如下：

  1. e4 e5
  2. Nf3 Nc6
  3. Bb5 a6
  4. Ba4 Bc5

董事会看起来如下：

稍后开放

白色可以selectcastling 。 部分要求是国王和有关的车不能移动，所以国王或任何一方的车辆是否移动都需要存储。 显然，如果他们不在起始位置，他们已经移动，否则需要指定。

有几个策略可以用来处理这个问题。

首先，我们可以存储额外的6位信息（每个车和国王1个），以表明这个片段是否已经移动。 如果正确的一块恰好在这里，我们可以通过只为这六个方块中的一个存储一点来简化这一点。 或者我们可以把每一个无动于衷的作品当作另一种types，所以不是每一边都有6种types（典当，白车，骑士，主教，女王和国王），而是有8个（加上不动的白嘴鸦和无动于衷的国王）。

En Passant

国际象棋中另一个特殊而常常被忽视的规则就是“ 被动” 。

en passant http://img37.imageshack.us/img37/6535/chessa.png

游戏已经进展。

  1. e4 e5
  2. Nf3 Nc6
  3. Bb5 a6
  4. Ba4 Bc5
  5. OO b5
  6. Bb3 b4
  7. C4

黑方在b4上的棋子现在可以select在b4上移动他的棋子到c3上，在c4上select白棋。 这只发生在第一次机会，即如果黑方传递选项，现在他不能采取下一步行动。 所以我们需要存储这个。

如果我们知道以前的举动，我们可以肯定地回答，如果En Passant是可能的。 或者，我们可以存储每个第四级的棋子是否已经向前移动了两次。 或者我们可以看看董事会上每个可能的En Passant职位，并且有一个标志来表明是否可能。

提升

典当推广http://img689.imageshack.us/img689/5970/chess.png

这是白方的举动。 如果白棋将他的棋子在h7上移动到h8，它可以被提升为任何其他棋子（但不是国王）。 99％的时间被提升为女王，但有时不是，通常是因为这可能会迫使一个僵局，否则你会赢。 这写成：

  1. H8 = Q

这对我们的问题很重要，因为这意味着我们不能指望每一边都有固定的数量。 如果所有8个兵都晋升，那么完全有可能（但极不可能）一方得到9名皇后，10名白嘴鸦，10名主教或10名骑士。

相持

当你无法赢得最好的战术的时候，就是尝试一个僵局 。 最有可能的变体是你无法做出合法行动的地方（通常是因为在把国王放在手中时的任何举动）。 在这种情况下，你可以要求平局。 这个很容易迎合。

第二个变种是三倍重复 。 如果同一棋盘位置在一场比赛中出现三次（或者在下一次移动中第三次出现），可以要求平局。 这些职位不一定按照任何特定的顺序（意思是不需要重复三次同样的步骤）。 这个问题使问题变得非常复杂，因为你必须记住以前的每一个董事会职位。 如果这是问题的一个要求，那么问题的唯一可能的解决scheme是存储每一个先前的移动。

最后，有五十个移动规则 。 如果没有棋子移动，并且在之前的五十次连续移动中没有棋子被占用，那么玩家可以要求抽签，因此我们需要存储棋子移动或棋子被移走后的移动次数（这是最新的两次。 6位（0-63）。

该轮到谁啦？

当然，我们也需要知道它是谁的，这是一个单一的信息。

两个问题

由于僵局的情况，存储游戏状态的唯一可行或合理的方式是存储导致该位置的所有移动。 我会解决这个问题。 棋盘状态问题将被简化为： 将所有棋子的当前位置存储在棋盘上，忽略棋盘格，转场，僵局条件以及轮到它 。

可以通过两种方法之一来广泛地处理片段布局：通过存储每个方块的内容或通过存储每片的位置。

简单的内容

有六种types（典当，白嘴鸦，骑士，主教，女王和国王）。 每件作品可以是白色或黑色，所以正方形可以包含12个可能的部分之一，或者可以是空的，所以有13个可能性。 13可以存储在4位（0-15）因此，最简单的解决scheme是存储每平方64位的信息64位或256位的4位。

这种方法的优点是操作非常简单快捷。 这甚至可以通过增加3个可能性而不增加存储要求来扩展：在最后一个回合中移动了2个空间的棋子，没有移动的国王和没有移动的棋子，这将迎合很多之前提到的问题。

但是我们可以做得更好。

基地13编码

认为董事会的地位是非常大的数字往往是有帮助的。 这通常在计算机科学中完成。 例如， 暂停问题将一个计算机程序（正确地）视为一个大数目。

第一个解决scheme将该位置视为一个64位的基数为16的数字，但是如所certificate的，在这个信息中存在冗余（每个“数字”有3个未使用的可能性），所以我们可以将数字空间减less到64位的13位数字。 当然，这不可能像基地16那样有效地完成，但是这将节省存储需求（并且最小化存储空间是我们的目标）。

在基数10中，数字234等于2×10 2 + 3×10 1 + 4×10 0 。

在基数16中，数字0xA50相当于10×16 2 + 5×16 1 + 0×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.这样就减less了可能的棋盘到11 16 ×13 48 = 1.35×70（大约），需要233比特的存储空间。

实际上，将这些值与十进制（或二进制）进行编码和解码有点复杂，但它可以可靠地完成，并作为练习留给读者。

可变宽度字母表

前两种方法都可以描述为固定宽度的字母编码 。 11,13或16个字母中的每一个都代替另一个值。 每个“字符”是相同的宽度，但是当你考虑到每个字符的可能性不大时，效率可以提高。

莫尔斯电码

考虑莫尔斯电码 （上图）。 消息中的字符被编码为一系列破折号和圆点。 那些破折号和圆点通过无线电（通常）传输，在它们之间暂停以划定它们。

注意字母E（ 英文中最常见的字母 ）是单点，是最短的序列，而Z（最不频繁）是两个短划线和两个哔哔声。

这种scheme可以显着减小预期消息的大小，但是以增加随机字符序列的大小为代价。

应该注意的是，莫尔斯电码具有另一个内置function：破折号只要三个点，所以上面的代码是为了尽量减less破折号的使用而创build的。 由于1和0（我们的构build块）没有这个问题，所以不是我们需要复制的function。

最后，莫尔斯电码有两种rest方式。 短暂的rest（点的长度）用于区分点和破折号。 较长的间隔（短划线的长度）用于分隔字符。

那么这怎么适用于我们的问题呢？

霍夫曼编码

有一种algorithm用于处理称为霍夫曼编码的可变长度码。 霍夫曼编码创build可变长度代码replace，通常使用符号的期望频率将更短的值分配给更常见的符号。

霍夫曼代码树

在上面的树中，字母E被编码为000（或者左 – 左 – 左），S是1011.应该清楚的是，这种编码scheme是明确的 。

这是摩尔斯电码的重要区别。 摩尔斯电码具有字符分隔符，所以它可以做其他含糊不清的replace（例如4个点可以是H或2个Is），但是我们只有1个和0个，所以我们select一个明确的replace。

下面是一个简单的实现： 

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(), &quot;&quot;); 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×1 + 16×3 + 12×5 + 4×6 = 164位。

状态差异

另一种可能的方法是将第一种方法与霍夫曼编码相结合。 这是基于这样的假设，即大多数预期的棋盘（而不是随机生成的棋盘）更可能至less部分地类似于起始位置。

所以你要做的是将256位当前的电路板位置与256位的起始位置进行异或运算，然后对其进行编码（使用霍夫曼编码或者某种运行长度编码方法）。 显然，这将是非常有效的开始（64 0可能对应于64位），但随着游戏进行所需的存储增加。

片位置

如前所述，攻击这个问题的另一种方法是改为存储玩家所拥有的每个棋子的位置。 这对于大多数方格将为空的残局位置特别有效（但是在霍夫曼编码方法中，空方块仅使用1位）。

每边将有一个国王和0-15其他件。 由于晋升，这些作品的确切组成可以有所不同，你不能假设基于起始位置的数字是最大的。

划分这个的逻辑方法是存储一个由两个面（白色和黑色）组成的位置。 每一方都有：

  • 王：6位的位置;
  • 有典当：1（是），0（否）;
  • 如果是的话，兵数：3比特（0-7 + 1 = 1-8）;
  • 如果是的话，每个棋子的位置是编码的：45位（见下文）;
  • 非兵数：4比特（0-15）;
  • 对于每一块：input（皇后，白嘴鸦，骑士，主教2位）和位置（6位）

至于兵的位置，兵只能在48个可能的正方形（不像其他的64个）。 因此，最好不要浪费使用每个棋子6位的额外16个值。 所以如果你有八个兵，就有48 八个可能，等于28,179,280,429,056。 你需要45位来编码许多值。

这是每边105位或总共210位。 起始位置是这种方法最糟糕的情况，但是当你移除碎片时，它会变得更好。

需要指出的是，由于棋子不能全部在同一个方格中，所以有48个以下的可能性。第一个有48个可能性，第二个有47个可能。 48 x 47 x … x 41 = 1.52e13 = 44位存储。

你可以通过消除其他棋子（包括对方）所占据的方块来进一步改善这一点，所以你可以先放置白色的非棋子，然后是黑色的非棋子，然后是白色的棋子，最后是黑色的棋子。 在起始位置，这将存储要求降低到白色的44位和黑色的42位。

组合方法

另一种可能的优化是每种方法都有其优点和缺点。 你可以说，select最好的4，然后在前两位编码一个schemeselect器，然后编码scheme专用存储器。

以小的开销，这将是最好的方法。

游戏状态

我回到了存储游戏的问题，而不是一个位置 。 由于三重复制，我们必须存储已经发生的移动列表。

注释

有一件事你必须确定的是你只是存储一个移动列表，或者你注释游戏？ 国际象棋游戏经常被注释，例如：

  1. BB5！ NC4？

白方的举动有两个惊叹号，而黑方被认为是一个错误。 请参阅国际象棋标点符号 。

此外，您可能还需要在描述移动时存储自由文本。

我假设这些举措是足够的，所以不会有注释。

代数符号

我们可以简单地将移动的文本存储在这里（“e4”，“Bxb5”等）。 包括每移动6个字节（48位）的最终字节（最坏的情况）。 这不是特别有效。

第二件事是尝试存储起始位置（6位）和结束位置（6位），以便每移动12位。 这显然更好。

或者，我们可以以可预测的和确定性的方式，从现在的位置来确定所有的合法行动，并且我们已经select了状态。 然后返回到上面提到的可变基编码。 白方和黑方在第一步中有20个可能的步骤，第二个步骤则更多，等等。

结论

这个问题没有绝对正确的答案。 有很多可能的方法，其中以上只是less数。

我喜欢这个和类似的问题是，它要求任何程序员的能力都很重要，比如考虑使用模式，准确地确定需求和思考angular落案例。

国际象棋位置训练师截图的国际象棋位置 。

国际象棋比赛最好是以可读的标准格式存储。

便携式游戏符号假设一个标准的起始位置（尽pipe它不必 ），只是列出移动，依次轮stream。 一个紧凑的，人类可读的标准格式。

例如 

 [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. OO Be7 6. Re1 b5 7. Bb3 d6 8. c3 OO 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

如果你想把它做得更小，那就把它压缩一下 。 任务完成！

伟大的难题！

我看到大多数人都在储存每一件作品的位置。 如何采取更简单的方法，并存储每个广场的内容 ？ 这需要照顾升级和自动捕获件。

它允许霍夫曼编码 。 实际上，棋盘上的棋子的初始频率几乎是完美的：一半的棋子是空的，另一半棋子是棋子，等等。

考虑到每一个片断的频率，我在纸上构build了霍夫曼树 ，这里我不再重复。 结果，其中c代表颜色（白色= 0，黑色= 1）：

  • 0为空方块
  • 1c0为典当
  • 1c100为白嘴鸦
  • 1c101为骑士
  • 1c110为主教
  • 女王1c1110
  • 1c1111为国王

对于整个董事会的初始状况，我们有

  • 空方块：32 * 1位= 32位
  • 典当：16 * 3位= 48位
  • 白嘴鸦/骑士/主教：12 * 5位= 60位
  • 皇后/王：4 * 6位= 24位

总计： 初始板状态的164位 。 大大低于当前最高票数答案的235位。 随着游戏的进行，游戏只会变得越来越小（除了升级之外）。

我只看着棋盘上棋子的位置; 另外的状态（轮到谁，有谁做过，有没有做过，重复的动作等等）将不得不单独编码。 也许是最多16位，所以整个游戏状态为180位 。 可能的优化：

  • 把不那么频繁的部分留下，分开存放他们的位置。 但是，这将无济于事……用一个空的方块代替国王和王后节省了5位，这就是你需要以另一种方式编码他们的位置的5位。
  • “后排没有棋子”可以很容易地通过对后排使用不同的霍夫曼表进行编码，但是我怀疑它有多大的帮助。 你可能还会得到同样的霍夫曼树。
  • “一个白人，一个黑人主教”可以通过引入额外的没有c位的符号来编码，然后可以从主教所在的方格中推导出来。 （提升给主教的棋子打乱了这个计划…）
  • 空方块的重复可以通过引入额外的符号（例如，“连续2个空方块”和“连续4个空方块”）来进行连续编码。 但是估计这些频率并不是那么容易，如果你弄错了，它将会受到伤害而不是帮助。

真正的大查找表方法

位置 – 18个字节
估计法律职位的数量是 10 43
简单列举一下，位置可以存储在143位。 需要1个比特来指示接下来要播放哪一边

枚举当然是不实际的，但是这表明至less需要144位。

移动 – 1个字节
每个职位通常会有大约30-40个法律动作，但是这个数字可能高达218个。让我们列举每个职位的所有法律动作。 现在每个动作都可以编码成一个字节。

我们仍然有足够的空间来进行特殊动作，例如0xFF代表辞职。

这会增加对人类玩典型游戏的平均大小进行优化的兴趣，而不是最坏的情况。 （问题陈述并不是说哪个;大部分回答都是最坏的情况。）

对于移动序列，有一个好的棋盘引擎从每个位置产生移动; 它会生成一个k个可能的移动列表，按其质量sortingsorting。 人们通常比随机动作更经常地select好​​的动作，所以我们需要学习从列表中的每个位置到人们select“好”动作的概率的映射。 使用这些概率（基于来自某个互联网国际象棋数据库的游戏语料库），用算术编码对这些移动进行编码 。 （解码器必须使用相同的国际象棋引擎和映射。）

对于开始的位置，ralu的方法将起作用。 如果我们有某种方式来按概率对选项进行加权，我们也可以用算术编码对其进行优化 – 例如，棋子常常出现在相互捍卫的configuration中，而不是随机的。 很难看到一个简单的方法来结合这些知识。 一个想法：从上面的移动编码，而不是从标准的开放位置，并find一个序列，结束在所需的董事会。 （你可以尝试A *search，其启发距离相当于从最终位置到最终位置的距离的总和，或者沿着这些线的东西）。这样做会导致一些低效率，从过度指定移动序列和利用下棋的效率知识。 （通过消除导致A *search中以前探索的位置的移动select，您可以回避一些无效率：这些可以在算术代码中得到权重0）。

如果没有从实际的语料库中收集一些统计数据，估计在平均情况下会有多less节省，这也是很难估计的。 但是，我认为所有动作的起点都相当可能已经超过了这里的大部分提议：算术编码不需要每移动一个整数位。

在初始位置编码之后，攻击编码步骤的子问题。 方法是创build一个“链接列表”的步骤。

游戏中的每一步都被编码为“旧位置 – >新位置”对。 你知道棋局开始的初始位置， 通过遍历步骤的链表，可以在X移动之后到达状态。

为了对每一步进行编码，您需要64个值来对开始位置进行编码（板上64个方块的6位 – 8×8方块），以及6位的结束位置。 每边移动16位。

编码一个给定的游戏所需要的空间量将与移动的数量成比例：

10 x（白色移动数量+黑色移动数量）位。

更新：与提升的兵的潜在并发症。 需要能够说明哪些棋子被提升 – 可能需要特殊的位（为了节省空间，将使用灰色代码，因为典当提升是非常罕见的）。

更新2：您不必编码结束位置的完整坐标。 在大多数情况下，被移动的棋子可以移动到不超过X个位置。 例如，一个棋子在任何给定的点上最多可以有3个移动选项。 通过实现每个片段types的最大移动次数，我们可以将位保存在“目的地”的编码中。 

 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位（根据被移动物体的types，可变位数）。

昨天晚上我看到这个问题，这让我很兴奋，所以我坐在床上思考解决scheme。 我的最终答案与int3实际上非常相似。

基本解决scheme

假设一个标准的国际象棋游戏，你不规则编码（如白色总是先行），那么你可以节省很多编码只是每件作品的举动。

总共有32件，但是在每一次移动中，你知道什么颜色在移动，所以只有16个方格担心，这是本回合移动的4个位 。

每件作品只有一个有限的动作，你会以某种方式列举。

  • 典当：4个选项， 2位 （向前1步，向前2步，对angular线1）
  • Rook：14个选项， 4位 （每个方向最多7个）
  • 主教：13个选项， 4位 （如果你有一个对angular线7，你只有6在另一个）
  • 骑士：8个选项， 3位
  • 女王：27个选项， 5位 （Rook + Bishop）
  • 国王：9个选项， 4位 （8个一步移动，加上castling选项）

对于促销，有4件可供select（白嘴鸦，主教，骑士，女王），所以在这一举动，我们将增加2位来指定。 我认为所有其他规则都是自动涵盖的（例如en passant）。

进一步优化

首先，在捕获8种颜色之后，可以将片段编码减less到3位，然后将2位减less到4片，依此类推。

主要的优化是只列举游戏中每个点的可能动作。 假设我们将一个棋子的棋步存储为{00, 01, 10, 11} ，分别向前1步，向前2步，向左对angular线和向右对angular线。 如果有些动作是不可能的，我们可以从这个回合的编码中删除它们。

我们知道每个阶段的游戏状态（从所有的动作开始），所以在阅读了哪一段文件之后，我们总能确定需要读取的位数。 如果我们认识到一个棋子在这一点上的唯一动作就是对angular地向右或向前移动，我们知道只读取1位。

总之，上面列出的每一块的位存储量是最大的 。 几乎每一个举动都将有更less的select，往往更less的位。

在每个位置获得所有可能移动的数量。

下一步是生成为 

 index_current_move =n % num_of_moves //this is best space efficiency n=n/num_of_moves

可以存储随机生成的游戏的最佳空间效率，因为你有30-40个可能的移动，所以平均需要大约5比特/移动。 assembly存储只是以相反的顺序生成n。

由于冗余度大，存储位置更难以破解。 （一个地方最多可以有9个王后，但是在这种情况下，没有棋子，如果棋盘上的主教是在相对的彩色方格上），但是通常就像在其余的方块上存放相同棋子的组合）。

编辑：

节省移动的重点是只存储移动的索引。 而不是存储KC1-C2，并试图减less这个信息，我们应该只添加确定性的movegenerator（位置）产生的移动索引，

在每一步我们添加大小的信息 

 num_of_moves = get_number_of_possible_moves(postion) ;

在游泳池和这个数字不能减less

生成信息池是 

 n=n*num_of_moves+ index_current_move

额外

如果在最终位置只有一个可用的移动，则保存为以前完成的强制移动的数量。 例如：如果起始位置每边有2次强制移动（2次移动），我们希望将其保存为一次移动游戏，则将1储存在池n中。

存储到信息池中的示例

让我们假设我们已经知道了起始位置，我们做了3步。

第一步有5个可用的移动，我们采取移动索引4.第二步移动有6个可用的移动，我们采取位置索引3，在第三步移动有7个可用的移动，他select了移动索引2。

vectorforms; index = [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次移动应该没有问题。

节省的位置

可以做到接近最佳。

当我们了解信息和存储信息时，让我多谈一谈。 总的想法是减less冗余（我将在稍后讨论）。 假设没有晋升和不考虑，所以有8个兵，2个车，2个骑士，2个主教，1个国王和1个皇后。

我们要保存什么：1，每个和平的地位2，铸造的可能性3，可能性4，移动的可能性

假设每件作品都可以放在任何地方，但不能放在同一个地方。 （8/8）（二项式）32位，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位）为castling限制和一点点有移动的网站。 我们以142 + 3 + 4 + 1 = 150比特结束

但是，现在让我们继续在32板上寻找冗余，没有考虑。

  1. 黑色和白色的棋子都在同一列上面对面。 每一个棋子都面对着另一个棋子，这意味着白色棋子最多可以排在第六位。 这给我们带来了8 * C（6/2）而不是C（64/8）* C（48/8），它将信息减less了56位。

  2. castling的可能性也是多余的。 如果白嘴鸦不在出发地点，那么没有白车的可能性。 所以我们可以想象在船上加4个方格来获得额外的信息，如果摔跤这个白嘴鸦是可能的，并删除4个castling位。 所以不是C（56/2）* C（40/2）* 16而是C（58/2）* C（42/2），我们损失了3.76位（几乎全部是4位）

  3. en-passant：当我们存储8个符合条件的可能性中的一个时，我们知道黑色棋子的位置并且减less信息的重新expression（如果它是白色棋子并且有第3个棋子，那么黑色棋子在c5上，白色棋子也是c2，c3或c4）如此的C（6/2），我们有3个，我们输了2.3个比特。 如果我们存储可以完成的惠益对方数字（3种可能性 – >左，右，两者），我们减less一些冗余，并且我们知道可以使用的典当的位置。 （例如，从c5上的事件例子中可以看出，在左边，右边或者两者都有，如果在一个地方，我们有2 * 3（3个用于存储psissibilites，2个可能的移动用于黑色棋子， ）C（6/2），我们减less1.3位，如果两边减less4.2位，那么我们可以减less2.3 + 1.3 = 3.6位。

  4. 主教：bisops只能在opostite正方形，这减less了每个站点的冗余1位。

如果我们总结，我们需要150-56-4-3.6-2 = 85比特存储国际象棋的位置，如果没有收益

如果有考虑到收入和促销活动的话，可能不会更多（但是如果有人能够find这么长的信息，我会在后面写这个）

大多数人一直在编码板的状态，但关于自己的移动..这是一个位编码的描述。

每件的比特数：

  • Piece-ID：最大4位，用于识别每边16个碎片。 可以推断白色/黑色。 有一个订单定义的作品。 随着件数下降到两个相应的幂次之下，用较less的位来描述剩余件。
  • 典当：第一步有三种可能性，所以+2位（向前一个或两个方块，即可）后续的移动不允许向前移动两个，所以+1位就足够了。 在解码过程中可以通过注意棋子何时击中最后一个等级来推断促销。 如果已知棋子被提升，则解码器将期望另外2个比特指示它已被提升到的4个主要部分中的哪一个。
  • 主教：对angular线使用+1比特，对angular线距离多达+4比特（16种可能性）。 解码器可以推断出该块可以沿着该对angular线移动的最大可能距离，所以如果它是较短的对angular线，则使用较less的位。
  • 骑士： 8个可能的移动，+3位
  • Rook：水平/垂直+1位，沿线距离+4位。
  • 国王： 8个可能的移动，+3位。 Indicate castling with an 'impossible' move — since castling is only possible while the king is on the first rank, encode this move with an instruction to move the king 'backwards' — ie out of the board.
  • Queen: 8 possible directions, +3bits. Up to +4 more bits for distance along the line / diagonal (less if the diagonal is shorter, as in the bishop's case)

Assuming all pieces are on the board, these are the bits per move: Pawn – 6 bits on first move, 5 subsequently. 7 if promoted. Bishop: 9 bits (max), Knight: 7, Rook: 9, King: 7, Queen: 11 (max).

Is the problem to give an encoding that is most efficient for typical chess games, or one that has the shortest worst case encoding?

For the latter, the most efficient way is also the most opaque: create an enumeration of all possible pairs (initial board, legal sequence of moves), which, with the draw-on-thrice-repeated-position and no-more-than-fifty-moves since last-pawn-move-or-capture rules, is recursive. Then the index of a position in this finite sequence gives the shortest worst-case encoding, but also and equally long encoding for typical cases, and is, I expect, very expensive to compute. The longest possible chess game is supposed to be over 5000 moves, with there typically being 20-30 moves available in each position to each player (though fewer when there are few pieces left) – this gives something like 40000 bits needed for this encoding.

The idea of enumeration can be applied to give a more tractable solution, as described in Henk Holterman's suggestion for encoding moves above. My suggestion: not minimal, but shorter than the examples above I've looked at, and reasonable tractable:

  1. 64 bits to represent which squares are occupied (occupancy matrix), plus list of which pieces are in each occupied square (can have 3 bits for pawns, and 4 bits for other pieces): this gives 190 bits for start position. Since there can't be more than 32 pieces on board, the encoding of the occupancy matrix is redundant & so something like common board positions can be encoded, say as 33 set bits plus index of board from common boards list.

  2. 1 bit to say who makes first move

  3. Code moves per Henk's suggestion: typically 10 bits per pair of white/black move, though some moves will take 0 bits, when a player has no alternative moves.

This suggests 490 bits to code a typical 30-move game, and would be a reasonably efficient representation for typical games.

Abouth encoding the draw-on-thrice-repeated-position and no-more-than-fifty-moves since last-pawn-move-or-capture rules: if you encode thepast moves back to the last pawn move or capture, then you have enough information to decide whether these rules apply: no need for the whole game history.

The position on a board can be defined in 7 bits (0-63 , and 1 value specifying it is not on the board anymore). So for every piece on the board specify where it is located.

32 pieces * 7 bits = 224 bits

EDIT: as Cadrian pointed out… we also have the 'promoted pawn to queen' case. I suggest we add extra bits at the end to indicate which pawn have been promoted.

So for every pawn which has been promoted we follow the 224 bits with 5 bits which indicate the index of the pawn which has been promoted, and 11111 if it is the end of the list.

So minimal case (no promotions) is 224 bits + 5 (no promotions). For every promoted pawn add 5 bits.

EDIT: As shaggy frog points out, we need yet another bit at the end to indicate whose turn it is ;^)

I'd use a run length encoding. Some pieces are unique (or exist only twice), so I can omit the length after them. Like cletus, I need 13 unique states, so I can use a nibble (4 bits) to encode the piece. The initial board would then look like this: 

 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

which leaves me with 8+2+4+2+8 nibbles = 24 nibbles = 96 bits. I can't encode 16 with a nibble but since "Empty, 0" doesn't make sense, I can treat "0" as "16".

If the board is empty but for a single pawn in the upper left corner, I get "Pawn, 1, Empty, 16, Empty, 16, Empty 16, Empty, 15" = 10 nibbles = 40 bits.

The worst case is when I have an empty square between each piece. But for the encoding of the piece, I just need 13 out of 16 values, so maybe I can use another one to say "Empty1". Then, I need 64 nibbles == 128bits.

For the movements, I need 3 bits for the piece (the color is given by the fact that white always moves first) plus 5 bits (0..63) for the new position = one byte per movement. Most of the time, I don't need the old position since only a single piece will be within range. For the odd case, I must use the single unused code (I just need 7 codes to encode the piece) and then 5 bits for the old and 5 bits for the new position.

This allows me to encode castling in 13 bites (I can move the King towards the Rook which is enough to say what I intend).

[EDIT] If you allow a smart encoder, then I need 0 bits for the initial setup (because it doesn't have to be encoded in any way: It's static) plus one byte per move.

[EDIT2] Which leaves the pawn transformation. If a pawn reaches the last row, I can move it in place to say "transforms" and then add the 3 bits for the piece it is replaced with (you don't have to use a queen; you can replace the pawn with anything but the King).

Just like they encode games on books and papers: every piece has a symbol; since it's a "legal" game, white moves first – no need to encode white or black separetely, just count the number of moves to determine who moved. Also, every move is encoded as (piece,ending position) where 'ending position' is reduced to the least amount of symbols that allows to discern ambiguities (can be zero). Length of game determines number of moves. One can also encode the time in minutes (since last move) at every step.

Encoding of the piece could be done either by assigning a symbol to each (32 total) or by assigning a symbol to the class, and use the ending position to understand which of the piece was moved. For example, a pawn has 6 possible ending positions; but on average only a couple are available for it at every turn. So, statistically, encoding by ending position might be best for this scenario.

Similar encodings are used for spike trains in computational neuroscience (AER).

Drawbacks: you need to replay the entire game to get at the current state and generate a subset, much like traversing a linked list.

There are 64 possible board positions, so you need 6 bits per position. There are 32 initial pieces, so we have 192 bits total so far, where every 6 bits indicates the position of the given piece. We can pre-determine the order the pieces appear in, so we don't have to say which is which.

What if a piece is off the board? Well, we can place a piece on the same spot as another piece to indicate that it is off the board, since that would be illegal otherwise. But we also don't know whether the first piece will be on the board or not. So we add 5 bits indicating which piece is the first one (32 possibilities = 5 bits to represent the first piece). Then we can use that spot for subsequent pieces that are off the board. That brings us to 197 bits total. There has to be at least one piece on the board, so that will work.

Then we need one bit for whose turn it is – brings us to 198 bits .

What about pawn promotion? We can do it a bad way by adding 3 bits per pawn, adding on 42 bits. But then we can notice that most of the time, pawns aren't promoted.

So, for every pawn that is on the board, the bit '0' indicates it is not promoted. If a pawn is not on the board then we don't need a bit at all. Then we can use variable length bit strings for which promotion he has. The most often it will be a queen, so "10" can mean QUEEN. Then "110" means rook, "1110" means bishop, and "1111" means knight.

The initial state will take 198 + 16 = 214 bits , since all 16 pawns are on the board and unpromoted. An end-game with two promoted pawn-queens might take something like 198 + 4 + 4, meaning 4 pawns alive and not promoted and 2 queen pawns, for 206 bits total. Seems pretty robust!

===

Huffman encoding, as others have pointed out, would be the next step. If you observe a few million games, you'll notice each piece is much more likely to be on certain squares. For example, most of the time, the pawns stay in a straight line, or one to the left / one to the right. The king will usually stick around the home base.

Therefore, devise a Huffman encoding scheme for each separate position. Pawns will likely only take on average 3-4 bits instead of 6. The king should take few bits as well.

Also in this scheme, include "taken" as a possible position. This can very robustly handle castling as well – each rook and king will have an extra "original position, moved" state. You can also encode en passant in the pawns this way – "original position, can en passant".

With enough data this approach should yield really good results.

I'd try to use Huffman encoding . The theory behind this is – in every chess game there will be some pieces that will move around a lot, and some that don't move much or get eliminated early. If the starting position has some pieces already removed – all the better. The same goes for squares – some squares get to see all action, while some don't get touched much.

Thus I'd have two Huffman tables – one for pieces, other for squares. They will be generated by looking at the actual game. I could have one large table for every piece-square pair, but I think that would be pretty inefficient because there aren't many instances of the same piece moving on the same square again.

Every piece would have an assigned ID. Since there are 32 different pieces, I would need just 5 bits for the piece ID. The piece IDs are not changing from game to game. The same goes for square IDs, for which I would need 6 bits.

The Huffman trees would be encoded by writing each node down as they are traversed in inorder (that is, first the node is output, then its children from left to right). For every node there will be one bit specifiying whether it's a leaf node or a branch node. If it's a leaf node, it will be followed by the bits giving the ID.

The starting position will simply be given by a series of piece-location pairs. After that there will be one piece-location pair for every move. You can find the end of the starting position descriptor (and the start of the moves descriptor) simply by finding the first piece that is mentioned twice. In case a pawn gets promoted there will be 2 extra bits specifying what it becomes, but the piece ID won't change.

To account for the possibility that a pawn is promoted at the start of the game there will also be a "promotion table" between the huffman trees and the data. At first there will be 4 bits specifying how many pawns are upgraded. Then for each pawn there will be its huffman-encoded ID and 2 bits specifying what it has become.

The huffman trees will be generated by taking into account all the data (both the starting position and the moves) and the promotion table. Although normally the promotion table will be empty or have just a few entries.

To sum it up in graphical terms: 

 <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>)

Added: This could still be optimized. Every piece only has a few legal moves. Instead of simply encoding the target square one could give 0-based IDs for the possible moves of every piece. The same IDs would get reused for every piece, so in total there would be no more than 21 different IDs (the queen can have at most 21 diffferent possible move options). Put this in a huffman table instead of the fields.

This would however present a difficulty in representing the original state. One might generate a series of moves to put each piece in its place. In this case it would be necessary to somehow mark the end of the initial state and start of the moves.

Alternatively they could be placed by using uncompressed 6-bit square IDs.

Whether this would present an overall decrease in size – I don't know. Probably, but should experiment a bit.

Added 2: One more special case. If the game state has NO moves it becomes important to distinguish who moves next. Add one more bit at the end for that. 🙂

[edited after reading the question properly] If you assume every legal position can be reached from the initial position (which is a possible definition of "legal"), then any position can be expressed as the sequence of moves from the start. A snippet of play starting from a non-standard position can be expressed as the sequence of moves needed to reach the start, a switch to turn the camera on, followed by subsequent moves.

So let's call the initial board state the single bit "0".

Moves from any position can be enumerated by numbering the squares and ordering the moves by (start, end), with the conventional 2 square jump indicating castling. There is no need to encode illegal moves, because the board position and the rules are always already known. The flag to turn the camera on could either be expressed as a special in-band move, or more sensibly as an out-of-band move number.

There are 24 opening moves for either side, which can fit in 5 bits each. Subsequent moves might require more or less bits, but the legal moves are always enumerable, so the width of each move can happily grow or expand. I have not calculated, but I imagine 7 bit positions would be rare.

Using this system, a 100 half-move game could be encoded in approximately 500 bits. However, it might be wise to use an opening book. Suppose it contains a million sequences. Let then, an initial 0 indicate a start from the standard board, and a 1 followed by a 20 bit number indicate a start from that opening sequence. Games with somewhat conventional openings might be shortened by say 20 half-moves, or 100 bits.

This is not the greatest possible compression, but (without the opening book) it would be very easy to implement if you already have a chess model, which the question assumes.

To further compress, you'd want to order the moves according to likelihood rather than in an arbitrary order, and encode the likely sequences in fewer bits (using eg Huffman tokens as people have mentioned).

If computational time is not an issue then you could use a deterministic possible position generator to assign unique ids to a given position.

From a given position first generate number of possible positions in a deterministic manor, eg starting bottom left moving to top right. That determines how many bits you'll need for the next move, some situations it could be as little as one. Then when the move is made store just the unique id for that move.

Promotion and other rules simply count as valid moves as long as they are handled in a deterministic way, eg to queen, to rook, to bishop each count as a separate move.

The initial position is hardest and could generate around 250 million possible positions (I think) which would require about 28 bits plus an extra bit to determine whose move it is.

Assuming we know who's turn it is (each turn flips from white to black) the deterministic generator would look something like: 

 for each row for each column add to list ( get list of possible moves( current piece, players turn) )

'get list of possible moves' would do something like: 

 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.

If the king is in check then each 'list of possible xxx moves' only returns valid moves that change the check situation.

Most of the answers overlooked 3 fold repetition. unfortunately for 3 fold repetition you have to store all the positions played so far…

The question required us to store in space efficient manner so we really don't need to store position as long as we can construct it from the list of moves (provided we have standard starting position). We can optimize PGN and thats it we are done. Bellow is a simple scheme.

There are 64 squares on the board, 64 = 2^ 6. If we store only the initial and final square of each move that would take 12 bits (Promotion will be tackled later). Note that this scheme already covers player to move, emphassant, piece captured, castling etc; as of these can be constructed from just replaying the move list.

for promotion we can keep a separate array of vectors which would say "at move N promote to Piece XYZ". we can keep a vector of (int, byte).

It is tempting to optimize (To,From) vector also, Since many of these (To,From) vectors are not posible in chess. 例如。 there wont be a move from e1 to d8 etc. But I couldnt come up with any scheme. Any further ideas are most welcomed.

I've thought about that one for a long time (+- 2hours). And there is no obvious answers.

假设：

  1. Ignoring time state (A player didn't use to have a time limit therefore could force a draw by not playing)
  2. When was the game played?!? It's important because the rules have changed over time (so will assume a modern game in the subsequent point a modern game…) Please refer to dead pawn rule for example (wikipedia has a very famous problem showing it), and if you want to go back in time good luck bishop used to only move slowly and dice used to be used. 大声笑。

… so up to date modern rules it is. First irrespective of repetition and move repitition limit.

-C 25 bytes rounded ( 64b+32*4b+5b= 325b)

=64 bits (something/nothing) +32*4 bits [ 1bit=color{black/withe} +3bit=type of piece{King,Queen,Bishop,kNight,Rook,Pawn,MovedPawn} NB:Moved pawn… eg if it was the last moved pawn in the previous turn indicating that an 'en passant' is feasible. ] +5bit for the actual state (who's turn, en passant, possibility of rooking or not on each sides)

到现在为止还挺好。 Probably can be enhanced but then there would be variable length and promotion to take in consideration!?

Now, following rules are only applicable WHEN a player apllies for a draw, IT IS NOT automatic! So consider this 90 moves without a capture or aa pawn move is feasible if no player calls for a draw! Meaning that all moves need to be recorded… and available.

-D repetion of position… eg state of board as mentioned above (see C) or not… (see following regarding the FIDE rules) -E That leaves the complex problem of 50 move allowance without capture or pawn move there a counter is necessary… However.

So how do you deal with that?… Well really there is no way. Because neither player may want to draw, or realize that it has occurred. Now in case E a counter might suffice… but here is the trick and even reading the FIDE rules (http://www.fide.com/component/handbook/?id=124&view=article) I can't find an answer… what about loss of ability of rooking. Is that a repetition? I think not but then this is a blurred subject not addressed, not clarified.

So here is two rules that are two complex or undefined even to try to encode… Cheers.

So the only way to truly encode a game is to record all from start… which then conflict (or not?) with the "board state" question.

Hope this help… not too much math 🙂 Just to show that some question are not as easy, too open for interpretation or pre-knowledge to be a correct and efficient. Not one I would consider for interviewing as it open too much of a can of worm.

Possible improvement on the starting position in Yacoby's solution

No legal position has more than 16 pieces of each color. The number of ways to place up to 16 black and 16 white pieces on 64 squares is about 3.63e27. Log2(3.63e27)=91.55. This means you can encode the position and color of all pieces in 92 bits. This is less than the 64 bits for position + up to 32 bits for color that Yacoby's solution requires. You can save 4 bits in the worst case at the expense of considerable complexity in the encoding.

On the other hand, it increases the size for positions with 5 or more pieces missing. These positions represent only <4% of all positions, but they are probably a majority of the cases where you want to record a starting position different than the inital position.

This leads to the complete solution

  1. Encode the position and color of pieces according to the method above. 92 bits .
  2. To specify the type of each piece, use a Huffman Code: pawn: '0', rook: '100', knight: '101', bishop: '110', queen: '1110', king: '1111'. This requires (16*1 + 12*3 + 4*4) = 68 bits for a full set of pieces. The full board position can be encoded in 92 + 68 = 160 bits maximum .
  3. Additional game state shoud be added: turn: 1 bit, which castling is possible: 4 bits, “en passant” possible: up to 4 bits (1 bit tells it is the case and 3 bits tell which one). The starting position is encoded in = 160 + 9 = 169 bits
  4. For the list of moves, enumerate all possible moves for a given position and store the position of the move in the list. The list of moves includes all special cases (castling, en passant, and resigning). Use only as many bits as necessary to store the highest position. On average it shouldn't exceed 7 bits per move (16 possible pieces and 8 legal moves per piece on average). In some case, when a move is forced, it requires only 1 bit (move or resign).

There are 32 pieces on the board. Each piece has a position (one in 64 squares). So you just need 32 positive integers.

I know 64 positions hold in 6 bits but I wouldn't do that. I'd keep the last bits for a few flags (dropped piece, queen'ed pawn)

cletus ' answer is good, but he forgot to also encode whose turn it is. It is part of the current state, and is necessary if you're using that state to drive a search algorithm (like an alpha-beta derivative).

I'm not a chess player, but I believe there's also one more corner case: how many moves have been repeated. Once each player makes the same move three times, the game is a draw, no? If so, then you'd need to save that information in the state because after the third repeat, the state is now terminal.

As several others have mentioned you could for each of the 32 pieces you could store which square they're on and if they're on the board or not, this gives 32 * (log2(64) + 1) = 224 bits.

However the bishops can only occupy either the black or white squares so for these you only need log2(32) bits for the position, which give 28 * 7 + 4 * 6 = 220 bits.

And since the pawns don't start at the back and can only move forward, they can only be on 56, it should be possible to use this limitation to reduce the number of bits needed for the pawns.

A board has 64 squares, and can be represented by 64 bits showing if a square is empty or not. We only need piece information if a square has a piece. Since the player + piece takes 4 bits (as shown earlier) we can get the current state in 64 + 4 * 32 = 192 bits. Throw in the current turn and you have 193 bits.

However, we also need to encode the legal moves for each piece. First, we calculate the number of legal moves for each piece, and append that many bits after the piece identifier of a full square. I calculated as follows:

Pawn: Forward, first turn two forward, en passant * 2, promotion = 7 bits. You can combine the first turn forward and promotion into a single bit since they cannot happen from the same position, so you have 6. Rook: 7 vertical squares, 7 horizontal squares = 14 bits Knight: 8 squares = 8 bits Bishop: 2 diagonals * 7 = 14 bits Queen: 7 vertical, 7 horizontal, 7 diagonal, 7 diagonal = 28 bits King: 8 surrounding squares

This still means you would need to map the targeted squares based on the current position, but it (should be) a simple calculation.

Since we have 16 pawns, 4 rooks/knights/bishops, and 2 queens/kings, this is 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = 312 more bits, bringing the total to 505 bits overall.

As for the number of bits required per piece for possible moves, some optimisations could be added to that and the number of bits probably reduced, I just used easy numbers to work with. For example, for sliding pieces you could store how far away they could move, but this would require extra calculations.

Long story short: Only store extra data (piece, etc) when a square is occupied, and only store the minimum number of bits for each piece to represent its legal moves.

EDIT1: Forgot about castling and pawn promotion to any piece. This could bring the total with explicit positions to 557 moves (3 more bits for pawns, 2 for kings)

Each piece can be represented by 4 bits (pawn to king, 6 types), black/white = 12 values

Each square on the board can be represented by 6 bits (x coord, y coord).

Initial positions require maximum of 320 bits (32 pieces, 4 + 6 bits)

Each subsequent move can be represented by 16 bits (from-position, to-position, piece).

Castling would require an extra 16 bits, as it's a dual move.

Queened pawns could be represented by one of the 4 spare values out of 4 bits.

Without doing the maths in detail, this starts to save space after the first move compared to storing 32 * 7 bits (predefined array of pieces) or 64 * 4 bits (predefined assignment of squares)

After 10 moves on both sides, the maximum space required is 640 bits

…but then again, if we identify each piece uniquely (5 bits) and add a sixth bit for flagging queened pawns, then we only need piece-id + to-position for each move. This changes the calculation to…

Initial positions = max 384 bits (32 pieces, 6 + 6 bits) Each move = 12 bits (to-position, piece-id)

Then after 10 moves on each side the maximum space required is 624 bits

Like Robert G, I'd tend to use PGN since it's standard and can be used by a wide range of tools.

If, however, I'm playing a chess AI that's on a distant space probe, and thus every bit is precious, this is what I'd do for the moves. I'll come bock to encoding the initial state later.

The moves don't need to record state; the decoder can take keep track of state as well as what moves are legal at any given point. All the moves need to record is which of the various legal alternatives is chosen. Since players alternate, a move doesn't need to record player color. Since a player can only move their own color pieces, the first choice is which piece the player moves (I'll come back to an alternative that uses another choice later). With at most 16 pieces, this requires at most 4 bits. As a player loses pieces, the number of choices decreases. Also, a particular game state may limit the choice of pieces. If a king can't move without placing itself in check, the number of choices is reduced by one. If a king is in check, any piece that can't get the king out of check isn't a viable choice. Number the pieces in row major order starting at a1 (h1 comes before a2).

Once the piece is specified, it will only have a certain number of legal destinations. The exact number is highly dependent on board layout and game history, but we can figure out certain maximums and expected values. For all but the knight and during castling, a piece can't move through another piece. This will be a big source of move-limits, but it's hard to quantify. A piece can't move off of the board, which will also largely limit the number of destinations.

We encode the destination of most pieces by numbering squares along lines in the following order: W, NW, N, NE (black side is N). A line starts in the square furthest in the given direction that's legal to move to and proceeds towards the. For an unencumbered king, the list of moves is W, E, NW, SE, N, S, NE, SW. For the knight, we start with 2W1N and proceed clockwise; destination 0 is the first valid destination in this order.

  • Pawns: An unmoved pawn has 2 choices of destinations, thus requiring 1 bit. If a pawn can capture another, either normally or en passant (which the decoder can determine, since it's keeping track of state), it also has 2 or 3 choices of moves. Other than that, a pawn can only have 1 choice, requiring no bits. When a pawn is in its 7 th rank, we also tack on the promotion choice. Since pawns are usually promoted to queens, followed by knights, we encode the choices as:
    • queen: 0
    • knight: 10
    • bishop: 110
    • rook: 111
  • Bishop: at most 13 destinations when at {d,e}{4,5} for 4 bits.
  • Rook: at most 14 destinations, 4 bits.
  • Knights: at most 8 destinations, 3 bits.
  • Kings: When castling is an option, the king has it's back to S and can't move downwards; this gives a total of 7 destinations. The rest of the time, a king has at most 8 moves, giving a maximum of 3 bits.
  • Queen: Same as choices for bishop or rook, for a total of 27 choices, which is 5 bits

Since the number of choices isn't always a power of two, the above still wastes bits. Suppose the number of choices is C and the particular choice is numbered c , and n = ceil(lg( C )) (the number of bits required to encode the choice). We make use of these otherwise wasted values by examining the first bit of the next choice. If it's 0, do nothing. If it's 1 and c + C < 2 n , then add C to c . Decoding a number reverses this: if the received c >= C , subtract C and set the first bit for the next number to 1. If c < 2 n – C , then set the first bit for the next number to 0. If 2 n – C <= c < C , then do nothing. Call this scheme "saturation".

Another potential type of choice that might shorten the encoding is to choose an opponents piece to capture. This increases the number of choices for the first part of a move, picking a piece, for at most an additional bit (the exact number depends on how many pieces the current player can move). This choice is followed by a choice of capturing piece, which is probably much smaller than the number of moves for any of the given players pieces. A piece can only be attacked by one piece from any cardinal direction plus the knights for a total of at most 10 attacking pieces; this gives a total maximum of 9 bits for a capture move, though I'd expect 7 bits on average. This would be particularly advantageous for captures by the queen, since it will often have quite a few legal destinations.

With saturation, capture-encoding probably doesn't afford an advantage. We could allow for both options, specifying in the initial state which are used. If saturation isn't used, the game encoding could also use unused choice numbers ( C <= c < 2 n ) to change options during the game. Any time C is a power of two, we couldn't change options.

Thomas has the right approach for encoding the board. However this should be combined with ralu's approach for storing moves. Make a list of all possible moves, write out the number of bits needed to express this number. Since the decoder is doing the same calculation it knows how many are possible and can know how many bits to read, no length codes are needed.

Thus we get 164 bits for the pieces, 4 bits for castling info (assuming we are storing a fragment of a game, otherwise it can be reconstructed), 3 bits for en passant eligibility info–simply store the column where the move occurred (If en passant isn't possible store a column where it's not possible–such columns must exist) and 1 for who is to move.

Moves will typically take 5 or 6 bits but can vary from 1 to 8.

One additional shortcut–if the encode starts with 12 1 bits (an invalid situation–not even a fragment will have two kings on one side) you abort the decode, wipe the board and set up a new game. The next bit will be a move bit.

Algorithm should deterministically enumerate all possible destinations at each move. Number of destinations:

  • 2 bishops, 13 destinations each = 26
  • 2 rooks, 14 destinations each = 28
  • 2 knights, 8 destinations each = 16
  • queen, 27 destinations
  • king , 8 destinations

8 paws could all become queens in worst (enumeration-wise) case, thus making largest number of possible destinations 9*27+26+28+16+8=321. Thus, all destinations for any move can be enumerated by a 9 bit number.

Maximum number of moves of both parties is 100 (if i'm not wrong, not a chess player). Thus any game could be recorded in 900 bits. Plus initial position each piece can be recorded using 6 bit numbers, which totals to 32*6 =192 bits. Plus one bit for "who moves first" record. Thus, any game can be recorded using 900+192+1=1093 bits.

Storing the board state

The simplest way I thought of is too first have a array of 8*8 bits representing the location of each piece (So 1 if there is a chess piece there and 0 if there isn't). As this is a fixed length we don't need any terminator.

Next represent every chess piece in order of its location. Using 4 bits per piece, this takes 32*4 bits (128 in total). Which is really really wasteful.

Using a binary tree, we can represent a pawn in one byte, a knight and rook and bishop in 3 and a king and queen in 4. As we also need to store the color of the piece, which takes an extra byte it ends up as (forgive me if this is wrong, I have never looked at Huffman coding in any detail before):

  • Pawn : 2
  • Rook: 4
  • Knight: 4
  • Bishop: 4
  • King: 5
  • Queen: 5

Given the totals: 

 2*16 + 4*4 + 4*4 + 4*4 + 2*5 + 2*5 = 100

Which beats using a fixed size set of bits by 28 bits.

So the best method I have found is to store it in a 8 2 + 100 bit array 

 8*8 + 100 = 164

Storing Moves
The first thing we need to know with is which piece is moving to where. Given that there are at maximum 32 pieces on the board and we know what each piece is, rather than an integer representing the square, we can have an integer representing the piece offset, which means we only have to fit 32 possible values to represent a piece.

Unfortunately there are various special rules, like castling or overthrowing the king and forming a republic (Terry Pratchett reference), so before we store the piece to move we need a single bit indicating if it is a special move or not.

So for each normal move we have a necessary 1 + 5 = 6 bits. (1 bit type, 5 bits for the piece)

After the piece number has been decoded, we then know the type of piece, and each piece should represent its move in the most efficient way. For example (If my chess rules are up to scratch) a pawn has a total of 4 possible moves (take left, take right, move one forward, move two forward).
So to represent a pawn move we need '6 + 2 = 8' bits. (6 bit for initial move header, 2 bits for what move)

Moving for the queen would be more complex, in that it would be best to have a direction (8 possible directions, so 3 bits) and a total of 8 possible squares to move to for each direction (so another 3 bits). So to represent moving a queen it would require 6 + 3 + 3 = 12 bits.

The last thing that occurrences to me is that we need to store which players turn it is. This should be a single bit (White or black to move next)

Resultant Format
So the file format would look something like this

[64 bits] Initial piece locations
[100 bits max] Initial pieces [1 bit] Player turn
[n bits] Moves

Where a Move is
[1 bit] Move type (special or normal)
[n bits] Move Detail

If the Move is a normal move, the Move Detail looks something like
[5 bits] piece
[n bits] specific piece move (usually in the range of 2 to 6 bits]

If it is a special move
It should have an integer type and then any additional information (like if it is castling). I cannot remember the number of special moves, so it may be OK just to indicate that it is a special move (if there is only one)

In the base case of the initial board plus subsequent moves, consider the following.

Use a chess program to assign probabilities to all possible moves. For example, 40% for e2-e4 20% for d2-d4, and so on. If some moves are legal but not considered by that program, give them some low probability. Use arithmetic coding to save which choice was taken, which will be some number between 0 and 0.4 for the first move, 0.4 and 0.6 for the second, and so on.

Do the same for the other side. For example, if there is a 50% chance of e7-e5 as the response to e2-e4 then the encoded number will be between 0 and 0.2. Repeat until the game is done. The result is a potentially very small range. Find the binary fraction with the smallest base which fits in that range. That's arithmetic coding.

This is better than Huffman because it can be thought of as fractional bit encoding (plus some at the end of the game to round up to a whole bit).

The result should be more compact than Huffman, and there are no special cases for promotion, en passant, the 50 rule move, and other details because they are handled by the chess evaluation program.

To replay, again use the chess program to evaluate the board and assign all probabilities to each move. Use the arithmetic encoded value to determine which move was actually played. Repeat until done.

If your chess program is good enough, you can get better compression with a two-state encoder, where the probabilities are defined based on moves for both black and white. In the most extreme case of some 200+ states, this encodes the entire set of all possible chess games, and is therefore not feasible.

This is pretty much a different way of saying what Darius already wrote, only with a bit of example of how arithmetic coding might work, and a real example of using an existing chess program to help evaluate the probability of the next move(s).

    Interesting Posts

    骑士的最短path棋问题

    实现一个象棋引擎有多难？

    有一个完美的国际象棋algorithm吗？

    开发国际象棋程序时初始化方向数组的意义是什么？