# モンテカルロ木探索(MCTS) モンテカルロ木探索(Monte Carlo Tree Search, MCTS)は、木探索とモンテカルロ法によるサンプリングを組み合わせた探索手法である。完全に全幅で読むのではなく、試行を繰り返しながら有望そうな手に探索資源を集中させる。 コンピュータ将棋では、[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)を中心とする探索が長く主流である。一方、[AlphaZero](/shogi/shogiwiki/alphazero/) 型や [dlshogi](/shogi/shogiwiki/softs/dlshogi/) では、方策・価値ネットワークと組み合わせた MCTS が重要な役割を持つ。 ## 基本的な流れ MCTS は、一般に次の処理を何度も繰り返す。 1. 選択 既に展開されている木の中を、探索済みの評価と未探索手への期待をもとに葉へ進む。 2. 展開 必要に応じて新しい子ノードを作る。 3. 評価 原始モンテカルロ探索ではランダムプレイアウトで終局まで進める。AlphaZero 型ではニューラルネットワークの価値出力で葉を評価する。 4. 逆伝播 評価結果を通ったノードへ戻し、訪問回数や平均価値を更新する。 この反復により、よく調べられた手ほど訪問回数が増える。最終的には、訪問回数が最大の手や、[温度パラメータ](/shogi/shogiwiki/search/temperature/)で調整した訪問回数分布から選んだ手を指す。 ## UCT と PUCT MCTS では、どの子ノードを選ぶかが重要である。古典的には UCT(Upper Confidence bounds applied to Trees)が使われる。UCT は、平均評価が高い手を選びつつ、まだ十分に調べていない手にも探索機会を与える。 AlphaZero 型では、方策ネットワークの事前確率を選択式に入れた [PUCT](/shogi/shogiwiki/search/puct/) 系の選択が使われることが多い。これは、ニューラルネットワークが有望と見た手を優先しながら、訪問回数による探索と活用のバランスを取る考え方である。 ## AlphaZero 型での使われ方 AlphaZero では、局面を入力したニューラルネットワークが、合法手ごとの方策と局面価値を出力する。MCTS はこの方策を探索の事前分布として使い、葉局面では価値ネットワークで評価する。 自己対局では、MCTS のルート訪問回数分布が方策の教師になる。つまり MCTS は、対局中に強い手を選ぶためだけでなく、次の学習データを作るためにも使われる。この点が、単なる思考部としての探索とは少し異なる。 AlphaZero 論文では、各手の探索に 800 simulations を用いたことが記載されている。また、探索の多様性を確保するため、ルートの方策に [Dirichlet noise](/shogi/shogiwiki/search/dirichlet-noise/) を加える。将棋では合法手数の規模に合わせ、チェスや囲碁とは異なる noise パラメータが使われている。 ## 将棋での注意点 将棋で MCTS を使う場合、持ち駒による合法手数の多さ、詰みの重要性、入玉規則、千日手、持将棋、定跡との関係などを考える必要がある。とくに終盤では、ニューラルネットワークの価値評価だけでは読み抜けが起こりうるため、詰み探索や勝敗確定ノードの伝播などが重要になる。 dlshogi では、MCTS による自己対局と USI エンジンでの探索が実装されている。実装上は、方策・価値の[バッチ推論](/shogi/shogiwiki/search/batch-inference/)、[NN キャッシュ](/shogi/shogiwiki/search/nn-cache/)、[Virtual loss](/shogi/shogiwiki/search/virtual-loss/)、詰み探索、df-pn、定跡、温度やノイズなど、実戦運用に必要な要素が組み合わされている。 ## アルファベータ法との違い アルファベータ法は、minimax の値を保ったまま不要な枝を枝刈りする深さ優先探索である。良い手の並べ替え、静止探索、置換表、枝刈り、延長などの技術と相性がよく、将棋ソフトでは非常に強い。 MCTS は、訪問回数とサンプリングに基づいて探索資源を配分する。評価関数やニューラルネットワークが不確かな局面でも、探索を重ねることで手の有望度を推定できる。一方、強制手順や詰みのように厳密な読みが必要な局面では、専用の詰み探索や alpha-beta 系の読みが有利になる場合がある。 そのため現実の将棋AIでは、MCTS だけで完結させるというより、ニューラルネットワーク、詰み探索、定跡、時間管理、自己対局による学習などを組み合わせて使うことが多い。 ## 関連項目 - [探索](/shogi/shogiwiki/search/) - [ゲーム木](/shogi/shogiwiki/search/search-tree/) - [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/) - [PUCT](/shogi/shogiwiki/search/puct/) - [Dirichlet noise](/shogi/shogiwiki/search/dirichlet-noise/) - [温度パラメータ](/shogi/shogiwiki/search/temperature/) - [Virtual loss](/shogi/shogiwiki/search/virtual-loss/) - [AlphaZero](/shogi/shogiwiki/alphazero/) - [自己対局](/shogi/shogiwiki/self-play/) - [dlshogi](/shogi/shogiwiki/softs/dlshogi/) - [Proof-Number Search](/shogi/shogiwiki/search/proof-number-search/) ## 参考にしたホームページ - [Browne et al., "A Survey of Monte Carlo Tree Search Methods"](https://research.monash.edu/en/publications/a-survey-of-monte-carlo-tree-search-methods/) - [Kocsis and Szepesvári, "Bandit based Monte-Carlo Planning"](https://cris.technion.ac.il/en/publications/bandit-based-monte-carlo-planning/) - [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) - [TadaoYamaoka/DeepLearningShogi](https://github.com/TadaoYamaoka/DeepLearningShogi)