國際象棋譯文苑》文摘
 
電腦國際象棋簡史
 
Frederic Friedel/
 
第一臺會下棋的機器
 
  在1769年,匈牙利工程師巴朗·沃爾夫岡·凡·坎比林(Baron Wolfgang von Kempelen)為奧地利皇后做了一臺會下國際象棋的機器來消遣。這是一個外形呆板的機械裝置,不過它的出色棋力來自有一名象棋高手巧妙地藏在機器里的。所以這臺會下棋的“機器”是個冒牌貨。(如圖)
 
 
圖靈的“紙上機器”
  第一個棋弈程序寫于電腦被真正發明之前,這是一個非常有趣的事實。它是由一名想象力豐富的人所編寫的,他知道可編程電腦即將出現,一旦發明出來,就有下棋的能力。這位先生就是阿倫·圖靈(Alan Turing),有史以來最偉大的數學家之一。圖靈的偉大成就是領導專家小組破譯了納粹德國的“謎”密碼,因此對第二次世界大戰的決定性結束作出了貢獻。他對國際象棋非常感興趣,不過他盡管智力超群并且下了很大工夫在學棋上,他還是一個蹩腳的棋手。戰爭結束不久,他就寫下了能夠讓機器下棋的指令。由于當時還沒有一臺機器能夠執行這些指令,于是他就自己執行,充當一個“人類CPU”,每走一步需要半個多小時【譯注:所謂“自己執行”,即圖靈根據他所寫的算法去運算,嚴格根據運算得出的結果去走棋】。這里有一局棋,圖靈的“紙上機器”輸給了同事:
圖靈的“紙上機器”——Alick Glennie
曼徹斯特 1952
 
1.e4 e5 2.Nc3 Nf6 3.d4 Bb4 4.Nf3 d6 5.Bd2 Nc6 6.d5 Nd4 7.h4 Bg4 8.a4 Nxf3+ 9.gxf3 Bh5 10.Bb5+ c6 11.dxc6 0-0 12.cxb7 Rb8 13.Ba6 Qa5 14.Qe2 Nd7 15.Rg1 Nc5 16.Rg5 Bg6 17.Bb5 Nxb7 18.0-0-0 Nc5 19.Bc6 Rfc8 20.Bd5 Bxc3 21.Bxc3 Qxa4 22.Kd2? [22.h5 本可得象] 22...Ne6 23.Rg4 Nd4? [23...Rxb2! 24.Bxb2 Rxc2+] 24.Qd3 Nb5 25.Bb3 Qa6 26.Bc4 Bh5 27.Rg3 Qa4 28.Bxb5 Qxb5 29.Qxd6 Rd8 0-1.
 
申朗的策略
 
  貝爾實驗室的克勞迪·申朗(Claude Shannon)是和圖靈同時代的另一位偉大的數學家,他一直在探索教電腦下棋。他認識到問題在于棋步數量大得可怕,因此把搜索所有棋步的“A策略”和剔除某些變化路線的“B策略”區分開來。如今我們也區分“強行搜索”和“選擇搜索”程序,盡管所有強大的程序或多或少屬于前者。
 
國際象棋代替核彈
 
  戰爭期間美國在新墨西哥州的阿拉莫斯建立了一個巨大的實驗室,它的主要目的就是發展核武器。要正確執行觸發鏈式反應的內部爆炸需要數量巨大的計算。
  1946年美籍匈牙利數學家約翰·凡·諾依曼(John von Neumann)被指派設計一臺強大的計算機器以加快工作進度的任務。到了1950年,一臺叫“MANIAC一號”的巨型機被交付使用(圖左),它內裝有數千個電子管和開關,每秒能執行10,000條指令。它也可以編程。科學家并不馬上用它來設計核彈,而是先試驗一下這臺機器,而首先做的事情之一就是編寫一個下棋的程序。這是一個縮小的6x6棋盤,沒有象。雖然這么簡化了但程序要搜索四層的深度就需要12分鐘【譯注:四層相當于當前局面雙方各兩步】,如果加上象,就需要3個小時。
  50年代中期,這臺機器下了三局棋。第一局是自己對自己,白勝。第二局是對一位讓王后的強棋手,這局棋進行了10個小時,結果人類大師勝。第三局機器的對手是一位剛學棋一個星期的的年輕姑娘,結果程序23回合得勝。這是在智力博弈中人類首次負于電腦。
 
國際象棋和數學
 
  程序下棋遇到的主要難題是所包含的棋步數量實在太多太多了。平均每個局面大約有40步符合規則的著法。如果你對每步著法都考慮應著就會遇到40 x 40 = 1600個局面。這意味著兩層(ply,一層為半步棋)之后,單一步棋就會出現1600個不同的局面,而兩步之后是250萬個,三步之后是41億個。平均一局棋大約走40步,于是所有可能局面就有10128次方個,這個數字遠遠多于已知宇宙世界的原子總數目(大約1080次方)
  很顯然沒有一臺電腦或其它機器可以搜索全部可能的著法來下棋,但人類也不行呀?唯一的問題是機器要達到人類的策略水平,需要搜索多深的深度。早期的電腦可以每秒產生和評價大約500個局面,或者在比賽中三分鐘內對每步計算90,000個可能。意思就是它們僅能搜索三層的深度(即一步半),這是很低的水平了,相當于新手。要搜索多一層需要每秒計算大約15,000個局面,也就是要快30倍。但即使能搜索四層也很淺薄,因此似乎電腦不可能達到大師級水平?
 
Alpha-beta算法
 
  第一個突破出現在1958年,匹茲堡大學的三位科學家奈維爾、肖恩和西蒙(Newell, Shaw and Simon)有重大發現:可以從搜索樹中剔除相當大的部分而不影響最后結果,他們把這叫Alpha-beta算法。很重要指出的是,這是一個純數學領域的技巧,獨立于任何國際象棋知識而生效。
 
Alpha-Beta算法示意圖1
 
  我們很粗略地描述一下Alpha-beta算法:比方說電腦已經完成評價一步棋,開始計算第二步棋。一旦單個變化顯示返回的值低于第一步棋的值,就可以立即中止這個搜索。我們不需要精確知道第二步棋究竟有多差,程序會明確選擇第一步棋。
 
Alpha-Beta算法示意圖2
 
  除非另有需要,當只搜索數目的平方根那么多局面時,Alpha-beta算法產生的結果和完全搜索是一樣的。早期的電腦突然間也能向前看五至六層了,到了70年代最快的電腦可以搜索七層,棋力令人矚目了。但即使使用Alpha-beta算法,要搜索深一層還是需要提高5倍速度。數目的指數爆發性增長再次趕上程序設計者。
 
硬件尤物
 
  電腦科學家肯·湯普森(Ken Thompson,下圖左)覺得不能等待快5-25倍的百萬美元級超級電腦來用于提高下棋能力。他和貝爾實驗室的同事一起決定建造一臺專門用途的機器,使用了價值大約20,000美元的幾百個芯片。他們把這臺機器叫做“尤物”(belle,下圖右),它只會下國際象棋。它能夠每秒搜索大約18萬個局面(而當時的超級電腦只能搜索5000)。“尤物”在比賽中可以搜索八至九層那么深,因此可以和大師同場競技。從1980年到1983年它贏得了世界電腦國際象棋和所有其它電腦競賽冠軍,直到被價錢貴上千倍的克雷X-MPs巨型機(Cray X-MPs)取代為止。
下棋的芯片
 
  80年代中期,電腦科學家、卡梅隆大學的漢斯·貝利納(Hans Berliner,下圖左)教授接手肯·湯普森放下的工作。貝利納曾經是世界國際象棋通訊賽冠軍,他制造了一臺硬件型的機器叫“高技術”(HiTech),他和他的研究生一起研究可拔插芯片。裝有64個并行芯片的“高技術”差點贏得了1986年的世界電腦國際象棋冠軍(冠軍是克雷)。隨后貝利納的幾個學生包括華人許鋒雄等自行研究叫“芯測”的機器,后來則是“深思”(Deep Thought)。它只花5000美元但每秒搜索50萬個局面。許鋒雄(下圖右)等后來加入了IBM,和其他人合作制造了IBM現在的“深藍”(Deep Blue)
深藍
 
  加里·卡斯帕羅夫在費城和紐約面對的這臺電腦包括一個裝備大量專門用以進行高速運算芯片的IBMSP/2服務器,每個芯片每秒能處理2-3百萬個局面。使用超過200個這種芯片,整個程序的速度達到了每秒處理2億個局面。
  棋弈機器每秒能處理2億個局面意味著什么?肯·湯普森,“尤物”之父(也是UnixC語言之父),在80年代對搜索深度和棋力提高之間的關系做了非常有意義的試驗。他讓“尤物”自己跟自己下,但只有一方的搜索深度不斷增加,平均每增加一個搜索深度可大約換算成200個國際象棋等級Elo分。于是,“尤物”搜索四層其水平大約是1230分,搜索到九層它的水平達到了2328分。延伸這條曲線,到了頂端會變平緩,可以計算出搜索深度達到十四層時,就達到了世界冠軍的程度即2800分。(如下圖,橫坐標是搜索層數,縱坐標是國際等級分。上部橫線是卡斯帕羅夫的分數作參考,A線表示對電腦水平的樂觀估計,B線表示悲觀估計,C線表示現實估計)
 
搜索深度和棋力關系曲線圖
 
  專家的結論是:要與人類世界冠軍爭奪冠軍,必須做一臺每秒運算10億次的電腦(搜索到十四層的深度)。深藍接近了,但還達不到。【譯注:注意這里搜索到十四層的深度,應該是指規定比賽分配時間內對所有回合而言。否則對一步棋不限制時間地搜索,或者對一些簡單局面的搜索,要達到十四層對當今眾多高速電腦來說實在不是難事。】
  當然,程序的質量也扮演重要角色。今天的頂級個人電腦程序象FritzJunior可以達到并超過每秒處理50萬個局面。它們事實上已經超過2600分的水平,可以對抗除世界前100名棋手之外的任何人。在快棋戰里人類只有大約前十幾位可以勝任,而在超快棋里大概只有兩、三名人類棋手能過關。【譯注:也可見,每升高等級而要求的運算速度的提高絕不是僅僅直線式的,而是指數式的。所以每秒計算50萬次就達到2600分的特級大師水平,但要達到2800分,根據上面估算則需要每秒計算10億次之多。】
 
挑戰所有開局
 
  電腦棋力的一個重要方面是下棋時使用廣闊的開局庫。多少代人類大師的知識積累和經驗可以輕易地儲存在硬盤上并且在開局階段采用。即使是個人電腦程序也懂得幾千萬個開局局面,并且對這些局面的每一個都有完全的統計(比如出現過那些著法、用哪些著法勝過、使用過的人有多少,等等)。程序經常是連走1520步之后才第一次需要計算。如果沒有從這些人類的開局知識精華中受益,程序將實力大減。
  當電腦從數目龐大的、從國際象棋歷史積累下來的開局知識中取得堅實優勢之時,它們也從對局的另一端搜索中受益。
 
殘局數據庫
 
  這又是那位影響力到處有的肯·湯普森充當了研究先鋒。他在80年代就開始生成和儲存棋盤上剩四至五子的所有符合規則的殘局。一個典型的五子殘局,比如王雙象對王單馬,包含總數121萬個局面。加上一只移動不連續的兵,這個數字增加到335萬。湯普森編寫程序產生所有符合規則的局面并計算出每個殘局可能的強制變化。他還以一種方式把結果壓縮,使得一張標準的CD-ROM能存放大約20個殘局。【譯注:原文沒有提另一位對殘局數據庫的發展作出重大貢獻的Nalimov。】
  電腦使用這些殘局數據庫,可以把每個殘局走得絕對完美,就象上帝一樣。對于棋盤出現子力及數目符合的任何局面,電腦可以立刻知道該勝、該和還是該負,并且知道要多少步。它經常宣布15步棋之后取勝或將死,而執輸棋那一種顏色的則能夠最優化地防守【即在必然被將死前每一步防守都盡力最優化】。深藍使用了湯普森的殘局數據庫,而象Fritz這樣的個人電腦程序也把它們貫徹在搜索樹中。這些對棋力有什么影響還有待觀察。有些五子的殘局極之困難甚至對于人類來說難以掌握,但這些五子殘局對于湯普森正在努力的六子殘局來說只是小巫見大巫,在某些六子局面里,要取勝不得不進行超過200步的計算【譯注:當然這是在純電腦國際象棋領域來說,實際上人類走殘局,經驗和知識比重很大,有很多棋根本不用考慮就知道該怎么樣走。但電腦卻是“一絲不茍”地全部去算。所以,從數字上比意義還不大】。自然硬件技術的發展是有利于電腦的,湯普森的六子殘局,每個包含80200億個局面,剛好能夠壓縮進一張DVD【譯注:高端應用情況不得知,而普遍應用于個人電腦程序的Nalimov殘局數據庫,全部四子殘局大約占30MB儲存,全部五子殘局需要7GB,至于六子殘局,目前可見的只是一些比較簡單局面而且一只兵也沒有的,因為兵會升變,復雜性巨增,如果加上則相當時期內一般電腦的硬盤難以承受,別忘了增長不是直線而是指數式的。】
  好在,局面數量更大得不可思議的七子殘局,離產生依然很遙遠。更好在的是,對局的兩端即開局和殘局,永不可能接在一起。是啊,假如看到一臺電腦走了 1.e4 然后宣布40步棋之內將死,這就太難以讓人接受了。但是電腦在比賽中穩定戰勝人類世界冠軍大概只是時間問題,若干年或若干十年之后……
  【譯注:1997年深藍在“回敬賽”中戰勝棋王卡斯帕羅夫,但那次的場外不明朗因素太多,結果未必有說服力,何況注意到兩次比賽總成績其實還是卡帕羅夫以6.5-5.5戰勝深藍。200210月的克拉姆尼克對Deep Fritz人機大戰,不明朗因素又有點傾向于克拉姆尼克,以至輿論認為電腦機會不大,且到時看。卡斯帕羅夫本人當初認為電腦真正穩定戰勝人類世界冠軍要到2010年,湯普森則認為可能要到2018年。有趣的是包括貝利納、許鋒雄等人在上世紀90年代初認為電腦在1994年就可以達到這點的。】
 
湯普森和卡斯帕羅夫
 
  出處:ChessBase網站的專欄
  譯者:michael
  類型:略有刪節
  • 上一篇
  • 下一篇 人機大戰:魅力無窮
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果