一文讀懂蒙特卡洛方法 | 谷歌圍棋機器人科普

作者：阮一峰

轉自：http://www.ruanyifeng.com/blog/2015/07/monte-carlo-method.html

本文通過五個例子，介紹蒙特卡羅方法（Monte Carlo Method）。

一、概述

蒙特卡羅方法是一種計算方法。原理是通過大量隨機樣本，去了解一個系統，進而得到所要計算的值。

它非常強大和靈活，又相當簡單易懂，很容易實現。對於許多問題來說，它往往是最簡單的計算方法，有時甚至是唯一可行的方法。

它誕生於上個世紀40年代美國的"曼哈頓計劃"，名字來源於賭城蒙特卡羅，象徵概率。

第一個例子是，如何用蒙特卡羅方法計算圓周率π。

正方形內部有一個相切的圓，它們的面積之比是π/4。

現在，在這個正方形內部，隨機產生10000個點（即10000個坐標對 (x, y)），計算它們與中心點的距離，從而判斷是否落在圓的內部。

如果這些點均勻分布，那麼圓內的點應該佔到所有點的 π/4，因此將這個比值乘以4，就是π的值。通過R語言腳本隨機模擬30000個點，π的估算值與真實值相差0.07%。

上面的方法加以推廣，就可以計算任意一個積分的值。

比如，計算函數 y = x2在 [0, 1] 區間的積分，就是求出下圖紅色部分的面積。

這個函數在 (1,1) 點的取值為1，所以整個紅色區域在一個面積為1的正方形裡面。在該正方形內部，產生大量隨機點，可以計算出有多少點落在紅色區域（判斷條件 y <>

用Matlab模擬100萬個隨機點，結果為0.3328。

蒙特卡羅方法不僅可以用於計算，還可以用於模擬系統內部的隨機運動。下面的例子模擬單車道的交通堵塞。

根據 Nagel-Schreckenberg 模型，車輛的運動滿足以下規則。

當前速度是 v 。

如果前面沒車，它在下一秒的速度會提高到 v + 1 ，直到達到規定的最高限速。

如果前面有車，距離為d，且 d < v，那麼它在下一秒的速度會降低到="" d="" -="" 1="">

此外，司機還會以概率 p 隨機減速， 將下一秒的速度降低到 v - 1 。

在一條直線上，隨機產生100個點，代表道路上的100輛車，另取概率 p 為 0.3 。

上圖中，橫軸代表距離（從左到右），縱軸代表時間（從上到下），因此每一行就表示下一秒的道路情況。

可以看到，該模型會隨機產生交通擁堵（圖形上黑色聚集的部分）。這就證明了，單車道即使沒有任何原因，也會產生交通堵塞。

某產品由八個零件堆疊組成。也就是說，這八個零件的厚度總和，等於該產品的厚度。

已知該產品的厚度，必須控制在27mm以內，但是每個零件有一定的概率，厚度會超出誤差。請問有多大的概率，產品的厚度會超出27mm？

取100000個隨機樣本，每個樣本有8個值，對應8個零件各自的厚度。計算髮現，產品的合格率為99.9979%，即百萬分之21的概率，厚度會超出27mm。

證券市場有時交易活躍，有時交易冷清。下面是你對市場的預測。

已知你的成本在每股5.5元到7.5元之間，平均是6.5元。請問接下來的交易，你的凈利潤會是多少？

取1000個隨機樣本，每個樣本有兩個數值：一個是證券的成本（5.5元到7.5元之間的均勻分布），另一個是當前市場狀態（冷清、活躍、溫和，各有三分之一可能）。

模擬計算得到，平均凈利潤為92, 427美元。

電腦是如何下棋的：蒙特卡洛樹搜索法

轉自

圍棋

　　圍棋盤由19條橫線和19條豎線組成，共有19×19＝361個交叉點。此外，也有13×13、9×9的小棋盤。圍棋子分為黑白兩色，對弈雙方各執一種顏色的棋子，輪流將一枚棋子下在交叉點上。終局時，佔領(圍起)的「地盤」(即其中的交叉點個數)多的一方獲勝。

　　空白的交叉點稱為「目」，圍到的地盤又稱為「空」。對弈過程中，棋手經常會「數目」，也就是計算雙方目前所圍的「空」的大小，以此判斷形勢優劣。

　　對弈雙方的水平差距較大時，常會採用讓子棋的方式，也就是水平較弱的一方先在棋盤的固定位置放上1～9個子(分別稱為讓先、讓二子、讓三子……)，然後雙方再輪流落子。

　　「指數級增長」與「EXPTIME-Complete問題」

　　指數級增長可算是大規模計算第一大「攔路虎」了。在一個著名的傳說中，國際象棋的發明者印度人塞薩(Sessa)向他的國王請求賞賜，他 說，希望因為發明國際象棋棋盤的第一個格而得到一粒米，因為第二個格得到兩粒米，因為第三格得到四粒米，如此在每後一個格都增加一倍的米量。不識指數級增 長威力的國王欣然答允，甚至還有些責怪塞薩要求太少，然而事後才發現整個國庫的米都倒乾淨了仍然無法填滿整個棋盤。故事的結局是，國王惱羞之下偷偷派人把 塞薩殺掉了。學過等比數列的現代人按一按計算器就知道，國王因為這64個棋盤格子總共要支出2^64-1=18446744073709551615＞10^19粒米，這據估計已經超出整個人類歷史上產米量的總和！

　　回到局勢變化的複雜度問題上。即使10^19這樣的天文數字也「只不過」是一個從當前盤面出發，每次只考慮2種走法，持續64步之後的可 能性空間的大小。對於國際象棋和圍棋這樣的複雜棋類，從初始盤面出發窮盡所有變化的複雜度(也稱窮舉複雜度)更是大得難以想像。資訊理論創始人克勞德香農在 1950年第一個估計出國際象棋的窮舉複雜度大概在10^120種變化左右，具體數字被後人稱為「香農數」。而圍棋的窮舉複雜度又遠遠超出國際象棋，達到 了驚人的10^360。作為比較，目前可觀測宇宙中的原子總數據估計「只有」10^75個。

　　有人會問，為了分析當前盤面一定要窮舉所有未來走勢的可能性嗎？有沒有可能存在一個高效的演算法可以在避免遍歷呈指數級增長的可能性空間的 同時仍然對當前盤面做出準確評估呢？答案是，對於國際象棋和圍棋，我們可以從數學上證明，不僅僅是窮舉複雜度，其局勢變化的計算複雜度也必須隨所考慮的步 數呈指數級增長！對於任意一個給定的盤面，我們定義這個盤面的「最優值」為當博弈雙方都下出「完美走法」的情況下導致的最終博弈結果。如果一個盤面的最優 值是「黑棋勝」，那就是說在黑棋自己不出錯的情況下白棋無論如何努力都是必敗的。理論計算機科學家先後在1981年和1983年證明國際象棋和圍棋都屬於 EXPTIME-Complete類問題，這意味著「任何」能正確計算盤面最優值的方法所花費的時間「必然」隨棋盤大小(亦或棋局的平均步數)呈指數級增 長。事實上大部分流行的「雙人零和」棋類的計算複雜度都是指數級的。有一些棋類如西洋跳棋、五子棋，它們的規模足夠小，所以其初始盤面的最優值已經被計算 出來了。但是像國際象棋和圍棋這樣的複雜棋類，計算其初始盤面的最優值，以現在的硬體計算能力看來還遙遙無期。

　　零和遊戲

　　又稱零和博弈(Zero-Sum Game)，是博弈論中的一個概念，指遊戲(博弈)雙方是競爭而不是合作關係，或者說是一種「你死我活」的狀態。例如兩人對弈，一方贏，另一方必然是輸，不存在「雙贏」。贏棋得1分，輸棋減1分，兩人得分之和就總是0，所以稱為零和遊戲。

　　蒙特卡洛樹搜索法

使用蒙特卡羅方法估算π值。圖/維基百科

選取的隨機點(n)越多，估計值離π的真值越近。圖/維基百科

　　這種選擇很大程度上跟現有圍棋弈棋系統對盤面靜態評估方法的整體捨棄有關。前面提到，由於人們在設計具有一定通用性的圍棋盤面靜態評估函數的問題上長期止步不前，大概在2002年之後人們開始思考採用另一種完全不同的方式對盤面進行快速評估，這就是蒙特卡洛採樣。

　　做為一種通用的計算方法，蒙特卡洛採樣法的思想是當我們在求解一個確定但未知的值的時候，「在概念上」巧妙構造一個隨機過程，使得這個隨機過程的某個數字特徵依概率收斂於我們要求的值，然後「在實際操作中」通過對該隨機過程進行採樣來對這個值進行統計估計。

　　比如說，一種計算圓周率π的蒙特卡洛方法是，在一個二維坐標系中0≤x≤1和0≤y≤1對應的方形區域里隨機選取若干個點，並判斷每個點(x1,y1)是否落在「以原點為圓心半徑為1的單位圓」內(也即判定

　　x12+y12是否小於1)。根據中心極限定理，這些隨機點落在單位圓內的比例依大概率快速趨於π/4。所以我們選取的隨機點數量越多，越有可能得到的一個離的真值更接近的估計。

　　相同的「蒙特卡洛」思想也可以用於圍棋盤面評估。前面提到了，每個圍棋盤面都有一個「最優值」，對應於對弈雙方都採用完美走法的情況下該盤面的最終結果。對於圍棋已經證明，計算這個最優值的時間至少隨該盤面到終盤之間的步數呈指數級數增長(平均200步，每步平均增長200倍數量的可能盤面)。既然從理論上無法得到最優值，有沒有可能根據蒙特卡洛思想對整個可能性空間進行某種採樣，然後通過統計估值的方法逼近這個最優值呢？人們對這個問題的思考在2006年終於取得了突破性進展，提出了一種稱為蒙特卡洛樹搜索的動態評估方法。

　　需要指出的是，現有的蒙特卡洛樹搜索法雖然能保證大量採樣的結果最終收斂到盤面最優值，但為達到「足夠收斂」所需的採樣次數仍然是隨整個可能性空間的規模指數級增長的。但是在圍棋弈棋系統的實踐中，蒙特卡洛樹搜索在比賽時間受限的情況下確實表現出遠遠超過傳統方法的棋力。最近幾年人們受這一觀察的鼓舞，在選擇策略中加入更多和圍棋相關的專家知識，使得基於蒙特卡洛樹搜索的圍棋弈棋系統水平不斷提高。

　　*1有些圍棋軟體會在特定條件下觸發「死活棋判斷」或者「劫爭」模式，但這些優化更像是在特殊情況下的一種特殊戰術，而不是作為一種基本思考模式。

　　*2這裡「思考深度」定義為對每個變化的展開步數。假設一台機器原本一秒鐘可以考察b^d個變化，對應思考深度為d。增加b倍硬體能力使得機器一秒鐘可以考察b×b^d=b^(d+1)個變化，對應思考深度為d+1。使用αβ剪枝法使得機器僅需考察(b^2d)^(1/2)=b^d個變化就達到和考察b^2d個變化一樣的效果，對應的思考深度為2d。

　　*3前面已經強調過了，國際象棋使用的策略只是在「效果上」等價於對一定階段內所有變化的窮舉，而並不在實際運算過程中真的窮舉整個可能性空間。

　　*4不僅如此，蒙特卡洛樹搜索方法目前已經作為一種通用的動態評估方法廣泛應用於「通用博弈比賽」(這種比賽要求為事先不知道具體規則的棋類遊戲設計對弈程序)。

推薦閱讀：