TadaoYamaokaの日記

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

将棋AIの進捗 その37(FPU reduction)

昨日MCTSで未訪問のノードの価値を、動的に親ノードの価値で初期化する方法を試した。
その結果、技巧2(4コア)に対する勝率が、60%から69%(R+68.6)になった。

昨日の結果の考察

今までは0.5(引き分け)で初期化していたため、劣勢の局面で未探索のノードがすべて1回は探索されることになるので、終盤の合法手の多い局面では探索が広すぎる条件になっていた。
十分な数の探索が行われれば問題ないが、探索の深いノードでは十分な数の探索が行われないので、すべてのノードが探索対象となると、ひどい手がバックアップされることになる。
そう考えると、0.5(引き分け)で初期化するのは明らかに良くないと思われる。

0.5(引き分け)にしていたのは、AlphaGoの論文にQ(s,a)=0で初期化するという記述があり、AlphaGoは価値ネットワークの出力を-1(負け)、1(勝ち)としていたためである。
その後、AlphaZeroの中の人の投稿で、探索時は0を負けとしていることが明らかになった。
この時点で、0で初期化することを試したが、dlshogiではかえって弱くなったので、0.5のままとしたという経緯がある。

FPU reduction

Leela ZeroのPRで、FPUを訪問済みのノードの方策の確率に応じて低減することが提案され、有意に差があることが確認されている。
modify fpu reduction depending on visited policy by Eddh · Pull Request #827 · leela-zero/leela-zero · GitHub
※FPU(First Play Urgency)は、未訪問のノードを探索する緊急度を表す用語で、未訪問のノードの初期値のこと

これをdlshogiでも試してみた。

下記式の低減係数C_{FPU}は、ルートで0、中間ノードで0.2とした。
\displaystyle
V(s) - C_{FPU} \sqrt{ \sum_{a'}{ I(N(a')>0) P(a') } }

技巧2との対局結果

技巧2(4コア)と1手3秒で100対局した結果は以下の通り。

条件 結果 勝率 信頼区間
FPU reductionなし 65勝28敗7分 69% 59.9~78.3%
FPU reductionあり 67勝27敗6分 71% 61.4~79.4%

100対局では、有意差は測定できなかった。
対局数を増やして確認してみたい。

FPU低減の係数はチューニングパラメータなので、チューニングでさらに良くなる可能性がある。
また、未訪問のノードの初期値を変えたことで、PUCTの係数も再チューニングを行う予定である。

自己対局のプログラムでも0.5は良くないので、変更する予定である。