• ハッシュ法

  リバーシプログラムの置換表には、ハッシュ法がよく使われます。
  ハッシュ法とは、「データを直接比較するのではなく、ある手続きによって小さいデータに変換してから比較する」手法を指します。
  変換手続きをハッシュ関数、変換後のデータをハッシュ値と呼びます。
  

• ハッシュ法を利用した置換表

  本プログラムではハッシュ法を利用して以下のような処理を行います。

  1. 局面を64bitのハッシュ値に変換する。
  2. ハッシュ値の下位n bitを求め（iとします）、置換表のi番目にハッシュ値と局面情報を登録する。
  3. 局面が登録されているかどうか調べるときには、局面のハッシュ値と、i番目のレコードのハッシュ値とを比較する。

• ハッシュ法の問題点

  ハッシュ法では元のデータが異なっていても、ハッシュ値が同じという場合が発生します。
  これを衝突と呼びます。
  本プログラムでは以下の衝突が発生します。
  

  • ハッシュ値自体の衝突
  • レコードの衝突

  本プログラムではハッシュ値自体の衝突については考慮しません。
  ハッシュ値が異なる場合には常に元の局面も異なるとして扱います。
  後述するハッシュ関数ではハッシュ値自体が衝突する可能性は極めて低いためです。
  

  レコードが衝突した場合には、古いデータを新しいデータで上書きするようにします。
  本プログラムではハッシュ法を高速化のためだけに使用するので、古いデータを上書きしても思考結果が変わるということはありません。
  

• ハッシュ関数

  本プログラムでは以下のハッシュ関数を使用します。
  

  1. 各マス、各色毎に64bitの乱数を割り当てる。
     例えばA1に黒石がある場合にはX1、A2に白石がある場合にはX2というような割り当てを行う。
     
  2. 局面の石の状態に応じて、対応する値のXOR(排他的論理和)をとりハッシュ値とする。
     
  3. 手番に対しても乱数を割り当て、上で求めたハッシュ値のさらなるXORをとる。
     

• ハッシュ関数の定義

  ハッシュ関数はBoardクラスに追加しました。
  関数定義は以下のようになっています。
  

  • void Board_HashValue(Board *self, int in_color, HashValue *out_value) 引数
     self : Boardクラスへのポインタ
     in_turn : 手番
     out_value : ハッシュ値を格納するHashValue構造体へのポインタ
    戻り値 なし

  またHashValue構造体を使用するため、"board.h"の最初の方に以下の一文を追加しておきます。
  

  #include "hash.h"
  

次節ではハッシュ関数の実装を行います。