Zobrist Hash

概要

盤面(状態) をhash化出来るデータ構造。
起源は、Zobristさんという方がチェスのコンピュータを作成する時に、チェスの盤面をhash化するために作成したhash方法とのこと。

作成part

hash関数

• ある1要素に対して乱数(hash)を割り当てる。( 要素は何でもよい )
• 状態v (初期0) を定義して、そこにhash を xor させたものを、として扱う。

確率論

• Zobrist Hash を言い換えるならば ”確率論”。
• パッと見衝突が不安だが、自分のprogramを見ると分かるように、要素の種類が 1e6 とかなら、hash衝突の確率は宝くじ 1 等当選と同じくらい低い。

ハッシュ値が衝突する確率について

zenn.dev

集合同士をO(1)で比較する（Zobrist Hash） - Qiita

はじめに集合を比較するとなると，基本的にはかかる．ところが状況によっては簡潔に管理したかったり，比較をもう少し速くやりたいケースも出てくる．ここで，そんな時にぴったりなZobris…

qiita.com

method

• init(): 保持してるhashを0にする。( O(1) )
• get(): 今現在の盤面のhashを返す。( O(1) )
• flip(x): xからhashを求める (過去にhashを求めた場合はそれを再利用)。そしてその分だけ hash を xor する。( O(1) )

Program

template <class S>
struct Zobrist_hash_set {
    public:
    Zobrist_hash_set() : v(0) {
        mt.seed(rand());
        rnd = uniform_int_distribution<ll>(-LLONG_MAX, LLONG_MAX);
   }

    // 64bit整数値でhashを取る → max(N) = 2^20 = 104856 ≒ 1e6 の時
    // hash衝突確率p :
    // 1-p <= ( (2^64-n)/2^64 )^n ≒ 0.99999994039
    // p ≒ 1e(-7) (宝くじ1等の当選確率位)

    // 盤面のhashに関しても同様
    // → 調べたい盤面が高々1e6位の時は基本衝突しない。

    // 今現在の状態をvとして、xのhashをxorしてあげる
    void flip(const S& x) {
        // x 初出現 → 新hash値を割当
        if (!x_to_hash.count(x)) {
            x_to_hash[x] = rnd(mt);
        }
    
        // 状態のhash値更新
        v ^= x_to_hash[x];
    }
    
    // hash初期化
    void init() { v = 0; }
    
    // 現時点の状態hash値を返す．
    ll get() { return v; }
    
    private:
    // hash値
    ll v;

    // 各 x ∈ X に対するハッシュの割当
    unordered_map<S, ll> x_to_hash;
    mt19937_64 mt;
    uniform_int_distribution<ll> rnd;
};