[Theory of Computer Game 7]
Chinese
遊戲AI
Zobrist Hashing (Z-hashing)
Z-hashing 是一種 hash 的方式。以下方 4x4 的棋盤為例，首先把每個位置、每個下法都給定隨機字串。我們用陣列來表示，建立陣列 A：
A 陣列每個位置都填入隨機字串。運算為提高效率都使用 xor。
下在空白處
前面下的三步在陣列的位置分別為：[0,0,0]、[1,2,1]、[0,1,2]， 計算 S1 = A[0,0,0] xor A[1,2,1] xor A[0,1,2]，S1 即為現在盤面的 hash 字串。
移除一個棋子
如果要移除一顆棋，把當前盤面 hash 字串去 xor 拿掉的那顆棋。
例如移除 [0,0,0] 的話需要算 S2 = S1 xor A[0,0,0]，S2 即為新的棋盤 hash 字串。
移動一個棋子
如果要移動一個棋子，要 xor 舊的位置，並 xor 新的位置。
例如移動 [0,1,2] 到 [0,3,2] 的話需要算 S3 = S2 xor A[0,1,2] xor A[0,3,2]，S3 即為新的棋盤 hash 字串。
注意
定義棋盤位置 hash 字串的方式很多種，可以依照使用需求設計相應的方式。例如你希望 xor 結果包含下棋順序的資訊，那就需要再多一些設計。
此外，隨機數字要夠亂、夠隨機才能降低重複的機率表達較多資訊含量。例如你有一個一百格的棋盤，你想要產生一百個隨機數字，你的字串大小只有 5 個 bits，那麼你就會有不小機率會重複；如果你的字串有 64 bit 那任兩個隨機數字重複的機率就會很低。