蒙特卡洛樹是什麼演算法？

01-03

蒙特卡洛樹是指蒙特卡洛模擬樹么？是一種模擬人下棋的搜索演算法嗎？據說五子棋模擬只要簡單枚舉就可以模擬出來，而圍棋卻不行，有內行人懂嗎？圍棋究竟是怎麼模擬的？能不能講一下其中的具體原因。

蒙特卡羅樹搜索(Monte Carlo Tree Search)並不是一種"模擬人"的演算法。而是通過隨機的對遊戲進行推演來逐漸建立一棵不對稱的搜索樹的過程。可以看成是某種意義上的強化學習，當然這一點學界還有一些爭議。

蒙特卡羅樹搜索大概可以被分成四步。選擇(Selection)，拓展(Expansion)，模擬(Simulation)，反向傳播(Backpropagation)。

在開始階段，搜索樹只有一個節點，也就是我們需要決策的局面。

搜索樹中的每一個節點包含了三個基本信息：代表的局面，被訪問的次數，累計評分。

[1]選擇(Selection)

在選擇階段，需要從根節點，也就是要做決策的局面R出發向下選擇出一個最急迫需要被拓展的節點N，局面R是是每一次迭代中第一個被檢查的節點；

對於被檢查的局面而言，他可能有三種可能：

1)該節點所有可行動作都已經被拓展過

2)該節點有可行動作還未被拓展過

3)這個節點遊戲已經結束了(例如已經連成五子的五子棋局面)

對於這三種可能：

1)如果所有可行動作都已經被拓展過了，那麼我們將使用UCB公式計算該節點所有子節點的UCB值，並找到值最大的一個子節點繼續檢查。反覆向下迭代。

2)如果被檢查的局面依然存在沒有被拓展的子節點(例如說某節點有20個可行動作，但是在搜索樹中才創建了19個子節點)，那麼我們認為這個節點就是本次迭代的的目標節點N，並找出N還未被拓展的動作A。執行步驟[2]

3)如果被檢查到的節點是一個遊戲已經結束的節點。那麼從該節點直接執行步驟{4]。

每一個被檢查的節點的被訪問次數在這個階段都會自增。

在反覆的迭代之後，我們將在搜索樹的底端找到一個節點，來繼續後面的步驟。

[2]拓展(Expansion)

在選擇階段結束時候，我們查找到了一個最迫切被拓展的節點N，以及他一個尚未拓展的動作A。在搜索樹中創建一個新的節點Nn作為N的一個新子節點。Nn的局面就是節點N在執行了動作A之後的局面。

[3]模擬(Simulation)

為了讓Nn得到一個初始的評分。我們從Nn開始，讓遊戲隨機進行，直到得到一個遊戲結局，這個結局將作為Nn的初始評分。一般使用勝利/失敗來作為評分，只有1或者0。

[4]反向傳播(Backpropagation)

在Nn的模擬結束之後，它的父節點N以及從根節點到N的路徑上的所有節點都會根據本次模擬的結果來添加自己的累計評分。如果在[1]的選擇中直接發現了一個遊戲結局的話，根據該結局來更新評分。

每一次迭代都會拓展搜索樹，隨著迭代次數的增加，搜索樹的規模也不斷增加。當到了一定的迭代次數或者時間之後結束，選擇根節點下最好的子節點作為本次決策的結果。

一次迭代的圖例[1]:

上面描述的是UCT (UCB for Tree)演算法，可以說是最經典的蒙特卡羅樹搜索演算法了。但隨著演算法的發展，MCTS已經有了非常大的改變。例如很多圍棋AI都已經不再使用純粹的UCB公式而改用效果更好的UCB1-Tuned了[2]，而搜索方法上也有了非常多的改動了。

Reference:

[1]:Browne C B, Powley E, Whitehouse D, et al. A Survey of Monte Carlo Tree Search Methods[J]. IEEE Transactions on Computational Intelligence Ai in Games, 2012, 4:1(1):1-43.

[2]:P. Auer, N. Cesa-Bianchi, and P. Fischer, 「Finite-time Analysis of the Multiarmed Bandit Problem,」 Mach. Learn., vol. 47, no. 2, pp. 235–256, 2002.

關於 AlphaGo 整體框架，可以看我前段時間寫的一篇推送：要不我也說說 AlphaGo？

可以看出，在 AlphaGo 的框架中，蒙特卡洛樹搜索 (Monte Carlo Tree Search) 是用來快速評估棋面位置價值的。它的核心思想用 Sutton 的 RL 書 [1] 中一句話就可以概括：

Monte Carlo methods are ways of solving the reinforcement learning problem based on averaging sample returns

下棋其實就是一個馬爾科夫決策過程（MDP），根據當前棋面狀態，確定下一步動作。

那麼，該下哪步才能保證後續贏棋的概率比較大呢？

最容易想到的就是枚舉之後的每一種下法，然後計算每步贏棋的概率，選擇概率最高的就好了：

但是，對於圍棋而言，狀態空間實在是太大了，沒辦法枚舉啊：

這種時候就是靠蒙特卡洛樹搜索了。它的方法也非常簡單，那就是「沒病走兩步」：

在當前狀態的基礎上，選擇一個備選動作/狀態；
從備選動作/狀態開始，「走兩步」，不需要枚舉後續所有狀態，只要以一定的策略（如隨機策略和 AlphaGo 中的快速走棋網路）一直模擬到遊戲結束為止；
計算這次採樣的回報；
重複幾次，將幾次回報求平均，獲得該備選動作/狀態的價值。

換個通俗點的說法，就是用頻率估計概率。只要採樣的樣本數越多，頻率越接近概率。

具體的演算法原理和理論推導，建議直接去看 Sutton 的書 [1]。

[1] Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. Vol. 1. No. 1. Cambridge: MIT press, 1998.

傳統意義上講，演算法名字帶有蒙特卡洛的意思就是，他對搜索空間的搜索都是隨機給一個方向的，譬如說蒙塔卡羅算圓周率，就是在一個正方形裡面隨機取點，看看落在圓裡面有多少。蒙特卡洛光線追蹤，在需要對環境積分的時候隨機取角度射光線。蒙特卡洛走迷宮，隨便走。

這坑有點大。最近坑多，要戒一段時間知乎，短期沒法填坑了。

怎麼用 Excel 做蒙特卡洛模擬？ - Microsoft Excel

看到了這個問題，應該對題主有所幫助。蒙特卡洛模擬軟體我還在下。雖然以概率學角度來看，我等技術渣玩出個名堂的可能性極低。

最後再感慨一句：大excel真牛逼！自從知道可以用excel，「世界末日」問題，我再也不用傻兮兮的編程了！遞歸問題也更簡單了！

哈哈，一開頭就說了，蒙（特卡洛樹）演算法主要靠蒙。

專欄鏈接：蒙特卡洛樹搜索簡介

什麼是 MCTS？

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

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

基本演算法

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

搜索樹的構建過程

選擇 Selection：從根節點 R 開始，遞歸選擇最優的子節點（後面會解釋）直到達到葉子節點 L。

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

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

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

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

節點選擇

Bandits 和 UCB

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

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

Exploitation 和 Exploration

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

MCTS 和 UCT

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

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

優點

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

Aheuristic

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

Asymmetric

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

非對稱的增長

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

任何時間

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

簡潔

演算法實現非常方便

缺點

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

行為能力

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

速度

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

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

提升

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

領域知識

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

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

領域獨立

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

背景和歷史

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

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

2006：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 of MCTS: State of the Art. Speakers included:

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

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

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

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

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

https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/ https://jeffbradberry.com/tag/alphago/ http://lamda.nju.edu.cn/yuy/(S(o2npwm55cfhx2yinvnpmnczl))/course_ai16.ashx http://lamda.nju.edu.cn/yuy/(S(o2npwm55cfhx2yinvnpmnczl))/GetFile.aspx?File=course_ai16/Lecture5.pdf http://www.cameronius.com/cv/mcts-survey-master.pdf

怎麼說呢，蒙特卡洛演算法就是用很多個隨機事件的結果去逼近所需要的精確結果。

與常規的牛頓搜索，正交共軛搜索之類演算法不同，蒙特卡洛不用確定搜索方向，每取一個值，都跟上一個取值無關，正因為如此每一步都有很多種的可能性，這樣在設計圍棋這樣求解步數很多的事情或過程時，所需要的內存和CPU性能幾乎是無窮大，所以你懂的。

貌似這幾天圍棋人機大戰的alphaGo就是基於這種演算法實現的哦。

先簡單說說佔個坑，考完試來填。剛好複習（預習）的時候看到，順便做個整理：

簡單來說，Monte Carlo樹搜索（MCTS）就是在所有可能的選擇中（到底把棋子落在哪裡）選擇一個把握最大的可能（最有可能最後勝利的落子方式），好吧我知道這個是個廢話。

但是MCTS牛就牛在，如何選擇這個把握最大的可能。目前流行選擇最大把握的方法的是使用（UCT, Upper Confidence Bounds for Trees），MCTS會對所有情況進行一個評分（隨機評的，符合隨機性），然後使用UCT演算法選擇一個分最高的選項。而且每一次的選擇都會對整體產生影響（牽一髮而動全身，畢竟下圍棋不是走一步就搞定的事，可能是組合連環擊？），所以每一次做出選擇之後，會修改整個系統（樹）的分值，比如上一步的分值（父點），上上步的分值（祖父點）。

MCTS和其他方法相比，更加有概括性（generalization），就是說不僅僅使用於某一種遊戲，可以玩其他的遊戲也玩的很好，比如馬里奧。

至於什麼叫做UCT。。。具體MCTS演算法。。。先祝我考試順利吧。。。

我只講講廣義上的蒙特卡洛(MC)演算法．

蒙特卡洛(MC)演算法是一種廣義的定義，vczh說的差不多，它可以指any algorithm with a significant random component.

但樓上還有一點沒有提到，就是它和動態規劃(dynamic programming)一樣都屬於強化學習範疇，都用於解決馬爾可夫決策過程（MDP）問題的演算法.　但前者是基於模型的(model-based)，後者是無模型的(model-free)

動態規劃(dynamic programming)有兩大弊端：１．其中的值迭代（value iteration）或者是策略迭代（policy iteration）中的轉移概率p(s",r|s,a)在實際情況中不好測量（比如我們讓無人車向前走，它可能由於誤差等原因，向右拐到了一個新的狀態，這個狀態轉移的概率不好測量）;　２．當狀態量相當大的時候，（比如圍棋3^（19x19）個狀態），動態規劃裡面要對所有狀態掃一遍（暫時不考慮Asynchronous dynamic programming），這是相當耗代價的

而蒙特卡洛(MC)就是解決這個問題的．

怎麼解決？

就是隨機採樣．

ＭＣ相對動態規劃(ＤＰ)做了以下幾點改動(這邊就不列公式，簡要闡述)：

１．每個action後不進行更新，而在整個一輪遊戲模擬後，進行更新

(因為對於強化學習中的control problem（也就是找一個最優policy）,一般用policy evaluaiton-policy improvement 循環，而如果這樣子對ＭＣ來說就是雙重循環，運算量極大，所以這裡乾脆跳出來，整輪遊戲後再進行更新)（這只是一個trick,目前為止，沒人證明這樣收斂，但確實很好用）

(第二個原因在於後面的第4，5點，回報G(s)是與未來的狀態中的回報有關的，所以必須要將整輪遊戲模擬結束後才能更新)

２．放棄policy evaluaiton部分．（這也是一個trick,因為很多情況估計每個狀態的狀態值函數Ｖ(s)是在浪費生命，有時候策略收斂了，但Ｖ(s)仍然沒有收斂，乾脆放棄）（目前為止，沒人證明這樣收斂，但確實很好用）

３．每輪遊戲模擬前都隨機選一個初始state和action,然後從這個(s,a)開始模擬（這也就解決了ＤＰ中的缺點２，即使狀態再多，也沒關係，不用全掃）

４．狀態值函數Ｖ(s)用Ｎ輪模擬後狀態s的回報G(s)的平均近似　

５．同理，動作值函數Q(s,a)也用Ｎ輪模擬後的在狀態s進行動作a的回報G(s,a)的平均近似　

　（4，5兩點本質就是通過採樣平均來代替期望，從而避開了貝爾曼公式中的轉移概率p(s",r|s,a)，用於解決了ＤＰ中的缺點１）

但上述這5點中的第３點在有些情況下很難做到，這步意味這我需要先確定好所有的狀態和action,然後隨機才有意義;但是很多情況，比如無人車，很難找出其所有的狀態，而且精確地把它擺放到那個狀態下執行action a也很麻煩;所以這裡可以改成：

３．每輪遊戲模擬時，採用exploit-explore演算法進行．

（同時很多exploit-explore演算法，如ε-greedy,ucb1,mayesian method等都可以用上）

那我們發現：DP是需要模型的，而MC又要等整輪遊戲模擬後，才能更新，有沒有方法將兩者結合？

TD learning（這就不繼續扯了）

蒙特卡洛模擬

基本思想：

蒙特卡羅演算法並不是一種演算法的名稱，而是對一類隨機演算法的特性的概括。主要是在在隨機採樣上計算得到近似結果，隨著採樣的增多，得到的結果是正確結果的概率逐漸加大。

1：EM演算法：

最大期望演算法經過兩個步驟交替進行計算：

第一步是計算期望（E），利用概率模型參數的現有估計值，計算聯合分布條件概率的期望；第二步是最大化（M），利用E 步上求得的聯合分布的條件概率的期望，對參數模型進行最大似然估計。

M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。

2：遺傳演算法 :

遺傳演算法將要解決的問題模擬成一個生物進化的過程，通過複製、交叉、突變等操作產生下一代的解，並逐步淘汰掉適應度函數值低的解，增加適應度函數值高的解。這樣進化N代後就很有可能會進化出適應度函數值很高的個體。

3:粒子群演算法：

　 PSO初始化為一群隨機粒子(隨機解)。然後通過迭代找到最優解。在每一次的迭代中，粒子通過跟蹤兩個「極值」(pbest,gbest)來更新自己。在找到這兩個最優值後，粒子通過下面的公式來更新自己的速度和位置。

4:退火演算法 :

模擬退火演算法基於爬山演算法。爬山演算法是每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。

模擬退火的搜索過程引入了隨機因素，即以一定的概率來接受一個比當前解要差的解，因此有可能會跳出這個局部的最優解，達到全局的最優解。

5:MCMC:

對於一個給定的概率分布P(X) ，如果想要得到其樣本，通過馬爾可夫鏈的概念，可以構造一個轉移矩陣為P 的馬爾可夫鏈，使得該馬爾可夫鏈的平穩分布為P(X) 。這樣，無論其初始狀態為何值，那麼隨著馬爾科夫過程的轉移，得到了一系列的狀態值。如果這個馬爾可夫過程在第N步時滿足收斂條件，那麼分布P(X) 的樣本即為第

N個數開始的樣本。

6: 蒙特卡羅樹搜索(Monte Carlo Tree Search)

蒙特卡羅樹搜索是通過隨機的對遊戲進行推演來逐漸建立一棵不對稱的搜索樹的過程。也就是選擇，拓展，模擬，反向傳播。

在開始階段，搜索樹只有一個節點。搜索樹中的每一個節點包含了三個基本信息：代表的局面，被訪問的次數，累計評分。每一次迭代都會拓展搜索樹，隨著迭代次數的增加，搜索樹的規模也不斷增加。當到了一定的迭代次數或者時間之後結束，選擇根節點下最好的子節點作為本次決策的結果。

應用舉例：

1：基於EM演算法的半監督文本分類是通過EM演算法將標註訓練集與未標註訓練集相結合構建分類器,利用未標註訓練集的信息提高分類器的性能。EM演算法的求解隱變數和模型參數的思想也會應用在LDA求解主題模型中，具體表現即為Gibbs採樣。

2：戰機，航空飛機等協同任務規劃優化：首先在兩條飛行路線之間的區域內產生隨機數列，然後逐個驗證這些元素的值是否符合約束條件，，否則棄置並繼續驗證下一數值。如此，即能得出在該公共區域內的最佳飛行路線。利用蒙特卡羅方法，將搜索區域限定在這些點所構成的矩形平面內，並將產生的隨機點在此區域內進行遍歷，篩選出滿足條件的點。

3：衍生品定價或者量化投資中的應用。例如期權：風險中性概率測度下，期權的價格是其期望價值的折現。一句話概括：蒙特卡洛演算法通過大量隨機生成資產價格路徑，模擬資產未來價格中不確定因素，估計資產期望收益率。這種模擬定價方法比較適用於價格由資產價格路徑決定的衍生品。或者也可以利用模擬方法算VaR的，或者用來估計各種風險。

也許，這是最接近人類想法的一個演算法！

請教學習MCTS應該看那本書嗎？想從這個地方切入AI，只看大家的回答太零散。

David 9 給出的解釋：蒙特卡洛樹搜索 MCTS 入門

蒙特卡洛在當前結點R的時候去隨機尋找下個節點T，有點類似遺傳演算法，不過遺傳演算法是不記錄歷史節點，可能自己以前學習的都是很淺的東西。

蒙特卡羅一個前提是大數定律，我理解的意思就是足夠多的樣本的期望收斂，那麼放到圍棋上來就是隨機搜索足夠多的點，總會找到勝率最高的點，認為是最優點，可能是全局最優也可能是局部最優。考慮這個分布有多個峰值