阿爾發狗為啥連勝三局卻第四局崩潰？計算機專家從身世揭秘密！

圍棋人機大戰激斗正酣，人工智慧「阿爾法狗」前三局吊打世界冠軍李世石，卻又在第四局走出超級爛招，引發世人猜測「電腦也會故意輸棋」時，我們約請在美國大學任教的計算機專家，撰寫系列評論，從阿爾發狗的前世今生揭開它表現反常的秘密！敬請關注。

↓↓↓

文/梅俏竹（美國密歇根大學信息學院和計算機系副教授，長年從事大數據分析研究）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

或許有人說，圍棋之神也不一定每手都算到底吧，往後推算個三五十步差不多了。好，序盤的時候（按60手以內）推算50步大概有超過10^120種變化。10步？10^24。就算只推5步也有超過2*10^12種變化。何況對計算機來說有更嚴肅的問題：不走到底怎麼知道誰好誰壞？

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

好了，現在我們知道圍棋之神和宇宙之神大概是同一位。「她」既然能洞悉棋盤上所有的變化，大概也熟悉宇宙中所有的原子。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^24種變化，用上alpha-beta的剪枝和IBM強大的並行運算能力，完全可以處理！

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

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

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

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

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

「蒙特卡洛樹」示意圖。

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

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

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

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

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

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

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

沒關係，樣本不夠可以多下，反正是隨機棋不費電。看上去不錯的招，咱們就多下十萬盤，看上去不怎麼樣的，咱們就少下幾盤甚至把這一枝減掉。深藍用過的搜索演算法，咱們一樣能用，只要把估值函數換了就好。

————————————————————

奇異的蒙特卡洛樹，再加上「國象之神」的動態評估、剪枝等辦法，計算機圍棋是不是找到了通向圍棋之神的正確道路了？請繼續關注川報觀察客戶端的系列報道，專家將揭秘最強大的阿爾發狗的武功秘籍，以及它突然崩潰的根本原因！

編輯：曾東平

推薦閱讀：