モンテカルロ木探索とは？わかりやすく解説

モンテカルロ木探索（モンテカルロきたんさく、英: Monte Carlo tree search、略称MCTS）とは、モンテカルロ法を使った木の探索の事。決定過程に対する、ヒューリスティクス（＝途中で不要な探索をやめ、ある程度の高確率で良い手を導ける）な探索アルゴリズムである。

モンテカルロ木検索は、主に囲碁・チェス・将棋などのゲームの次の着手の決定などに使用される。また、リアルタイムPCゲームや、大富豪、ポーカーなどの相手の手の内が全て分かるわけではないゲームへも使用される。

歴史

モンテカルロ法

他のアプローチでは解決不可能または困難な決定問題を、ランダム性を使用するモンテカルロ法で解決する試みは、1940年代に始まった。ブルース・アブラムソンは、1987年の博士論文で、通常の静的評価関数ではなく、ミニマックス法をランダムなゲームプレイアウトに基づく期待結果モデルと組み合わせた^[1]。アブラムソンは、期待結果モデルは「正確・高精度で簡単に推定でき、効率的に計算でき、ドメインに依存しないことが示された」と述べた^[1]。アブラムソンは、三目並べ、リバーシ、チェスの機械生成の評価関数を詳細に実験した^[1]。

この方法は、1989年に、W・エルテル・シューマンとC・ズットナーによって、定理の自動証明の分野に適用され、幅優先探索、深さ優先探索、反復深化などの探索アルゴリズムにおいて、指数関数的な探索時間を改善することが発見された^[2]^[3]^[4]。

1992年、B・ブルークマンは、コンピュータ囲碁のプログラムに初めてそれを採用した^[5]。チャンら^[6]は、マルコフ決定プロセスモデルのアダプティブマルチステージサンプリング（AMS）アルゴリズムで「適応型」サンプリングを選択して、「再帰的ロールアウトとバックトラック」のアイデアを提案した。AMSは、サンプリング/シミュレーション（モンテカルロ）ツリーの構築におけるUCBベースの探査と開発のアイデアを探求した最初の試みであり、UCT（上位信頼性ツリー）のメインシードだった^[7]。

モンテカルロ木検索

→「コンピュータ囲碁」も参照

2006年、これらの研究に触発されて^[8]、レミ・クーロンは、ゲームツリー検索へモンテカルロ法を適用させ、「Monte Carlo tree search（モンテカルロ木検索）」と命名した^[9]。L・コチシュとCs・セーペスヴァーリはUCT（ツリーに適用される上限信頼限界）アルゴリズム^[10]を開発した。S・ゲーリーらは、彼らのプログラムMoGoにUCTを実装した^[11]。2008年にMoGoは9路盤の囲碁でアマチュア有段者の域に到達し、Fuegoは9路盤でアマチュアの強豪プレーヤーに勝ち始めた^[12]。

2012年1月、モンテカルロ木探索を導入したZenは、19路盤のアマチュア二段のプレーヤーとの番勝負に3対1で勝利した^[13] 。また、クーロンが開発に携わっているCrazy Stoneも2014年の第2回電聖戦で依田紀基九段に19路盤の4子局の置き碁（ハンデ戦）で勝利するなど、着実に進歩していった^[14]。それでもなおトップ棋士に勝てるようになるには10年以上かかると考えられていたが^[15]、2016年1月、Google DeepMind社は開発を進めていたAlphaGoについて公表した。AlphaGoは2015年10月に樊麾二段に19路盤でハンディキャップなしに勝利しており、初めてプロ棋士に互先で勝利したコンピュータ碁プログラムになっていた^[16]^[17]^[18]。2016年3月、AlphaGoは国際棋戦優勝多数の李世乭九段を相手に5番勝負を行い、4勝1敗で勝利した（詳細はAlphaGo対李世乭を参照）^[19]。AlphaGoは、以前の囲碁プログラムを大幅に改善しただけでなく、機械学習は、ポリシー（移動選択）と値に人工ニューラルネットワーク（ディープラーニング手法）を使用したモンテカルロ木検索を使用したため、以前のプログラムをはるかに上回る効率が得られた^[20]。

MCTSアルゴリズムは、他のボードゲーム（例えば、ヘックス^[21] 、ハバナ（英語版）^[22]、アマゾンズ（英語版）^[23]、アリマア^[24]）、リアルタイムビデオゲーム（例えばパックマン^[25]^[26]、Fable Legends（英語版）^[27]）、不完全情報ゲーム（スカート^[28]、ポーカー^[29]、マジック・ザ・ギャザリング^[30]、カタンの開拓者たち^[31]）などに応用された。

AlphaGo登場以降はディープラーニングを利用したプログラムが主流となったが、モンテカルロ木探索を利用したプログラムの開発も一部で行われている^[32]。

アルゴリズム

モンテカルロ木探索は、最も良い手を選択するために使われ、ランダムサンプリングの結果に基づいて探索木を構築する。ゲームでのモンテカルロ木検索は、最後までプレイしたシミュレーション結果に基づいて構築する。ゲームの勝敗の結果に基づいてノードの値を更新して、最終的に勝率が高いことが見込まれる手を選択する。

最も単純な方法は、それぞれの有効な選択肢に、同数ずつプレイアウトの回数を一様に割り振って、最も勝率が良かった手を選択する方法である^[5]。これは単純なモンテカルロ木探索（pure Monte Carlo tree search）と呼ばれる。過去のプレイアウト結果に基づき、よりプレイヤーの勝利に結びつく手にプレイアウトの回数をより多く割り振ると探索効率が向上する。

モンテカルロ木探索は4つのステップからなる^[33]。

選択：根Rから始めて、葉ノードLにたどり着くまで、子ノードを選択し続ける。根が現在のゲームの状態で、葉ノードはシミュレーションが行われていないノード。より有望な方向に木が展開していくように、子ノードの選択を片寄らせる方法は、モンテカルロ木探索で重要なことであるが、探索と知識利用の所で後述する。
展開：Lが勝負を決するノードでない限り、Lから有効手の子ノードの中からCを1つ選ぶ。
シミュレーション：Cから完全なランダムプレイアウトを行う。これはロールアウトとも呼ばれる。単純な方法としては、一様分布から手を選択してランダムプレイアウトを実行する。
バックプロパゲーション：CからRへのパスに沿って、プレイアウトの結果を伝搬する。

上記のグラフは各ステップの選択を表している。ノードの数字は、そのノードからのプレイアウトの"勝った回数/プレイアウトの回数"を表している^[34]。Selectionのグラフでは、今、黒の手番である。根ノードの数字は白が21回中11回勝利していることを表している。裏を返すと黒が21回中10回勝利していることを表していて、根ノードの下の3つのノードは手が3種類あることを表していて、数字を合計すると10/21になる。

シミュレーションで白が負けたとする。白の0/1ノードを追加して、そこから根ノードまでのパスの全てのノードの分母（プレイアウトの回数）に1加算して、分子（勝った回数）は黒ノードだけ加算する。引き分けの際は、0.5加算する。こうすることで、プレイヤーは最も有望な手を自分の手番で選択することが出来る。

計算の制限時間に到達するまで、これを反復し、最も勝率が高い手を選択する。

探索と知識利用

子ノードを選択する際の難しい点は、何回かのプレイアウトの結果により高い勝率であるという知識利用（英: exploitation）とプレイアウトの回数が不足してるので探索（英: exploration）することのバランスを取ることである。手法は無数にあり Cameron B. Browne らが2012年2月までに発表された物を論文にまとめている^[35]。

UCT (Upper Confidence Tree)

探索と知識利用のバランスを取る1つの方法は、Levente Kocsis と Csaba Szepesvári が2006年に発表した UCT（木に適用したUpper Confidence Bound 1）である^[10]。UCT は Auer, Cesa-Bianchi, Fischer が2002年に発表した UCB1 (Upper Confidence Bound 1)^[36] に基づく方法である。Kocsis と Szepesvári は ${\frac {w}{n}}+c{\sqrt {\frac {\ln N}{n}}}$

^ “Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning”. Google Research Blog (27 January 2016). 2020年4月30日閲覧。

^ “Google achieves AI 'breakthrough' by beating Go champion”. BBC News (27 January 2016). 2020年4月30日閲覧。

^ “Match 1 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo”. Youtube (9 March 2016). 2020年4月30日閲覧。

^ “Google AlphaGo AI clean sweeps European Go champion”. ZDNet (28 January 2016). 2020年4月30日閲覧。

^ Broderick Arneson; Ryan Hayward; Philip Henderson (June 2009). “MoHex Wins Hex Tournament”. ICGA Journal 32 (2): 114–116. doi:10.3233/ICG-2009-32218.

^ Timo Ewalds (2011). Playing and Solving Havannah. Master's thesis, University of Alberta

^ Richard J. Lorentz (2008). “Amazons Discover Monte-Carlo”. Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.). Springer. pp. 13–24. ISBN 978-3-540-87607-6

^ Tomáš Kozelek (2009). Methods of MCTS and the game Arimaa. Master's thesis, Charles University in Prague

^ Xiaocong Gan; Yun Bao; Zhangang Han (December 2011). “Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man”. ICGA Journal 34 (4): 209–222. doi:10.3233/ICG-2011-34404.

^ Tom Pepels; Mark H. M. Winands; Marc Lanctot (September 2014). “Real-Time Monte Carlo Tree Search in Ms Pac-Man”. IEEE Transactions on Computational Intelligence and AI in Games 6 (3): 245–257. doi:10.1109/tciaig.2013.2291577.

^ Mountain, Gwaredd (2015年). “Tactical Planning and Real-time MCTS in Fable Legends”. 2019年6月8日閲覧。 “.. we implemented a simulation based approach, which involved modelling the game play and using MCTS to search the potential plan space. Overall this worked well, ...”

^ Michael Buro; Jeffrey Richard Long; Timothy Furtak; Nathan R. Sturtevant (2009). “Improving State Evaluation, Inference, and Search in Trick-Based Card Games”. IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009. Craig Boutilier (ed.). pp. 1407–1413

^ Jonathan Rubin; Ian Watson (April 2011). “Computer poker: A review”. Artificial Intelligence 175 (5–6): 958–987. doi:10.1016/j.artint.2010.12.005. オリジナルの2012-08-13時点におけるアーカイブ。.

^ C.D. Ward; P.I. Cowling (2009). “Monte Carlo Search Applied to Card Selection in Magic: The Gathering”. CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games. IEEE Press. オリジナルの2016-05-28時点におけるアーカイブ。

^ István Szita; Guillaume Chaslot; Pieter Spronck (2010). “Monte-Carlo Tree Search in Settlers of Catan”. In Jaap Van Den Herik; Pieter Spronck. Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers. Springer. pp. 21–32. ISBN 978-3-642-12992-6

^ “Ray - Computer Go Program”. computer-go-ray.com. 2025年1月25日閲覧。

^ G.M.J.B. Chaslot; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; B. Bouzy (2008). “Progressive Strategies for Monte-Carlo Tree Search”. New Mathematics and Natural Computation 4 (3): 343–359. doi:10.1142/s1793005708001094.

^ Bradberry, Jeff (2015年9月7日). “Introduction to Monte Carlo Tree Search”. 2019年4月12日閲覧。

^ C. B. Browne; E. Powley; D. Whitehouse; S. M. Lucas; P. I. Cowling; P. Rohlfshagen; S. Tavener; D. Perez et al. (February 2012). “A Survey of Monte Carlo Tree Search Methods”. IEEE Transactions on Computational Intelligence and AI in Games 4: 1-43. doi:10.1109/TCIAIG.2012.2186810. ISSN 1943-068X.

^ Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). “Finite-time Analysis of the Multiarmed Bandit Problem”. Machine Learning 47 (2/3): 235–256.

^ Auger, David; Couetoux, Adrien; Teytaud, Olivier (2013). “Continuous Upper Confidence Trees with Polynomial Exploration - Consistency”. Machine Learning and Knowledge Discovery in Databases (Springer Berlin Heidelberg) 8188: 194-209. doi:10.1007/978-3-642-40988-2_13.

^ AlphaZero: Shedding new light on the grand games of chess, shogi and Go | DeepMind

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

モンテカルロ木探索とは？ わかりやすく解説