蒙地卡羅樹搜尋

蒙地卡羅樹搜尋（英語：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]。科奇什和塞派什瓦里建議選擇遊戲樹中的每個結點移動，從而使表達式 ${\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln t}{n_{i}}}}$ 具有最大值。在該式中：

$w_{i}$ 代表第 $i$ 次移動後取勝的次數；
$n_{i}$ 代表第 $i$ 次移動後仿真的次數；
$c$ 為探索參數—理論上等於 ${\sqrt {2}}$ ；在實際中通常可憑經驗選擇；
$t$ 代表仿真總次數，等於所有 $n_{i}$ 的和。

目前蒙地卡羅樹搜尋的實現大多是基於UCT的一些變形。

參見

AlphaGo，一個同時使用蒙地卡羅樹搜尋和深度學習的圍棋程式。

參考來源

^ MCTS.ai: Everything Monte Carlo Tree Search. [2012-02-19]. （原始內容存檔於2018-11-27）.
^ Nicholas, Metropolis; Stanislaw, Ulam. The monte carlo method. Journal of the American statistical association. 1949, 44: 335-341.
^ 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）.
^ Brügmann, Bernd. Monte Carlo Go (PDF). Technical report, Department of Physics, Syracuse University. 1993 [2016-03-15]. （原始內容存檔 (PDF)於2021-04-14）.
^ Rémi Coulom. The Monte-Carlo Revolution in Go. Japanese-French Frontiers of Science Symposium (PDF). 2008 [2016-03-15]. （原始內容存檔 (PDF)於2015-02-18）.
^ 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.0 ^7.1 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）.
^ 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）.
^ 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）.
^ Markus Enzenberger, Martin Mūller. Fuego – An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search (PDF). Technical report, University of Alberta. 2008. （原始內容 (PDF)存檔於2012-05-29）.
^ The Shodan Go Bet. [2012-05-02]. （原始內容存檔於2021-04-14）.
^ Sensei's Library: KGSBotRatings. [2012-05-03]. （原始內容存檔於2021-05-06）.
^ 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）.
^ Timo Ewalds. Playing and Solving Havannah (PDF). Master's thesis, University of Alberta. 2011 [2016-03-15]. （原始內容存檔 (PDF)於2016-03-04）.
^ 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.
^ 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）.
^ Xiaocong Gan, Yun Bao, Zhangang Han. Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man. ICGA Journal. December 2011, 34 (4): 209–222.
^ 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）.
^ Tactical Planning and Real-time MCTS in Fable Legends. [2015-08-27]. （原始內容存檔於2015-08-21）.
^ Monte-Carlo Tree Search in TOTAL WAR: ROME II's Campaign AI. [2014-08-13]. （原始內容存檔於2017-03-13）.
^ 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）.
^ Jonathan Rubin, Ian Watson. Computer poker: A review (PDF). Artificial Intelligence. April 2011, 175 (5–6): 958–987. doi:10.1016/j.artint.2010.12.005. （原始內容 (PDF)存檔於2013-10-01）.
^ C.D. Ward, P.I. Cowling. Monte Carlo Search Applied to Card Selection in Magic: The Gathering. CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games (PDF). IEEE Press. 2009. （原始內容 (PDF)存檔於2016-05-28）.
^ István Szita, Guillaume Chaslot, Pieter Spronck. Monte-Carlo Tree Search in Settlers of Catan. Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers (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）.
^ 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）.
^ Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul. Finite-time Analysis of the Multiarmed Bandit Problem (PDF). Machine Learning. 2002, 47: 235–256 [2016-03-15]. doi:10.1023/a:1013689704352. （原始內容 (PDF)存檔於2014-05-12）.
^ 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. A Survey of Monte Carlo Tree Search Methods（蒙特卡洛树搜索方法综述） (PDF). IEEE Transactions on Computational Intelligence and AI in Games. March 2012, 4 (1). （原始內容 (PDF)存檔於2013-03-09）.

[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.

[Abramson-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）.

[Bruegmann-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）.

[Kocsis-Szepesvari-7] 7.0 ^7.1 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）.

[Gelly-et-al-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. Fuego – An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search (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] Tactical Planning and Real-time MCTS in Fable Legends. [2015-08-27]. （原始內容存檔於2015-08-21）.

[20] Monte-Carlo Tree Search in TOTAL WAR: ROME II's Campaign AI. [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. Computer poker: A review (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. CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games (PDF). IEEE Press. 2009. （原始內容 (PDF)存檔於2016-05-28）.

[24] István Szita, Guillaume Chaslot, Pieter Spronck. Monte-Carlo Tree Search in Settlers of Catan. Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers (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）.

[chaslot2008-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. Finite-time Analysis of the Multiarmed Bandit Problem (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）.

[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]