# Virtual loss Virtual loss は、並列化された [モンテカルロ木探索(MCTS)](/shogi/shogiwiki/search/monte-carlo-tree-search/)で、複数のスレッドや探索ワーカーが同じ有望ノードへ集中しすぎることを防ぐための技術である。日本語では `仮想損失` と訳されることがある。 MCTS では、選択規則に従って有望な子ノードをたどる。並列探索では、まだ評価が終わっていないノードが非常に有望に見えたままだと、他のスレッドも同じ経路を選び、探索資源が重複してしまう。Virtual loss は、この重複を避けるために、探索中の経路を一時的に少し悪く見せる。 ## 基本的な考え方 Virtual loss の典型的な流れは次の通りである。 1. あるスレッドが MCTS の経路を選ぶ。 2. その経路上のノードに、一時的な訪問回数や損失を加える。 3. 他のスレッドからは、その経路が少し選ばれにくく見える。 4. 評価が終わったら、一時的な値を取り除くか、実際の探索結果で上書きする。 これにより、複数スレッドが同じ葉へ向かう確率が下がり、並列化したときの探索効率が上がる。 ## PUCT との関係 [PUCT](/shogi/shogiwiki/search/puct/) では、平均価値、方策 prior、訪問回数から子ノードを選ぶ。Virtual loss は、この訪問回数や価値の見え方を一時的に変えることで、選択規則の結果に影響を与える。 たとえば、ある手を評価中に訪問回数だけを先に増やしておくと、その手の探索ボーナスは下がる。その結果、他のスレッドは別の候補手を読みやすくなる。実装によっては、訪問回数だけでなく仮想的な負けを加えて、平均価値も一時的に下げる。 ## 並列 MCTS での位置づけ 並列 MCTS には、主に root parallelization、leaf parallelization、tree parallelization などの方法がある。Virtual loss は、とくに複数スレッドが同じ探索木を共有する tree parallelization で重要になる。 ロックだけでもデータ競合は防げるが、ロックは「同時に壊さない」ための仕組みであり、「同じ経路を重複して読まない」ことまでは保証しない。Virtual loss は、探索の選択規則そのものに一時的な混雑情報を入れる技術である。 ## dlshogi での位置づけ 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 更新、破棄された経路の扱い、[バッチ推論](/shogi/shogiwiki/search/batch-inference/)待ちの扱いを慎重にそろえる必要がある。 ## 関連項目 - [モンテカルロ木探索(MCTS)](/shogi/shogiwiki/search/monte-carlo-tree-search/) - [PUCT](/shogi/shogiwiki/search/puct/) - [FPU reduction](/shogi/shogiwiki/search/fpu-reduction/) - [バッチ推論](/shogi/shogiwiki/search/batch-inference/) - [方策・価値ネットワーク](/shogi/shogiwiki/evaluation-function/policy-value-network/) - [dlshogi](/shogi/shogiwiki/softs/dlshogi/) - [AlphaZero](/shogi/shogiwiki/alphazero/) ## 参考にしたホームページ - [Chaslot et al., "Parallel Monte-Carlo tree search"](https://cris.maastrichtuniversity.nl/en/publications/parallel-monte-carlo-tree-search) - [Nature: Mastering the game of Go with deep neural networks and tree search](https://www.nature.com/articles/nature16961) - [PubMed: Mastering the game of Go with deep neural networks and tree search](https://pubmed.ncbi.nlm.nih.gov/26819042/) - [TadaoYamaoka/DeepLearningShogi](https://github.com/TadaoYamaoka/DeepLearningShogi)