蒙特卡洛樹搜索 MCTS 入門

02-02

來源：http://nooverfit.com

什麼是 MCTS？

全稱 Monte Carlo Tree Search，是一種人工智慧問題中做出最優決策的方法，一般是在組合博弈中的行動（move）規劃形式。它結合了隨機模擬的一般性和樹搜索的準確性。

MCTS 受到快速關注主要是由計算機圍棋程序的成功以及其潛在的在眾多難題上的應用所致。超越博弈遊戲本身，MCTS 理論上可以被用在以 {狀態 state，行動 action} 對定義和用模擬進行預測輸出結果的任何領域。

基本演算法

基本的 MCTS 演算法非常簡單：根據模擬的輸出結果，按照節點構造搜索樹。其過程可以分為下面的若干步：

搜索樹的構建過程

選擇 Selection：從根節點 R 開始，遞歸選擇最優的子節點（後面會解釋）直到達到葉子節點 L。
擴展 Expansion：如果 L 不是一個終止節點（也就是，不會導致博弈遊戲終止）那麼就創建一個或者更多的字子節點，選擇其中一個 C。
模擬 Simulation：從 C 開始運行一個模擬的輸出，直到博弈遊戲結束。
反向傳播 Backpropagation：用模擬的結果輸出更新當前行動序列。

參看Tutorial了解關於這個過程更多的信息。

每個節點並需包含兩個重要的信息：一個是根據模擬結果估計的值和該節點已經被訪問的次數。

按照最為簡單和最節約內存的實現，MCTS 將在每個迭代過程中增加一個子節點。不過，要注意其實根據不同的應用這裡也可以在每個迭代過程中增加超過一個子節點。

節點選擇

Bandits 和 UCB

在樹向下遍歷時的節點選擇通過選擇最大化某個量來實現，這其實類似於n Multiarmed bandit problem，其中的參與者必須選擇一個 slot nmachine（bandit）來最大化每一輪的估計的收益。我們可以使用 Upper Confidence nBounds（UCB）公式常常被用來計算這個：

其中 v_i 是節點估計的值，n_i 是節點被訪問的次數，而 N 則是其父節點已經被訪問的總次數。C 是可調整參數。

Exploitation 和 Exploration

UCBn 公式對已知收益的 exploitation 和鼓勵接觸那些相對未曾訪問的節點的 exploration n進行平衡。收益估計基於隨機模擬，所以節點必須被訪問若干次來缺包估計變得更加可信；MCTS n估計會在搜索的開始不大可靠，而最終會在給定充分的時間後收斂到更加可靠的估計上，在無限時間下能夠達到最優估計。

MCTS 和 UCT

Kocsisn 和 Szepervari 在 2006 年首先構建了一個完備的 MCTS 演算法，通過擴展 UCB 到 minimax 樹搜索，並將其命名為 nUpper Confidence Bounds for Trees（UCT）方法。這其實是用在當前眾多 MCTS 實現中的演算法版本。

UCT 可以被描述為 MCTS 的一個特例：UCT = MCTS + UCB。

優點

MCTS 提供了比傳統樹搜索更好的方法。

Aheuristic

MCTSn n不要求任何關於給定的領域策略或者具體實踐知識來做出合理的決策。這個演算法可以在沒有任何關於博弈遊戲除基本規則外的知識的情況下進行有效工作；這意味著一個簡單的n MCTS 實現可以重用在很多的博弈遊戲中，只需要進行微小的調整，所以這也使得 MCTS 是對於一般的博弈遊戲的很好的方法。

Asymmetric

MCTS 執行一種非對稱的樹的適應搜索空間拓撲結構的增長。這個演算法會更頻繁地訪問更加有趣的節點，並聚焦其搜索時間在更加相關的樹的部分。

非對稱的增長

這使得 MCTS 更加適合那些有著更大的分支因子的博弈遊戲，比如說 19X19 的圍棋。這麼大的組合空間會給標準的基於深度或者寬度的搜索方法帶來問題，所以 MCTS 的適應性說明它（最終）可以找到那些更加優化的行動，並將搜索的工作聚焦在這些部分。

任何時間

演算法可以在任何時間終止，並返回當前最有的估計。當前構造出來的搜索樹可以被丟棄或者供後續重用。

簡潔

演算法實現非常方便（參見Code）

缺點

MCTS 有很少的缺點，不過這些缺點也可能是非常關鍵的影響因素。

行為能力

MCTS 演算法，根據其基本形式，在某些甚至不是很大的博弈遊戲中在可承受的時間內也不能夠找到最好的行動方式。這基本上是由於組合步的空間的全部大小所致，關鍵節點並不能夠訪問足夠多的次數來給出合理的估計。

速度

MCTSn n搜索可能需要足夠多的迭代才能收斂到一個很好的解上，這也是更加一般的難以優化的應用上的問題。例如，最佳的圍棋程序可能需要百萬次的交戰和領域最佳和強化才能得到專家級的行動方案，而最有的n GGP 實現對更加複雜的博弈遊戲可能也就只要每秒鐘數十次（領域無關的）交戰。對可承受的行動時間，這樣的 GGP n可能很少有時間訪問到每個合理的行動，所以這樣的情形也不大可能出現表現非常好的搜索。

幸運的是，演算法的性能可以通過一些技術顯著提升。

提升

很多種 MCTS 強化的技術已經出現了。這些基本上可以歸納為領域知識或者領域獨立兩大類。

領域知識

特定博弈遊戲的領域知識可以用在樹上來過濾掉不合理的行動或者在模擬過程中產生重要的對局（更接近人類對手的表現）。這意味著交戰結果將會更加的現實而不是隨機的模擬，所以節點只需要少量的迭代就能給出一個現實的收益值。

領域知識可以產生巨大的性能提升，但在速度和一般性上也會有一定的損失。

領域獨立

領域獨立強化能夠應用到所有的問題領域中。這些一般用在樹種（如 AMAF），還有一些用在模擬（如在交戰時傾向於勝利的行動）。領域獨立強化並不和特定的領域綁定，具有一般性，這也是當前研究的重心所在。

背景和歷史

1928：John von Neumann 的 minimax 定理給出了關於對手樹搜索的方法，這形成了計算機科學和人工智慧的從誕生至今的決策制定基礎。

n1940s：Monte Carlo 方法形成，作為一種通過隨機採樣解決不太適合樹搜索解決的弱良定義問題的方法。

n2006：Rémi Coulomb 和其他研究者組合了上面兩種想法給出了一個新的圍棋程序中行動規劃的觀點——MCTS。Kocsis 和 Szepesvári 將此觀點形式化進 UCT 演算法。

研究興趣

從 MCTS 誕生後幾年內，就有超過 150 篇與 MCTS 相關的研究論文發布，平均下來是每兩周一篇新的文章。這些文章中包含了大概 50 個推薦的變體、強化和優化，這和傳統樹搜索自其 1928 年誕生開始的加強的數量也差不太多。

這個新的研究領域當前是 AI 中非常熱的研究話題，有很多的開放的研究問題有待發掘和解決。

MCTS: 最新成果

Imperial College London held the first international MCTS workshop in August 2010 on the theme ofMCTS: State of the Art. Speakers included:

nO. Teytaud, 「State of the Art: What is MCTS, where is it now, and where is it going?」 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:london2010.pdf

nM. Müller, 「Challenges in Monte Carlo Tree Search,」 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:london2010-mcts-challenges.pdf

nR. Hayward, 「MoHex: Computer Hex world champion,」 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:mohextalk.pdf

nH. Finnsson and Y. Bj?rnsson, 「CadiaPlayer: MCTS in General Game Playing,」 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:cadiaplayer_lic_slides_print.pdf

nA. Rimmel, 「Havannah, Monte Carlo Enhancements and Linear Transforms,」 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:presmctsworkshop_rimmel.pdf

參考文獻：

蒙特卡洛樹搜索 MCTS_演算法藝術_酷勤網
Introduction to Monte Carlo Tree Search | Caktus Group