TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

Multi Ponderについて

今年の世界コンピュータ将棋選手権はMulti Ponderを採用しているチームが多く関心も高かったようです。

dlshogiでも、Multi Ponderの考え方を取り入れていました。
Multi Ponderは、どの手にどれだけのリソースを配分すると誤差を最小化できるかという問題としてとらえられると解釈しました。

モンテカルロ木探索の場合、UCB1が最大になる手にリソースを配分することで、理論的に最善でない手を調べる期待値をO(log n)に押させることができます。
これは、相手番で単純に相手局面に対してモンテカルロ木探索を行い、自分の手番では相手が指した枝から続きの探索をするだけで実現できます。

選択的探索と、Multi Ponderの親和性は高いと思っています。
(αβ探索の場合も近い考え方はできそうですが、自分としてはαβ探索に手を出すつもりはないです。)