热门问题
时间线
聊天
视角

蒙地卡羅樹搜尋

来自维基百科,自由的百科全书

Remove ads

蒙特卡洛樹搜索(英語: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]

Thumb
自2007年以來KGS圍棋服務器上最優秀圍棋程序的評級。自2006年以來,最優秀的程序全部使用蒙特卡洛樹搜索。[12]

蒙特卡洛樹搜索也被用於其他棋盤遊戲程序,如六貫棋[13]三寶棋[14]亞馬遜棋[15]印度鬥獸棋[16];即時電子遊戲,如《吃豆小姐英語Ms. Pac-Man[17][18]、《神鬼寓言:傳奇英語Fable Legends[19]、《羅馬II:全面戰爭[20];不確定性遊戲,如斯卡特[21]撲克[22]萬智牌[23]卡坦島[24]

Remove ads

原理

蒙特卡洛樹搜索的每個循環包括四個步驟:[25]

  • 選擇(Selection):從根節點R開始,連續向下選擇子節點至葉子節點L。下文將給出一種選擇子節點的方法,讓遊戲樹向最優的方向擴展,這是蒙特卡洛樹搜索的精要所在。
  • 擴展(Expansion):除非任意一方的輸贏使得遊戲在L結束,否則創建一個或多個子節點並選取其中一個節點C
  • 仿真(Simulation):再從節點C開始,用隨機策略進行遊戲,又稱為playout或者rollout。
  • 反向傳播(Backpropagation):使用隨機遊戲的結果,更新從CR的路徑上的節點信息。

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

Thumb
蒙特卡洛樹搜索的步驟

探索與利用

選擇子結點的主要困難是:在較高平均勝率的移動後,在對深層次變型的利用和對少數模擬移動的探索,這二者中保持某種平衡。第一個在遊戲中平衡利用與探索的公式被稱為UCT(Upper Confidence Bounds to Trees,上限置信區間算法 ),由匈牙利國家科學院計算機與自動化研究所高級研究員列文特·科奇什與阿爾伯塔大學全職教授喬鮑·塞派什瓦里提出[7]。UCT基於奧爾(Auer)、西薩-比安奇(Cesa-Bianchi)和費舍爾(Fischer)提出的UCB1公式[26],並首次由馬庫斯等人應用於多級決策模型(具體為馬爾可夫決策過程[27]。科奇什和塞派什瓦里建議選擇遊戲樹中的每個結點移動,從而使表達式 具有最大值。在該式中:

  • 代表第次移動後取勝的次數;
  • 代表第次移動後仿真的次數;
  • 為探索參數—理論上等於;在實際中通常可憑經驗選擇;
  • 代表仿真總次數,等於所有的和。

目前蒙特卡洛樹搜索的實現大多是基於UCT的一些變形。

參見

參考來源

延伸閱讀

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads