Zobrist Hashing

Zobrist Hashingは将棋やチェスなどで用いられる、状態をハッシュ値に落とし込む方法です。

というのも将棋やチェスのような状態のハッシュ値を計算する場合、n進数や辞書順によるハッシュ関数では状態空間に対してハッシュ値を不偏的に散らすことはなかなか難しいです。そこでZobrist Hashingは乱数とXORを使って不偏性を作り出します。


WikipediaのZobrist Hashingの擬似コードを引用します。

   constant indices
       white_pawn := 1
       white_rook := 2
       # etc.
       black_king := 12
   
   function init_zobrist():
       # fill a table of random numbers/bitstrings
       table := a 2-d array of size 64×12
       for i from 1 to 64:  # loop over the board, represented as a linear array
           for j from 1 to 12:      # loop over the pieces
               table[i][j] = random_bitstring()
   
   function hash(board):
       h := 0
       for i from 1 to 64:      # loop over the board positions
           if board[i] != empty:
               j := the piece at board[i], as listed in the constant indices, above
               h := h XOR table[i][j]
       return h

(Wikipediaより: http://en.wikipedia.org/wiki/Zobrist_hashing)


・init_zobrist
まず下準備として、予めパズルの各マスに対してランダムビットstringを定義する。
例えば将棋なら、
７六に歩がある状態を 0100 0111 のように定義する。
７七に角がある状態を 1001 1100...
のように全てのマスの、全てのありうる状態に対するキーの値をテーブルに保存する。（以後テーブル値とする。）


・hash(board)
全てのマスの状態に対して定義されたテーブル値をビット毎のXORでかけていく。


さて、このZobrist Hashingの特徴を見ていきましょう。

・まず、Zobrist HashingはPerfect Hashingである保証は全くありません。盤が違う状態でも同じハッシュ値になり得ます。簡単な例だと
0000 XOR 0011 = 0011
0100 XOR 0111 = 0011
ですので。

・そこから一歩進んで、このハッシュ関数は同じフレームワークの中でビット長を変えることでハッシュの重複度を変化させることが出来ます。つまり、ビットを長くするほど違う盤の状態が同じハッシュ値を持つ割合(確率)を小さくさせることが出来ます。これは当然計算速度とメモリ量のトレードオフになります。

・n進数や辞書順によるハッシュ関数と比較して、盤の状態に対して偏りのないハッシュ値が得られることが多い。Bitwise XORなのでハッシュ値のビットストリングの各桁は、全てのマスの状態の関数なので、全てのマスのテーブル値を参照した結果の値といえる。ただしここで注意しなければならないのは、必ず偏りがないハッシュになるとは限らないということです。それは状態空間の性質にもよりますし、乱数の揺れにも依存します。



天才的な発想ですよね。どの位実用されているのかはよく知らないのですが、こういうアイディアの出せる人間になりたいものですね。




C++で簡単なサンプルを実装をしたものが以下のコードです。

/*
 * zobrist.cc
 *
 * Short sample to test Zobrist hashing.
 * Zobrist hashing is a hash function construction for abstract board games.
 *
 *
 *  Created on: Jun 10, 2014
 *      Author: Yuu Jinnai
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INDICES 16
#define SIZE 32

void initZobrist(int* table);
void initRandomBoard(int* board);
int hash(int* board);

int* table;

int main() {

 srand(time(NULL));
 table = new int[SIZE*INDICES];
 initZobrist(table);

 int* board = new int[SIZE];
 for (int i = 0; i < 10; ++i) {
  initRandomBoard(board);
  printf("hash(board) = %d\n\n", hash(board));
 }

}

void initZobrist(int* table) {
 for (int i = 0; i < SIZE; ++i) {
  for (int j = 0; j < INDICES; ++j) {
   table[i+SIZE*j] = rand();
   printf("table[%d][%d] = %d\n", i, j, table[i+SIZE*j]);
  }
 }
}

void initRandomBoard(int* board) {
 for (int i = 0; i < SIZE; ++i) {
   board[i] = rand() % INDICES;
   printf("%d ", board[i]);
 }
 printf("\n");
}

int hash(int* board) {
 int h = 0;
 for (int i = 0; i < SIZE; ++i) {
  h = (h ^ table[i+SIZE*board[i]]);
 }
 return h;
}