點選上方“MLNLP”，選擇“星标”公衆号
重磅幹貨，第一時間送達
編輯：憶臻
https://www.zhihu.com/question/39916945
本文僅作為學術分享，如果侵權，會删文處理
蒙特卡洛樹是什麼算法？
作者：陸君慨https://www.zhihu.com/question/39916945/answer/83799720
蒙特卡羅樹搜尋(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.
作者：vczhhttps://www.zhihu.com/question/39916945/answer/247549008
傳統意義上講，算法名字帶有蒙特卡洛的意思就是，他對搜尋空間的搜尋都是随機給一個方向的，譬如說蒙塔卡羅算圓周率，就是在一個正方形裡面随機取點，看看落在圓裡面有多少。蒙特卡洛光線追蹤，在需要對環境積分的時候随機取角度射光線。蒙特卡洛走迷宮，随便走。
作者：Xiaohu Zhuhttps://www.zhihu.com/question/39916945/answer/247549008
什麼是 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 中非常熱的研究話題，有很多的開放的研究問題有待發掘和解決。
推薦閱讀：
實戰 | Pytorch BiLSTM + CRF做NER
如何評價Word2Vec作者提出的fastText算法？深度學習是否在文本分類等簡單任務上沒有優勢？
從Word2Vec到Bert，聊聊詞向量的前世今生(一)