有效存储国际象棋的位置

Question

我已经阅读了大量与此问题相关的网页点击,但我仍然没有遇到任何明确的答案.

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

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

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

其中一个讨论者谈论在方形矩阵上编码片段,使用4 x 64位加上一些位用于附加信息(castling,en passant等):有六件(Pawn,Rook,Knight,Bishop,Queen,King)加上一个空的正方形,即3位(2 ^ 3),并且还有一个位用于颜色.

总共将有4个数字,每个64位,加上一些额外的信息.

问题:还有其他更有效的存储国际象棋位置的方法吗？

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

谢谢,阿德里安

Answer 1

棋盘上有 32 个棋子，64 个方格。平方索引可以用 6 位数字表示，因此要表示每个部分的位置，您需要 32 个 6 位数字，或总共 192 位，小于 4x64。

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

由于棋盘上也可能完全没有棋子，您应该从国王的位置开始，因为它们总是在那里 - 然后，将另一个棋子的位置编码为与国王相同的位置将意味着该棋子已被占用。

编辑：

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

• 国王、王后、骑士和车可以在棋盘上的任何位置（64 个位置）
• 主教每人限制在 32 个位置
• Pawn 限制在 21、26、30、32、32、30、26 和 21 个位置（AH 列）。

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

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