正确实现Zobrist哈希算法

Question

我目前正在我的国际象棋引擎中添加置换表，但我在增量更新Zobrist键方面遇到了问题。 我进行了一些研究并实现了基本思想，但它的行为不像我期望的那样。 我遇到的问题是等效的局面不总是具有相同的键。 例如，在起始位置中，如果两个玩家都只移动马并将其移回，则键将与起始位置的键不同。 然而，再次执行此操作（移动马）并返回到起始位置会导致原始键。 因此，对于每个玩家，这种序列的周期似乎为4个移动，当它应该只是2个时。

是否有人遇到过这样的问题或可以想出解决办法？ 我已经包括了我的make / unmake方法的相关部分。 我不包括变动方，易位权利等； 它们不应影响我提出的特定情况。 HashValue存储随机值，其中第一个索引是棋子类型，第二个索引是方格。

void Make(Move m) {
    ZobristKey ^= HashValue[Piece[m.From].Type][m.From];
    ZobristKey ^= HashValue[Piece[m.From].Type][m.To];
    ZobristKey ^= HashValue[Piece[m.To].Type][m.To];
    //rest of make move
}

void Unmake(Move m) {
    ZobristKey ^= HashValue[m.Captured.Type][m.To];
    ZobristKey ^= HashValue[Element[m.To].Type][m.To];
    ZobristKey ^= HashValue[Element[m.To].Type][m.From];
    //rest of unmake
}

- Kira Chow

---

通常make和unmake应该是相同的。（XOR是对称的）哈希不应反映移动，而是棋盘上的棋子。捕获一枚棋子:=从哈希中删除其价值。移动一枚棋子:=从哈希中删除先前的位置+将新位置添加到哈希中。（王车易位和吃过路兵状态有点不同） - wildplasser

是的，我相信这就是我的代码所做的。还有其他的制作/取消制作代码也必须考虑在内，这就是为什么“起始”和“目标”方块会发生变化的原因；在制作方法中位于“起始”位置的棋子在取消制作方法中显然不再存在。 - Kira Chow

不，Make() 代码应该只有两个组件：一个用于将棋子从旧位置移除，另一个用于将其添加到新位置。（可能还有一个额外的组件用于移除被吃掉的棋子） - wildplasser

我有一个“空”棋子类型，所以我认为我不需要检查被捕获的棋子。我不认为这会造成任何问题，但检查一下是个好主意。 - Kira Chow

好吧，我错了。包括“空”的那一部分搞砸了事情。感谢您的帮助；如果您提供答案，我会接受它的 :)。 - Kira Chow

通常，“空”棋子只是具有零的Zobrist条目，因此您不需要将其添加/删除到哈希值中。我会添加一些伪代码。 - wildplasser

Answer 1

Make_a_move() {
    hashval ^= Zobrist_array[oldpos][piece];
    hashval ^= Zobrist_array[newpos][piece];
    /* if there is a capture */
    hashval ^= Zobrist_array[otherpos][otherpiece];
    }

Undo_a_move() {
    hashval ^= Zobrist_array[oldpos][piece];
    hashval ^= Zobrist_array[newpos][piece];
    /* if there was a capture */
    hashval ^= Zobrist_array[otherpos][otherpiece];
    }

王车易位可以看作是两步棋的结合（显然不包括吃子）。

兵升变可以被视为将某个兵从棋盘上移除（从2或7位置），并加入一个新的棋子（在1或8位置）。

- wildplasser