Virtual loss は、並列化された モンテカルロ木探索(MCTS)で、複数のスレッドや探索ワーカーが同じ有望ノードへ集中しすぎることを防ぐための技術である。日本語では 仮想損失 と訳されることがある。
MCTS では、選択規則に従って有望な子ノードをたどる。並列探索では、まだ評価が終わっていないノードが非常に有望に見えたままだと、他のスレッドも同じ経路を選び、探索資源が重複してしまう。Virtual loss は、この重複を避けるために、探索中の経路を一時的に少し悪く見せる。
Virtual loss の典型的な流れは次の通りである。
これにより、複数スレッドが同じ葉へ向かう確率が下がり、並列化したときの探索効率が上がる。
PUCT では、平均価値、方策 prior、訪問回数から子ノードを選ぶ。Virtual loss は、この訪問回数や価値の見え方を一時的に変えることで、選択規則の結果に影響を与える。
たとえば、ある手を評価中に訪問回数だけを先に増やしておくと、その手の探索ボーナスは下がる。その結果、他のスレッドは別の候補手を読みやすくなる。実装によっては、訪問回数だけでなく仮想的な負けを加えて、平均価値も一時的に下げる。
並列 MCTS には、主に root parallelization、leaf parallelization、tree parallelization などの方法がある。Virtual loss は、とくに複数スレッドが同じ探索木を共有する tree parallelization で重要になる。
ロックだけでもデータ競合は防げるが、ロックは「同時に壊さない」ための仕組みであり、「同じ経路を重複して読まない」ことまでは保証しない。Virtual loss は、探索の選択規則そのものに一時的な混雑情報を入れる技術である。
DeepLearningShogi の USI エンジン側 usi/UctSearch.cpp には、AddVirtualLoss、SubVirtualLoss、UpdateResult がある。VIRTUAL_LOSS は usi/UctSearch.h で定義され、選択した子ノードと現在ノードの move_count に一時的な値を加える。
探索経路が評価待ちになったときは Virtual loss を残し、評価が終わったら実際の結果を UpdateResult で反映する。破棄された探索経路については SubVirtualLoss で戻す処理がある。
dlshogi のように、ニューラルネットワーク推論をバッチ化しながら MCTS を進める実装では、評価待ちのノードが発生しやすい。その間に他の探索が同じノードへ殺到しないようにするため、Virtual loss は実用上かなり重要な部品になる。
Virtual loss を強くしすぎると、本当に有望な手から探索が離れすぎることがある。弱すぎると、並列化しても同じ経路に探索が重複しやすい。
また、仮想損失を戻し忘れたり、評価結果との整合が崩れたりすると、訪問回数や平均価値が壊れ、探索が不安定になる。実装では、ロック、atomic 更新、破棄された経路の扱い、バッチ推論待ちの扱いを慎重にそろえる必要がある。