2009-11-21

■　Bonanzaの定跡データベースはどういう構造になっているのか？

指し手生成について一通り解説が終わったので、その他の部分を順番に解説していく。

解説していくとは言うものの、私自身そんなに時間がとれるわけではないので、Bonanzaのソースにコメントを大量に追記した私のソース上のコメントをその解説代わりとしたい。

■　定跡ファイルの構造

  Opening Book Data Structure: Index BookData
	定跡データ構造は、 Index BookDataで構成される。

    Index:         IndexEntry.. (NUM_SECTION times)
		Indexは、IndexEntryがNUM_SECTION回ある。

      IndexEntry:  SectionPointer SectionSize
			IndexEntryは、SectionPointerとSectionSizeから構成される。
			このSectionSizeぶんだけ読み込む。

    BookData:      Section.. (NUM_SECTION times)
    BookDataは、SectionがNUM_SECTION回ある。ただし1つのセクションは可変長である。

      Section:     [DataEntry]..
			1つのSectionは、複数のDataEntryで構成される。

        DataEntry: Header Move...
				1つのDataEntryは、1つの局面における定跡の指し手(複数ありうる)を表現する。
				つまりDataEntryはHeaderと複数の指し手から構成される。
				指し手はその局面の定跡手。複数ありえる。最大32個。

				つまりDataEntryは可変長であり、ここへのポインターが
				必要になる。それがIndexにある。


- SectionPointer
  4 byte:  position of the section in character
  セクションポインターは4バイト。これは定跡ファイルのfseekで指定されるポジション。
  すなわち、ファイルの先頭からのバイト数。ファイルのその位置を参照しにいく。

- SectionSize
  2 byte:  size of the section in character
	セクションサイズは2バイト。
 
 ※ IndexEntry = SectionPointer + SectionSize なので 4 + 2 = 6バイト。
  
- Header (9バイト)

  1 byte:  number of bytes for the DataEntry
  ↑このDateEntryのサイズ。このぶんを加算すれば次のDataEntryに行く。

  for the DataEntryの"the"は、このDataEntry
  8 byte:  hash key
  ↑ここにhash keyがあるのでこれで本当に局面とぴったり一致するか調べる。
  
- Move (4バイト)

  2 byte:  a book move
		1つの指し手は2バイト(from,to)と、その手が選ばれる頻度からなる。

  2 byte:  frequency
		頻度はu16で表現されており、その局面の定跡指し手の合計は u16.MAXになるように
		正規化されている。また、指し手は頻度順にソートされている。

■　定跡ファイルで使う構造体

// 定跡ファイルのインデックスの1つのエントリーの大きさ
const u32 BK_SIZE_INDEX  =  6;

// 定跡ファイルのデータエントリーにあるヘッダーのサイズ
const u32 BK_SIZE_HEADER =  9;

// 定跡ファイルの指し手のサイズ
const u32 BK_SIZE_MOVE   =  4;

// 定跡ファイルの1局面における定跡手の最大数。
const u32 BK_MAX_MOVE    = 32;


// 定跡ファイルにおけるある定跡局面の定跡指し手情報
struct book_move_t
{
	u16 smove;	// 指し手。この指し手は、移動元と移動先を表現している。
	u16 freq;		// この指し手が選ばれる頻度
};

// 定跡ファイルで使われている指し手smoveからfromとtoを取り出したもの。
// 動かす駒の情報も、捕獲する駒の情報もない。
// あるのは移動元と移動先のみ。
struct ft_t
{
	BoardPos from, to;
};

■　定跡ファイルの読み込みに使う関数

// 指し手book move形式からMove形式に変換する。book move形式は、
// 指し手のうち捕獲する駒や、動かす駒についての情報が欠落しているので
// それを局面情報から補ってやる必要がある。
// is_flipは手番を反転させるのかのフラグ。
static Move bm2move( const Tree * restrict ptree, Move bmove , bool is_flip );

// 引数で受け取ったft_tを加工して返す。
// ft_t.from,ft_t.to を次の条件で移動させる。
// 　turnが後手番なら盤を180度反転させた場所に移動。
// 　is_flipがtrueなら左右盤を反転した場所に移動。
static ft_t flip_ft( ft_t ft, Turn turn, bool is_flip );

// この局面の指し手を正規化する。すなわち、0..moves-1のなかの手の頻度を全部足すと
// 頻度100%(u16.Max)になるように調整する。
// pbook_move = 定跡の1DataEntry
// moves      = そのなかで正規化の対象とする指し手の数
static Result normalize_book_move( book_move_t * restrict pbook_move, s32 moves );

// 定跡を読み込みモードで開く。
// 定跡を有効にする。book_offを呼び出すまで有効。
Result book_on();

// 定跡ファイルを閉じる。
// 定跡を無効にする。book_onをするまで有効。
Result book_off();

// 定跡データベースを調べる。
// 現在の局面が定跡ファイル上に見つかれば正。
// そのときの定跡手は↓ここに返される。
//   ptree->current_move[1] = move;
Result book_probe( Tree * restrict ptree );

// 定跡ファイルを調べる。
// key        = 局面のハッシュ値
// pbook_move = 定跡データベースで見つけた指し手
// 返し値は、↑に格納した数。3つ格納したならpbook_move[0..2]に格納される。
static Result book_read( u64 key, book_move_t *pbook_move, u32 *pposition );

// 現在の局面のhash値を求める
// 手番側を先手として計算する。また持ち駒もhash値に算定する。
// それ以外は普段探索で使っているhash値とだいたい同じ。
// あと盤面を左右反転させたハッシュも生成して、
// 小さい値のほうのハッシュ値をその局面のハッシュ値とする。
// こうしておけば、左右反転している局面も定跡データベースにヒットする。
// またその場合には、*pis_flip = 1を返す。
static u64 book_hash_func( const Tree * restrict ptree, bool *pis_flip );


// この局面の指し手を正規化する。すなわち、0..moves-1のなかの手の頻度を全部足すと
// 頻度100%(u16.Max)になるように調整する。
// pbook_move = 定跡の1DataEntry
// moves      = そのなかで正規化の対象とする指し手の数
static Result normalize_book_move( book_move_t * restrict pbook_move, int moves );

■　まとめ

今回は定跡ファイルの読み込み部について解説した。Bonanzaのソース上には定跡ファイルに対する書き出し用の関数群も用意されているが、それらについては今回の情報があれば自力で読めると思う。