TadaoYamaokaの日記

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

PythonでAlphaZero Shogiを実装する その4

迫田さんのブログで、AlphaZeroは自己対局時にノードを再利用しているという根拠のリンクが貼られていて、確認したことろ確かにDeepMindの中の人がノードを再利用していると答えていました。
Accelerating Self-Play Learning in Goを読んだ - 水たまり

Alphazero news - Page 22 - TalkChess.com

[Q] Normally, an MCTS search would do "tree reuse" from move to move, carrying forward the subtree that was actually chosen. But during the training, there is noise added to the root. If one does tree reuse, the effect of the noise is lessened. Leela Chess Zero decided to disable tree reuse because of that. Leela Zero has kept it enabled.

[A] It is enabled at all times unless we are testing something specific that will be affected by it. We introduce diversity in two ways - dirichlet noise and visit count sampling.
Dirichlet noise is used to modify prior at the root node before each search (if it's enabled). So if a subtree is reused, when the next search starts it will be added to the node that is now the root node.
Visit count sampling isn't really affected.

AlphaZeroの論文ではノードの再利用については触れられていなかったため、dlshogiの自己対局を実装する時にどちらにするか悩みました。
dlshogiでは、相手の探索の結果が、自分の探索の結果に影響してしまうため、勝率にも影響がでそうなので、ノードの再利用は行わないようにしました。
しかし、AlphaZeroでは再利用を行っていたようです。

質問には再利用するとディリクレノイズの影響が少なからずあると書かれていますが、回答では、ノイズはルートノードのみに加わるので次の手番には持ち越されることはないとあります。
確かにその通りで、再利用の影響があるとすると木のバランスが先手、後手で非対称になることくらいです。
それも、影響がでるのは初めの数手で、後の方になると双方が再利用するノード数も同じくらいになるので、影響はなさそうです。
30手までは局面のバリエーションを増やすために訪問数に応じた分布で選択しているので、木のバランスも気にする必要はありません。

そう考えると再利用する方が、探索の精度が上がるため、正解な気がしてきました。

Leela Chess Zeroは再利用なしで、Leela Zeroは再利用しているようです。

dlshogi-zeroも、再利用するように修正しました。
ノードを再利用する · TadaoYamaoka/dlshogi-zero@2f1d2a6 · GitHub


dlshogiの方は、世界コンピュータ選手権が終わったら修正することにします。