蒙地卡羅樹搜尋（英語：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]。
蒙地卡羅樹搜尋也被用於其他棋盤遊戲程式，如六貫棋[13]、三寶棋[14]、亞馬遜棋[15]和印度鬥獸棋[16]；即時電子遊戲，如《吃豆小姐》[17][18]、《神鬼寓言:傳奇》[19]、《羅馬II：全軍破敵》[20]；不確定性遊戲，如斯卡特[21]、撲克[22]、魔法風雲會[23]、卡坦島[24]。
原理
蒙地卡羅樹搜尋的每個迴圈包括四個步驟：[25]
- 選擇（Selection）：從根節點R開始，連續向下選擇子節點至葉子節點L。下文將給出一種選擇子節點的方法，讓遊戲樹向最佳的方向擴充，這是蒙地卡羅樹搜尋的精要所在。
- 擴充（Expansion）：除非任意一方的輸贏使得遊戲在L結束，否則建立一個或多個子節點並選取其中一個節點C。
- 仿真（Simulation）：再從節點C開始，用隨機策略進行遊戲，又稱為playout或者rollout。
- 反向傳播（Backpropagation）：使用隨機遊戲的結果，更新從C到R的路徑上的節點資訊。
每一個節點的內容代表勝利次數/遊戲次數
.svg)
探索與利用
選擇子結點的主要困難是：在較高平均勝率的移動後，在對深層次變型的利用和對少數模擬移動的探索，這二者中保持某種平衡。第一個在遊戲中平衡利用與探索的公式被稱為UCT（Upper Confidence Bounds to Trees，上限置信區間演算法 ），由匈牙利國家科學院電腦與自動化研究所進階研究員列文特·科奇什與阿爾伯塔大學全職教授喬鮑·塞派什瓦里提出[7]。UCT基於奧爾（Auer）、西薩-比安奇（Cesa-Bianchi）和費舍爾（Fischer）提出的UCB1公式[26]，並首次由馬庫斯等人應用於多級決策模型（具體為馬可夫決策過程）[27]。科奇什和塞派什瓦里建議選擇遊戲樹中的每個結點移動，從而使表達式 具有最大值。在該式中：
- 代表第次移動後取勝的次數；
- 代表第次移動後仿真的次數；
- 為探索參數—理論上等於；在實際中通常可憑經驗選擇；
- 代表仿真總次數，等於所有的和。
目前蒙地卡羅樹搜尋的實現大多是基於UCT的一些變形。
參見
參考來源
延伸閱讀
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
