确定两个国际象棋局面是否相等。

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;
}

性能/内存是需要考虑的因素，因为该表格每次操作都会有超过100,000个命中（键相等），并且典型的表格包含1百万项。因此，我正在寻找比复制和排序列表更快速的解决方案。

- Justin

Answer 1

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

您需要做的是使用Zobrist Hashing为每个不同的位置创建一个唯一（实际上并不是真正的唯一，但稍后我们会看到这在实践中不是问题）的键。这里介绍了应用于国际象棋的算法。

当您启动程序时，您需要创建我们称之为zobrist密钥。对于每个棋子/方格对，这些都是64位的随机整数。在C语言中，您将拥有以下类似的二维数组：

unsigned long long zobKeys[NUMBER_OF_PIECES][NUMBER_OF_SQUARES];

每个密钥都使用良好的随机数生成器进行初始化（警告：gcc或VC ++提供的随机数生成器不够好，使用Mersenne Twister的实现）。

当棋盘为空时，您将其哈希键任意设置为0，然后当您在棋盘上添加一个棋子时，比如在A1上放置一个车，您还会通过异或A1上的Zobrist密钥与棋盘的哈希键来更新哈希键。像这样（用C语言表示）：

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

如果您稍后从此方格中移除车，则需要撤销刚才所做的操作，因为异或可以通过再次应用它来撤销，因此在您删除棋子时，可以使用相同的命令：

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

如果你想移动某个棋子，比如车A1到B1的时候，你需要进行两次异或操作：一次是将A1的车移除，另一次是在B1添加一枚新的车。

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

每次修改棋盘时，都会同时修改哈希值，这种方法非常高效。你也可以每次从头计算哈希值，通过异或所有棋盘上对应的zobKeys来完成。你还需要异或可以被吃掉的兵的位置以及双方车的状态。使用相同的方式，为每个可能的值创建zobris键。

该算法不能保证每个位置都具有唯一的哈希值，但是如果使用良好的伪随机数生成器，则发生碰撞的概率非常低，即使让引擎下棋一辈子，几乎没有发生碰撞的可能性。

编辑：我刚才看到你正在尝试为一个具有离线棋子的国际象棋变体实现此功能。Zobrist哈希仍然是适合你的正确解决方案。你需要找到一种方法将这些信息合并到哈希中。例如，你可以为离线棋子设置一些键：

unsigned long long offTheBoardZobKeys[NUMBER_OF_PIECE][MAXIMUM_NUMBER_OF_ON_PIECE_TYPE];

如果您的棋子有两个爪子不在棋盘上，并将其中一个棋子放在a2上，则需要执行两个操作：

// 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];

- Mathieu Pagé

---

我已经在使用 Zobrist 哈希的变体。但是由于可放置的棋子，我正在使用加法和减法。 - Justin

我不确定你如何在异或的位置使用加法/减法？但是你只需要找到一种方法来散列“下棋盘”中的棋子状态。它可以使用常规算法完成，我在我的编辑中解释了一种方法。 - Mathieu Pagé

Answer 2

为什么不在数据库中保存一个对应于棋盘布局的64字节字符串呢？每种棋子，包括“没有棋子”，都代表一个字母（黑色用大写字母ABC表示，白色用小写字母abc表示）。棋盘比较简化为简单的字符串比较。

通常情况下，从棋盘的角度进行比较，而不是从棋子的角度进行比较，将消除你的置换问题！

- Jochem

---

那对传统的国际象棋可能行得通。但在我正在编写的变体中，棋子也可以被放置。这意味着您的棋盘视角解决方案将无法使用，因为需要放置或已死亡的棋子不会列在64字节字符串中。棋盘并不包含所有数据，我的问题是棋子列表更难检测到置换。 - Justin

哎呀，太糟糕了。通过将棋盘的64个字符追加到所有死亡棋子的有序列表中（即aabAC），仍然可以绕过此问题。但也许这开始变得不切实际了？这是存储时间与检索时间之间的经典问题。 - Jochem

请将存储板扩展，以允许在棋盘外有一个“未放置”区域。Justin。 - Esben Skov Pedersen

@Esben：除非按照我提到的方式进行排序，否则这是行不通的，因为这个未放置的区域更像是一个没有位置的池子。 - Jochem

Jochem。然后定义一些标准排序。或者只是对它们进行排序。 - Esben Skov Pedersen

Answer 3

"不建议我存储集中式而不是分件式"。

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

如果在删除 L2 的所有元素后，仍然有剩余的元素在板上，则 L1 必须具有未出现在 L2 中的元素，因此列表相等。只有在临时板清空后，L1 和 L2 才相等。

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

- MSalters

---

这个答案并没有完全解决问题。（我认为它可以轻松扩展来解决问题，但目前它没有考虑到可放置的方块和死亡方块之间的区别...） - psmears

Answer 4

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

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

- Andrew

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语句）用于成对棋子之间比较的内容。最后，你只需要使用上述方法比较兵。

- Jochem

---

这对我的变量无效。棋盘上的棋子是唯一的，但可放置/捕获的棋子并不是。例如，游戏开始时所有值都为“-2”（可放置）。您将失去索引分组的棋子类型信息。没有这个，失去两兵会和失去两车一样。此外，总和的想法不起作用，请参见 this。 - Justin

总体思路仅是快速排除某些板子（因为我预计这将是最常见的情况）。因为为了相等，总和至少应该相等。我认为这会起作用，placeable只是另一个索引。如果在B2上有一个棋子，有序列表总是会产生-2、-2、-2、-2、-2、-2、-2、X（其中X是B2索引）。在你的问题中，你说-1是可放置的，但没关系。 - Jochem

是的，相等的位置有相等的和，但反过来并不成立。此外，我的简单解决方案已经可以检测到在棋子没有转位的情况下的相等位置。但是无法检测到转位，而这正是我所需要的。 - Justin

基本上是分段复制、排序和比较。这样做可以行得通，但我正在寻找一种不需要复制/排序的解决方案。这个操作的一次成本很小，但是如果要进行 100,000 次以上，成本就会累加。 - Justin

Answer 6

还有第三种选择（我真的希望在stackoverflow上发布3个答案是可以的）：

始终按索引顺序保留相同类型的棋子，即列表中的第一个兵应始终具有最低的索引。如果发生破坏此规则的移动，请只需在列表中翻转兵的位置。用户看不到任何区别，兵就是兵。

现在，在比较位置时，您可以确信没有置换问题，可以直接使用您提出的for循环。

- Jochem

---

我认为这不会起作用，因为我的搜索函数是递归的，如果我不断交换棋子，它可能无法撤消移动。移动对象使用索引来进行移动/取消移动。你只是增加了更多的开销。 - Justin

这是一个非常好的回答：更一般地，在比较对象（如局面）时，如果存在多个有效表示方式（由于转置等原因），一个强大的策略是尝试找到一个“规范”表示法——即对于可能有多种表示形式的每个不同的局面，选择其中一个作为“正确”的表示法，然后在比较两个局面（或之前），将它们转换为这个“正确”的（“规范”的）表示法——这样，如果它们不相等，就可以确定它们是不同的局面。 - psmears

顺便说一句，递归不应该是一个问题（只需编写一个移动棋子并更新表示的函数，然后在进入时调用它一次以移动棋子，在退出时再次调用它以将其移回）。在绝大多数情况下，更新都是微不足道的 - 最多交换两个条目 - 因此“困难”情况应该很少，从而使其总体上获胜。但是，如果您准备更改棋盘表示，则Amoss的解决方案更好，并且Mathieu Pagé解释了如何使用哈希使其更加高效... - psmears

@justin：那就试着让它工作。例如，每当你构建一个新位置（无论是向前还是向后移动），你都可以确保它处于规范顺序。而且，认真点，不要抱怨——你在抱怨每个人的想法对你来说都不可能起作用的文本中，比你询问问题的文本还多。 - comingstorm

Answer 7

根据您选择的游戏状态表示方式，您必须对黑色棋子的索引、白色棋子的索引等进行排序。如果您在创建新的游戏状态时没有这样做，那么您将不得不在比较时进行排序。因为您只需要对最多8个元素进行排序，所以这可以很快地完成。

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

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

或者

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

这两种替代方法不会出现置换问题。

无论如何，我有这样的印象，觉得你在纠结于微观优化，而应该首先让它正常工作。

- Svante