判断两个棋局是否相等

Question

我目前正在调试国际象棋变体引擎的换位表，可以在其中放置棋子（即最初不在棋盘上）。我需要知道我发生按键碰撞的频率。我将片段列表与常用的哈希数据一起保存在每个表索引中。我确定两个位置是否相等的简单解决方案在换位上失败，因为我正在线性比较两个片段列表。

请不要建议我应该以板为中心而不是以件为中心进行存储。由于可放置和捕获的棋子具有独特的性质，我必须存储棋子列表。这些状态中的棋子就像占据了一个重叠且没有位置的位置。 请查看有关如何存储碎片的说明。

// [Piece List]
// 
// Contents: The location of the pieces.
//           Values 0-63 are board indexes; -2 is dead; -1 is placeable
// Structure: Black pieces are at indexes 0-15
//            White pieces are at indexes 16-31
//            Within each set of colors the pieces are arranged as following:
//            8 Pawns, 2 Knights, 2 Bishops, 2 Rooks, 1 Queen, 1 King
// Example: piece[15] = 6 means the black king is on board index 6
//          piece[29] = -2 means the white rook is dead
char piece[32];

当棋子以不同的顺序移动，但最终结果是相同的棋盘位置时，就会发生换位。例如以下位置是相等的：

1) first rook on A1; second rook on D7
2) first rook on D7; second rook on A1

以下是非优化的通用算法；内部循环类似于另一个一般问题，但增加了限制，0-63 中的值只会发生一次（即每平方仅一件）。

for each color:
    for each piece type:
        are all pieces in the same position, disregarding transpositions?

以下比较由于换位而不起作用。我需要的是一种检测换位是否相等并且仅报告实际不同位置的方法。

bool operator==(const Position &b)
{
    for (int i = 0; i < 32; i++)
        if (piece[i] != b.piece[i])
            return false;
    return true;
}

性能/内存是一个考虑因素，因为桌子每轮都会有超过 100K 次点击（其中键相等），并且典型的桌子有 100 万个项目。从今以后，我正在寻找比复制和排序列表更快的东西。

Answer 1

对计算机国际象棋进行了大量研究，为位置创建唯一哈希的方法是一个众所周知的问题，几乎每个国际象棋引擎都使用通用解决方案。

您需要做的是使用 Zobrist Hashing 创建一个独特的（不是真正独特的，但我们'稍后会看到为什么这在实践中不是问题）每个不同位置的关键。 此处解释了应用于国际象棋的算法。

当您启动程序时，您将创建我们所说的 zobrist 密钥。这些是每个棋子/方块对的 64 位随机整数。在 C 中，您将有一个像这样的二维数组：

unsigned long long zobKeys[NUMBER_OF_PIECES][NUMBER_OF_SQUARES];

每个密钥都使用一个好的随机数生成器进行初始化（警告：gcc 或 VC++ 提供的随机数生成器不够好，请使用 梅森旋转器）。

当棋盘为空时，您可以任意将其哈希键设置为 0，然后当您在棋盘上添加棋子（例如 A1 上的 Rook）时，您还可以通过将 A1 上的车的 zobrist 键与哈希键进行异或来更新哈希键董事会的。像这样（在 C 中）：

boardHash = boardHash ^ zobKeys[ROOK][A1];

如果您稍后从这个方块中删除车，您需要反转您刚刚所做的事情，因为异或可以通过再次应用来反转，所以当您删除该棋子时，您可以简单地再次使用相同的命令：

boardHash = boardHash ^ zobKeys[ROOK][A1];

如果你移动一个棋子，假设A1上的车到了B1，你需要做两次异或，一次删除A1上的车，一次添加B2上的车。

boardHash = boardHash ^ zobKeys[ROOK][A1] ^ boardHash ^ zobKeys[ROOK][B1];

这样，每次修改主板时，您也会修改哈希值。这是非常有效的。您还可以通过异或与棋盘上所有棋子相对应的 zobKey，每次从 scatch 计算哈希值。您还需要对可以被路过的棋子的位置和双方的掠夺能力状态进行异或。您可以用同样的方式为每个可能的值创建 zobris 键。

该算法不能保证每个位置都有唯一的散列，但是，如果您使用良好的伪随机数生成器，发生碰撞的几率非常低，即使您让引擎玩一辈子，也几乎没有机会曾经发生过的碰撞。

编辑：我只是红色，你正在尝试为具有棋盘外棋子的国际象棋变体实现此功能。 Zobrist 哈希仍然是适合您的解决方案。您必须找到一种方法将这些信息合并到哈希中。例如，您可以拥有一些用于棋盘外棋子的钥匙：

unsigned long long offTheBoardZobKeys[NUMBER_OF_PIECE][MAXIMUM_NUMBER_OF_ON_PIECE_TYPE];

如果您有 2 个爪子离开棋盘并将其中一个棋子放在 a2 上，您将必须执行 2 次操作：

// remove one pawn from the off-the-board
boardHash = boardHash ^ offTheBoardZobKeys[WHITE_PAWN][numberOfWhitePawsOffTheBoard];

// Put a pawn on a2
boardHash = boardHash ^ zobKeys[WHITE_PAWN][A2];

Answer 2

为什么不在数据库中保留一个与棋盘布局相对应的 64 字节字符串呢？每种类型的棋子，包括“无棋子”，都代表一个字母（两种颜色的大写字母不同，即 ABC 代表黑色，abc 代表白色）。板比较归结为简单的字符串比较。

一般来说，从棋盘的角度而不是棋子的角度进行比较，将摆脱你的换位问题！

Answer 3

“不建议我应该以板为中心而不是以件为中心进行存储”。

你太专注于不这样做，以至于错过了显而易见的解决方案。 比较特定于主板的情况。要比较两个位置列表 L1 和 L2，请将 L1 的所有元素放在（临时）板上。然后，对于 L2 的每个元素，检查它是否存在于临时板上。如果 L2 的元素不存在于棋盘上（因此也不存在于 L1 中），则返回不相等。

如果移除L2中的所有元素后，棋盘上仍然剩下棋子，那么L1一定有L2中不存在的元素，并且列表是相等的。仅当临时板随后为空时，L1 和 L2 才相等。

一种优化是首先检查L1和L2的长度。这不仅可以快速发现许多差异，还消除了从 baord 中删除 L2 的元素以及最后的“空板”检查的需要。仅需要捕获 L1 是 L2 的真正超集的情况。如果 L1 和 L2 具有相同的大小，并且 L2 是 L1 的子集，则 L1 和 L2 必须相等。

Answer 4

你对存储棋盘状态的主要反对意见是你有一袋无位置的棋子。为什么不维护一个棋盘+一个棋子向量呢？这将满足您的要求，并且它的优点是它是您所在州的规范表示。因此，您不需要排序，您可以在内部使用此表示形式，也可以在需要比较时转换为它：

Piece-type in A1
... 63 more squares
Number of white pawns off-board
Number of black pawns off-board
... other piece types

Answer 5

从整体角度来看，您可以这样做：

for each color:
    for each piece type:
        start new list for board A
        for each piece of this piece type on board A
            add piece position to the list
        start new list for board B
        for each piece of this piece type on board B
            add piece position to the list
        order both lists and compare them

优化可以通过不同的方式进行。您的优势是：一旦您发现差异：您就完成了！

例如，您可以通过总结两块板的所有部分的所有索引来开始快速而肮脏的检查。总和应该相等。如果没有，那就有区别了。

如果总和相等，您可以快速比较独特棋子（国王和王后）的位置。然后你可以写出（在有些复杂的 if 语句中）成对的部分的比较。然后您所要做的就是使用上述方法比较棋子。

Answer 6

第三种选择（我真的希望对一个问题发布 3 个答案是可以的，从 stackoverflow 的角度来看；））：

始终按索引顺序保留相同类型的棋子，即列表中的第一个 pawn 应该始终具有最低的值指数。如果发生的移动打破了这一点，只需翻转列表中的棋子位置即可。使用起来看不出区别，棋子就是棋子。

现在，在比较位置时，您可以确定不存在换位问题，并且可以仅使用建议的 for 循环。

Answer 7

考虑到您选择的游戏状态表示，您必须以一种或另一种方式对黑色棋子的索引、白色棋子的索引等进行排序。如果你在创建新游戏状态的过程中不这样做，你就必须在比较时这样做。因为您最多只需要对 8 个元素进行排序，所以可以非常快地完成。

有几种替代方法可以表示您的游戏状态：

• 将每种类型的棋子表示为位字段。前64位表示该棋盘坐标上有该类型的棋子；那么有 n 位“可放置”槽和 n 位“死”槽，必须从一侧填充（n 是该类型的件数）。

或者

• 给每种类型的棋子一个唯一的ID，例如白色棋子可以是0x01。游戏状态由 64 个棋子（棋盘）的数组和两个“可放置”棋子和“死”棋子的有序列表组成。在插入和删除时可以非常有效地维护这些列表的顺序。

这两种选择不会有换位问题。

不管怎样，我的印象是，当你应该首先让它发挥作用时，你却在摆弄微观优化。