artificial-intelligence - 生成棋盘的唯一标识符

Question

我正在寻找类似棋盘校验和之类的东西，棋子位于特定位置。我正在寻找动态编程或内存解决方案对于人工智能国际象棋棋手是否可行。唯一标识符将用于轻松检查两个板是否相等或用作数组中的索引。感谢您的帮助。

Answer 1

棋盘位置广泛使用的校验和是 Zobrist signature .

对于任何国际象棋位置来说，这几乎是唯一的索引号，要求两个相似的位置生成完全不同的索引。这些索引号用于更快且节省空间的换位表/打开书籍。

您需要一组随机生成的位串:

• 每个方格各有一个；
• 一个表示要移动的一侧；
• 四项用于王位继承权；
• 八个用于有效路过方格的文件(如果有)。

如果您想获取某个位置的 Zobrist 哈希码，则必须对与给定特征关联的所有随机数进行异或操作(详细信息: here 和 Correctly Implementing Zobrist Hashing )。

例如起始位置:

[Hash for White Rook on a1] xor [White Knight on b1] xor ... ( all pieces )
... xor [White castling long] xor ... ( all castling rights )

XOR 允许在移动/取消移动期间快速增量更新哈希键。

现代国际象棋程序中通常使用 64 位作为标准大小(请参阅 The Effect of Hash Signature Collisions in a Chess Program)。

当您计算 √ 2³² == 2¹⁶ 时，您可能会在 32 位哈希中遇到冲突。使用 64 位哈希，您可以预期在大约 2³² 或 40 亿个位置 ( birthday paradox ) 后发生冲突。