蒙特卡洛演算法和AI史上的革命

估計只有程序員願意去了解Aplha go的實際實現原理，大部分吃瓜群眾樂呵樂呵就完事兒了。

為什麼圍棋一直是程序員的巔峰呢？傳統的博弈程序，碰到棋類的時候，一直是這麼做的：思考未來幾步，電腦和人分別在忙什麼。

比如，輪到電腦下了，電腦就把自己能下的位置都點出來，這是第一步；接著，電腦琢磨自己走了這些位置以後，人會怎麼辦；再接著，考慮人這麼走以後，自己又該怎麼辦，子子孫孫無窮匱也。

這讓我想起了曹操走華容道，基本就是玩了一次小遞歸，曹操多想一步，諸葛亮多想兩步，逮個正著。

其實人不是這麼下棋的。咱們回憶回憶，如果我們在下五子棋，會不會開局就下在棋盤邊緣呢？顯然是不會的。因為我們「感覺」，下那兒沒啥前途。電腦沒有感覺這回事兒，就得踏踏實實的證明，下那兒真沒前途，每一步都考慮那麼多種情況，這事兒基本就沒法玩了。

工作第一年的時候，我嘗試用博弈樹寫五子棋（現在回憶起來。五子棋真他娘的簡單啊），電腦考慮到5層左右就基本歇菜了。5層的意思就是我一步你一步，我再一步你再一步，接著我最後來一步。這5層里，我走3步你走2步，接著分析那個局面，看看對誰有利，對我最有利的那個，我就選這套路來。

這實在沒法和會走五子棋的人抗衡。小弟年方二八（注意是2乘以8）的時候，就曉得五子棋要搞別人，多想個3-4步。也就是說，電腦充其量也就我16歲的水平。而我16歲的時候，尚且會在精力充沛的時候，想個6-7步。我這種深入，和電腦完全不同，人的大腦會在其中做各種各樣的判斷，有時考慮的少，有時考慮的多。電腦如果做各種各樣的情況分析，總會有掛一漏萬的情況，不分析，由於局面太過龐大，又沒法搞下去。

我當時直接就放棄了。

現在每次回憶起年少時的點滴，這一段都有點不忍回首。廢了好多精力，少了多少個和異性網友見面的機會，少了多少次QQ撩撥陌生美女的機會，最後出來一個初中生水平的AI。唯一值得欣慰的是，當時同時里有一個國內知名演算法論壇的版主，也寫了一個AI，被我的AI吃的死死的,這就叫比上不足比下有餘。

後來我接觸了一個遊戲，來自北美國家加拿大。

這遊戲我在各個渠道推了好多次，英文名叫Quoridor，中文名叫「步步為營」

其遊戲複雜度要高於五子棋。

我這種時刻喜歡show智商優越感的，那必須把這個棋類熟悉起來。

熟悉起來就到處找人下。找的時候還要裝做自己也是初學者的樣子，享受虐人的快感。

好景不長，大多數親戚都掌握了我的套路，我一個都騙不到了。那時候就有個想法，無聊時間就寫個AI，用來進行對戰。

這個想法非常的強烈，我就從那個時候開始動手了。實際上我也碰到了和五子棋AI一樣的問題：想的深了，需要考慮的局面太多，想的淺了電腦非常弱智。

那個時候互聯網開始慢慢發達起來，我就開始漫遊互聯網。我想了解下，中國象棋、國際象棋、五子棋這些棋類，他們都是怎麼去解決這個問題的。那個時候有一個很有名的中國象棋軟體，叫棋隱。界面一看就是個程序員弄出來的，粗陋、不友好，但下起棋來確實凶。

我拿著棋隱這個軟體在QQ遊戲大廳里到處虐人，虐了一陣以後索然無味：每次行棋都是對方走一步，我把對方的那一步搬到棋隱里，然後耐心等棋隱出招，再同步到qq遊戲大廳。後來我回過味了。這我不他媽成了棋隱的助理了？到底是我玩電腦還是電腦玩我呢，果斷刪了！

網路上有不少文章介紹中國象棋的AI是怎麼出來的。有一個系列文章寫得非常不錯。它為我們這些笨蛋程序員提出了幾個思路：

1、把重心放在棋局估值函數上。

2、非對稱性拓展棋局。在開局的時候，電腦應該儘可能多的考慮局面，但在具體的交戰期間，應該放棄廣度，而在深度上下文章。

3、用一些比較簡單的辦法編碼整個棋局，讓電腦學習變得沒那麼困難。

就這3個點，一下子把我寫的步步為營遊戲。拉升了好大一個台階。尤其是第二點，在中後期的時候，我試過讓電腦思索後十三步，速度還很快。

實際證明，這個AI出來以後，初學者完全走不過了。他們把：當哥你設計的遊戲太弱智了這個話題，轉變為：當哥你設計的遊戲太無聊了。

而我蠻有成就感的，這個遊戲我就封存起來了。直到3年後的今天。

ALPHA GO擊敗圍棋冠軍，對於演算法界的程序員來說，是跟吃了搖頭丸一樣HIGH的——儘管我沒吃過搖頭丸。因為即使我剛才介紹的那個能讓步步為營上一個台階的3板斧都用上，即使是使用了當今最快的計算機，人工智慧走圍棋，還是差人類一大截的。

因為：圍棋的局面評估函數，幾乎無法寫出來。

圍棋的棋盤，對於AI來說，可以用四個字來形容，叫做浩若煙海。鬼神莫測，變化無窮。二十多年前，有一個叫陳志行的中國人，開發出一款圍棋軟體，他將它命名為「手談」（注意他當時的電腦，大概是現在電腦速度的1/100），下面是他的記錄

1995年9月，東京的FOST杯世界電腦圍棋錦標賽，冠軍。「手談」還被日本棋院認定為5級。

1995年，漢城的應氏杯國際電腦圍棋賽，冠軍。

1996年9月，東京的第二屆FOST杯世界電腦圍棋錦標賽，仍然是冠軍。

1996年，陳志行的老單位中山大學協辦應氏杯國際電腦圍棋賽，他主場作戰。除了「手談」，他所指導的一個小組編製的程序「烏鷺」也參加了比賽。「手談」又是冠軍。

1997年，名古屋的第三屆FOST杯世界電腦圍棋錦標賽。「手談」在第二輪就出了問題：它的對手雖弱，卻使「手談」超時作負。這也許是正是因為對手弱，在棋盤上留下許多未決的問題，使「手談」要花費大量時間來計算。　　但有驚無險，「手談」仍然奪得FOST杯世界電腦圍棋錦標賽三連冠。

1997年的時候，IBM的深藍，已經擊敗了當時的國際象棋冠軍，卡斯帕洛夫。

在此向已經去世的陳老先生致敬。

可是說到現在，我都沒有談到ALPHA GO，以及本文的標題蒙特卡洛演算法。現在來正式說說。

蒙特卡洛演算法的基本實質是，對於無法判定其優劣的局面，有一個特殊的處理辦法：模擬兩個笨蛋，隨機下棋，下完以後，哪邊贏了，就給哪邊計一分。

這種方法顯然非常的模糊，不過反正不是終盤，如果模擬個10000次，大家都隨機，黑的就硬是贏了6000多盤，白的才3000多盤，其實就是代表黑的其實有優勢。

這個思路一提出，演算法圈就炸了。其實人類本身也沒多聰明，也是不斷的看各種局勢，然後生出一個模糊的感覺：這個局面好像我有優勢。計算機只不過把這個局面變成了一種可量化的方式，通過大量的隨機落子盤勝負概率來決定局面的優劣。

這樣就好辦了。把圍棋最重要一個門檻給邁過了。

後來人們發現，原來的設計思路也不能全部拋棄。因為如果你從第一步就開始使用隨機落子來判斷局勢，很有可能出現非特徵的結果。比如，10000盤裡，黑的贏5100盤，白的4900盤。這不能代表黑的就比白的牛逼很多，恰恰說明了兩者是均勢的。

原來那個多層思想，還是要延續。人們就琢磨，把隨機落子這個事兒，還是放在多層思考的後面。比如我們假設電腦要算後三步，三步以後，再開始通過隨機落子來評估局勢。

那麼前面的問題就又冒出來了。計算機一旦思考起來，根本剎不住車。局面是幾何級數的增加。圍棋全盤有361個格子，開局的時候，去掉大夥走的那麼幾步，還有300多個地方能放棋，全部思考一遍基本啥事兒也不用幹了。

於是人們又對這個蒙特卡洛演算法做了優化。不斷的強化在隨機局裡獲勝的那個思考分支，最後呈現的形式就是

有前途的分支才會被計算機思考下去。怎麼判斷有沒有前途？用隨機落子的辦法來決定。

這個演算法非常的優雅與精緻。比起原來那種動輒3000-5000行的局勢判斷函數，窮舉各種複雜的情況，有一種不變應萬變，獨孤九劍的感覺。

這裡的演算法並非我寫的這麼簡單。還有更多細節問題。有點時候，隨機下棋的結果畢竟是有偏差，特別是有些步子，在一開始模擬的時候看起來特別的有優勢。舉個例子來說，中國象棋中，將軍對手的步子。演算法在設計時，有一個基本宗旨——在前期的時候，盡量給每一個步子都有照顧到的機會，直到後面模擬發現這個步子的質量不高，才進行拋棄。即使拋棄，後面也會有再次被發掘的可能（比如隨著某些思考分支越來越深，發現整條路子都有問題）。

接下來就好辦了——對掌握了蒙特卡洛演算法的電腦進行大量訓練。

了解到這個演算法後非常興奮，我春節期間就啟動了對步步為營演算法的修改。比較可怕的是，這種演算法由於天然就是要通過不斷的模擬對局來優化演算法，因此對於局面一直有記憶能力。換句話說，對局越多，思考就越精確。而我原來的演算法，雖然被我優化過多次以後，行棋速度很快，但一旦被戰勝，就會被摸到套路，很難再贏下去。

經過2-3天的優化，居然已經到了可以欺負初學者的水平了。每一步棋只是花了3秒而已，還有大量的優化沒有做，不過這麼快就達到這個效果，確實也是始料未及。

未來我會把這個遊戲分享到訂閱號里來。心情激動。就記錄了這麼一篇。