蒙地卡羅樹搜尋

蒙特卡洛樹搜索（英語：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，一個同時使用蒙特卡洛樹搜索和深度學習的圍棋程序。