1樓：何燕傑
最近正在研究計算機博弈，強答一發吧，輕噴，有錯請指正。
一般來說，策略遊戲可以用極大極小博弈樹進行搜尋。簡單點說，就是假如我現在有四種選擇ABCD，如果我選擇了A，那麼對於對方而言，對方有DEF三種選擇，如果對方選擇了D……依次類推。搜尋所有可能的情況，同時假設每一回合遊戲參與者都會選擇對自身最優的選擇。
但是這種搜尋方式有乙個問題，就是對於一般的棋類遊戲而言，可能的情況太太太太太太太太太太太多了！因此很多時候是搜尋不到棋局結束的時候的。在這種情況下，可以選擇限制搜尋深度，返回對當前棋局的估值作為評分。
問題在於，這個估值怎麼來呢？象棋、西洋棋這種還算好辦，可以從根據棋子子力和棋子的位置進行估值。像圍棋、五子棋、黑白棋這種，雖然也可以用類似的辦法，但是這樣做有時候效果不夠好，下棋過於死板，難以挑戰專業的人類選手。
最後附一張維基百科上井字棋的蒙特卡洛樹搜尋的圖示，感覺講得很清楚了。
2樓：雨行
我只講講廣義上的蒙特卡洛(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（這就不繼續扯了）
3樓：
蒙特卡洛在當前結點R的時候去隨機尋找下個節點T，有點類似遺傳演算法，不過遺傳演算法是不記錄歷史節點，可能自己以前學習的都是很淺的東西。
4樓：大亨
蒙特卡羅乙個前提是大數定律，我理解的意思就是足夠多的樣本的期望收斂，那麼放到圍棋上來就是隨機搜尋足夠多的點，總會找到勝率最高的點，認為是最優點，可能是全域性最優也可能是區域性最優。考慮這個分布有多個峰值
5樓：
蒙特卡羅樹搜尋(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.
蒙特卡洛模擬原理是什麼？
簡單粗暴的理解 1.對問題建模 就是由變數決定的函式值 2.確定變數的分布 3.抽取一組隨機數 作為變數概率 考慮變數的分布確定變數值，作為一次實驗的結果 4.試驗次數越多，因變數樣本越大，當樣本足夠大，因變數的分布近似可知。原理 n夠大，頻率趨近於概率。精度取決於 建的模型對不對，變數分布對不對，...
MATLAB多維T分布蒙特卡洛？
徐瑞龍 我來提供一點正規的學術界資訊吧。多元正態和多元t分布的計算與模擬，相關的理論和程式演算法請參考Alan Genz的主頁 http www.math.wsu.edu faculty ge nz homepage 這位華盛頓大學的教授在多元正態和多元t分布的計算與模擬方面著作頗豐。Alan Ge...
怎麼用 Excel 做蒙特卡洛模擬？
如果你想自己做不靠外掛程式就太難了我就會了 靠外掛程式可以看一下palisade或者vose 資料如果喜歡中文去看張巨集亮博士的書企業風險量化什麼的那本 佔位哪天想起來了寫.很久沒碰了要看看模型和相關資料。做含有path depandent feature的convertible bond的valu...