FPU reduction は、PUCT や モンテカルロ木探索(MCTS)で、まだ一度も探索していない手の初期価値を少し低く見積もるための技術である。FPU は First Play Urgency の略で、未訪問の子ノードに仮の Q 値をどう与えるかという問題を指す。
未訪問の手には探索結果が無いため、平均価値 Q(s, a) をそのまま計算できない。そこで、親ノードの価値や固定値を仮の初期価値として使う。FPU reduction は、その仮の初期価値から一定量を引くことで、低 prior の未探索手へ探索が広がりすぎることを抑える。
PUCT では、子ノードの選択に Q + U のような値を使う。訪問済みの手では Q を探索結果から計算できるが、未訪問の手では Q が未定である。
単純な方法では、未訪問の手の Q を 0 や親ノードの価値にする。しかし、方策 prior が低い未訪問手を次々に試しすぎると、強い候補手の読みが浅くなる。FPU reduction は、未訪問手の初期価値を親ノードの価値より少し下げることで、探索をやや保守的にする。
Q_unvisited = Q_parent - fpu_reduction実際の実装では、単純な定数差だけでなく、訪問済み prior の合計や探索状況に応じて reduction を変えることもある。
PUCT の探索ボーナス U は、方策 prior が高く訪問回数が少ない手を押し上げる。FPU reduction は、未訪問手の Q をどう置くかで、探索ボーナスとのバランスを調整する。
reduction が小さいと、未訪問手が楽観的に扱われ、探索が広がりやすい。reduction が大きいと、既に良さそうだと分かっている手へ探索が集中しやすい。どちらが良いかは、ネットワークの方策精度、持ち時間、探索回数、ノイズ、温度などに依存する。
Virtual loss は、並列探索中の経路を一時的に選ばれにくくする技術である。評価中のノードへ他のスレッドが集中しすぎないようにするために使う。
FPU reduction は、未訪問ノードの初期価値をどう置くかの技術である。どちらも PUCT の選択に影響するが、Virtual loss は「現在誰かが読んでいる経路」への一時的な混雑制御であり、FPU reduction は「まだ読んでいない手」への初期評価である。
DeepLearningShogi の selfplay/self_play.cpp と usi/UctSearch.cpp では、子ノード選択時に fpu_reduction を使って未探索手の parent_q を決めている。
selfplay/self_play.cpp では、root 以外で c_fpu_reduction を使い、root では reduction を 0 としている。USI エンジン側 usi/UctSearch.cpp では、通常ノード用の c_fpu_reduction に加えて、root 用の c_fpu_reduction_root も持っている。USI オプションとしては C_fpu_reduction と C_fpu_reduction_root が設定される。
また dlshogi/utils/usi_params_optimizer.py では、C_fpu_reduction が探索パラメータ最適化の対象に含まれている。これは、FPU reduction が単なる実装細部ではなく、実戦の強さや探索の性質に影響する調整項目であることを示している。
FPU reduction を強くしすぎると、方策 prior が低いが実は良い手を読み落としやすくなる。弱すぎると、低 prior の未訪問手に探索が広がりすぎ、深く読むべき候補に十分な探索資源が集まりにくくなる。
特に将棋では、低 prior の妙手、詰み筋、受けの手、入玉に関わる手などが問題になることがある。FPU reduction は、PUCT の定数、Dirichlet noise、温度、詰み探索、持ち時間、ニューラルネットワークの精度と合わせて調整する必要がある。