蒙特卡洛树搜索

蒙特卡洛树搜索（英語：Monte Carlo tree search；简称：MCTS）是一种用于某些决策过程的启发式搜索算法，最引人注目的是在游戏中的使用。一个主要例子是电脑围棋程序^[1]，它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。

历史

基于随机抽样的蒙特卡洛方法可以追溯到20世纪40年代^[2]。布鲁斯·艾布拉姆森（Bruce Abramson）在他1987年的博士论文中探索了这一想法，称它“展示出了准确、精密、易估、有效可计算以及域独立的特性。”^[3]他深入试验了井字棋，然后试验了黑白棋和国际象棋的机器生成的评估函数。1992年，B·布鲁格曼（B. Brügmann）首次将其应用于对弈程序^[4]，但他的想法未获得重视。2006年堪称围棋领域蒙特卡洛革命的一年^[5]，雷米·库洛姆（Remi Coulom）描述了蒙特卡洛方法在游戏树搜索的应用并命名为蒙特卡洛树搜索^[6]。列文特·科奇什（Levente Kocsis）和乔鲍·塞派什瓦里（Csaba Szepesvári）开发了UCT算法^[7]，西尔万·热利（Sylvain Gelly）等人在他们的程序MoGo中实现了UCT^[8]。2008年，MoGo在九路围棋中达到段位水平^[9]，Fuego程序开始在九路围棋中战胜实力强劲的业余棋手^[10]。2012年1月，Zen程序在19路围棋上以3：1击败二段棋手约翰·特朗普（John Tromp）^[11]。

 

自2007年以来KGS围棋服务器上最优秀围棋程序的评级。自2006年以来，最优秀的程序全部使用蒙特卡洛树搜索。^[12]

蒙特卡洛树搜索也被用于其他棋盘游戏程序，如六贯棋^[13]、三宝棋^[14]、亚马逊棋^[15]和印度斗兽棋^[16]；即时电子游戏，如《吃豆小姐（英语：Ms. Pac-Man）》^[17][18]、《神鬼寓言:传奇（英语：Fable Legends）》^[19]、《罗马II：全面战争》^[20]；不确定性游戏，如斯卡特^[21]、扑克^[22]、万智牌^[23]、卡坦岛^[24]。

原理

蒙特卡洛树搜索的每个循环包括四个步骤：^[25]

• 选择（Selection）：从根節点R开始，连续向下选择子節点至叶子節点L。下文將给出一种选择子節点的方法，让游戏树向最优的方向扩展，这是蒙特卡洛树搜索的精要所在。
• 扩展（Expansion）：除非任意一方的输赢使得游戏在L结束，否则创建一个或多个子節点并选取其中一个節点C。
• 仿真（Simulation）：再从節点C开始，用随机策略进行游戏，又称为playout或者rollout。
• 反向传播（Backpropagation）：使用随机游戏的结果，更新从C到R的路径上的節点信息。

每一個節點的內容代表勝利次數/遊戲次數

 

蒙特卡洛树搜索的步骤

探索与利用

选择子结点的主要困难是：在较高平均胜率的移动后，在对深层次变型的利用和对少数模拟移动的探索，这二者中保持某种平衡。第一个在游戏中平衡利用与探索的公式被称为UCT（Upper Confidence Bounds to Trees，上限置信区间算法 ），由匈牙利国家科学院计算机与自动化研究所高级研究员列文特·科奇什与阿尔伯塔大学全职教授乔鲍·塞派什瓦里提出^[7]。UCT基于奥尔（Auer）、西萨-比安奇（Cesa-Bianchi）和费舍尔（Fischer）提出的UCB1公式^[26]，并首次由马库斯等人应用于多级决策模型（具体为马尔可夫决策过程）^[27]。科奇什和塞派什瓦里建议选择游戏树中的每个结点移动，从而使表达式 ${\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln t}{n_{i}}}}}$ 具有最大值。在该式中：

• ${\displaystyle w_{i}}$ 代表第${\displaystyle i}$ 次移动后取胜的次数；
• ${\displaystyle n_{i}}$ 代表第${\displaystyle i}$ 次移动后仿真的次数；
• ${\displaystyle c}$ 为探索参数—理论上等于${\displaystyle {\sqrt {2}}}$ ；在实际中通常可凭经验选择；
• ${\displaystyle t}$ 代表仿真总次数，等于所有${\displaystyle n_{i}}$ 的和。

目前蒙特卡洛树搜索的实现大多是基于UCT的一些变形。

参见

• AlphaGo，一个同时使用蒙特卡洛树搜索和深度学习的围棋程序。

参考来源

1. MCTS.ai: Everything Monte Carlo Tree Search. [2012-02-19]. （原始内容于2018-11-27）. 
2. Nicholas, Metropolis; Stanislaw, Ulam. The monte carlo method. Journal of the American statistical association. 1949, 44: 335-341. 
3. Abramson, Bruce. The Expected-Outcome Model of Two-Player Games (PDF). Technical report, Department of Computer Science, Columbia University. 1987 [23 December 2013]. （原始内容 (PDF)于2016-10-27）. 
4. Brügmann, Bernd. Monte Carlo Go (PDF). Technical report, Department of Physics, Syracuse University. 1993 [2016-03-15]. （原始内容 (PDF)于2021-04-14）. 
5. Rémi Coulom. The Monte-Carlo Revolution in Go. Japanese-French Frontiers of Science Symposium (PDF). 2008 [2016-03-15]. （原始内容 (PDF)于2015-02-18）. 
6. Rémi Coulom. 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. 2007: 72–83 [2016-03-15]. ISBN 978-3-540-75537-1. （原始内容于2021-04-14）. 
7. Kocsis, Levente; Szepesvári, Csaba. Bandit based Monte-Carlo Planning. Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings. Lecture Notes in Computer Science 4212. Johannes Fürnkranz, Tobias Scheffer, Myra Spiliopoulou (eds.). Springer. 2006: 282–293 [2016-03-15]. ISBN 3-540-45375-X. （原始内容于2021-05-06）. 
8. Sylvain Gelly, Yizao Wang, Rémi Munos, Olivier Teytaud. Modification of UCT with Patterns in Monte-Carlo Go (PDF). Technical report, INRIA. November 2006 [2016-03-15]. （原始内容 (PDF)于2014-07-30）. 
9. Chang-Shing Lee, Mei-Hui Wang, Guillaume Chaslot, Jean-Baptiste Hoock, Arpad Rimmel, Olivier Teytaud, Shang-Rong Tsai, Shun-Chin Hsu, Tzung-Pei Hong. The Computational Intelligence of MoGo Revealed in Taiwan’s Computer Go Tournaments (PDF). IEEE Transactions on Computational Intelligence and AI in Games. 2009, 1 (1): 73–89 [2016-03-15]. doi:10.1109/tciaig.2009.2018703. （原始内容 (PDF)于2013-09-26）. 
10. Markus Enzenberger, Martin Mūller. (PDF). Technical report, University of Alberta. 2008. （原始内容 (PDF)存档于2012-05-29）. 
11. The Shodan Go Bet. [2012-05-02]. （原始内容于2021-04-14）. 
12. Sensei's Library: KGSBotRatings. [2012-05-03]. （原始内容于2021-05-06）. 
13. Broderick Arneson, Ryan Hayward, Philip Henderson. MoHex Wins Hex Tournament (PDF). ICGA Journal. June 2009, 32 (2): 114–116 [2016-03-15]. （原始内容 (PDF)于2021-04-16）. 
14. Timo Ewalds. Playing and Solving Havannah (PDF). Master's thesis, University of Alberta. 2011 [2016-03-15]. （原始内容 (PDF)于2016-03-04）. 
15. Richard J. Lorentz. 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. 2008: 13–24. ISBN 978-3-540-87607-6. 
16. Tomáš Kozelek. Methods of MCTS and the game Arimaa (PDF). Master's thesis, Charles University in Prague. 2009 [2016-03-15]. （原始内容 (PDF)于2021-04-16）. 
17. Xiaocong Gan, Yun Bao, Zhangang Han. Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man. ICGA Journal. December 2011, 34 (4): 209–222. 
18. Tom Pepels, Mark H. M. Winands, Marc Lanctot. Real-Time Monte Carlo Tree Search in Ms Pac-Man. IEEE Transactions on Computational Intelligence and AI in Games. September 2014, 6 (3): 245–257 [2016-03-15]. doi:10.1109/tciaig.2013.2291577. （原始内容于2015-09-09）. 
19. . [2015-08-27]. （原始内容存档于2015-08-21）. 
20. . [2014-08-13]. （原始内容存档于2017-03-13）. 
21. Michael Buro, Jeffrey Richard Long, Timothy Furtak, Nathan R. Sturtevant. 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.). 2009: 1407–1413 [2016-03-15]. （原始内容于2021-04-14）. 
22. Jonathan Rubin, Ian Watson. (PDF). Artificial Intelligence. April 2011, 175 (5–6): 958–987. doi:10.1016/j.artint.2010.12.005. （原始内容 (PDF)存档于2013-10-01）. 
23. C.D. Ward, P.I. Cowling. Monte Carlo Search Applied to Card Selection in Magic: The Gathering. (PDF). IEEE Press. 2009. （原始内容 (PDF)存档于2016-05-28）. 
24. István Szita, Guillaume Chaslot, Pieter Spronck. Monte-Carlo Tree Search in Settlers of Catan. (PDF). H. Jaap van den Herik, Pieter Spronck (eds.). Springer. 2010: 21–32 [2016-03-15]. ISBN 978-3-642-12992-6. （原始内容 (PDF)存档于2016-03-04）. 
25. G.M.J.B. Chaslot, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik, B. Bouzy. Progressive Strategies for Monte-Carlo Tree Search (PDF). New Mathematics and Natural Computation. 2008, 4 (3): 343–359 [2016-03-15]. doi:10.1142/s1793005708001094. （原始内容 (PDF)于2021-04-14）. 
26. Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul. (PDF). Machine Learning. 2002, 47: 235–256 [2016-03-15]. doi:10.1023/a:1013689704352. （原始内容 (PDF)存档于2014-05-12）. 
27. Chang, Hyeong Soo; Fu, Michael C.; Hu, Jiaqiao; Marcus, Steven I. An Adaptive Sampling Algorithm for Solving Markov Decision Processes (PDF). Operations Research. 2005, 53: 126–139 [2016-03-15]. （原始内容 (PDF)于2021-04-20）. 

延伸阅读

• Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, Simon Colton. (PDF). IEEE Transactions on Computational Intelligence and AI in Games. March 2012, 4 (1). （原始内容 (PDF)存档于2013-03-09）.