読者です 読者をやめる 読者になる 読者になる

将棋とかボードゲームでハッシュ値

CodeVSでちょっとした工夫として、どこにタワーを置いたかでハッシュ値をつけてた。
結果的にはいらない技術だったけど(他にもっと良いアルゴリズムがある)

将棋や今回のようなCodeVSで過去に同様の状態があったか、探索してるかどうか調べるのは少し難しい。
調べた配列を全て保存しておくなんてことはメモリの観点からもできないし、同一の配列か調べるのもすごい高コストになる。
そこでハッシュというわけだ。

状態に固有の数値がつけばハッシュとして機能する。
適当に割り振っても、後から同一の状態だったか判断できないので現在の状態から生成できるハッシュ値である必要がある。

今回、CodeVSでやった方法はあらかじめある位置にタワーを置いたこと表す乱数を決めておく。
例えば、Javaでの記述になるが

long[][] hash=new long[50][50];
Random ran = new Random();
for(int i=0;i<50;i++){
	for(int j=0;j<50;j++){
		hash[i][j]=ran.nextLong();
	}
}

あとはこの乱数とタワーを置いた位置でハッシュ値を生成する。
ハッシュ値の生成は排他的論理和が優れている。
理由は

C=A^B
A=C^B

になる。つまり、元にもどるということだ。
この例で言えば、Aが現在の状態、Bがある地点にタワーを置いた時の乱数、CがAの状態からBのタワーを置いた時のハッシュ値ということになる。

あとはデータ構造だが、今回はJavaのHashMapを使った。
たぶん追加も検索もO(logN)のはず・・・。
自分がみた将棋のAIは極力大きな配列を用意して、追加する時にすでに要素で埋まってる時は次の適当な位置を試す、みたいなことをしていた。(わかりにくくて申し訳ない・・・)
検索するときは、ハッシュ値も記録してあるので要素を取り出してからキーと比較することで同一の状態か調べられる。
(2^64の配列なんて用意できない。できればハッシュ値を保持しておく必要はなくなるけど)
そっちの方が少しは高速だろうか?けど、めんどくさい。

ハッシュを入れてみての効果のほどだけど、自分の場合はせいぜい2〜3倍高速化されたかどうかといったところ。
使い方次第で便利なこともあるはず・・・。