南方周末: 機器下棋的歷史

　　肯佩倫製造的、號稱能自動下棋的「土耳其人」，其實是個騙局。（南方周末資料圖）　　機器下棋史前史　　1769年，德國發明家兼外交家沃爾夫岡·肯佩倫（Wolfgang von Kempelen）男爵準備造一台機械的下棋裝置，一年後機器完工，取名「土耳其人」（The Turk），那時大家就把這玩意叫作「自動機」（automaton）。肯佩倫把這台機器展示給奧匈帝國的掌權者瑪麗婭·特蕾西婭（奧國女大公、匈國女王），於是它就成為娛樂歐洲各皇室的保留節目。稱為「土耳其人」是因為這個裝置的後面坐著一個土耳其裝束的木頭人。1804年，男爵死後，「土耳其人」被轉賣給德國發明家約翰·馬澤爾（Johann Nepomuk Maelzel），1809年馬澤爾把它展示給拿破崙，並和這位不可一世的歐洲征服者對弈一局。拿破崙執白棋先手，但最後「土耳其人」大勝，拿破崙惱羞成怒，把棋盤上的棋子全胡擼到地上。有好事者把拿破崙和「土耳其人」的對戰棋譜記錄在案，確實藝不如「機」。陸續和「土耳其人」接觸過的名人還有本傑明·富蘭克林、愛倫·坡、數學家查爾斯·巴貝奇。　　「土耳其人」在歐洲巡演了幾十年，最後被人發現是個徹頭徹尾的假貨：那個裝置里總是有個活人，而且是個下棋高手。肯佩倫只是發明了個魔術而已。那時的水平，想造台會下棋的機器，門兒都沒有。1827年，「土耳其人」到美國巡演時，請了美國當時的頂級高手施倫伯傑（Schlumberger）藏匿其中。在巴爾的摩的一次表演中，兩個孩子發現施倫伯傑頻繁出入後台，把這個秘密透露給了報界。見過這台機器的高人如富蘭克林和巴貝奇一開始就猜這是魔術而不是科技。但當時還是很多人願意相信「土耳其人」真會下棋。　　和牛頓、霍金一樣，巴貝奇還做過一屆劍橋的盧卡斯教授，他對所有機器裝置都感興趣，他在看到「土耳其人」時，正在研製第一台機械計算機「分析機」（analytical engine）。他認為他的分析機也可以下棋，但那至多是猜測。　　下棋一直就是人類智能的挑戰，自然也成了人工智慧的標誌之一。二戰沒結束，圖靈就研究計算機下棋，他1947年編了第一個下棋程序，可惜那時計算機的時間（簡稱「機時」）很寶貴，輪不到他上機，地主家也沒餘糧——圖靈也不能保證機時。但即使後來拿到機時，那機器和程序的水平也很有限。唐米歇（Donald Michie）是圖靈的追隨者，1950年試著在紙上模擬程序，和圖靈對弈，但這實在不是辦法。圖靈在曼徹斯特大學的同事迪特里希·普林茨（Dietrich Prinz）接著圖靈的思路，在1951年寫了一個殘局程序，能在離將死還有兩步的情況下，找到最優解。這個問題也被稱為「兩步將死」（mate-in-two）問題。　　跳棋插曲　　1951年，圖靈的朋友克里斯托弗·斯特拉切（Christopher Strachey）在曼徹斯特Mark-1上寫了第一款跳棋程序。圖靈在1952年曾與之對弈一局，輕鬆取勝。1956年IBM的亞瑟·撒米爾（Arthur Samuel）寫了第二個跳棋程序，這款程序的特點是自學習，這也是最早的機器學習程序之一，後來不斷改進，曾經贏過盲人跳棋大師。　　1980年代末，最強的跳棋程序一直就是加拿大阿爾伯塔大學的Chinook，作者是現任阿爾伯塔大學理學院院長的計算機系教授強納森·舍佛（Jonathan Schaeffer）。數學家丁斯利（Marion Tinsley）自1950年代起就一直是跳棋的人類冠軍。丁斯利對跳棋理論研究很深，對舍佛團隊也很支持，但美國、英國和加拿大的跳棋協會一直拒絕Chinook參賽。為了和Chinook比賽，丁斯利放棄他的冠軍稱號。1992年丁斯利大戰Chinook並取勝，1994年再戰，但在比賽中，丁斯利不幸確診為胰腺癌，不久病逝。丁斯利的公開紀錄，除了輸給Chinook幾局棋外，從沒有輸給過任何人類棋手。此後Chinook獨孤求敗。　　舍佛團隊繼續精研跳棋理論和實踐，直到2007年，他們證明對於跳棋，只要對弈雙方不犯錯，最終都是和棋，而Chinook已經可以不犯錯。他們的結果發表在2007年9月的《科學》雜誌上，自此跳棋這一頁就算翻過去了。舍佛的興趣遂轉向德州撲克和圍棋。　　計算機下棋之初　　幾乎和圖靈同時，馮諾依曼也在研究計算機下棋，他和經濟學家摩根斯頓合作的《博弈論》1944年出版，其中首先提出兩人對弈的minimax演算法。香農（Claude Shannon）1950年在《哲學雜誌》發表「計算機下棋程序」（Programming a Computer for Playing Chess）一文，開啟了計算機下棋的理論研究。其中主要思路在「深藍」和AlphaGo中還能看到。有趣的是戰時圖靈在布萊徹里莊園破解德國密碼，香農則在貝爾實驗室研究密碼理論，其中還用到了他後來發明的資訊理論。圖靈的工作直到1974年才部分解密，香農則偏理論。圖靈戰時到訪美國普林斯頓大學和貝爾實驗室，曾和香農多次會晤，但他們從來沒聊過密碼學，儘管香農猜到了圖靈在幹啥。1950年香農去英國參加資訊理論會議時到曼徹斯特大學圖靈的辦公室回訪，他們這次只聊了下棋和大腦，仍然沒聊密碼。圖靈沒有參加這次在倫敦的會議，但貢獻了兩篇短文，一篇講機器學習，另一篇講下棋。直到圖靈的工作解密，香農才知道圖靈在戰時已經用到了「熵」，但是不是從了解資訊理論的美國同事處學來的就無從考證了。信息安全專家史密斯（S.W.Smith)曾寫過一篇題為「圖靈來自火星，香農來自金星」的文章，很明顯這是受那本《男人來自火星，女人來自金星》的啟發。　　香農把棋盤定義為二維數組，每個棋子都有一個對應的子程序計算棋子所有可能的走法，最後有個評估函數（evaluation function）。傳統的棋局都把下棋過程分為三個階段，開局、中局和殘局，不同階段需要不同的技術手段。香農的論文引用了馮諾依曼的《博弈論》和維納的《控制論》。　　minimax演算法中，二人對弈的一方為max，另一方為min，max的一方的評估函數要越高越好，min的一方則越低越好。max和min的對弈就形成了博弈樹。樹的增長是指數式的，當樹很深時，樹的規模會變得不可控。達特茅斯會議的組織者之一麥卡錫首先提出α-β剪枝術以控制樹的增長。紐厄爾、司馬賀和肖（NSS，Newell, Simon and Shaw）在他們著名的定理證明程序之後，又做了下棋程序。他們首先實現了α-β剪枝術。他們的程序是在一台Johnniac上實現的。原始的minimax演算法是在博弈樹被全部畫出後再靜態地計算評估函數，而α-β剪枝術則採取邊畫樹邊計算評估函數的動態方法。當評估函數的值超越給定的上界和下界時，樹的搜索過程就停止，這樣大大減少了樹的規模。平均而言，同樣資源限制下，α-β剪枝術要比原始minimax演算法搜索的樹深度多一倍，也就是說，可以比minimax向前看的步數多一倍。　　第一個可以走完全局的下棋程序是IBM的工程師阿列克斯·伯恩斯坦1958年在一台IBM 704上做的。估計那時IBM支持下棋就像後來支持深藍和谷歌支持AlphaGo一樣，雖沒什麼短期實用價值，但是很好的公關。機器每步要花8分鐘想，隨便會走幾步棋的人就能擊敗這個程序。　　1959年，麻省理工（MIT）的幾位本科生在當時剛到MIT任教的麥卡錫指導下開始學習計算機下棋，當他們1962年本科畢業時，他們用FORTRAN實現了一款實戰下棋程序，跑在IBM新出的 7090大型機上，此時已經可以擊敗一般的象棋初學者了。這個結果變成了其中一位學生Kotok的本科學位論文。1962年麥卡錫前往斯坦福任教，他持續改進，這個程序後來被稱為Kotok-McCarthy程序。　　1966年這個不安寧的年份，美蘇的對抗也擴展到計算機下棋。蘇聯科學院的理論與實驗物理研究所（ITEP)也在本所研製的一台M20計算機上開發了一款下棋程序，他們要和斯坦福大學的Kotok-McCarthy程序一決高下。1966年11月22日開始，直到1967年3月10日止，他們通過電報的方式走了四局。最後蘇聯3∶1戰勝美國。　　當時MIT的程序員格林布拉特（Richard Greenblatt)也在改進Kotok的程序，格林布拉特本人還是成績不錯的棋手。他在PDP-6上實現了程序MacHack VI。1966年，一直批評人工智慧的哲學家德雷福斯也和MacHack對弈過一局，並且輸給MacHack，這倒沒有改變德雷福斯對待人工智慧的態度。1967年MacHack參加象棋錦標賽，並累計積分1400，這相當於不錯的高中生水平。這個程序用了16K內存，後來PDP的廠家DEC把它預裝到所有PDP系列的機器中。MacHack也是Internet前身ARPAnet上最早的網上遊戲。當時給格林布拉特幫忙的志願者中有個人叫克柔可（Stephen Crocker），他後來成為Internet前身ARPAnet的重要人物，並創辦了互聯網標準化組織IETF且寫了第一個標準化文本RFC。　　司馬賀在1957年預言十年內計算機下棋程序可以擊敗人類，明顯未果，於是他在1965年再度預言這個目標可以在20年內實現。1968年國際象棋大師列維（Levy）和麥卡錫打賭十年內機器不可能贏列維。1978年最厲害的計算機程序CHESS和列維比了一盤，自然是列維贏，麥卡錫為此輸了500英鎊。CHESS在七十年代末八十年代初一直是計算機下棋的冠軍。此時尚看不到計算機短期內可以贏人的可能性。　　1971年，當年擊敗Kotok-McCarthy的蘇聯小組改進了他們的程序，新程序名叫KAISSA（象棋女神）。KAISSA和傳奇大師鮑里斯·斯帕斯基（Boris Spassky）賽了兩局，一負一和，這個戰績驚動了棋界。1972年KAISSA接受了《共青團真理報》的挑戰：KAISSA將和讀者們下兩盤，《共青團真理報》從讀者寄來的各種走法中挑出推薦最多的。這其實就是「眾包」概念的雛形。最終，KAISSA還是一負一和。但1972年鮑里斯·斯帕斯基卻又輸給美國怪人鮑比·菲舍爾（Bobby Fischer），這是美國第一次在國際象棋領域戰勝蘇聯，尼克松稍晚在會見勃列日涅夫時送了對手一副袖珍國際象棋，成心噁心人家。　　1970年開始，美國計算機學會（ACM）每年的年會都在晚餐時舉行計算機象棋比賽，作為娛樂節目。CHESS連著四年都是冠軍。第二屆時，紐厄爾的學生漢斯·柏林納（Berliner）參加了，取得第二名，這鼓舞了紐厄爾，他決定把柏林納留校，專職在卡內基梅隆研究計算機做計算機象棋。柏林納本人也是國際象棋高手，曾贏得美國通訊賽冠軍，他留校後，並沒有走教學制（tenure track），而是走了研究口——卡內基梅隆的研究制教員也分三級，研究員（Research Scientist）對應助理教授，高級研究員（Senior Research Scientist）對應副教授，而首席研究員（Principal Research Scientist）對應正教授。後面幾年的比賽，都有紐厄爾的學生參加，成績不錯。　　1974年，在瑞典斯德哥爾摩召開的「國際信息聯合會大會」（IFIP）為了找點樂子，效仿美國計算機學會年會的做法，舉行了第一屆世界計算機象棋錦標賽。錦標賽的組織者是剛從哥倫比亞大學轉往加拿大麥吉爾大學的牛伯恩（Monty Newborn）。除了計算機下棋，牛伯恩的另一興趣是機器定理證明，他寫過兩款定理證明程序，參加各種定理證明比賽，儘管他的下棋程序和定理證明程序在比賽中並沒有出色表現，但他寫的下棋和定理證明的書卻很有意思。第一次錦標賽，除了美國和加拿大的幾位高手外，還邀請了歐洲的幾個團隊，當然要包括蘇聯神秘的KAISSA。KAISSA擊敗了在ACM年會拿了四次冠軍的CHESS，贏得頭籌，報了兩年前斯帕斯基輸給菲舍爾的一箭之仇。勃列日涅夫倒是沒把當年那副袖珍棋送還給已經下台的尼克松，不知算是小氣還是大度。　　進入1980年代，又出了新一茬象棋程序。當時最厲害的兩個電腦棋手，一個是跑在超級計算機克雷上的Blitz，另一個則是貝爾實驗室的專用機器Belle。Belle的發明人之一湯普森（Ken Thompson）那可是了不起的人物，在計算機界無人不曉。他最傑出的成績是發明了UNIX操作系統（現在蘋果操作系統，波音747的飛行系統和安卓手機操作系統也都是Unix的變種）和C語言，1999年被柯林頓授予「國家技術獎章」。他在計算機下棋上的貢獻多少被略視了。在1982年的北美計算機象棋錦標賽上，Belle擊敗了Blitz。Belle是第一個取得「大師」稱號的計算機棋手。1982年在去蘇聯比賽的路上，Belle被美國政府在肯尼迪機場海關沒收，理由是企圖向敵對國家輸送先進武器，Belle的終端里確實有當時對蘇聯禁運的超大規模集成電路。拖了小一年功夫，最後湯普森等破費了600大洋罰款，才贖回Belle，但比賽耽誤了。　　進入八十年代，機器之間的比賽此起彼伏，但機器和人之間仍然有著不可逾越的鴻溝。1980年，天才愛德華·弗里德金專為計算機下棋建立了弗里德金獎金，獎有三等，頭等獎是10萬美金，獎給第一款能贏現任世界冠軍的下棋機器。

　　《「深藍」揭秘：追尋人工智慧聖杯之旅》,許峰雄著，上海科技教育出版社，2005。（南方周末資料圖/圖）　　「深藍」　　1980年代中期，卡內基梅隆大學的柏林納開始用專用硬體來做下棋機，他的成果HiTech馬上成為最強的機器棋手。這時來自台灣的許峰雄到卡內基梅隆計算機系跟隨孔祥重讀計算機體系結構（就是我們常說的「硬體」）方向的博士，孔祥重是孔子後裔。許峰雄的室友很快把他拉到HiTech項目，幫忙設計一個硬體的評估函數，但許峰雄卻和柏林納關係不睦。在資金有限的情況下，許峰雄和幾個研究生利用業餘時間快速開發出了ChipTest，而ChipTest立即變成HiTech的競爭對手，並受到柏林納的打壓。許峰雄在計算機系也變成眾矢之的，每次都是靠導師孔祥重的幫忙化險為夷。ChipTest的改進版「深思」（Deep Thought）1989年贏得弗里德金二等獎：成為第一個國際象棋特級大師的機器棋手，累計得分超過2400。隨後HiTech也加入這個行列。此時IBM意識到「深思」的商業價值，勸說整個團隊在畢業後加入IBM，開發下棋機，把對手鎖定為當時的世界冠軍俄國的特級大師卡斯帕羅夫。卡斯帕羅夫對機器下棋非常熟悉，他在屢次和機器對決後曾說：機器下棋沒有洞見（insight）。　　IBM的外號叫Big Blue，於是新的項目1996年又被命名為「深藍」（Deep Blue）。1996年ACM年會的閉幕節目是「深藍」對決卡斯帕羅夫，六局棋。「深藍」旗開得勝，第一局就贏了老卡，最後還是老卡4∶2贏得決賽。但此時老卡對「深藍」刮目相看，他說機器對手不光有洞見，而且有幾步簡直像「上帝下的」。　　第二年「深藍」和老卡再戰，老卡號稱要捍衛人類的智力尊嚴。他贏了第一局，但隨後則越來越保守，徹底輸給「深藍」。老卡下棋時非常情緒化，這有時會給人類對手施加壓力，但「深藍」壓根不鳥這套。1997年5月11日，老卡認輸，「深藍」成了第一位戰勝當時世界冠軍的機器。事後，卡斯帕羅夫回憶：第二局是關鍵，機器表現超出他的想像，它經常放棄短期利益，表現出非常擬人的危險（「showing a very human sense of danger」）。　　在「深藍」贏了卡斯帕羅夫之後，職業棋手們並沒有因此而改行，他們倒反而更多地依賴計算機來訓練。而職業比賽的解說者也越來越多地藉助計算機程序來分析解說一場比賽。機器作為教練，倒反而更快地幫助人類棋手進步。有美國高中的象棋教練觀察到從來就沒有過這麼多年輕棋手在年齡很小時就積分這麼高，這都是得益於計算機教練，因為過去的孩子從來就沒有機會和特級高手比賽。　　瑞典青年棋手卡爾森（Magnus Carlsen）就是如此。內行說卡爾森的下法很像計算機。2013年卡爾森在印度的金奈（Chennai）客場擊敗印度老將、衛冕冠軍阿南德。現在兩台個人電腦下棋，人已經看不懂它們在下什麼。儘管如此，「深藍」隊員，同樣畢業於卡內基梅隆的坎普爾（Murray Campbell）仍然不認為機器有智能。　　圍棋和AlphaGo　　相對於計算機在國際象棋中的勝利，中國象棋的進展一直落後。一些外行的民族主義者認為中國象棋要比國際象棋難，其實非也。「深藍」勝利之後，聰明人認為計算機下棋這事已經到頭了，沒人願意費力不討好，IBM也解散了「深藍」團隊。遲至十年後的2006年，中國象棋程序開始擊敗特級大師級別的人類棋手。倒是圍棋確實更具挑戰性，但圍棋在西方沒什麼受眾，自然沒什麼聰明人願意花時間。　　圍棋的棋子多，組合可能性也多，畫出博弈樹的所有可能枝葉後，在上面跑α-β不太經濟。於是聰明人想到了蒙特卡羅方法。蒙特卡羅方法最常用的教學例子就是計算圓的面積：在一個正方形里貼邊畫一個圓，然後隨機向這個正方形里扔沙粒，扔到足夠多時，開始數有多少沙粒落在圓里，結果除以所扔沙粒總數再乘以正方形面積，就是圓的面積。　　思路和求圓的面積類似，隨機模擬對弈雙方走棋。當走棋的次數很多時，就可算出下棋點的概率，然後挑概率最大的地方落子。谷歌的AlphaGo首次引用了強化學習（Reinforcement Learning），使得機器和自己對弈學習。強化學習的發明者是巴托（Andy Barto）和他的學生薩頓（Richard Sutton）。說來話長，馮諾依曼在普林斯頓設計計算機的主要助手是伯克思（Arthur Bucks），伯克思培養了第一個計算機博士霍蘭德（John Holland）。霍蘭德發明了遺傳演算法。伯克思的另一個更有名的學生是Codd（因發明關係資料庫而獲圖靈獎）。霍蘭德的大弟子就是巴托，巴托被神人阿比卜（Michael Arbib）招到麻省大學計算機系，在那裡培養了自己的第一個博士生薩頓，在經歷了人工智慧的此起彼伏後，薩頓現在阿爾伯特大學任教。正是他和已經轉向圍棋研究的舍佛的碰撞，萌生了把強化學習應用到圍棋的想法。在神經網路的低潮期，巴托和薩頓利用他們所在的麻省大學計算機系和GTE實驗室資助了一幫同仁，其中就有後來成大氣的麥克·喬丹。　　強化學習1980年代就被發明，但一直不被重視，是AlphaGo使得它發出亮光。薩頓還值壯年，AlphaGo團隊里就有四個薩頓的學生，其中包括帶頭大哥David Silver。巴托老兵不死，在做了一屆計算機系主任後，幾年前從麻省大學退休了。退休前，他終於看到強化學習漸成顯學，他和薩頓合著的《強化學習》馬上要出第二版了。　　網路編輯: 劉小珊 責任編輯: 劉小磊
推薦閱讀：