ProbCutの手法を解説どうも！

http://d.hatena.ne.jp/tawake/20060710/1152520755

フダンの記録さまから、ProbCutを解説していただきました。感謝！

オセロの論文を見たときは、いまいちなにかよくわかりませんでしたが、やっとなんとなく判りました（たぶん）
要するに、10手先まで読もうとしているときに、5手まで読んで、そこでAlpha-BetaのWindowから、あるマージン分超えてるときは
カット。超えない場合は、ちゃんと10手まで読む。
という感じですね。
M.Buroの論文も見ましたが、5手までの評価と10手までの評価に、相関関係があることが前提ということで
5手までの結果が、10手先を決めているわけですから、相関があるのは確かでしょうし。
ただ、オセロは石の数だけだと変動するというか、逆転もあるゲームだろうし、そのへんがどうなのだろう。
もちろん、リスクの無い、ヒューリスティックは無いでしょうけど。

一方、Futility Pruningは、windowのうち、下限をした回ってるときに、あるマージン分下回ってると、
あとちゃんと手を打ったとしても、そのマージンを挽回するのは無理そうなので、もうそこでカットしてしまう。
という考え方と思いました。

比較するなら、ProbCutは、d'手まででd手分読んだという近似で、探索を削減
Futility Pruningは、末端に近いところで、あるマージンだけNega探索だと、alphaを下回ってる場合に
それ以上、さらに探索しても、意味が無いという推定かな。

後者は悪そうな手を切り捨てる手段。
前者は、もっと汎用的な感じがする。アルゴリズムを見ていると、ProbCutの特殊な方法例としてFutility Pruningが包含されている
ような気がする。

ROOTの段階から、nullWindowサーチで、任意の探索回数まででwindowをマージン分超えているか、調べておけば、
単純に下位を前向き枝狩するより良さそうに思いますね。
しかし、リスクもあるし、マージンの調整もあるので、実際にやってみないと、解らないように思います。

BonanzaはおそらくFutility Pruningは使ってるでしょうから、
そう考えると、全幅の味が出る程度の前向き枝狩はしていると考えた方がいいのではないかと思う。
よし。その路線でがんばりましょう。