TadaoYamaokaの日記

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

将棋AIの進捗 その36(UCBの価値の初期値)

AlphaZeroのMCTSのUCBには、
\displaystyle
Q(s, a) + C(s)P(s,a)\frac{\sqrt{N(s)}}{1+N(s,a)}
という式が使用されており、このUCBで行動価値の信頼区間の上限を見積もっている。

Q(s, a)は、行動aの行動価値を、探索を行った結果得られた価値の平均で推定する。
ここで、N(s, a)=0のときQ(s, a)は未定義であるため、何らかの値で推定する必要がある。
AlphaZeroでは0で初期化、つまり、未探索のノードの価値を0(負け)としている。


dlshogiでは、これを0.5(引き分け)で初期化している。
以前に、これをAlphaZeroに合わせて0で初期化してみたところ、勝率が極端に落ちたので、0.5のままとしている。

dlshogiで、負けで初期化すると勝率が極端に落ちる原因はよくわかっていない。
方策を分布ではなく指し手で学習しているという、学習方法の違いによるものかもしれない。

Leela Chess Zeroの初期値

Leela Chess Zeroでは、元々N(s, a)=0のときのQ(s, a)に、親ノードの価値が使用されていた。

以下のissueで、これをAlphaZeroと同様に0で初期化することについて議論されている。
Initialize Q = 0 instead of parent Q for self-play to match AGZ paper · Issue #344 · LeelaChessZero/lc0 · GitHub

学習時の自己対局では、負けで初期化することで、負けの局面は広く探索して、勝ちの局面では現在の方策が実際に良いか補強して検証するという目的があると考察されている。

以下のPRでは、ルートの初期値は、勝ちで初期化した方が、チェスではAlphaZeroにより近くなると主張されている。
理由は、35手くらいまではすべて探索されるからと説明されている。
Add AtRoot versions of FpuStrategy and FpuValue (and convert FpuReduction to FpuValue). by Mardak · Pull Request #750 · LeelaChessZero/lc0 · GitHub


現在のLeela Chess Zeroの設定を確認すると、ルートノードでは、勝ちで初期化し、中間ノードでは負けで初期化している。
対局時の設定も、同じになっている。

親ノードの価値で初期化を試す

dlshogiで負けで初期化するとうまく機能しないが、Leela Chess Zeroが以前に行っていた、親ノードの価値でN(s, a)=0のときのQ(s, a)を初期化する方法を試してみた。

技巧2と1手3秒で100対局した結果は、以下のようになった。

条件 結果 勝率
0.5(引き分け)で初期化 59勝38敗3分 60%
親ノードの価値で初期化 65勝28敗7分 69%

Core i7 4コア、GPU 2080Tiを使用
※自己対局で学習した最新のモデルを使用

親ノードで初期化することで、勝率が9%(R+68.6)上昇した。


Leela Chess Zeroで、親ノードの価値で初期化する場合は、さらに低減(reduction)項が加えられている。
\displaystyle
V(s) - C_{FPU} \sqrt{ \sum_{a'}{ I(N(a')>0) P(a') } }
これは、方策の確率が大きいノードが探索された数が多いほど、探索の緊急度を削減するという意味がある。
次は、この項も加えて検証してみたい。