Zobrist Hash

手法

状態を集合だとして説明する.

有限の母集合 \(U\) があって, 状態はこれの部分集合 \(X \subset U\) として与えられるとする. Zobrist Hash は予め \(U\) の各要素にランダムな整数値を割り当てておくので \(X\) のハッシュを要素の値の XOR で表現する.

# init
for x in U:
    h[x] = random()

def hash(X):
    return xor(h[x] for x in X)

適用

チェスのような盤面の状態のハッシュ化によく用いられる. これを今の枠組みに当てはめるためには, \(U\) として座標情報とコマの組の集合を用いれば良い.

• \(U = \{ (x, y, \mathrm{piece}) | 1 \leq x, y \leq N, \mathrm{piece} \in \mathcal{P} \}\)

局面はこの座標にこのコマがおいてあるという要素を全て集めた集合とすれば \(U\) の部分集合になる.

参考

• wikipedia/Zobrist_hashing

実装

/// Hash - Zobrist Hash
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
pub struct ZobristHash(i128);
impl ZobristHash {
    pub fn new() -> Self {
        Self(0)
    }
    pub fn add(&mut self, x: i128) {
        self.0 ^= x;
    }
    pub fn remove(&mut self, x: i128) {
        self.0 ^= x;
    }
    pub fn concat(&self, other: &ZobristHash) -> Self {
        Self(self.0 ^ other.0)
    }
}