ゾブリストハッシュ

ゾブリストハッシュでは、局面を構成し得る各要素に擬似乱数を割り当てます。通常は、駒の種類、色、マスの各組み合わせに対応する数値に加え、手番、キングとルークがその特別な手をまだ行えるかを示すキャスリング権、そしてポーンの特殊な捕獲であるアンパッサンに関係する状態にも数値を割り当てます。擬似乱数とは、値がランダムに見えても、同じ方法で再現可能に生成されることを意味します。

局面キーは、有効な値をXOR、つまり排他的OR（排他的論理和）で組み合わせて作ります。XORは切り替えのように働く二進演算で、同じ値を2回適用すると効果が打ち消されます。駒が動くとき、プログラムはキーを最初から作り直さず、移動元のマスに対応する値を外し、移動先の値を加えられます。捕獲、プロモーション、手番の交代も同じ方法で更新できます。

この指紋により、局面を解析するプログラムであるチェスエンジンは、同じ局面が以前にも現れたことを素早く認識できます。異なる手順が同じ状態に到達したときに保存済みの解析を再利用し、反復を検出し、過去の結果を高速に保持するキャッシュを整理できます。正しく比較するには駒の配置だけでは不十分で、手番や特別な権利によって合法手が変わることも考慮しなければなりません。

ゾブリストキーに一意性の保証はありません。異なる2つの局面が同じ数値になることがあり、これを衝突と呼びます。大きなキーを使えば可能性は低くなりますが、保存と検証の設計では衝突が起こり得ることを考慮する必要があります。perftのようなテストでは、指し手を実行して取り消した後に増分更新したキーが元の値へ戻らなければ、更新処理の誤りを見つける手掛かりにもなります。