阿爾法狗的前世今生

作者：梅俏竹，美國密歇根大學信息學院和計算機系副教授，研究領域為數據挖掘和機器學習，骨灰級圍棋愛好者。

編註：感謝松鼠悠揚牽線聯繫了梅老師。李世乭對戰阿爾法狗於北京時間2016年3月15日結束，可以預見，下一場人機大戰，應該還可以吸引到足夠多的關注。不過，耐心有限的人類，早晚會對這樣的對抗失去興趣，或許那時早已經有更有趣兒的比賽值得關註：機器VS機器。人機對抗的硝煙會慢慢消散，但包括谷歌阿爾法狗項目組成員在內的計算機科學家不會停歇，我們處在一段短暫但變革劇烈的歷史中，而今天這篇文章，或許可以幫助你了解自己所身處的時代已經發生、正在發生和將要發生的變革，哪怕只是窺見其過程中的星星點點的軌跡，也比全然無知要好吧。

一，「阿爾法狗」為什麼盯上圍棋，而不是麻將？

傳說堯作圍棋以教丹朱，如此算來圍棋就有4000多年歷史了。2009年的LG杯決賽，就被善於造勢的韓國人渲染為「四千年之戰」。當時對局的是李世石和古力，頗有中韓圍棋此消彼長的天王山之戰的意思。如今李世石又站在了歷史的關頭，肩負著人類四千年的高傲和尊嚴，只是對面坐著的是谷歌的計算機棋手阿爾法狗(AlphaGo)。谷歌，古哥，莫非前定。

圍棋是什麼？在計算機的眼裡，她無非是一個桌面遊戲。19*19的棋盤，黑白輪流走棋。一塊棋沒有氣了，就得從棋盤上拿掉。最後無處可下了，誰占的地方大誰就贏。規則如此簡單。

但在人類的眼裡，圍棋早就超越了遊戲的範疇。其中有歷史，有禮儀，有美學，有人生哲理。本能寺變，淮上信至，十番棋，擂台賽，見證了多少歷史；新布局，宇宙流，美學的大竹，石佛與妖刀，蘊含了多少風雅；入界宜緩，棄子爭先，早成了無數人的人生信條。當計算機真的坐到自己對面時，人是五味雜陳的：我說這是人生，你卻說這只是一場遊戲。

在浩如煙海的人類智力遊戲中，圍棋不過是一粟而已，其在民間的影響力，未必能比得上麻將和撲克。相比中國尋常巷陌的麻將桌子和賭城成千上萬的撲克檯子，下圍棋多少有點曲高和寡的意思。

那麼為什麼人工智慧如此青睞圍棋呢？為什麼不是「AlphaMajo」挑戰四川麻將高手，或者是「AlphaHoldem」挑戰德州撲克冠軍呢？其原因有三：

其一，圍棋有簡單的輸贏規則 (explicit winning condition)。這一點非常重要，因為電腦需要對每一個決策的好壞做精確、量化的評估。把圍棋下好可能需要十年，但初學者就能判斷一盤下完的棋誰輸誰贏。如果規則本身比較模糊，可以去想像電腦和人類比拼現代詩或者抽象派繪畫，會出現什麼樣的結果。

其二，圍棋是信息對稱的，或者說是信息完整的 (perfect information)。面對棋盤，電腦和其人類對手看到的是完全一樣的信息。象棋和國際象棋亦是如此。麻將、撲克和四國軍棋則不同：每個玩家只能看到自己一方的信息，而必須通過對手的行為去推測他的底牌。這就不難解釋，為什麼久經沙場的麻將老手往往輸給不按常理出牌的新手，以及為什麼德州撲克里有層出不窮的騙術與心理戰。信息的完整和對稱，讓電腦可以做絕對理性的決策：不管你為什麼這麼下，我只要下當前局面下最好的一手就行了。

其三，圍棋廣闊的搜索空間，帶來的挑戰和誘惑是電腦無法抗拒的。人類下象棋和國際象棋早已淪為電腦的手下敗將，而圍棋至少還能期待柯潔。

二，電腦學下圍棋，到底有多難？

圍棋究竟有多難呢？對人類棋手來說，這很難量化。聶衛平曾謙虛地表示「圍棋境界高不可及，我也只能算是剛剛入門。」 職業棋手經常被問到與「圍棋之神」的差距：有人說讓兩子，柯潔說讓先，有人則認為圍棋的發展接近盡頭，眾說不一。人類的視野總是被眼前的山擋住，等爬到山頂，才知道山外有山。

對計算機來說，這個問題就好回答得多。圍棋究竟有多少種變化呢？如果對每一種變化我都能判斷局面好壞，那我豈不就是每步都能走到最優的圍棋之神了嗎？早期的人工智慧的設計者們的確是這樣想的。

Tic-Tac-Toe遊戲你們都玩過吧？

設想我們玩一個Tic-Tac-Toe（圈叉棋，如上圖。）的遊戲：3*3的棋盤，玩家分別在空格中填入棋子，最先連成一行、一列、或一對角線者勝。如果考慮每個空格只有黑子、白子、無子三種狀態，那麼一共只有3⁹（3的9次方，即9個3相乘）＝19,683種狀態。就算考慮到落子的順序，也不過是9! = 362,880種變化。評估不到一百萬種變化的優劣，對當今的計算機來說，自然是小菜一碟。

但是這個辦法用得圍棋上，一下子就傻眼了，變化太多！

那麼圍棋的變化有多少呢？如果也考慮每個交叉點有黑子、白子、無子三個狀態，那麼一張圍棋盤的狀態是3³⁶¹種，除去實際不可能出現的狀態，大約是10¹⁷⁰。相比起來，國際象棋的狀態數只有不到10⁵⁰，這與圍棋的複雜度相比較，完全可以忽略不計。如果考慮行棋的順序，那麼圍棋有大概361!種變化，或者說是10⁷⁶⁸（實際上沒有這麼多，因為總有不能落子之處）。無論哪一個，都是天文數字，因為宇宙中可觀測的原子的總數，也無非是10⁸⁰。

或許有人說，圍棋之神也不一定每手都算到底吧，往後推算個三五十步差不多了。好，序盤的時候（按60手以內）推算50步大概有超過10¹²⁰種。10步？10²⁴。就算只推5步也有超過2?10¹²種變化。就算評價一種變化只需一個納秒（這當然是不可能的），那麼下這一手也要40分鐘。何況對計算機來說有更嚴肅的問題：不走到底我怎麼知道誰好誰壞？

看起來太難了！那麼棋盤小一點會不會簡單一點呢？答案是肯定的。在13*13的棋盤上，變化的個數降低到了10³⁰⁴。9*9的棋盤上則只有10¹²⁰。張栩自創的四路棋，變化數只有10¹³，而狀態數更降低到了幾千萬個：仍然很多，但對計算機來說完全可以處理。

好了，現在我們知道圍棋之神和宇宙之神大概是同一位。她既然能洞悉棋盤上所有的變化，大概也熟悉宇宙中所有的原子。AlphaGo真的能窮盡每一個變化嗎？沒關係，就算能也並不恐怖。我們明天就把棋盤擴大到21路，那就算全宇宙的原子都變成AlphaGo也不行了。

三，早期的計算機圍棋靠人教套路

計算機當然不是圍棋之神。你可以把他想像成一個天賦異稟的少年，想要挑戰武林高手。他內功極強，動作極快，但不會招數（想想剛剛學會九陽神功的張君寶或者張無忌），他如何才能戰勝招法嫻熟的武林高手呢？

由於對天文數字般的圍棋變化的恐懼，最早的計算機圍棋，選擇了模仿人類的方式。你會我不會，但你走哪、我就走哪總會吧。這也是被專業棋手戲稱為「背棋譜」的方式。小飛掛角，應以小飛。你逼住，我就跳，你跳，我就跟著跳，被人走得多的總是好的。大量的圍棋知識如定式（布局的套路）、手筋（局部戰鬥的妙招）等，就這樣從棋譜中提煉出來，然後被程序員以規則的方式告訴電腦。然後，電腦在實戰中按部就班跟著走。著名國產圍棋軟體「手談」的早期版本，就是走的這個路子。

這樣的演算法的棋力當然與規則庫的完備程度相關，但基本上是相當低下的。見一招流星飛墮，便會應以一招花開見佛，這充其量是林平之他爹的水平。這種背定式的演算法，實戰稍微變化一下，小飛掛變成大飛掛，跳著走變成飛著走，電腦就立刻感到面目全非，找不到北。

當然，程序員也有對策：他們在「死記硬背」之上，逐漸加入了許多模糊匹配的嘗試。在實戰中見到略有不同的場面下，也可以走出下一手。這可以看成一定程度上的舉一反三。當然，在差之毫厘、謬以千里的中盤戰鬥里，這樣的模糊匹配很難奏效。

「背棋譜」的演算法，還有一個重大缺陷，就是這些規則絕大多數都限於窄小的局部，而對全局棋子的協同則毫無章法。早期的圍棋程序，最怕「征子」，即是這個缺陷的典型體現。

既然背棋譜的下法缺陷如此明顯，為什麼還是計算機圍棋的程序員們的第一感呢？從計算機的角度講，背棋譜極大地縮小了選擇的空間。掛角除了小飛、跳、夾、尖頂、靠出，大概也沒有多少應法了吧。這樣值得考慮的選擇就變得很少，大大減輕了電腦的計算強度。

四，計算機圍棋的另一做法是評估局勢

那麼有人會問，既然縮減選擇範圍不靠譜，咱們能縮減變化的深度嗎？

這是一個相當有趣的想法。如果每一招棋都只管當下、不想後招，那麼每下一步不就只需要考慮最多三百來個變化了嗎？假設我們可以判斷每招棋放在棋盤上之後局面的好壞，那麼選最好的一步下不就行了嗎？這的確很誘人！可是當一盤棋只下了寥寥幾十步的時候，真的可以判斷局面的好壞嗎？偉大的圍棋之神，真的可以計算每顆棋子的效用嗎？

早期的計算機圍棋，的確在此做了很多有趣的嘗試。一些人在背棋譜，另一些人則在評估局勢，評估局勢的人甚至開始得更早。

這很好理解：往後推一步也不是終局，推十步也不是終局，那麼只要我能精確評估局面的好壞，那麼推多少步都能用得上。怎麼做呢？分而治之吧！圍棋不是誰圍的地盤（目數）大誰贏嗎？那假設棋盤上的每顆棋子都能折算成目，把它們加起來不就可以判斷局勢好壞了嗎？從50年前（那時計算機的水平可以想像），就有人開始做這樣的嘗試。

具體的做法不一，但大致想法都差不多：離我方棋子越近的空點，越容易是我的，離對方棋子越近的點，越容易是對方的；活子，死子，和半死不活的子則分開考慮。據說第一個圍棋程序誕生於1968年，其主要思想就是通過計算每一個棋子的「影響力」來評估局面，可惜其論文現在已經找不到。另一篇發表在1981年的文章筆者倒是讀了，基本的做法還是計算「氣」（與棋子相鄰的空位）的多少，選擇最大化己方的氣，最小化對方的氣的下法。（因為氣的多少關係到棋子的死活，也就是生存能力）

在1990年代的「手談」軟體里，其作者曾經把每個活子的影響力設置為：「對其相鄰位置為4，斜位（小尖）為3，單關和小飛位為2，稍遠為1。」 在子效累加的基礎上，設計者們又陸續加入了不少改進，以修正單子、相鄰的棋子和成塊的棋子的價值。

這樣的做法棋力如何呢？似乎還是很糟糕。即便結合了一些人工智慧的搜索演算法，1990年代計算機圍棋的冠軍大概只是業餘高手讓14-16子的水平。如果說「背棋譜」演算法是打完一套少林長拳，又重新打起；那這種靜態局面評估法，有點像所謂的「亂劈風」刀法：沒有後招，看哪好砍就砍哪，砍到哪算哪。值得一提的是，雖然棋力不逮，靜態局面評估作為中後盤的快速形勢分析手段，倒是深受圍棋愛好者喜歡。筆者在新浪圍棋下棋的時候，經常使用其提供的形勢分析工具來點目（數自己的空有多少）。在職業棋手孟泰齡的網路自戰解說中，我們驚訝地發現泰哥原來有時也會用這個工具。

整個二十世紀，計算機圍棋都處於背棋譜和形勢評估交相輝映的時代。設計者們加入了許多啟發式演算法以計算征子，識別打劫，模糊匹配，優化官子。可是計算機的棋力卻如走進了漫漫黑夜，一直上不去。

這導致圍棋高手們對計算機的水平有著根深蒂固的輕視：直到阿爾法狗與李世石決戰之前，羅洗河還認為自己可以輕鬆讓AlphaGo四子。的確，如果一個學了三十年棋的人，還只能和業餘高手下讓子棋，他的圍棋生涯恐怕早就被判了死刑吧。

當然，在筆者看來，這種背棋譜和靜態形勢評估的計算機圍棋，是遠遠稱不上「人工智慧」的。早期的設計者們播下了種子，這顆種子在黑夜裡，在石頭下慢慢生根發芽。它在等待掀開石頭的一天，距這一天還有很多年。

五，搜索：從走迷宮去領悟下棋秘籍

計算機圍棋的種子在石頭下緩緩成長。讓我們暫且按下不表，盪開一筆去看看真正的人工智慧的研究者們在做些什麼。他們絕大多數沒有接觸過圍棋，他們從小的目標是打敗國際象棋的人類棋王。

和東方人從小就接觸大棋盤不同，西方人的童年是從圈叉棋到國際象棋的過程。我們已經說過，圈叉棋的變化不到百萬，國象的變化看上去似乎也不多。因此西方的研究者一上來，心裡想的就是窮舉法。

窮舉也得有順序。從威尼斯出發，條條大路通羅馬。威尼斯是開局，羅馬是終局，我們把通向羅馬的過程叫做搜索。搜索在人工智慧的兵器譜上穩居第一位。1990年代以後由於互聯網的興起和人工智慧的低谷，人們提到搜索的時候，首先想到的往往變成了Google和百度。我問問題，電腦告訴我答案。

別忘了，搜索的本義，是尋找羅馬的過程而非羅馬本身！

人類對搜索可不陌生。不就是走迷宮嗎？在曼哈頓的每一個路口都有4個選擇，不管選哪一個，到下一個路口又有另外4個選擇在等你，直到你走出了迷宮或者窮盡了所有的選擇。

從數學上講，我們把迷宮的開始叫做「根」，每一個路口叫做「結點」，路口的每一個路叫做「分支」，每一個無路可走的狀態叫做「葉」，那麼走迷宮所有的變化就成了一棵「樹」。搜索的過程，就是按照某個順序遍歷這棵樹，直到找到出口的葉子或者找遍所有的葉子。

這多麼像圍棋！從空白的棋盤開始，每一步的選擇都帶來數十成百的分支，每一個終局都是一片葉子，而每一盤贏棋都是羅馬。

找到迷宮的出口或者找到羅馬可不難，只要在走過的路口做記號，一直靠左或者右走就行了（在計算機演算法里，這叫做深度優先搜索，它可以保證無遺漏地遍歷一棵樹）。難的是，到了羅馬還趕得上吃頓熱的。這可就難了，因此我們必須要放棄一些分支，放棄尋找大多數葉子。在有限的時間和選擇里，我們還能找到羅馬嗎？

無數人工智慧的先驅，前仆後繼地研究這個問題，其中包括著名的Dijkstra先生，他的演算法能讓人找到威尼斯到羅馬的最短路徑（當然，找到這條路徑的代價並不比深度優先的搜索低）。

計算機比人類擅長走迷宮，它可以自由地在已經發現的路口間跳躍（類似於機器貓的傳送門）。這使得它可以每個路口都試一下再決定下一步，即是所謂的廣度優先搜索。搜索演算法中名滿江湖的A星演算法（A* Search, 最佳優先搜索的一種），即是兼備了廣度優先搜索和最短路徑搜索之長。它在每一個路口派出探子，回報下一個路口有多遠、是哪裡。它再綜合當前路徑的長度和對下一個路口離終點的距離的估計，來決定下一步怎麼走。行軍數天到離長安幾百里外的隴右，似乎當然不如花十天出子午谷直逼長安城下。

這樣的演算法大大降低了搜索最優路徑的複雜度。但是，估計威尼斯到羅馬的距離容易，估計中盤到贏棋的距離，還是很難啊！

等一等，我們似乎忘記了一件重要的事情。迷宮是一個人走，棋是兩個人下的呀。不能預測對手的下法，怎麼能找到自己最優的下法呢？在把搜索應用到棋類遊戲的探索中，人工智慧的先驅們發明了「極小化極大演算法」（minmax algorithm)。聽起來是不是很拗口？其實不難理解，在尋找下一步棋的時候，我們優先選擇下在不管對方怎麼應，我們都不會太壞的地方（而不是下在，如果對方應錯了就佔大便宜，應對了可能反而吃大虧的地方）。研究者們又設計了紛繁複雜的演算法來進一步縮小搜索空間，以讓計算機能在更有效的分支上搜索得更深，而不把時間花在一看就不行的廢棋上。這其中一個相當重要的演算法叫做Alpha-Beta剪枝。前文提到的1990年代的計算機圍棋冠軍即是用它來配合局面評估。Alpha-Beta, Alpha-Bet，Alpha-Go，前世今生，情何以堪！

有了這些搜索演算法在手，計算機在圈叉棋上戰勝（或者打平）小朋友們早就不在話下了。可當人工智慧的研究者們把眼光投向國際象棋的時候，卻發現它的搜索空間意外的大，似乎怎麼剪枝也搜不到底。

當時的人們也沒有一個好的方法能準確估計非葉結點局勢的好壞（如果子力多就好，那擺象棋殘局的騙子們就都下崗了）。搞計算機圍棋的一看，你象棋都搜不到底，我圍棋就更別想了。於是計算機圍棋又在黑暗中度過了二十年，直到一個英雄的出現。

六，深藍帶來的啟示

1996年2月10日，一個叫「深藍」的電腦挑戰國際象棋棋王卡斯帕羅夫。讓所有人跌破眼鏡，它居然贏了第一局，之後兩和三負。深藍是IBM設計。雙方約定一年後再戰。1997年5月，雙方再下六局，「深藍」一勝五和戰勝棋王。這是人工智慧載入史冊的里程碑事件。

值得一提的是，輸棋之後的卡斯帕羅夫認為深藍表現出的智能和創造性不可思議，必有人類棋手在背後操刀。這次谷歌顯然早有準備：高調的營銷，讓幾乎所有的人類頂尖高手都現身講棋，從而杜絕了「機箱里躲著柯潔」的猜測。

「深藍」為什麼贏？除了摩爾定律帶來的計算力的顯著提高，深藍的演算法似乎也沒有什麼稀奇。Minmax搜索, Alpha-Beta剪枝, 為什麼一夜之間武功就變得如此厲害？

當深藍揭開神秘面紗，人們發現，深藍演算法中的秘密其實不外乎兩點：局勢評估和往前看。老熟人了，不是嗎？深藍的局勢評估考慮了棋子的重要性（皇后是9，小兵是1，車取其中），每個棋子的影響範圍（又很耳熟？），王的安全係數，以及先手 （tempo）。這個評估並非靜態的，而是要往前窮舉數步棋中的所有變化，再對所有可能導致的局面進行估計（相傳與卡斯帕羅夫下的時候，深藍往前推了12步）。這有多難呢？粗略以每一步棋有100種下法而計（每個兵最多2-3種下法，每個馬最多8種下法，每個車14種，去掉不能下的地方，以此類推），12步也就是10²⁴種變化。用上alpha-beta的剪枝和IBM強大的並行運算能力，完全可以處理！

深藍的成功，讓人類第一次正視人工智慧的強大潛力。讓我們看看深藍帶給計算機圍棋的前所未有的啟示與契機。一方面，深藍的成功宣告國際象棋已經是被解決的問題，這讓許多人工智慧的研究者們把目光投向了下一個挑戰：圍棋。另一方面，計算機圍棋的設計者們從深藍身上驚訝地領悟到了兩點：其一，並沒有多少專業知識，貌似蠻力的窮舉搜索竟能如此有效；其二，精確的局勢評估如此重要，但靜態的評估似乎並不足取。從現在開始，背棋譜不再是出路，而局勢評估將以動態的搜索為基礎！

2006年，一個叫做《瘋狂的石頭》的黑色幽默電影席捲中國。同年，一個同名（Crazy Stone）的計算機圍棋程序悄悄地在計算機奧運會上奪得9*9圍棋的冠軍。翌年，它在計算機奧運會上蟬聯9*9冠軍並奪得19*19比賽的亞軍。再下一年，瘋石在對真正的職業棋手（青葉熏四段）的授八子局中獲勝，同年年底又贏了授七子局。5年後（2013年），瘋石在對石田芳夫九段的授四子棋中取勝。第二年，同樣授四子，瘋石取勝棋力更強的依田紀基，其在圍棋界的影響力達到頂峰。

無獨有偶，2010年之後網上出現了一個叫Zen（禪）的計算機棋手，在KGS（一個著名的圍棋伺服器）上慢慢升到5段。筆者當時經常在KGS下棋，也曾和Zen互有勝負。可是不久就只能眼睜睜看著它的棋力超過自己，揚長而去。2012年，Zen也在授四子局中擊敗了專業九段：深受大家喜愛的武宮正樹。

從此計算機圍棋進入了一個新的時代，一個不斷帶給大家驚喜的時代。可我們不禁想問兩件事：第一，「瘋石」的出現離「深藍」也有十年過去了，這十年計算機都在做些什麼？第二，為什麼這一切總是和「石頭」有關？

七，一株奇異的樹——蒙特卡洛樹

從「瘋石」開始，這個時代可以被稱為「蒙特卡洛時代」。當代的計算機棋手，不約而同地採用了一種叫做「蒙特卡洛樹」的搜索演算法（Monte-Carlo Tree Search），直到AlphaGo也不例外。它是什麼獨門絕學？

深藍帶來的啟示之一，是尋找精確的形勢評估函數，而這個函數必須是動態的，必須要考慮到數步乃至數十步之後的局面。

這思路並非沒人想過。可是相比國際象棋，它有唯一的取勝目標——殺老王，圍棋的局勢判斷或許更為主觀。什麼是勢？什麼是厚？什麼是薄？勢與地如何換算？大局觀究竟是什麼？這些大概是圍棋永恆的問題。就連頂尖棋手也常常判斷不清。看頂尖高手的比賽最有趣，總是韓國解說覺得韓國人好，中國解說覺得中國人好。一邊說是棄子，一邊說是被吃…… 計算機可不喜歡橫看成嶺側成峰，它需要做理性和客觀的決斷。

那麼圍棋中有什麼是絕對客觀的呢？我們之前說過，只有終局的勝負。可那些代表終局的葉子在圍棋的搜索樹上似乎遙不可及。那麼，能否不窮舉所有的葉子，也能判斷一個枝頭的局勢呢？這個想法讓人精神一振。如果一棵枝頭有10片葉子，8片是贏，兩片是輸，我們一定要找到輸贏最大的一片才能判斷這個枝頭的好壞嗎？如果這棵枝頭有100片葉子，我們難道一定要看遍所有的葉子才能判斷優劣嗎？

喜愛統計的朋友們已經樂出了聲：要想知道添加劑是否超標，當然不需要打開所有的罐頭。抽樣就行了嘛！假設對每手棋我們都能抽樣調查它所導致的終局，大概不需要理解地、勢、厚、薄也可以做形勢判斷了吧？

如何抽樣？隨機既簡單又靠譜。一步新著法好壞不明時，職業棋手往往提倡實戰解決。計算機也一樣，只是並非找兩個高手下一盤，而是找兩個不懂棋的小朋友下一千盤罷了。隨機下一千盤棋，對電腦來說花費幾何？以毫秒計吧！

這不就好辦了嗎！從現在起，每一個局面我都可以客觀地估計好壞了，同時我並不需要遍歷整個搜索樹（所以請不要再叫我窮舉法！）。真是這樣簡單嗎？我可不信。難道從第一手右上星位開始，隨機模擬一千盤棋，發現白勝501盤，就說明黑1是敗招嗎？很可惜，隨機抽樣得到的結果是一個統計上的期望，而並非實際上的「最優」。它需要遵從統計之神的規律。第一手黑1對應的局面有多少呢？天文數字。勝負是怎樣分布的呢？不知道。那麼一千盤，一萬盤棋，對於這樣的統計分析來講，只是個微不足道的樣本，很難得出有實際意義的結論。

沒關係，樣本不夠可以多下，反正是隨機棋不費電。具體下多少盤呢？當然越多越好，但咱們不妨算到讀秒的時限為止。像這樣在確定時間內完成的隨機演算法，就叫做蒙特卡洛。說起來，這個名詞來自摩納哥著名的賭場勝地蒙特卡洛，因為這樣的演算法往往被用來計算賭博勝率的問題。既然有蒙特卡洛，那有沒有拉斯維加斯呢？當然有，我們暫且不表。「國際象棋之神」深藍用過的搜索演算法，現在一樣能用：只要把局面評估換成蒙特卡洛就行了（用模擬對局的最終勝率而不是評分值，來評價當前局面的好壞）。這就是所謂的「蒙特卡洛樹搜索」。

這法子聽起來相當靠譜。那為什麼直到10年之後，蒙特卡洛才開始在江湖流傳呢？

這是因為蒙特卡洛也有明顯的缺陷。由於其隨機性，蒙特卡洛不能保證答案的正確，而只能保證在一定的概率下不犯錯。這個概率邊界由什麼決定呢？當然和隨機模擬的次數有關。

這就又回到了當初的難題：因為圍棋之樹實在太大，每個結點模擬次數多，時間不夠用；少，答案又不精確。這個矛盾耽誤了蒙特卡洛圍棋整整十年。

八，「多臂老虎機」的閃亮登場

「瘋石」提供了解決矛盾的一個好思路。說起來並不難：看上去不錯的分支，咱們就多模擬幾盤，讓它的評估更精確。看上去不怎麼樣的，咱們就少下幾盤。實在不怎麼靠譜的，這個分支咱們根本就不看。這樣雖然搜索空間巨大，實際搜索的樹則變得很小。

可是有人會問，這會不會導致瘋石在「一棵樹上弔死」呢？它如果守著一個看上去不錯的分支，一根筋地往下找呢？

這個問題的確存在，而且它在人工智慧領域相當有名，被稱為「探索與利用的矛盾」 (exploration vs. exploitation)。用地質學家（或者星際爭霸玩家）的話來說更有意思，大概是勘探和開發的平衡吧：過多地開發當前的油田，減少了勘探到更富的油田的機會，而過多的勘探則讓開發的效率變低。

這很讓人困擾。不過，這個問題有一個優美的解決方案。

既然身在蒙特卡洛，我們還是用賭場的方式解決賭場的事情吧！玩老虎機的賭客們往往有這樣的苦惱：老虎機有的吐幣容易、有的難。現在我玩的這個還算不錯。可一直玩下去吧，又總覺得隔壁的沒準會更出幣；換到隔壁去吧，又怕我一走，這兒就出個大的。

機器學習里，有一個演算法叫做「多臂老虎機」(multi-armed bandit)，解決的就是這個問題。它用一個叫做UCB的策略，精確地計算哪個老虎機應該多試，哪個應該少試，並告訴賭客下一把應該去試哪一個。當這個策略應用在蒙特卡洛樹上時，就成了「瘋石」賴以成名的UCT演算法（UCB applied to trees）。與局部焦點相關的分支多試，較遠的地方則少試，但並非不試。UCT推薦的分支，我們就優先往下搜索，用蒙特卡洛模擬更多的棋局。

蒙特卡洛和多臂老虎機，這兩大賭神，給電腦圍棋帶來一片欣欣向榮。電腦「瘋石」和「禪」交相輝映，近十年里不斷刷新著人們的期望，他們分先戰勝專業棋手似乎指日可待。

可是行百里者半九十，差的就是這臨門一腳。到了最近兩年，我們發現，它們的進步速度又變緩了，就連Zen的段位也升不上去了。

大家終於知道它們又遇到了瓶頸。這也難怪，即便是蒙特卡洛，也需要走到底；即便是多臂老虎機，也需要試很多枝。計算能力仍然是瓶頸，除非能更加有效地減小搜索的寬度與深度。

可是，連賭神都搬出來了，人工智慧的高手們似乎已無計可施。

可是人們忘記了，在數十年的漫漫黑夜裡，有顆種子一直在生長。這一天終於到了，它將頂開石頭，破繭而出。

「韋小寶，我一定會回來的。下次我再出現的時候，你一定不會認得我是誰。」

九，人類棋手的兩大獨門秘笈

漫漫黑夜終於過去了，我們不經意間就等到了AlphaGo。它的橫空出世如此讓人驚訝，以致於最初報道AlphaGo登上《Nature》的消息，在朋友圈裡被不少人疑為謠言。

在我們盼望著「瘋石」和「禪」能逐步逼近職業棋手棋力的時候，「阿爾發狗」一出手就咬暈了歐洲冠軍，還把戰書下到了另一個瘋狂的石頭李世石面前。它究竟有何秘密？

「瘋石」和「禪」遇到的瓶頸，我們不妨換一個思路來想。我們算是知道了電腦怎樣挑戰人，可人憑什麼可以和電腦對抗呢？再強的專業棋手，顯然也沒辦法每秒鐘算出幾千種變化，他們也不會蒙特卡洛或者Alpha-Beta剪枝，那他們憑藉什麼能在圍棋迷宮裡遊刃有餘呢？計算能力顯然是比不過的，但一定有什麼是人類比計算機強的。

其實，在搜索圍棋之樹的過程里，人類棋手的確有獨門秘笈。

人類的第一種魔法，是能夠顯著地降低搜索空間，在複雜開放的局面下不可思議地找到寥寥幾種可行的下法。這就是所謂的棋感，對於頂尖高手而言，甚至是「第一感」。假如計算機也學會這種能力，那豈不是可以把可貴的計算資源集中在探索這少數幾個分支上嗎？

人類的第二種魔法在於其強大的形勢判斷能力，不用精確推算也能判斷全盤局面的優劣。這就是所謂的「大局觀」。假如計算機也具有這種能力，那豈不是不需要搜索很深也能正確地評估局勢了嗎？棋感和大局觀難道是人類與生俱來的魔法嗎？當然不是。它們其實是千百年來人類棋手智慧的結晶；它們的根基是被一張張棋譜和一代代棋手流傳下來的圍棋知識與經驗。

這個想法非常讓人興奮：良好的棋感和大局觀，一個能減小搜索寬度，一個能減小搜索深度，這不正是蒙特卡洛夢寐以求的嗎！棋感和大局觀從哪裡來呢？小時候教我學棋的老師就一句話：多打高手的譜。想到這裡，人工智慧的研究者們釋然了：原來答案還在棋譜啊。我們收集了數以十萬計的人類棋譜，卻沒有好好利用它們，「惟能消敵內力，不能引而為我用，猶日取千金而復棄之於地，暴殄珍物，殊可哂也」。

歷史總是像車輪一樣滾動前進的。眾里尋他千百度，原來那人早在燈火闌珊處。是時候把沉睡了幾十年的「背棋譜」和「亂劈風」請回來了。只是這時候他們早已破繭成蝶，練就了武林秘笈，以全新的面目出現在我們面前。

這本秘笈叫做「深度學習」。

十，深度學習帶來的臨門一腳

「深度學習」是什麼？「卷積神經網路」又是什麼？聽上去好科幻的名詞，可我們不需要太深究。

你只要知道，深度學習是機器學習的一種，它是一台精密的流水線，整頭豬從這邊趕進去，香腸從那邊出來就可以了。豬是棋盤，香腸是一手棋，深度學習，可以用來預測當前局面可能的下一手。豬是棋盤，香腸有好有壞，那麼深度學習也可以用來判斷當前局面的優劣。

那麼這個流水線是如何搭建的呢？它可不是拍腦袋設計的，而是看過了數以百萬的豬和它們做出的香腸之後，計算出來的。豬我們可有的是。人類高手的棋譜大概走了三千萬步（三千萬頭豬），而電腦還可以自己養豬（自己模擬對局）。

那麼這位問了，為什麼是深度學習而不是其他的什麼學習呢？它和背棋譜究竟有什麼區別呢？

傳統的機器學習，需要先把豬按一定規則分解成各種「特徵」（顏色，重量，後腿有塊疤，等等），香腸的做法則由這些特徵共同決定。當只有少數幾個死規則的時候，就和背棋譜區別不大了（看到後腿有疤的豬，請下小飛）。

可是「道可道，非常道」，棋感這樣只可意會的東西，硬要把它寫成規則和特徵，既不達意也沒必要。你總不能逼著古力告訴你，他想到那招「峭壁鑿火」的妙手，是因為左邊有個彎三，右邊有個曲四吧！

深度學習則省略了這個步驟，整豬進，讓機器自動去尋找這些特徵和他們的組合。還記得手談的形勢估計辦法「相鄰加4、小尖加3」嗎？深度學習找到的，可不是這樣簡單的加加減減（線性組合）。在理論上，它可以模擬任何的非線性函數。

好，到現在我們大概明白AlphaGo的秘訣了。它的主體仍然是蒙特卡洛樹，但它巧妙地用了兩個深度學習模型，一個預測下一手，一個判斷形勢。預測的結果，降低了搜索寬度；而形勢判斷，則減小了搜索深度。深度學習從人類的經驗中學來了棋感與大局觀，它們使蒙特卡洛如虎添翼，一扇翅膀就飛到了李世石的面前。縱橫江湖15年的李石頭，在另一位「古哥」的面前低下了高傲的頭。

寫到這裡，「阿爾發狗」的前世今生就介紹得差不多了。我們要看到，這並不簡單的是人工智慧的勝利。

AlphaGo的成功，極大部分應該歸功於谷歌的工程師們。他們有效地把複雜的演算法並行化，嫻熟地在CPU和GPU間轉換，遊刃有餘地用「雲計算」解決著計算力的瓶頸。

我們也要看到，除了谷歌和AlphaGo，還有很多設計者、工程師，和計算機棋手在同時努力著。「瘋石」，「禪」，以及華人科學家主導的Facebook的「黑暗森林」，都在一起前行。

這是一場人類經驗和電腦演算法共同的狂歡，而歸根結底，這是一場屬於圍棋的盛宴。

十一，成也蒙特卡洛，敗也蒙特卡洛

寫就此文的時候，AlphaGo正和李世石下著第五盤棋。前三盤幾乎完勝的AlphaGo，令人驚訝地幾乎短路般地輸掉了第四盤。一時間眾說紛紜，謠言四起。當我們了解了AlphaGo的前世今生之後，或許能對一些問題有更好的理解。知道了它的武功秘笈，人類棋手也更能針鋒相對。

以下是一些我的思考，一家之言，貽笑方家。由於AlphaGo一直在暗處，Google的論文也信息有限，不少觀點是筆者自己的推測。相信隨著AlphaGo與更多棋手交戰，它會越來越透明，而它面對的挑戰也會越來越難。

AlphaGo會犯錯嗎？當然會。不僅序盤會，中盤會，官子也會。

因為蒙特卡洛會犯錯。蒙特卡洛只能保證在一定概率下得到正確的結果，而模擬的次數越多，犯錯的可能越小。

計算力永遠是瓶頸，如果讓電腦得以把計算資源集中在狹小的搜索空間，那麼它在這裡犯錯的可能極小。想想第一盤的上邊和第三盤的左邊，局部雖然複雜，但搜索的空間卻很小。狹小空間里的直線計算，人恐怕很難討好（參見AlphaGo在第一盤右邊的妙手一點）。因為演算法使然，計算機圍棋永遠希望縮小搜索空間，因此AlphaGo不愛保留後續變化、多俗手、總是簡化局面的特點，就不難理解了吧。

那人應該怎麼辦呢？說來簡單：反其道而行之。

盡量擴大搜索空間，迫使電腦搜索更多的分支，而且每個分支也搜索得更深。當有限的計算資源不得不分配到大量的局部時，出錯的可能就變大了。

當AlphaGo想斷其一指的時候，我們偏偏讓它十指均勻用力。

李世石第四盤第78著「挖」的一手，恰恰就是AlphaGo漏算的一手。深度學習和多臂老虎機可能並沒有推薦它，也可能推薦排名靠後，導致沒有深入計算；它也可能被剪掉了，不得而知。可是不管怎麼樣，那一手之前的局勢，牽一髮而動全身，全局可能的落點很多；那手棋又牽扯到潛在的劫和引征，讓形勢判斷變得複雜，導致了搜索深度的顯著增加。真是成也蒙特卡洛，敗也蒙特卡洛呀！

十二，打狗棒法就是打劫！

說得容易，但那一手挖分明是可遇不可求的一步，難道還能複製嗎？

其實也有更加易行的辦法，那就是這幾天被討論得底朝天的「打劫」（圍棋術語，即在一個關鍵處雙方來回提子）。具體情況圍棋高手和同行專家都已分析得很透徹了，簡而言之，打劫能同時增加搜索的寬度和深度。

因為劫材可能散布全盤各地，多數甚至和劫的本身無關，這使得深度學習也無法準確預測如何找劫，迫使計算機做全局的搜索。

劫與劫材的不確定性，又導致局面好壞很難判斷，讓AlphaGo無法有效地減小搜索深度。

這裡有兩個有趣的地方：其一是AlphaGo不可能不會打劫，因為同樣使用蒙特卡洛的「瘋石」和「禪」都會，只是它打劫的能力未必比別的計算機棋手強。正因為如此，我們可以看到幾盤棋AlphaGo都有明顯規避打劫的傾向。試想如果柯潔對上一個棋力為不打劫13段、打劫業餘5段的對手，恐怕也有辦法對付吧。

其二是打劫可以引而不發，打而不消，最好在不同的地方多造幾個劫來打。你問為什麼？消劫太快不就又降低搜索難度了嗎？

那麼AlphaGo在漏算之後，為何表現得如同「失魂落魄」呢？這當然很有可能是谷歌的演算法在處理「漏算」的時候出現了瑕疵。但即便不是這樣，通過演算法也不難解釋。

我們知道，就算深度學習可以幫助電腦評估局面，但每一個變化都評估，再好的計算能力也吃不消。就算是工作簡單得多的「國際象棋之神」深藍，也是每向深處考慮多步才評估一次局面的。如哈薩比斯自己說，到79手的時候AlphaGo還認為自己的勝率很高，又走10手之後才發現形勢已非。那時已無後悔葯可吃，手忙腳亂也不難理解了。

至於AlphaGo為什麼無厘頭地在右邊二路立下呢？我的理解是這樣的。還記得前文提到的minmax演算法嗎？計算機會優先選擇不管對方怎麼應，我都不會太差的招。那一手立，不管對方如何應，恐怕都不會讓當前的形勢變得更差吧！這樣的策略應該也可以解釋，為什麼AlphaGo總有局面領先了就等等你的感覺。這倒是為人類棋手提供了一個思路：因為minmax演算法，AlphaGo不太會走冒險和過分的棋，那麼它在逆境下如何翻盤真是一個有趣的問題。至於左下那個虧到姥姥家的「挖」，筆者就真的不懂了。

十三，狗不是圍棋之神，人工智慧還很青澀

AlphaGo在自己左右互搏中練棋，真的能武功大進嗎？這又是一個有趣的問題。

我覺得，自我對弈會有效果，但不可能不斷提高棋力。

在《自然》那篇論文里可以看到，自我對弈主要是為了解決從人類棋譜中深度學習帶來的過擬合的問題。從機器學習的角度看，它並不能不斷提升武功。南大的周志華教授把自我對弈比作武當的梯雲縱，非常妙！在空中左腳踩右腳，真能不斷往上飛嗎？沒有外物借力，這顯然是不符合物理規律的。物理沒有永動機，人工智慧也沒有。

兩個AlphaGo同鑽一個牛角尖，對的更對，錯的更錯。

比起把有限的計算資源用來自我對弈，我更擔心谷歌把它用在創造拉斯維加斯搜索樹上，那可是一個真正不犯錯誤的傢伙。

那AlphaGo究竟有沒有可能，不藉助與人類的對局來提升棋力呢？當然有，但那需要兩個棋力極高，而且武功路數迥然不同的AlphaGo。

下過棋的人都知道，和高手下受益無窮，和低手下也許偶有收穫，而和自己下嘛，只能叫做擺棋吧。我們很期待看見AlphaGo和黑暗森林的十番棋或是史無前例的百番棋。

AlphaGo帶給人們無窮的興奮，也帶來了前所未有的浮躁與恐慌：

人工智慧會搶走我的工作嗎？

機器會統治人嗎？

人類是否自掘墳墓呢？

其實，人工智慧遠遠沒有到值得恐慌的地步。

它會搶走我們的工作嗎？蒸汽機到來的時候人們恐慌過，PC到來的時候人們也恐慌過。但它們並沒有「搶走」人類的工作，而只是把我們從不擅長的工作中解放出來，提高了效率，去做更擅長、更重要的事情。

想想會聊天的微軟小冰，掃地的機器人，和無人駕駛的汽車。它們是我們的朋友而不是掘墓人。

它無所不能了嗎？不是的，人工智慧還很年輕，還有很長的路要走。君不見從深藍到AlphaGo整整20年，時間長得讓人們幾乎忘記了它。

它會統治人類嗎？在我能預見的將來，應該不會。要這麼做，它首先得擁有創造力，可是作為一個人工智慧的擁躉，我能看到的，還是漫漫長夜。

鑰匙永遠掌握在人類的手裡。即使人工智慧有了統治人類的能力，那一天來臨的時候，我們至少還可以切斷電源，不是嗎：）

（全文完）

關於

原文發表于于四川在線，之後經梅老師修訂後，授權科學松鼠會刊發。

相關文章
推薦閱讀：