佐布里斯特散列法

佐布里斯特散列法（也被称为佐布里斯特钥匙或佐布里斯特签名）是一种散列函数结构，用于玩抽象棋类游戏的计算机程序，如国际象棋和围棋，以实现换位表，这是一种特殊的散列表，以棋盘位置为索引，用于避免多次分析同一位置。佐布里斯特散列法是以其发明人阿尔伯特-林赛-佐布里斯特命名的。它也被作为一种方法用于识别晶体材料模拟中的替代合金配置。佐布里斯特散列法是被称为制表散列法的普遍有用的基础技术的xxx个已知实例。

Zobrist散列法首先为棋盘游戏的每个可能元素随机生成比特串，即为每个棋子和位置的组合（在国际象棋游戏中，这就是12个棋子×64个棋盘位置，或者如果可能仍然是城堡的国王和车，以及可能捕捉通行的卒，对两种颜色分别处理，则是18×64）。现在，任何棋盘配置都可以被分解成独立的棋子/位置组件，这些组件被映射到之前生成的随机比特串上。最终的Zobrist哈希值是通过使用位数XOR将这些位串结合起来计算出来的。国际象棋游戏的示例伪码。

white_pawn:=1white_rook:=2#等。black_king:=12

init_zobrist():#填充一个随机数/比特串表table:=一个大小为64×12的2维数组forifrom1to64:#循环计算棋盘，以线性数组的形式表示j从1到12:#循环计算棋子table[i][j]:=random_bitstring()table.black_to_move=random_bitstring()functionhash(board):h:=0ifis_black_turn(board):h:=hXORtable.black_to_moveforifrom1to64:#循环计算棋盘位置，如果棋盘[i]≠空：j:=棋盘[i]处的棋子，如上面常数索引中所列h:=hXORtable[i][j]返回h

如果比特串足够长，不同的棋盘位置几乎肯定会散列成不同的值；然而较长的比特串需要成比例的计算机资源来操作。最常用的位串（key）长度是64位。许多游戏引擎在换位表中只存储哈希值，完全省略了位置信息本身以减少内存的使用，并假设哈希碰撞不会发生，或者即使发生也不会对换位表的结果产生很大影响。Zobrist散列是xxx个已知的制表散列的例子。其结果是一个3维独立的哈希族。特别是，它是强通用的。举个例子，在国际象棋中，在任何时候，64个格子中的每个格子都可能是空的，或者包含6个棋子中的一个，这些棋子要么是黑的，要么是白的。另外，可以是轮到黑棋下，也可以是轮到白棋下。因此，我们需要生成6x2x64+1=769个随机比特串。给定一个位置，通过找出哪些棋子在哪些位置上，并将相关的位串组合在一起，就可以得到佐布里斯特哈希值。如果这个位置是黑棋走的，那么黑棋走的位串也会包含在佐布里斯特哈希值中。

与其像上面的伪代码那样每次都计算整个棋盘的哈希值，不如通过XOR掉位置发生变化的位串，再XOR入新位置的位串，来逐步更新棋盘的哈希值。例如，如果一个棋盘上的小卒被另一个棋盘上的车所取代，那么产生的位置将通过将现有的哈希值与以下的位串进行XOR而产生。卒在此方"（XOR出此方的卒）"车在此方"（XOR入此方的车）"车在源方"（XOR出源方的车）这使得佐布里斯特散列法在遍历棋谱树时非常有效。在计算机围棋中，这种技术也被用于超级子的检测。

更广泛的是，佐布里斯特散列可以应用于有限的元素集（在国际象棋的例子中，这些元素是{displaystyle(piece,position)}的图元）。图元），只要能给每个可能的元素分配一个随机位串就可以了。对于较小的元素空间，可以用随机数发生器来完成，对于较大的元素空间，可以用哈希函数来完成。这种方法在蒙特卡洛模拟过程中被用来识别替代合金配置，以防止在已经计算过的状态上浪费计算精力。