2.6 ハッシュ法

今回は、同一局面の取り扱いについて解説します。 オセロでは、別の手順でも同じ局面になるということがよくあります。 例えば、図1に示した2種類の手順はともに虎定石とよばれ、同じ局面になります。

図1. 2種類の虎定石の手順

ゲーム木にこのような局面が存在した場合、それぞれについてさらに先読みして評価するのは非効率です。 この問題は、今評価しようとしている局面がすでに評価されたものかどうかを調べることで解決されます。 これを行うための方法として、ハッシュ法があります。 ハッシュ法とは、キー（ここでは局面）をハッシュ値とよばれる値に変換し、データが保存されている配列（ハッシュ表）のハッシュ値に対応する場所を探すというものです。 具体的には次のようにします。 局面からハッシュ値を生成する。 ハッシュ表の、ハッシュ値に対応する場所を調べる。 対応する場所に局面が登録されていたら、同一局面かどうかを調べ、同一なら評価値をとりだす。 同一局面が登録されていない場合には、現在の局面を評価し、ハッシュ表に登録する。

図2. ハッシュ表のイメージ

ハッシュ法を使う上で重要なのが、ハッシュ関数と、ハッシュ値が衝突したときの処理です。 ハッシュ関数とは、キーからハッシュ値を生成するための関数です。 例として、キーが整数の場合に、キーをある整数で割った時の余りをハッシュ値として使用する方法があります。 ハッシュ関数は、すべてのハッシュ値が同程度の確率で生成されるものがよく、この場合には割る数に素数を使うのがよいとされています。 ハッシュ値の衝突とは、異なるキーから同一のハッシュ値が生成されることをいいます。 この問題に対するいくつかの方法が考案されています。 チェイン法 同一のハッシュ値をもつデータをリストでつなぐ方法です（図3）。 データを保存する領域はハッシュ表とは別の領域に確保されます。 図3. チェイン法のイメージ 開番地法 すでに同じハッシュ値をもつデータが登録されていた場合に、ハッシュ表の別の場所を探索する方法です。 もっとも単純なのは、ハッシュ値を1ずつ増やしながら探索する方法で、線型操作法と呼ばれます。 線型操作法で、ハッシュ値の増加分をハッシュ関数とは別の関数によって求める方法もあり、2重ハッシュ法と呼ばれます。 図4. 開番地法のイメージ ハッシュ表に登録する際に注意しなければならないのは、その局面の評価値が真の評価値であるかどうかです。 Alpha-Beta法を使った場合には、枝刈りによって真の評価値が得られない場合があります。 その場合には現在の評価値が評価の上限か下限か、真の値なのかを区別する必要があります。

トップに戻る 2.5 Scout法 2.7 前向き枝刈り