モンテカルロ木探索
モンテカルロ木探索は、最も良い手を選択するために使われ、ランダムサンプリングの結果に基づいて探索木を構築する。ゲームでのモンテカルロ木検索は、最後までプレイしたシミュレーション結果に基づいて構築する。ゲームの勝敗の結果に基づいてノードの値を更新して、最終的に勝率が高いことが見込まれる手を選択する。
最も単純な方法は、それぞれの有効な選択肢に、同数ずつプレイアウトの回数を一様に割り振って、最も勝率が良かった手を選択する方法である。これは単純なモンテカルロ木探索(pure Monte Carlo tree search)と呼ばれる。過去のプレイアウト結果に基づき、よりプレイヤーの勝利に結びつく手にプレイアウトの回数をより多く割り振ると探索効率が向上する。
モンテカルロ木探索は4つのステップからなる。
選択:根Rから始めて、葉ノードLにたどり着くまで、子ノードを選択し続ける。根が現在のゲームの状態で、葉ノードはシミュレーションが行われていないノード。より有望な方向に木が展開していくように、子ノードの選択を片寄らせる方法は、モンテカルロ木探索で重要なことであるが、探索と知識利用の所で後述する。
展開:Lが勝負を決するノードでない限り、Lから有効手の子ノードの中からCを1つ選ぶ。
2006年、これらの研究に触発されて、レミ・クーロンは、ゲームツリー検索へモンテカルロ法を適用させ、「Monte Carlo tree search(モンテカルロ木検索)」と命名した。L・コチシュとCs・セーペスヴァーリはUCT(ツリーに適用される上限信頼限界)アルゴリズムを開発した。S・ゲーリーらは、彼らのプログラムMoGoにUCTを実装した。2008年にMoGoは9路盤の囲碁でアマチュア有段者の域に到達し、Fuegoは9路盤でアマチュアの強豪プレーヤーに勝ち始めた。
2012年1月、モンテカルロ木探索を導入したZenは、19路盤のアマチュア二段のプレーヤーとの番勝負に3対1で勝利した 。また、クーロンが開発に携わっているCrazy Stoneも2014年の第2回電聖戦で依田紀基九段に19路盤の4子局の置き碁(ハンデ戦)で勝利するなど、着実に進歩していった。それでもなおトップ棋士に勝てるようになるには10年以上かかると考えられていたが、2016年1月、Google DeepMind社は開発を進めていたAlphaGoについて公表した。
edu/sites/default/files/mfu/files/cfhm05.pdf?m=1449834091.
↑ 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.
↑ Rémi Coulom (2008). “The Monte-Carlo Revolution in Go”. Japanese-French Frontiers of Science Symposium. http://remi.coulom.free.fr/JFFoS/JFFoS.pdf
↑ 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.
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.
↑ 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.
↑ 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
子ノードを選択する際の難しい点は、何回かのプレイアウトの結果により高い勝率であるという知識利用(英: exploitation)とプレイアウトの回数が不足してるので探索(英: exploration)することのバランスを取ることである。手法は無数にあり Cameron B. Browne らが2012年2月までに発表された物を論文にまとめている。
AlphaGoは2015年10月に樊麾二段に19路盤でハンディキャップなしに勝利しており、初めてプロ棋士に互先で勝利したコンピュータ碁プログラムになっていた。2016年3月、AlphaGoは国際棋戦優勝多数の李世乭九段を相手に5番勝負を行い、4勝1敗で勝利した(詳細はAlphaGo対李世乭を参照)。AlphaGoは、以前の囲碁プログラムを大幅に改善しただけでなく、機械学習は、ポリシー(移動選択)と値に人工ニューラルネットワーク(ディープラーニング手法)を使用したモンテカルロ木検索を使用したため、以前のプログラムをはるかに上回る効率が得られた。
MCTSアルゴリズムは、他のボードゲーム(例えば、ヘックス 、ハバナ(英語版)、アマゾンズ(英語版)、アリマア)、リアルタイムビデオゲーム(例えばパックマン、Fable Legends(英語版))、不完全情報ゲーム(スカート、 ポーカー、マジック・ザ・ギャザリング、カタンの開拓者たち)などに応用された。
Google Research Blog (2016年1月27日). 2020年4月30日閲覧。
↑ “Google achieves AI 'breakthrough' by beating Go champion”. BBC News (2016年1月27日). 2020年4月30日閲覧。
↑ “Match 1 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo”. Youtube (2016年3月9日). 2020年4月30日閲覧。
↑ “Google AlphaGo AI clean sweeps European Go champion”. ZDNet (2016年1月28日). 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. http://webdocs.cs.ualberta.ca/~hayward/papers/rptPamplona.pdf.
↑ Timo Ewalds (2011). Playing and Solving Havannah. Master's thesis, University of Alberta. http://havannah.ewalds.ca/static/thesis.pdf
↑ Richard J. Lorentz (2008).