database - 有效存储国际象棋位置

Question

我已经阅读了大量与此问题相关的网络点击量，但我仍然没有找到任何明确的答案。

我想做的是制作一个国际象棋位置数据库，能够识别换位(通常是哪些棋子在哪些方格上)。

编辑:它还应该能够识别相似(但不完全相同)的位置。

这是大约 20 年前的讨论(当时空间 是个问题): https://groups.google.com/forum/#!topic/rec.games.chess.computer/wVyS3tftZAA

其中一位讨论者谈到了在方阵上编码片段，使用 4 x 64 位加上更多的位来提供附加信息(caSTLing、en passant 等):有六 block 棋子(兵、车、马、象、王后、王)加上一个空方 block ，即 3 位 (2^3)，还有一位表示棋子的颜色。

总共有 4 个 64 位数字，外加一些附加信息。

问题:是否有其他更有效的方式来存储国际象棋位置？

我应该提到这个问题是以数据库为中心，而不是以游戏为中心(即我唯一的兴趣是有效地存储和检索，而不是创建任何 AI 或生成任何 Action )。

谢谢，阿德里安

Answer 1

棋盘上有 32 个棋子，64 个方格。方形索引可以用6位数字表示，所以要表示每 block 的位置需要32个6位数字，总共192位，小于4x64。

您可以通过意识到并非所有位置都是可能的(例如，棋子无法到达其自身颜色的末行)并在这些情况下使用少于 6 位的位置来做得更好。此外，一个位置已经被另一个棋子占据，其他棋子无法使用该位置。

因为一 block 棋子也可能完全从棋盘上消失，你应该从国王的位置开始，因为它们总是在那里 - 然后，将另一 block 棋子的位置编码为与国王相同的位置意味着该棋子已经拍摄。

编辑:

对棋子可能位置的简短分析:

• 国王、王后、骑士和车可以在棋盘上的任何位置(64 个位置)
• 每个主教被限制在 32 个职位上
• 棋子限制在 21、26、30、32、32、30、26 和 21 个位置(A-H 列)。

因此，这组合法的国际象棋位置可以用从零到 (64^12 * 32^4 * 21^4 * 26^4 * 30^4 * 32^8)-1 的整数简单描述，或 391935874857773690005106949814449284944862535808450559999，适合 188 位。对一个位置进行编码和解码非常简单——但是，有多个数字解码到相同的位置(例如，白骑士 1 在 B1，白骑士 2 在 G1；白骑士 1 在 G1，白骑士 2 在B1).

由于没有两 block 可以占据同一个方 block ，因此有更严格的限制，但编码和解码都有点困难，因此在实际应用中可能没有用。此外，上面显示的数字非常接近 2^188，所以我认为即使是这种更严格的编码也无法放入 187 位。