蒙特卡羅演算法是什麼？

11-26

本題已收錄至知乎圓桌 ? 對弈人工智慧，更多關於李世乭對戰人工智慧的解讀歡迎關注討論。
-----
是一種人工智慧？聽說軟體zen基於這種演算法幹掉了武宮正樹的四子局？

太數學的東西就不說了，只用通俗唱法回答樓主的問題。

蒙特卡羅演算法並不是一種演算法的名稱，而是對一類隨機演算法的特性的概括。媒體說「蒙特卡羅演算法打敗武宮正樹」，這個說法就好比說「我被一隻脊椎動物咬了」，是比較火星的。實際上是ZEN的演算法具有蒙特卡羅特性，或者說它的演算法屬於一種蒙特卡羅演算法。

那麼「蒙特卡羅」是一種什麼特性呢？我們知道，既然是隨機演算法，在採樣不全時，通常不能保證找到最優解，只能說是盡量找。那麼根據怎麼個「盡量」法兒，我們我們把隨機演算法分成兩類：

蒙特卡羅演算法：採樣越多，越近似最優解；
拉斯維加斯演算法：採樣越多，越有機會找到最優解；

舉個例子，假如筐里有100個蘋果，讓我每次閉眼拿1個，挑出最大的。於是我隨機拿1個，再隨機拿1個跟它比，留下大的，再隨機拿1個……我每拿一次，留下的蘋果都至少不比上次的小。拿的次數越多，挑出的蘋果就越大，但我除非拿100次，否則無法肯定挑出了最大的。這個挑蘋果的演算法，就屬於蒙特卡羅演算法——盡量找好的，但不保證是最好的。

而拉斯維加斯演算法，則是另一種情況。假如有一把鎖，給我100把鑰匙，只有1把是對的。於是我每次隨機拿1把鑰匙去試，打不開就再換1把。我試的次數越多，打開（最優解）的機會就越大，但在打開之前，那些錯的鑰匙都是沒有用的。這個試鑰匙的演算法，就是拉斯維加斯的——盡量找最好的，但不保證能找到。

所以你看，這兩個詞並不深奧，它只是概括了隨機演算法的特性，演算法本身可能複雜，也可能簡單。這兩個詞本身是兩座著名賭城，因為賭博中體現了許多隨機演算法，所以借過來命名。

這兩類隨機演算法之間的選擇，往往受到問題的局限。如果問題要求在有限採樣內，必須給出一個解，但不要求是最優解，那就要用蒙特卡羅演算法。反之，如果問題要求必須給出最優解，但對採樣沒有限制，那就要用拉斯維加斯演算法。對於機器圍棋程序而言，因為每一步棋的運算時間、堆棧空間都是有限的，而且不要求最優解，所以ZEN涉及的隨機演算法，肯定是蒙特卡羅式的。

機器下棋的演算法本質都是搜索樹，圍棋難在它的樹寬可以達到好幾百（國際象棋只有幾十）。在有限時間內要遍歷這麼寬的樹，就只能犧牲深度（俗稱「往後看幾步」），但圍棋又是依賴遠見的遊戲，甚至不僅是看「幾步」的問題。所以，要想保證搜索深度，就只能放棄遍歷，改為隨機採樣——這就是為什麼在沒有MCTS（蒙特卡羅搜樹）類的方法之前，機器圍棋的水平幾乎是笑話。而採用了MCTS方法後，搜索深度就大大增加了。比如，在題主說的ZEN與武宮正樹九段的對局中，我們可以看這一步棋：

武宮正樹九段（執白）第53步大飛，明顯企圖攻角，而ZEN（執黑）卻直接不理，放棄整個右下角，轉而把中腹走厚。這個交換究竟是否划算，就不在這裡討論了，但我們至少可以看出，ZEN敢於在此脫先，捨棄這麼大的眼前利益，其搜索深度確實達到了人類專業棋手的水平。

蒙特卡羅是一類隨機方法的統稱。這類方法的特點是，可以在隨機採樣上計算得到近似結果，隨著採樣的增多，得到的結果是正確結果的概率逐漸加大，但在（放棄隨機採樣，而採用類似全採樣這樣的確定性方法）獲得真正的結果之前，無法知道目前得到的結果是不是真正的結果。

舉例說明，一個有10000個整數的集合，要求其中位數，可以從中抽取m&<10000個數，把它們的中位數近似地看作這個集合的中位數。隨著m增大，近似結果是最終結果的概率也在增大，但除非把整個集合全部遍歷一邊，無法知道近似結果是不是真實結果。

另外一個例子，給定數N，要求它是不是素數，可以任選m個小於N的數，看其中有沒有能整除N的數，如果沒有則判斷為素數。這和通常見到的蒙特卡羅例子不同，近似結果往往錯得更離譜，但隨著m增大，近似結果是最終結果的概率也在增大。

把蒙特卡羅方法和另外一類方法——拉斯維加斯方法[1]——對比一下，更容易了解哪些方法屬於蒙特卡羅，哪些不屬於。拉斯維加斯方法是另一類隨機方法的統稱。這類方法的特點是，隨著採樣次數的增多，得到的正確結果的概率逐漸加大，如果隨機採樣過程中已經找到了正確結果，該方法可以判別並報告，但在但在放棄隨機採樣，而採用類似全採樣這樣的確定性方法之前，不保證能找到任何結果（包括近似結果）。

舉例說明，有一個有死胡同但無環路的迷宮，要求從入口走到出口的一條路徑。可以從入口出發，在每個叉路口隨機選擇一個方向前行，到死胡同則報告失敗並回到入口重新試探，到出口則報告成功。隨著試探次數增多，找到一條入口到出口的路徑的概率增大，但除非全枚舉，即使試10000年，也無法保證找到任何要求的路徑。

[1] http://en.wikipedia.org/wiki/Las_Vegas_algorithm

題主想要問的可能是——模特卡羅模擬樹，這是一種博弈搜索演算法。

我們知道，解決對弈問題，比如五子棋、圍棋，的一種人工智慧方法就是搜索演算法。說白了，就是枚舉：你走一步，我就枚舉後面五步，根據遊戲規則，看枚舉出來的哪種走法最優，就按照那種走法進行對弈。這種方法對於五子棋等簡單的遊戲十分的有效，一般也都是這麼做的。

但對於複雜的遊戲，比如圍棋，就十分困難。其難點有兩個：其一，有效的枚舉下幾步棋耗費的時間實在太大，大到完全不可行；其二，圍棋的規則太過於簡單，單純依照這種遊戲規則，很難對搜索出來的棋局進行有效評分。

為了突破這兩點，我們引入一種稱之為蒙特卡洛模擬樹的方法。最簡單的蒙特卡洛模擬樹，就是完全隨機的模擬下棋，輪流在棋盤上隨機的下棋，直到棋盤被下滿為止，這樣，我們就可以利用圍棋的規則對結果進行精確的評分，然後按照評分最高的下一步進行對弈。在這種最簡單的方法上，我們還可以做兩點改進，第一點就是隨機從某種分布採樣下棋，第二點就是利用樹狀結構來更有效的利用蒙特卡洛得到的評分。對於第一點，我們可以從某個Markov鏈中採樣，簡單說：棋子密集的地方下棋的比率更高。對於第二點，我們利用樹狀結構，更有效的管理採樣的進行和對評分的利用。

綜上所述，利用蒙特卡洛模擬樹解決對弈問題是個不錯的選擇。當然，在這裡我們還需要引入某些原理性的規則來提高效率和能力。最為經典的一種原理就是樂觀優化原則，他可以指導樹狀結構有效的展開。樓主要是對這方面感興趣不妨按照本答案所出現的關鍵詞檢索一些文獻看看。

很多類演算法都叫蒙特卡羅（簡稱蒙卡）。蒙卡最重要的應用是算積分，尤其是高維 —— 例如無窮維的積分（路徑積分），其他數值積分演算法可能完全不適用。

舉個例子：統計力學指出，系統的一個熱力學量 $A$ 的平均值等於 $langle A angle = sum_{varphi(x)} A[varphi(x)] e^{-frac{E[varphi(x)]}{k_BT}}$ ，其中 $varphi(x)$ 是一個場，取決於空間中的每一點； $E[varphi(x)]$ 是能量，取決於場的分布；T是溫度。一般來說可以講空間離散化成為 $N^3$ 的格點；再將場函數的取值離散化。即使如此，每一個場分布 $varphi$ 對應於 $sim N^3$ ；假定場函數取值可以離散為 $n$ 個值；那麼場分布（又叫構型）的總數為 $mathcal N = n^{N^3}$ 個 —— 這是直接計算時的複雜度。取 $n = 2, N = 100 Rightarrow mathcal N = 2^{10^6}$ ! 用最強的超級計算機來計算，1 exaFLOPS = 10^18 次每秒，一共需要 $2^{10^5}$ 秒遠遠大於宇宙年齡 $10^{17}$ 秒。蒙卡解決的辦法是，按照波爾滋蔓分布隨機抽樣出一小部分場分布（構型）來計算 $A$ 的平均值。只要抽樣足夠好，&的計算就能夠足夠準確。

常用的隨機抽樣演算法是Metropolis，這是一個滿足馬爾科夫過程的演算法。

當然除了算積分蒙卡還可以干別的事情，比如在大構型空間尋找最低態（只要注意到 min、max、算符與sum算符的代數性質很接近，都可以用來做reduce）。你提到的圍棋演算法就是其中一例，在這個例子中，每一個構型就是一局從開始到結束的棋 —— 構型空間顯然是巨大的。

上面敘述的是定義，我來描述一個例子，也是自己做過的一個最簡單的實現：蒙特卡羅法計算圓周率

考慮一個圓半徑R，它有一個外切正方形邊長2R。
易知：
圓面積pi*R^2
正方形面積 2R*2R=4R^2
從這個正方形內隨機抽取一個點，對這個點的要求是在正方形內任意一點的概率平均分布。
那麼這個點在圓以內的概率大概就是pi*R^2/4R^2=pi/4
生成若干個這樣的點，利用平面上兩點間距離公式計算這個點到圓心的距離來判斷是否在圓內。

當我們使用足夠多的點來進行統計時，我們得到的概率值十分接近pi/4
這樣就可以得到pi值

實際上足夠多的點大概要取10萬個。
《三體》描述這一演算法用於解決三體問題的一般情況，因為計算量過大未能成功。
大劉形容這個演算法是使用蠻力對抗精密的方法，我覺得這一說法很好。

所有涉及隨機取樣和平均的演算法都可以稱為蒙特卡洛演算法。用於取樣的metropolis演算法非常有名，曾經被評為20世紀最美演算法之一。

以管窺豹。

蒙特卡羅演算法——大家聽說過蒙特卡羅求π吧？就是畫一個正方形和內切圓，隨機撒點，數一下點落在園內和正方形內的數量之比，就是二者面積之比π/4。
所以蒙特卡羅就是求面積的方法。
而積分是曲線下的面積
所以蒙特卡羅就是求積分的方法
而均值就是概率密度與自變數乘積的積分
所以蒙特卡羅就是求均值的方法
而期望就是均值
所以蒙特卡羅就是求期望的方法
而最優值往往接近或就是期望
所以蒙特卡羅就是求最優值的方法

阮一峰的總結：蒙特卡羅方法入門

我結合 @蘇椰@鵪鶉的答案，對蒙特卡羅演算法有了形象理解。下面是蒙特卡羅演算法的數學描述，截圖來自受限玻爾茲曼機（RBM）學習筆記（一）預備知識。深度學習中的RBM演算法用到了蒙特卡羅演算法。

蒙特卡洛演算法是強化學習的一種演算法。為了確保能夠得到優化的反饋，蒙特卡洛演算法一般只用於片段性任務的學習。也就是說把一段經歷分解成各個片段，無論選擇什麼樣的action都會有終止點。只有當每個片段的policy都被評估過後才能開始對policy進行優化。
大概的演算法是這樣的：
Initialize:
π ← policy to be evaluated
V ← an arbitrary state-value function
Returns(s) ← an empty list, for all s ∈ S

Repeat forever:
(a) Generate an episode using π
(b) For each state s appearing in the episode:
G ← return following the first occurrence of s
Append G to Returns(s)
V (s) ← average(Returns(s))

First-visit MC method for estimating vπ. Note that we use a capital letter V for the approximate value function because, after initialization it quickly becomes a random variable.

蒙特卡洛演算法是將一個不確定性的問題轉化成很多個確定性問題的方法，也可以看成是枚舉法的一種變異。
總體說來，蒙特卡洛就是拿一堆點去模擬一個概率密度分布，這樣原來概率密度分布的不確定性就被一堆確定的點所代替。蒙特卡洛的優點很明顯，簡單，計算準確；缺點就是計算的速度慢，收斂慢。用的點越多，對概率密度分布的模擬就越好，得到的結果就越準確，每一個點都得算一遍啊，所以工作量會及其的大。
為什麼說是枚舉法的一種呢？枚舉法是我們小學就接觸的演算法，就是把所有情況都考慮進去，這就與蒙特卡洛方法的想法很類似，點考慮的越多計算的就越準確。

蒙特卡羅演算法是一種隨機化演算法，最簡單的解釋就是，把問題的正確性擺上賭桌，來換取在一定的時間內解決這一問題，從而實現演算法的簡化。
蒙特卡羅演算法有兩個主要特徵：
1，正確地概率要比錯誤的概率大，並且錯誤的概率有限。（否則這一演算法就沒有意義了）
2. 資源的使用是確定的（這個演算法的優點）

具體的例子可以參考羅賓素性檢測

此演算法誕生的背景是，1.曼哈頓計劃，有極大的計算需求。2.計算機剛開始發展，最適合做計算。
蒙特卡洛演算法理論基礎是概率論，實際就是暴力計算逼近理想結果。正是在以上兩個背景下，它剛好得到了極大的應用和發展。
由烏拉姆最早提出，和馮諾伊曼一起加以發展和完善，他倆是好基友！當時都在參與曼哈頓計劃，後者又在搞計算機。其中過程在烏拉姆自傳一位數學家的經歷中有記載。

類似於粒子濾波演算法，根據已知的數據推測出預測值，再根據當前值和預測值推測出未來值。

蒙特卡羅法（Monte Carlo method）是以概率和統計的理論、方法為基礎的一種計算方法，將所求解的問題同一定的概率模型相聯繫，用電子計算機實現統計模擬或抽樣，以獲得問題的近似解，故又稱統計模擬法或統計試驗法。這個在計算物理裡面學過的。

粗暴點說的話，蒙特卡羅演算法複雜度不高，有比較高的概率得到正確的結果
舉例：利用費馬小定理判斷一個數是不是質數，因為存在卡邁克爾數（不多），所以有一定幾率會判斷錯誤
相對的，拉斯維加斯演算法的複雜度不高，一定會得到正確結果

假定問題的最佳答案在某個範圍里,將範圍內的每個值都試一遍,理論上,一定可以找到最佳答案,這叫窮舉法.
窮舉法的問題在於效率不高,實際操作中往往難於實現(需要嘗試的值,數量多到無窮大),因此發展出一種更加智能,選擇範圍更有目的性的窮舉法,即蒙特卡羅法.
可以理解為使用隨機數(類似投骰子),來指定整個範圍內的某些區域的值進行嘗試,這樣就縮小了嘗試的規模,實際操作中易於實現.

簡單講就是：
一個面積為1的圓盤上,有一小塊圈定的區域，向圓盤上隨機扔飛鏢1萬次（或者更多），其中打在圈定區域中假設5千次。那麼可以得出結論：圓盤上圈出的圖形，面積約為1*(5千/1萬)=0.5

有效的人工智慧往往都是人工，並不智能，但是畢竟不能那這個去忽悠大眾，所以就找了一段有理論支持，理論里還有外國人名的演算法來宣傳一下。給你一台計算機，教會你寫循環，賦值和運算，然後請你寫一個計算pi的方法。於是你就在想像中把一個n x n正方形分成n x n的點陣，進而數出距離中心小於半徑的點的數量，然後計算pi的取值。n的取值越大，pi計算的越準確。但是畢竟n增長的時候，nxn增長的很快，進而你又想隨機取幾個點好了，只要點背後的分布的概率密度是均等的。這個聰明點的小學生都能獨立想出來第一步，聰明點的中學生就能搞定第二步，也就是他們都能獨立的發明Monte Carlo method. 只是他們不是外國人，一輩子都沒機會把自己的創造力發揮出來罷了。