ゾブリストハッシュ

ゾブリストハッシュ法（ゾブリスト鍵またはゾブリスト署名 ^[1]とも呼ばれる）は、チェスや囲碁などの抽象的なボードゲームをプレイするコンピュータプログラムで使用されるハッシュ関数構造であり、ボードの位置によってインデックスが付けられ、同じ位置を複数回分析することを避けるために使用される特殊な種類のハッシュテーブルである転置表を実装する。ゾブリストハッシュ法は、発明者であるアルバート・リンゼイ・ゾブリストにちなんで名付けられている。^[2] また、結晶材料のシミュレーションで置換合金構成を認識する方法としても適用されている。^{[3]ゾブリストハッシュ法は、一般的に有用な基礎技術である}タブレーションハッシュ法 の最初の例として知られている。

ゾブリスト ハッシュは、ボード ゲームの可能な各要素、つまり駒と位置の各組み合わせに対してビット文字列をランダムに生成することから始まります (チェス ゲームでは、12 個の駒 × 64 個のボード位置、または、キャスリング ^{[疑わしい–議論]できるキングとルーク、および}アン パサントで捕獲できるポーンが両方の色で別々に扱われる場合は 18 × 64 になります)。これで、ボードの構成を独立した駒/位置コンポーネントに分割でき、これらは以前に生成されたランダムなビット文字列にマッピングされます。最終的なゾブリスト ハッシュは、ビット単位のXOR を使用してこれらのビット文字列を組み合わせることで計算されます。チェス ゲームの擬似コードの例: ^{[引用が必要]}

定数インデックス
    白のポーン:= 1
    白ルーク := 2
    # など
    黒キング := 12

関数init_zobrist():
    # 乱数/ビット文字列のテーブルを埋める
    テーブル:=サイズ64×12の2次元配列
    for i from 1 to 64: # 線形配列として表されるボードをループします
        for j from 1 to 12: # ピースをループします
            テーブル[i][j] := ランダムビット文字列()
    table.black_to_move = ランダムビット文字列()

関数ハッシュ(ボード):
    h := 0
    if is_black_turn(ボード):
        h := h XOR テーブル.black_to_move
    for i from 1 to 64: # ボードの位置をループします
        if board[i] ≠ empty:
            j := 上記の定数インデックスに記載されているボード[i]の駒
            h := h XOR テーブル[i][j]
    戻るh

ビット文字列が十分に長い場合、異なるボードの位置はほぼ確実に異なる値にハッシュされます。ただし、ビット文字列が長くなると、操作に比例して多くのコンピュータリソースが必要になります。最も一般的に使用されるビット文字列（キー）の長さは 64 ビットです。^[1]多くのゲームエンジンは、メモリ使用量を削減するために位置情報自体を完全に省略し、ハッシュ値のみを転置テーブルに保存し、ハッシュの衝突は発生しないか、発生したとしてもテーブルの結果に大きな影響を与えないと想定しています。

ゾブリストハッシュは、タブレーションハッシュの最初の既知の例です。その結果、3つの独立したハッシュファミリが生成されます。特に、これは強力なユニバーサル性を備えています。

たとえば、チェスでは、64 個のマス目はいつでも空になっているか、黒か白の 6 つの駒のいずれかが置かれている可能性があります。また、黒がプレイする番か白がプレイする番のどちらかになります。したがって、6 x 2 x 64 + 1 = 769 個のランダムなビット文字列を生成する必要があります。位置が与えられたら、どの駒がどのマス目にあるかを調べ、関連するビット文字列を組み合わせることで、そのゾブリスト ハッシュを取得します。位置が黒が動く場合は、黒が動くビット文字列もゾブリスト ハッシュに含まれます。^[1]

上記の疑似コードのように毎回盤全体のハッシュを計算するのではなく、変更された位置のビット文字列をXORし、新しい位置のビット文字列をXORするだけで、盤のハッシュ値を段階的に更新できます。^[1]たとえば、チェス盤のマスにあるポーンが別のマスにあるルークに置き換えられた場合、結果の位置は、既存のハッシュと次のビット文字列をXORすることで生成されます。

「このマスのポーン」（このマスのポーンをXORする）
「このマスにルークを置く」（このマスにルークを置くとXORする）
「ソース スクエアのルーク」(ソース スクエアのルーク
を XORする)

これにより、Zobrist ハッシュはゲーム ツリーのトラバースに非常に効率的になります。

コンピュータ囲碁では、この技術はスーパーコ検出にも使用されます。

より一般的には、ゾブリストハッシュ法は、ランダムなビット文字列を各要素に割り当てることができる限り、有限の要素セット（チェスの例では、これらの要素はタプル）に適用できます。これは、小さな要素空間の場合は乱数ジェネレーターを使用して、大きな要素空間の場合はハッシュ関数を使用して行うことができます。この方法は、モンテカルロシミュレーション中に置換合金構成を認識するために使用され、すでに計算された状態で計算労力を無駄にすることを防ぎます。^[3]${\displaystyle (ピース,位置)}$

• アルファベータ剪定