阿爾發狗為啥連勝三局卻第四局崩潰?計算機專家從身世揭秘密!
圍棋人機大戰激斗正酣,人工智慧「阿爾法狗」前三局吊打世界冠軍李世石,卻又在第四局走出超級爛招,引發世人猜測「電腦也會故意輸棋」時,我們約請在美國大學任教的計算機專家,撰寫系列評論,從阿爾發狗的前世今生揭開它表現反常的秘密!敬請關注。
↓↓↓
文/梅俏竹(美國密歇根大學信息學院和計算機系副教授,長年從事大數據分析研究)
一,「阿爾發狗」為什麼盯上圍棋,而不是麻將?
傳說堯作圍棋以教丹朱,如此算來圍棋就有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對應的局面有多少呢?天文數字。勝負是怎樣分布的呢?不知道。那麼一千盤,一萬盤棋,對於這樣的統計分析來講,只是個微不足道的樣本,很難得出有實際意義的結論。
沒關係,樣本不夠可以多下,反正是隨機棋不費電。看上去不錯的招,咱們就多下十萬盤,看上去不怎麼樣的,咱們就少下幾盤甚至把這一枝減掉。深藍用過的搜索演算法,咱們一樣能用,只要把估值函數換了就好。
————————————————————
奇異的蒙特卡洛樹,再加上「國象之神」的動態評估、剪枝等辦法,計算機圍棋是不是找到了通向圍棋之神的正確道路了?請繼續關注川報觀察客戶端的系列報道,專家將揭秘最強大的阿爾發狗的武功秘籍,以及它突然崩潰的根本原因!
編輯:曾東平
推薦閱讀:
※windows7設置印表機共享
※超凡傳更新到什麼章節了?
※2018年UI設計的流行趨勢是什麼?
※從模擬電路到計算機軟體
※《大話計算機》助推國產半導體浴火重生!