# PUCT PUCT は、[モンテカルロ木探索(MCTS)](/shogi/shogiwiki/search/monte-carlo-tree-search/)で子ノードを選ぶための選択規則の一種である。[AlphaZero](/shogi/shogiwiki/alphazero/) 型では、ニューラルネットワークの方策出力を事前確率として使い、探索済みの価値と未探索手への探索ボーナスを組み合わせて次に読む手を選ぶ。 名前は Predictor + Upper Confidence bounds applied to Trees の略として説明されることが多い。ここで Predictor は、[方策・価値ネットワーク](/shogi/shogiwiki/evaluation-function/policy-value-network/)の方策出力を指す。 ## 基本形 PUCT では、各候補手 `a` に対して、おおむね次のような値を計算し、最大の手を選ぶ。 ```text score(s, a) = Q(s, a) + U(s, a) U(s, a) = c_puct * P(s, a) * sqrt(N(s)) / (1 + N(s, a)) ``` ここで各記号は次の意味を持つ。 - `Q(s, a)` その手を選んだ後の平均価値。これまでの探索結果から得られる活用項。 - `P(s, a)` 方策ネットワークが出した、その手の事前確率。 - `N(s)` 親局面の訪問回数。 - `N(s, a)` その手の訪問回数。 - `c_puct` 探索ボーナスの強さを調整する定数。 方策が高い手は探索されやすくなるが、同じ手を何度も読むと `1 + N(s, a)` が大きくなり、探索ボーナスは小さくなる。このため、PUCT は「方策ネットワークが有望だと言う手を優先する」ことと「まだ十分に読んでいない手も試す」ことを両立させる。 ## UCT との違い 古典的な UCT は、子ノードの平均価値と訪問回数から探索と活用のバランスを取る。方策ネットワークのような外部の事前知識は基本的に使わない。 PUCT は、ここに `P(s, a)` を入れることで、ニューラルネットワークが有望と見た手を早い段階から優先できるようにする。これは、合法手数が多い将棋で MCTS を使うときに特に重要である。方策がなければ、序盤から候補手が多すぎて探索資源が薄く広がりやすい。 ## AlphaZero 型での役割 AlphaZero 論文では、各 simulation が木をたどる際、訪問回数が少なく、方策確率が高く、価値が高い手を選ぶと説明されている。PUCT は、この考え方を実装するための代表的な選択規則である。 自己対局では、PUCT によって MCTS の探索分布が作られ、そのルート訪問回数分布が次の方策教師になる。つまり PUCT は、対局中の読み筋を決めるだけでなく、次に学習される方策データの質にも影響する。 ## dlshogi での位置づけ DeepLearningShogi の `selfplay/self_play.cpp` や `usi/UctSearch.cpp` では、UCB 値が最大となる子ノードを選ぶ処理があり、評価値 `q`、訪問回数に基づく項 `u`、ニューラルネットワーク由来の `nnrate` を組み合わせて `q + c * u * rate` 型の値を計算している。 また、ルートノードでは [Dirichlet noise](/shogi/shogiwiki/search/dirichlet-noise/) などのノイズ、未探索ノードの初期価値を調整する [FPU reduction](/shogi/shogiwiki/search/fpu-reduction/)、勝敗確定ノード、千日手、詰み探索などが絡む。実装上の PUCT は、教科書的な式をそのまま置くだけではなく、将棋固有の規則や探索安定化の工夫と一体で調整される。 ## 調整上の注意 `c_puct` やそれに相当する探索定数を大きくすると、方策 prior や未探索手への探索が強くなりやすい。小さくすると、既に高い価値を得た手へ探索が集中しやすい。 ただし、強さへの影響はネットワークの精度、持ち時間、推論速度、ルートノイズ、温度、詰み探索、定跡、引き分け価値などと相互作用する。dlshogi のような実戦エンジンでは、単独の式だけでなく、自己対局や対局実験を通じてまとめて調整する必要がある。 ## 関連項目 - [モンテカルロ木探索(MCTS)](/shogi/shogiwiki/search/monte-carlo-tree-search/) - [方策・価値ネットワーク](/shogi/shogiwiki/evaluation-function/policy-value-network/) - [Dirichlet noise](/shogi/shogiwiki/search/dirichlet-noise/) - [FPU reduction](/shogi/shogiwiki/search/fpu-reduction/) - [AlphaZero](/shogi/shogiwiki/alphazero/) - [自己対局](/shogi/shogiwiki/self-play/) - [dlshogi](/shogi/shogiwiki/softs/dlshogi/) - [探索パラメータの確率的最適化](/shogi/shogiwiki/search/search-parameter-optimization/) ## 参考にしたホームページ - [David Silver, et al. "Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm"](https://arxiv.org/abs/1712.01815) - [arXiv PDF: Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://arxiv.org/pdf/1712.01815) - [Nature: Mastering the game of Go without human knowledge](https://www.nature.com/articles/nature24270) - [Nature: Mastering the game of Go with deep neural networks and tree search](https://www.nature.com/articles/nature16961) - [Kocsis and Szepesvári, "Bandit based Monte-Carlo Planning"](https://cris.technion.ac.il/en/publications/bandit-based-monte-carlo-planning/) - [TadaoYamaoka/DeepLearningShogi](https://github.com/TadaoYamaoka/DeepLearningShogi)