走近人工智能——寫在AlphaGo與李世乭鏖戰前夕（七之三）

三、閉著眼睛瞎蒙

1983年聖誕節期間，時年9歲的法國男孩雷米●庫侖（Rémi Coulom）從父親那裏得到了一件讓他欣喜若狂的節日禮物：一台可編程遊戲機。

可以想象，在電腦還沒有走進千家萬戶的當時，一台智能遊戲機對於一個不到十歲的男孩會產生怎樣的誘惑。不過小雷米並沒有滿足於玩機器本身自帶的遊戲，沒過多久他就開始嚐試通過編程來開發自己喜愛的遊戲。僅僅用了不到一年的時間，他便成功地寫出了第一款智能遊戲。從此以後，他的這一愛好更加一發而不可收。到18歲時，他已經開發出了難度極高的能與國際象棋選手對弈的人工智能軟件。

在網絡尚不發達的當時，寫出一款人工智能遊戲可不是一件容易的事。由於找不到可供參考的源代碼，對於每一種算法，雷米隻能自己一行一行地用代碼去實現。因此，他的國際象棋軟件的表現並不是很理想。

不過，國際象棋軟件卻成為他進入棋類編程的切入點。1997年，也就是“深藍”打敗卡斯帕羅夫那年，雷米參加了在巴黎舉辦的世界電腦國際象棋冠軍賽。這次活動讓他有幸結識了這一領域裏的很多牛人。也正是由於這個原因，後來在進入研究生院學習時，他選擇了以電腦編程為自己的主攻方向。

拿到博士學位之後，雷米在法國裏爾第三大學（Université de Lille 3）任教。其間他曾指導一名碩士生做關於圍棋電腦人機對弈問題的畢業論文。碩士生在做完論文後就離開轉而攻讀博士學位去了，可雷米自己卻深深地陷入了這個問題之中。

雷米覺得靠當前的蠻力搜索法是很難在這個領域裏取得突破性進展的。必須想出一種算法，盡可能多地把一些昏招除去，才有可能把電腦從無窮無盡的搜索中解放出來。有一次他和同事討論這個問題，同事覺得也許可以嚐試一下用概率統計學的方法來指導機器下棋。

雷米頓覺眼前一亮。很多逐一列舉法無能為力的難題都可以用統計學的方法來解決。現成的例子就有人口普查問題，總統選舉的預測問題。這些問題與圍棋人機對弈問題有著類似的難度：不可能把真實情況一一列舉出來。解決的方法也很簡單：取一小部分有代表性的樣本，用這些樣本來估算整個係統的特征。

雷米的同事並沒能給出用概率統計學解決圍棋對弈問題的具體方法。不過在得到這個靈感之後，雷米便一頭鑽了進去。不久，他將電腦蠻力搜索與概率統計學結合在一起，發明了一種全新的算法：蒙特卡羅樹搜索（Monte Carlo Tree Search，簡寫MCTS）方法。使用這個算法，他寫出了全新一代電腦圍棋軟件。

什麽是蒙特卡羅樹搜索？聽上去很高深抽象，其實它的基本原理非常簡單。具體的做法就是：閉著眼睛瞎蒙！

啊，電腦這麽不負責任嗎？其實這是沒有辦法的辦法。我們人類在很多情況下也必須借助這種不靠譜的方法來決策。假如我們在森林裏迷了路，分不清東南西北，手上既沒有地圖也沒有指南針，電話不巧也沒電了。在這種情況下，除了認定幾個不知正確與否的方向聽天由命地向外衝之外，誰還能想出更高明的辦法？

相比之下，電腦的瞎蒙其實是非常科學的。讓我們依舊以5x5圍棋盤來舉例說明。

還是假定黑子第一手下在B-1，現在輪到電腦走白子。

由於電腦沒有人類擁有的無與倫比的直覺，所以它必須把每一種落子的可能性都試一遍，然後從推導出的結果來決定這步棋好不好。假定它從A-0開始，A-1，A-2……一直試到E-4。

咦，這和前麵的蠻力搜索不是完全一樣嗎？

不一樣，在蠻力搜索時，電腦必須把接下來有可能產生的每一種落子都列舉清楚。而在進行蒙特卡羅樹搜索時，它隻需閉著眼睛隨便選取一定數量的走法，然後根據這些走法所產生的結果來評估落子的優劣。

說得再具體一些。假定現在電腦想要知道在E-4落子是不是一步好棋。如果是蠻力搜索法，那麽電腦會把接下來黑子的23種下法，再接下來白子的22種下法……一直到把棋盤擺滿的所有下法都一一列舉出來加以評估。稍有數學常識的人都會知道這樣得出的會是一個天文數字，姑且假定有一億種。

蒙特卡羅樹搜索的基本思路就是：在評估當前的落子時，不必把接下來的一億種可能性全都列舉出來，而隻需從中隨機挑選一部分，比如說一萬種下法來進行比較。

這裏的一億、一萬隻是為了舉例方便。實際數字會比它們大得多得多。

隻需隨機挑選一萬種？那萬一把能夠出奇製勝的妙招漏掉，或者把蠢得不能再蠢的昏招包含在裏麵，那不是要對整個形勢做出錯誤的判斷了嗎？

答案是即使漏掉了個把妙招或者包含進了個把昏招也沒關係。

是不是太不負責任了呢？

完全沒有。還拿這個5x5的棋盤來舉例：假設一個水平正常的人和一個臭棋簍子來比賽，水平正常的人執黑，先走了B-1，而臭棋簍子接下來走了E-4。突然，臭棋簍子想起自己得去和女朋友約會了，於是他對正在旁邊觀陣的圍棋大師說，接下來的棋你幫我下吧。結果是，圍棋大師在十分不利的情況下依然戰勝了水平正常的人。

盡管臭棋簍子開了個臭局，然而在圍棋大師接手之後，白方反而取得了勝利。原因就在於圍棋大師後來走出了幾步誰也沒想到的妙招。

然而這個結果是不能用來評估臭棋簍子開局的好壞的。

要想正確判斷E-4這步棋是不是高明之舉，最好的辦法是找兩個水平普通、實力相當的人接著下完這盤棋。為了排除諸如發揮失常等偶然因素，最好能多找些水平類似的選手來捉對廝殺。最後再用這些選手比賽的總結果，來衡量E-4這手棋水平的高低。

讓實力相當的雙方在正常發揮的情況下下完這盤棋，然後根據比賽結果來判斷當前這手棋下得好不好，這便是蒙特卡羅樹搜索的核心思想。

由於是選擇是完全隨機的，因而無法排除這些落子裏不包含絕處逢生或大意失荊州棋招的可能性。

不過即使有也沒關係，因為棋盤上的落子，絕大多數都屬於平庸的普通下法，極妙和極蠢的走法均屬於鳳毛麟角之類。從一億種下法中隨機選取一萬種，即使真的選到這二者，其數量也不可能多。由於蒙特卡羅樹搜索看的是整體統計結果，因而這裏的偏差不會對總結果造成影響。

下麵就是蒙特卡羅樹搜索算法的實例。為了畫圖方便，這裏把隨機樣本從一萬改為十。

比如說電腦想比較到底是下E-4好還是C-2好。它知道不管選哪個，接下來的走法都是成千上億，不可能全部列舉。於是電腦就從以E-4開始的棋局中隨機挑了10局，又從以C-2開始的棋局中隨機挑了10局，看看哪種走法自己贏的局數多。

結果它發現，從E-4開始下，10局棋自己隻贏了1局；而從C-2開始下，10局棋自己贏了8局。所以電腦認為：C-2比E-4好。

這樣一個算法，把電腦的圍棋能力提高了好幾個數量級。

待續

階梯講師原創作品•謝謝閱讀