10

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

请不要建议我应该以 board-centric 而不是 piece-centric 来存储。由于可放置和捕获的作品的独特性，我必须存储作品清单。这些状态中的碎片就像它们占据了重叠且无位置的位置。请查看有关如何存储碎片的说明。

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

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

4

7 回答 7

8

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

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

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

unsigned long long zobKeys[NUMBER_OF_PIECES][NUMBER_OF_SQUARES];

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

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

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

如果您稍后从该方格中移除车，您需要反转您刚刚所做的，因为 XOR 可以通过再次应用它来反转，您可以在移除时再次使用相同的命令：

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

如果你移动一个棋子，假设 A1 上的车去 B1，你需要做两次 XOR，一次是删除 A1 上的车，一次是在 B2 上添加一个车。

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

这样，每次修改板时，您也会修改哈希。这是非常有效的。您还可以通过异或与板上所有棋子对应的 zobKeys 来计算每次 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];
于 2010-10-08T12:51:51.403 回答
6

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

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

于 2010-10-08T08:43:53.400 回答
4

“不要建议我应该以板为中心而不是以块为中心来存储”。

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

如果在删除 的所有元素后L2，棋盘上仍有棋子，则L1一定有元素不存在L2且列表相等。L1并且L2仅当临时板之后为空时才相等。

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

于 2010-10-08T12:01:45.737 回答
3

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

Piece-type in A1
... 63 more squares
Number of white pawns off-board
Number of black pawns off-board
... other piece types
于 2010-10-08T12:58:27.737 回答
1

从作品的角度来看，您可以这样做：

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 语句中）成对的部分的比较。然后，您所要做的就是使用上述方法比较棋子。

于 2010-10-08T09:10:16.427 回答
1

第三个选项（我真的希望发布一个问题的 3 个答案是可以的，stackoverflow-wise ;)）：

始终以索引顺序保持相同类型的棋子，即列表中的第一个棋子应始终具有最低索引。如果发生破坏这一点的移动，只需翻转列表中的棋子位置。使用不会看到区别，棋子就是棋子。

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

于 2010-10-08T09:15:54.837 回答
1

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

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

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

或者

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

这两种选择不会有转置问题。

无论如何，我的印象是，当你应该首先让它工作时，你正在摆弄微优化。

于 2010-10-08T11:50:24.107 回答