并不是一个严格的问题，更像是一个谜题...
这些年来，我参与过一些新员工技术面试。除了问"你知道X技术吗"这样的标准问题外，我还尝试了解他们如何解决问题。通常，我会在面试前一天通过电子邮件发送问题，并期望他们在隔天想出解决方案。
通常结果会相当有趣——错误的，但很有趣——如果他们能够解释为什么采取了特定的方法，那么他们仍然会得到我的推荐。
所以我想把其中一个问题提供给Stack Overflow的听众。
问题：您能想到最节省空间的方式来编码国际象棋游戏（或其子集）的状态吗？也就是说，给定一个棋盘并合法地排列棋子，对游戏中所有初始状态和所有后续的合法移动进行编码。
答案不需要包含代码，只需描述您将使用的算法即可。
编辑：正如其中一位发布者所指出的那样，我没有考虑移动之间的时间间隔。如有需要，请自由添加这个作为可选项 :)
编辑2：仅作进一步澄清...请记住，编码器/解码器是具有规则意识的。唯一真正需要存储的是玩家的选择——任何其他东西都可以被编码器/解码器认为是已知的。
编辑3：在这里挑选一个赢家会很困难:) 有很多好答案！
更新：我非常喜欢这个主题，所以我写了编程谜题、国际象棋局面和哈夫曼编码。如果你读完这篇文章，我已经确定了存储完整游戏状态的唯一方法是通过存储完整移动列表。继续阅读了解原因。因此，我对棋子布局的问题进行了稍微简化的版本。
这张图片展示了起始的国际象棋局面。国际象棋在一个8x8的棋盘上进行，每个玩家都以相同的16个棋子开始比赛，包括8个兵，2个车，2个马，2个象，1个皇后和1个国王，如下图所示：
位置通常用列字母加行数字表示，因此白方的皇后位于d1。移动通常以象棋代数记谱的形式存储，这种方法是明确无误的，并且通常只指定必要的最小信息。考虑以下开局：
它的翻译如下：
棋盘看起来像这样：
那么缺少什么或含糊不清呢？事实证明有很多。
第一件需要确定的事情是，你是在存储游戏状态还是棋子在棋盘上的位置。仅编码棋子的位置是一回事，但问题中提到了“所有随后的合法移动”。问题也没有提及知道此刻为止的移动。我将解释这实际上是个问题。
游戏进展如下：
棋盘如下所示：
白方可以选择王车易位。这需要满足国王和相关的车从未移动过，因此需要存储每一侧国王和车是否移动。如果它们不在起始位置上，那么它们已经移动，否则需要指定。
有几种处理这个问题的策略。
首先，我们可以存储额外的6位信息（对于每个车和国王各1位），以指示该棋子是否移动。如果正确的棋子恰好在其中一个6个方格中，则只需为这六个方格中的一个存储一位即可简化此过程。或者，我们可以将每个未移动的棋子视为另一种棋子类型，这样每边就不是6种棋子类型（兵、车、马、象、后和王），而是8种（添加未移动的车和未移动的国王）。
国际��棋中另一条奇特且常被忽略的规则是吃过路兵。
游戏已经进展。
黑方的b4兵现在可以选择将其移动到c3并取下白方的c4兵。这只会在第一次机会发生，这意味着如果黑方现在放弃该选项，则下一步就无法进行。因此我们需要存储这个信息。
如果我们知道上一步棋，我们肯定可以回答是否可能进行吃过路兵。或者，我们可以存储每个兵在第四排是否刚刚向前双步移动。或者，我们可以查看棋盘上每个可能的过路兵位置，并有一个标志来指示是否可能进行过路兵。
2256约等于1.16e77。1364约等于1.96e71，需要237位存储空间。仅节省了7.5％的成本，代价是显著增加的操作成本。
在合法的棋盘上，某些棋子不能出现在某些方格中。例如，兵卒不能出现在第一或第八排，将这些方格的可能性减少到11个。这将使可能的棋盘减少到1116 x 1348 = 1.35e70（约），需要233位存储空间。
实际编码和解码这些值为十进制数（或二进制数）有点复杂，但可以可靠地完成，留给读者作为练习。
前两种方法都可以描述为固定宽度字母表编码。字母表的11、13或16个成员中的每一个都被替换为另一个值。每个“字符”具有相同的宽度，但是考虑到每个字符的出现概率不相等，因此可以提高效率。
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
至于兵的位置，兵只能在48个可能的格子上（不像其他棋子有64个）。因此，最好不要浪费使用每个兵6位的额外16个值。因此，如果你有8个兵，就有488种可能性，相当于28,179,280,429,056。你需要45位来编码这么多的值。
这是每方105位或总共210位。然而，起始位置是这种方法的最坏情况，随着你移除棋子，它会变得更好。
应该指出，可能性少于488，因为兵不能都在同一个格子上。第一个有48种可能性，第二个有47种，依此类推。48 x 47 x … x 41 = 1.52e13 = 44位存储。
您可以通过消除被其他棋子占据的方格（包括对方）来进一步改善这一点，这样您就可以先放置白色非兵棋子，然后是黑色非兵棋子，接着是白色兵和最后是黑色兵。在起始位置上，这将减少白色的存储需求为44位，黑色的存储需求为42位。最好将国际象棋游戏存储在一种易于阅读且标准的格式中。
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
如果您想将其缩小，那么只需压缩即可。工作完成！
好的难题！
我看到大多数人都在存储每个棋子的位置。为什么不采用更简单的方法，存储每个方格的内容？这会自动处理晋升和被吃掉的棋子。
而且它允许使用Huffman编码。实际上，棋盘上的初始棋子频率几乎完美符合这一点：一半的方格为空，其余方格中有一半是兵等等。
考虑到每个棋子的频率，我在纸上构建了一个Huffman树，这里不再重复。结果如下，其中c代表颜色（白=0，黑=1）：
对于整个初始局面，我们有：
总计：164位用于初始棋盘状态。比当前最高票答案的235位要少得多。而且随着游戏的进行（除了晋升之后），它只会变得更小。
我只关注了棋子在棋盘上的位置；额外状态（轮到谁走棋，谁已经王车易位，吃过路兵等等）将需要分别编码。也许最多还有16位，因此整个游戏状态需要180位。
可能的优化：
棋面状态 - 18 字节
合法棋面数量估计为 1043
枚举所有棋面虽然不切实际，但这至少说明需要 144 位来存储一个棋面。另外还需要一位来指示下一步是哪一方行动。
每个棋面通常有30-40个合法着法，但可能高达218个。让我们枚举每个棋面的所有合法着法，现在每个着法可以编码成一个字节。
我们仍然有足够的空间来存储特殊着法，例如使用 0xFF 表示认输。
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
在每个位置获取所有可能移动的数量。
下一步移动的生成方式为：
index_current_move =n % num_of_moves //this is best space efficiency
n=n/num_of_moves
可证明的最佳空间效率，用于存储随机生成的游戏，平均每步需要约5位，因为有30-40个可能的移动。组装存储只是以相反的顺序生成n。
存储位置更难破解，因为存在很大的冗余性。（一个站点上可能有多达9个皇后，但在这种情况下没有兵，如果主教在棋盘上，则在不同颜色的方格上）但通常就像存储相同的棋子组合在剩下的方格上一样。
编辑：
保存移动的关键在于仅存储移动的索引。我们应该添加从确定性移动生成器（位置）生成的移动索引，而不是存储Kc1-c2并尝试减少此信息。
在每个移动中，我们添加大小信息。
num_of_moves = get_number_of_possible_moves(postion) ;
在池中，这个数字无法减少
生成信息池是
n=n*num_of_moves+ index_current_move
额外说明
如果在最后一个位置只有一种可用的移动方式，则将其保存为之前已经强制执行的移动次数。 例如：如果起始位置对于每个方向都有1次强制移动（2次移动），并且我们想将其保存为一次移动游戏，则在池n中存储1。
存储信息池的示例
假设我们已知起始位置并进行了3次移动。
在第一步中，有5种可用的移动方式，我们选择移动索引4。在第二步中，有6种可用的移动方式，我们选择位置索引3，而在第3步中，该方向有7种可用的移动方式，他选择了选择移动索引2。
矢量形式; 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
index=15%6=3
n=15/6=2
我们选择移动索引3，这将使我们到达一个位置，有7个可能的移动。
index=2%7=2
n=2/7=0
如果黑白兵在同一列且面对面，那么每个兵都面对着另一个兵，这意味着白兵最多只能在第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位）。
吃过路兵：当我们存储8个“吃过路兵”的可能性之一时，我们知道黑兵的位置并减少了信息冗余（如果是白方走棋并且有第三个兵可以吃过路兵，那么黑兵就在c5上，白兵要么在c2、c3或c4上）。因此，我们得到了3而不是C(6/2)，失去了2.3位。如果我们还存储了可以进行“吃过路兵”的一侧（3种可能性-左、右、两者），并且我们知道可以进行“吃过路兵”的兵的位置（例如，从之前的“吃过路兵”例子中，黑色兵在c5上，可以在左边、右边或两边。如果它在一个方向上，我们有2*3（3用于存储可能性，2个可能的走法为黑色兵在第7或第6排），而不是C(6/2)，我们减少了1.3位；如果在两侧，我们减少了4.2位。这样，我们每个“吃过路兵”可以减少2.3+1.3=3.6位。
象：象只能在相反的方格上，这使每个方格的信息冗余减少了1位。
如果没有棋子被吃掉，我们需要150-56-4-3.6-2=85位来存储国际象棋的位置。
如果考虑到吃子和升变，那么可能需要的位数也不会多很多（但如果有人觉得这篇长帖有用，我会在以后写关于这个的内容）。
优化典型人类玩家玩的典型游戏的平均情况大小会增加趣味性，而不是最坏情况。 （问题陈述没有说明哪种情况； 大多数回答都假设最坏情况。）
对于移动序列，请让一个好的国际象棋引擎从每个位置生成移动; 它将产生一个按其质量排名排序的k个可能移动的列表。 人们通常比随机移动更经常选择好的移动，因此我们需要从列表中的每个位置学习到人们选择“好”移动的概率的映射。 使用这些概率（基于某个互联网国际象棋数据库中的游戏语料库），使用算术编码对移动进行编码。 （解码器必须使用相同的国际象棋引擎和映射。）
对于起始位置，ralu的方法是可行的。如果我们有一种方式通过概率加权来选择，例如，棋子通常以保护彼此的配置出现，而不是随机的，我们可以在那里使用算术编码进行细化。更难的是看到如何轻松地将该知识纳入其中。一个想法：退回到上面的移动编码，从标准开局位置开始，找到以所需棋盘结束的序列。（您可以尝试具有启发式距离的A *搜索，该距离等于棋子从其最终位置的距离之和，或类似的东西。）这样可以通过过度指定移动序列与利用下棋知识获得效率之间的平衡来换取一些低效率。（您可以通过消除会导致在A *搜索中出现先前探索过的位置的移动选择来挽回一些低效率：这些移动选择在算术编码中可能会获得重量0。）昨晚我看到了这个问题，它引起了我的兴趣，所以我躺在床上想出了解决方案。我的最终答案与int3的答案非常相似。
假设是标准的国际象棋游戏，并且您不编码规则（例如白色总是先走），那么您可以通过仅编码每个棋子的移动来节省很多空间。
总共有32个棋子，但在每次移动中，您知道哪种颜色正在移动，因此只需要关注16个格子，即这一步移动的棋子，只需要4位。
每个棋子只有有限的移动集，您可以以某种方式枚举它们。
对于晋升，有4种棋子可供选择（车，象，马，后），因此在该移动中，我们需要添加2位以指定它。我认为所有其他规则都会自动处理（例如吃过路兵）。
首先，在捕获一个颜色的8个棋子后，您可以将棋子编码减少到3位，然后是4个棋子的2位，以此类推。
但主要的优化是仅枚举游戏中每个点可能的移动。假设我们将兵的移动存储为{00, 01, 10, 11}，分别表示向前1步，向前2步，左对角线和右对角线。如果某些移动不可能，我们可以从本轮编码中删除它们。
我们知道每个阶段的游戏状态（通过跟踪所有移动），因此在读取哪个棋子将移动后，我们总是可以确定需要读取多少位。如果我们意识到兵在这一点上只能向右对角线吃子或向前移动一步，我们就知道只需要读取1位。
简而言之，上面每个棋子的位存储是最大值。几乎每个移动都会有较少的选项，通常也会有更少的位数。
在棋盘上的位置可以用7个比特位（0-63，以及1个值指定它不再在棋盘上）来定义。因此，对于棋盘上的每个棋子，都要指定其所在位置。
32个棋子 * 7个比特位 = 224个比特位
编辑： 正如Cadrian所指出的那样...我们还有“兵升为后”的情况。我建议我们在末尾添加额外的比特位，以指示哪些兵被晋升了。
因此，对于每个被晋升的兵，我们在224个比特位后跟随5个比特位，指示被晋升的兵的索引，如果是列表的结尾，则为11111。
因此，最小情况（没有晋升）是224个比特位+5个比特位（没有晋升）。对于每个被晋升的兵，增加5个比特位。
编辑： 正如shaggy frog所指出的，我们需要另外一个比特位来指示轮到谁了 ;^)