PUCT は、モンテカルロ木探索(MCTS)で子ノードを選ぶための選択規則の一種である。AlphaZero 型では、ニューラルネットワークの方策出力を事前確率として使い、探索済みの価値と未探索手への探索ボーナスを組み合わせて次に読む手を選ぶ。
名前は Predictor + Upper Confidence bounds applied to Trees の略として説明されることが多い。ここで Predictor は、方策・価値ネットワークの方策出力を指す。
PUCT では、各候補手 a に対して、おおむね次のような値を計算し、最大の手を選ぶ。
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 は、子ノードの平均価値と訪問回数から探索と活用のバランスを取る。方策ネットワークのような外部の事前知識は基本的に使わない。
PUCT は、ここに P(s, a) を入れることで、ニューラルネットワークが有望と見た手を早い段階から優先できるようにする。これは、合法手数が多い将棋で MCTS を使うときに特に重要である。方策がなければ、序盤から候補手が多すぎて探索資源が薄く広がりやすい。
AlphaZero 論文では、各 simulation が木をたどる際、訪問回数が少なく、方策確率が高く、価値が高い手を選ぶと説明されている。PUCT は、この考え方を実装するための代表的な選択規則である。
自己対局では、PUCT によって MCTS の探索分布が作られ、そのルート訪問回数分布が次の方策教師になる。つまり PUCT は、対局中の読み筋を決めるだけでなく、次に学習される方策データの質にも影響する。
DeepLearningShogi の selfplay/self_play.cpp や usi/UctSearch.cpp では、UCB 値が最大となる子ノードを選ぶ処理があり、評価値 q、訪問回数に基づく項 u、ニューラルネットワーク由来の nnrate を組み合わせて q + c * u * rate 型の値を計算している。
また、ルートノードでは Dirichlet noise などのノイズ、未探索ノードの初期価値を調整する FPU reduction、勝敗確定ノード、千日手、詰み探索などが絡む。実装上の PUCT は、教科書的な式をそのまま置くだけではなく、将棋固有の規則や探索安定化の工夫と一体で調整される。
c_puct やそれに相当する探索定数を大きくすると、方策 prior や未探索手への探索が強くなりやすい。小さくすると、既に高い価値を得た手へ探索が集中しやすい。
ただし、強さへの影響はネットワークの精度、持ち時間、推論速度、ルートノイズ、温度、詰み探索、定跡、引き分け価値などと相互作用する。dlshogi のような実戦エンジンでは、単独の式だけでなく、自己対局や対局実験を通じてまとめて調整する必要がある。