ボナンザでの探索アルゴリズム比較

ボナンザver.4のコマンドバッチを使って１０局面・深さ6での平均探索ノード数／探索時間を比較しました。
アルゴリズムは以下の４つを比較しました。

ref	depth reduction/hash cut/futility cut　全てを無効
	（静止探索、反復深化、多重反復深化、ネガスカウト、手のソート/延長、1/3手詰み含む）
reduction	refからreductionを追加
hash	refからhashを追加
futility	refからfutility cutを追加

【結果】

-	reduction	hash	futility	ref
ノード数	369900	920358	78716	1462376
探索時間[sec]	1.777	5.494	1.465	7.512
ノード数[%]	25.29	62.94	5.38	100.00
探索時間[%]	23.66	73.14	19.50	100.00

【考察】
・futility cutは95%近くのノード数を大幅カット。評価ステップがはいるので時間削減は80%。
・reductionは75%ノードカット。時間削減も75%
　※上記二つは前向き枝刈りなので、読みぬけが発生するかも
・ハッシュは40%近くノードカット。探索時間も25%カット。これは教科書[1]通りの数値か。

futility cutは評価関数が複雑な場合に特に効果がでそうなので、
fv.binをゼロで埋めて、駒得だけにするとまた変わってくるかと。
ボナンザは一瞬で基準深さ６以上読むのですが、これはfutility cut、reductionの効果が大きいようです（基準深さとは静止探索に入るまでの深さ）
これを切ると、深さ６でも数分かかるようです。
先日のレポートとハッシュの削減効率が全然違うので僕のプログラムが誤っているようです。

[1]小谷ら著、ゲーム計算メカニズム、コロナ社、2010
　・・・基本探索アルゴリズムが詳しいです。将棋プログラマー必読です。