モンテカルロ木探索

モンテカルロ木探索（モンテカルロきたんさく、英: 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]）などに応用された。

アルゴリズム

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

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

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

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

モンテカルロ木探索の4つのステップ

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

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

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

探索と知識利用

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

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)[35] に基づく方法である。Kocsis と Szepesvári は ${\displaystyle {\frac {w}{n}}+c{\sqrt {\frac {\ln N}{n}}}}$ が最大となる子ノードを選択することを提案している。各変数は以下の通り。

• w は勝った回数
• n はこのノードのシミュレーションの回数
• N は全シミュレーション回数
• c は定数。理論上は ${\displaystyle {\sqrt {2}}}$ であるが、実際は探索が上手く行くように調整する。

第1項の勝率は知識利用である。第2項は探索を表現していて、シミュレーション回数が少ないのを選択するようにする。

PUCT (Polynomial Upper Confidence Tree)

PUCT は David Auger, Adrien Couetoux, Olivier Teytaud が2013年に発表した手法[36]。

木は根は決断ノードとし、決断ノードとランダムノードを交互に繰り返す形で構築する。決断ノードで行為 a を選択し、ランダムノードに遷移する。

• 決断ノード z を選択した場合、
  • ${\displaystyle \lfloor n(z)^{\alpha }\rfloor >\lfloor (n(z)-1)^{\alpha }\rfloor }$ ならば、そのノードでシミュレーションを行う
  • さもなければ ${\displaystyle {\hat {V}}(z,a)+{\sqrt {\frac {n(z)^{e(d)}}{n(z,a)}}}}$ が最大となる子ノードを選択する
• ランダムノード w を選択した場合、
  • ${\displaystyle \lfloor n(w)^{\alpha }\rfloor =\lfloor (n(w)-1)^{\alpha }\rfloor }$ ならば、最も訪れていない子ノードを選択する
  • さもなければ、新しい子ノードを作成する

関数は以下の通り。

• ${\displaystyle {\hat {V}}(z,a)}$ - 決断ノード z で行為 a を選択した際のランダムノードでの平均報酬（勝率など）
• ${\displaystyle n(z)}$ - 決断ノード z の訪問回数
• ${\displaystyle n(z,a)}$ - 決断ノード z で行為 a を選択した際のランダムノードの訪問回数
• ${\displaystyle \alpha (d)}$ - 深さ d に対して定めた progressive widening 係数（定数）
• ${\displaystyle e(d)}$ - 深さ d に対して定めた探索係数（定数）

AlphaZero

David Silver らが AlphaZero にて2017年に採用した方法は PUCT を更に改変していて、以下の評価値で子ノードを選択する[37]。

${\displaystyle Q(s,a)+C(s)P(a\mid s){\frac {\sqrt {N(s)}}{1+N(s,a)}}}$

${\displaystyle C(s)=\log {\frac {1+N(s)+c_{\mbox{base}}}{c_{\mbox{base}}}}+c_{\mbox{init}}}$

関数は以下の通り。

• ${\displaystyle Q(s,a)}$ - 状態 s で行為 a を行った際の平均報酬
• ${\displaystyle P(a\mid s)}$ - 状態 s で行為 a を選択する確率。ニューラルネットワークの出力
• ${\displaystyle N(s)}$ と ${\displaystyle N(s,a)}$ - 訪問回数

参照

1. ^ Abramson, Bruce (1987). The Expected-Outcome Model of Two-Player Games. Technical report, Department of Computer Science, Columbia University. http://academiccommons.columbia.edu/download/fedora_content/download/ac:142327/CONTENT/CUCS-315-87.pdf 23 December 2013閲覧。 
2. Wolfgang Ertel; Johann Schumann; Christian Suttner (1989). “Learning Heuristics for a Theorem Prover using Back Propagation.”. In J. Retti; K. Leidlmair. 5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208,pp. 87-95.. Springer. http://www.hs-weingarten.de/~ertel/veroeff_bib.html#ESS89 
3. Christian Suttner; Wolfgang Ertel (1990). “Automatic Acquisition of Search Guiding Heuristics.”. CADE90, 10th Int. Conf. on Automated Deduction.pp. 470-484. LNAI 449.. Springer. http://www.hs-weingarten.de/~ertel/veroeff_bib.html#ES90:CADE 
4. Christian Suttner; Wolfgang Ertel (1991). “Using Back-Propagation Networks for Guiding the Search of a Theorem Prover.”. Journal of Neural Networks Research & Applications 2 (1): 3–16. http://www.hs-weingarten.de/~ertel/veroeff_bib.html#ES90:IJNN. 
5. ^ Brügmann, Bernd (1993). Monte Carlo Go. Technical report, Department of Physics, Syracuse University. http://www.ideanest.com/vegos/MonteCarloGo.pdf 
6. Chang, Hyeong Soo; Fu, Michael C.; Hu, Jiaqiao; Marcus, Steven I. (2005). “An Adaptive Sampling Algorithm for Solving Markov Decision Processes”. Operations Research 53: 126–139. doi:10.1287/opre.1040.0145. hdl:1903/6264. http://scholar.rhsmith.umd.edu/sites/default/files/mfu/files/cfhm05.pdf?m=1449834091. 
7. Hyeong Soo Chang; Michael Fu; Jiaqiao Hu; Steven I. Marcus (2016). “Google DeepMind's Alphago: O.R.'s unheralded role in the path-breaking achievement”. OR/MS Today 45 (5): 24–29. https://www.informs.org/ORMS-Today/Public-Articles/October-Volume-43-Number-5. 
8. Rémi Coulom (2008). “The Monte-Carlo Revolution in Go”. Japanese-French Frontiers of Science Symposium. http://remi.coulom.free.fr/JFFoS/JFFoS.pdf 
9. Rémi Coulom (2007). “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search”. Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers. H. Jaap van den Herik, Paolo Ciancarini, H. H. L. M. Donkers (eds.). Springer. pp. 72–83. ISBN 978-3-540-75537-1 
10. ^ Kocsis, Levente; Szepesvári, Csaba (2006). "Bandit based Monte-Carlo Planning". In Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4212. Springer. pp. 282–293. CiteSeerX 10.1.1.102.1296. doi:10.1007/11871842_29. ISBN 3-540-45375-X。
11. Sylvain Gelly; Yizao Wang; Rémi Munos; Olivier Teytaud (November 2006). Modification of UCT with Patterns in Monte-Carlo Go. Technical report, INRIA. http://hal.inria.fr/docs/00/11/72/66/PDF/MoGoReport.pdf 
12. Markus Enzenberger; Martin Mūller (2008). Fuego – An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search. Technical report, University of Alberta. http://pug.raph.free.fr/files/Fuego.pdf 
13. “The Shodan Go Bet”. 2012年5月2日閲覧。
14. “第２回電聖戦”. 日本棋院. 2021年10月8日閲覧。
15. “なぜ「囲碁」だったのか。なぜ「10年かかる」と言われていたのか──AlphaGo前日譚”. WIRED (2016年3月15日). 2021年10月8日閲覧。
16. Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis et al. (28 January 2016). “Mastering the game of Go with deep neural networks and tree search”. Nature 529 (7587): 484–489. Bibcode: 2016Natur.529..484S. doi:10.1038/nature16961. ISSN 0028-0836. PMID 26819042. 
17. “Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning”. Google Research Blog (27 January 2016). 2020年4月30日閲覧。
18. “Google achieves AI 'breakthrough' by beating Go champion”. BBC News (27 January 2016). 2020年4月30日閲覧。
19. “Match 1 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo”. Youtube (9 March 2016). 2020年4月30日閲覧。
20. “Google AlphaGo AI clean sweeps European Go champion”. ZDNet (28 January 2016). 2020年4月30日閲覧。
21. Broderick Arneson; Ryan Hayward; Philip Henderson (June 2009). “MoHex Wins Hex Tournament”. ICGA Journal 32 (2): 114–116. doi:10.3233/ICG-2009-32218. http://webdocs.cs.ualberta.ca/~hayward/papers/rptPamplona.pdf. 
22. Timo Ewalds (2011). Playing and Solving Havannah. Master's thesis, University of Alberta. http://havannah.ewalds.ca/static/thesis.pdf 
23. 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 
24. Tomáš Kozelek (2009). Methods of MCTS and the game Arimaa. Master's thesis, Charles University in Prague. http://arimaa.com/arimaa/papers/TomasKozelekThesis/mt.pdf 
25. 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. 
26. 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. 
27. 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, ...”
28. 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 
29. 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時点におけるアーカイブ。. https://web.archive.org/web/20120813081731/https://www.cs.auckland.ac.nz/~jrub001/files/CPReviewPreprintAIJ.pdf. 
30. 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時点におけるアーカイブ。. http://scim.brad.ac.uk/staff/pdf/picowlin/CIG2009.pdf 
31. 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. http://ticc.uvt.nl/icga/acg12/proceedings/Contribution100.pdf 
32. 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. https://dke.maastrichtuniversity.nl/m.winands/documents/pMCTS.pdf. 
33. Bradberry, Jeff (2015年9月7日). “Introduction to Monte Carlo Tree Search”. 2019年4月12日閲覧。
34. 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. http://mcts.ai/pubs/mcts-survey-master.pdf. 
35. Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). “Finite-time Analysis of the Multiarmed Bandit Problem”. Machine Learning 47 (2/3): 235–256. https://link.springer.com/content/pdf/10.1023/A:1013689704352.pdf. 
36. 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. 
37. AlphaZero: Shedding new light on the grand games of chess, shogi and Go | DeepMind