阿基米德的報復第十章 計算機——未來的象棋之王

第十章計算機——未來的象棋之王

　　到此為止，我們所注意的大部分是計算機科學中的理論問題，計算機和人在原則上能進行哪些類型的計算。我們已經討論的限制都是無條件的。如果綜合性理論學家能夠證明他們的推測是真實的，那麼旅行推銷員問題就不可能找到有效的解法。這既不是因為數學家的問題，也不是計算機缺少適當的運算工具；而是根本沒有這種工具，將來也決不會有。　　大多數的數學家和計算機科學家都不會遇到理論上難以超越的限制。他們所面臨的障礙都是自我設置的，而且都是可以超越的，至少在原理上是可以超越的。一個主要的障礙——在數學之外的許多工作中也很突出——就是這樣一種傾向：穩妥的做法是照搬被普遍接受的他人的解題方法，即使這些方法不是那麼圓滿。那些想靠自己的努力取得成就的人，最好一下子就能搞出名堂來，否則就會招來他人的嘲笑。本章內，讓我們看看漢斯·伯利納的開拓性工作，他製造了一台能夠下好國際象棋的計算機。下一章，我們則將探討W．丹尼爾·希利斯的工作，他試圖用他自己的改革性設計取代曾很好地為電子計算機服務了40年的基本體系結構。　　漢斯·伯利納是美國匹茲堡市卡內基-梅隆大學計算機學科的研究人員，他本人態度文雅，還很想躋身於世界佼佼者行列。他曾經有過這樣的榮譽，現在也想為他的計算機成果贏得同樣的榮譽。1968年，他曾以42步一盤棋的卓越成績擊敗了蘇聯足智多謀的國際象棋策略家J．埃斯特林，成為國際象棋通信比賽的世界冠軍，為此他曾撲在棋盤上琢磨戰術整整500小時。1979年，他又設計了稱為BKG（15子棋）9．8的計算機程序，並在蒙特卡洛城舉行的大做廣告的15子棋^①比賽中，以7－1的壓倒比分擊敗了世界15子棋冠軍義大利的盧吉·維拉。伯利納也和他自豪的父親一樣，他很高興，BKG9．8程序已成為第一台能在任何棋盤上或紙牌遊戲比賽中擊敗人類世界冠軍的機器。　　現在，BKG9．8程序已被擱置起來，世界15子棋聯合會已禁止在正式比賽中應用計算機，但是，由伯利納和他的研究生卡爾·埃貝林設計的一種稱為Hitech（高科技）的新計算機程序卻在另一種棋盤競賽場所中保持了計算機的榮譽。1985年10月，Hitech程序贏得了北美計算機國標象棋的冠軍稱號。這項成功與其他一連串擊敗人類天才的勝利一起，完全證明了Hitech程序在下國際象棋方面優於任何其他計算機，也優於參加美國國際象棋協會認可的各種比賽的30，000名高明棋手（「思維」人）的99％。　　現在，伯利納已注視著弗雷德金獎金，這項10萬美元的獎金將給能擊敗人類世界冠軍的第一台計算機的設計師。Hitech程序目前要擊敗人類世界冠軍力量尚不足。但就伯利納的頑強性格、教育情況與比賽紀錄來看，其程序的前途是不可低估的。　　若按年月順序來看，伯利納早先熱愛國際象棋，而後才愛他的計算機。他1929年出生於德國， 8歲時隨父母遷居美國，定居在首都華盛頓。他發現那裡的學校的要求比德國松得多，因此他尋求課堂外的挑戰。在1942年的夏令營時，他看到了一些年輕人在下國際象棋，就向他們請教比賽規則。伯利納回憶說：「甚至就在第一天，已有些棋手成為我的手下敗將，情況就是這樣。我從此著了迷。」　　兩年以後，他是他所在地區國際象棋俱樂部的冠軍，並且保住華盛頓地區最佳國際象棋俱樂部冠軍的稱號。伯利納說道：「我父母從不鼓勵我。他們警告我說，如果我把時間都花在下棋上，我將沒有什麼前途。如果沒有人告訴我，誰知道我將成為什麼樣的人？」不過在短期內，伯利納未控制自己的棋癮。到了1949年，他終於贏得了人人盼望的華盛頓市國際象棋冠軍稱號，那時他剛剛20歲，這是個破紀錄的年齡。　　同年，美國數學家克勞德·香農發表了一篇頗有影響的論文，他在論文中概括地論述了如何編製計算機下國際象棋的程序。當時電子計算機剛剛問世，但是，下國際象棋已被作為在新生的人工智慧領域中的一個重要的目標。它與其他智力遊戲不同，國際象棋引起人們的興趣是因為在控制的條件下，通過讓計算機與人類選手對陣就可以精確判斷出計算機在國際象棋上的能力。參加比賽的棋手都有數字的等級，這是根據他們與其他等級對手比賽時的成績如何而定的。計算機也要取得等級，以反映它與人的等級棋手比賽所獲得的成績。　　當計算機科學的先驅們努力把香農的想法付諸實踐時，年輕的伯利納正集中精力於下國際象棋。1954年，他是這個國家中最佳的12名棋手之一，並保持了12年。50年代初期，他閱讀有關計算機下棋的第一批研究成果。他回憶說：「他們的把戲在我看來是相當可笑的。」　　英國數學界傑出人物艾倫·馬西森·圖靈也是計算機的開拓者之一，他是人工智慧方面有創造性的思想家（已在第八章中論述過），而且，憚精竭慮地窮究數學領域的奧秘。他還是一名國際象棋手，和愛因斯坦一樣，即使算不上精通，也至少樂此不疲；也許由於他認為國際象棋是少數幾種他未掌握的智力活動之一，因此他畢生熱愛這項活動。不管情況如何，他至少撰寫了6頁有關以機械方式下國際象棋的配方性棋步，這實際上是一種計算機程序。雖然他還沒有花費精力把下國際象棋的方法譯成編碼輸入計算機，但他曾用這些配方棋步於1952年與阿利克·格倫尼對弈。阿利克·格倫尼是英國曼徹斯特大學的一名學生，他也是很有才能的計算機程序設計者，但卻是一名不大高明的木材推銷員。圖靈的紙上下棋機（所以這麼叫它是因為它還只是在紙張上存在）在那次對弈中失敗了，但畢竟是首次用任意一種理想化的或者可以實現的計算機下棋。　　圖靈的配方是給每個棋子以數量價值，像國際象棋教科書所定級的那樣，以便大體上反映各棋子的相對實力：王1，000，後10，車5，象3．5、馬3和兵1。在選擇棋步時，都是接著走所有後續棋步，包括捉子在內，一直走到兩方既不能吃子也不能給予將死的靜止棋勢時為止。對於每種靜止棋勢，兩方的相對實力是把棋子的數值加在一起進行計算的，並把計算機的棋子數值看成正數，把對方的棋子數值看成負數。選擇導致靜止狀況的棋步，在這種狀態中，機器能使其相對實力增加到最大限度。　　圖靈的估值方案是能夠找到求勝的棋步的，但是在靜態情況下則無法使用。例如，它不能判別白方的頭一步如何走，因為在比賽開始時，在其20個可能的棋步（16個進兵步和4個上馬步）中，沒有一步棋捉子或者可能捉子，因此這20個靜止棋勢都是同樣0值的相對實力，顯然，要用該方案判斷是很荒謬的。　　圖靈還用加權的方法來克服這個問題，在靜態棋位中考慮諸如機動性與王的安全性等因素。例如對兵來說，走兵越過自己的布陣之後，每橫線增加0．2，如果受到別的子而不是本方兵的保衛，則另加0．3，如果不受到保衛，則要另減0．3。對於車、象、馬和後來說，如果走它們能走的法定棋步，則每走一步棋都增加其數值的平方根，如果這些棋步中至少有一步棋可以捉子，則另加1點。而且，要是車、象、或馬（不包括後）受到保衛，得到保衛一次另外獎給1點，兩次或兩次似上另外獎給2點。如果王得到車的保衛，則加0．3，如果與車保持均勢，則加0．2，要是以車保王未來仍能出現，則加0．1。　　圖靈也考慮王的安全性。在他的估值方案中，王所要損失的點數取決於它易於受到攻擊的程度。圖靈設想王是另一個後，並計算這個後的機動性，用此來量度其受到攻擊的程度。此外，圖靈還給攻對方王棋的棋步增加0．5，給立即能將對方王棋的威脅性棋步增加1。

　　在靜態情況下，紙上下棋機將按照其求值函數、最大的機動性、本方王的安全性以及對方王的易受攻擊性來決定棋步。在1952年與格倫厄博弈時，紙上下棋機以P－K₄開局，即走王前兵兩步，在20個可能棋步中，P－K₄棋步具有最大的數值，這個棋步不僅可以進兵到第四橫線，而且還可以提高後、王前象和王前馬的機動性。早在第三步棋時，紙上下棋機走了一步軟著的兵出擊，但格倫尼並沒有乘機利用它。在第二十九步棋時，由於紙上下棋機的求值函數示出格倫尼沒有立即有效的捉子應步，因此它貪婪地用後吃掉一兵。　　紙上下棋機的程序忽視一個簡單然而可以壓車的棋步，該棋步可以用下棋機的後看住對方的王，使得後可以強行捉子。最後，圖靈這個安樂死控制論的倡導者，代表紙上下棋機主動認負。　　紙上下棋機儘管非常原始，仍然有一些獨到之處。例如，它認為，只有在沒有任何捉子的可能時，實力的研究才有重要性。在棋盤上的某一棋位中，你可能缺少後，這種情況通常是很糟的，但只要是該你走子，你仍有機會，你可能捉住對方的後。你大概不需要一個估值的過程，它只不過統計出棋子的相對實力，卻沒有把可能的捉子考慮進去。　　當圖靈把諸如機動性與王的安全性等國際象棋知識的一些方面包括在求值函數之內時，他的思路是正確的。在與格倫尼博弈時，紙上下棋機的棋輸掉了是由於這些知識還不夠充分。它不能辨別在特定的棋局中的內在的危險性：王與後在同一縱列上。　　伯利納和其他國際象棋大師，甚至許多很不熟練的棋手都把這種棋局和不計其數的其他棋局牢記在他們腦子裡。研究證明，人類國際象棋大師對棋局和棋位都有非凡的記憶力，而且這種優異的記憶力不一定會轉移到與國際象棋無關的事物上。站在人的水準上，伯利納覺得，他在棋盤上所享受到的成功的喜悅沒有延續到教室中，至少在最初時沒有。　　伯利納回憶說：「一些人往往剛上大學不久，就會遇到麻煩，我就是其中之一。本來，我曾是一名物理學的優等生，但是不知怎麼一來，我走上了岔道。我一邊打工，一邊上學，終於攢夠了錢來付學費，可以不再打工。這是一個關鍵性的錯誤，忽然間我有了很多時間，因此除了下國際象棋之外，我還打橋牌。很快地，我就成為華盛頓市15名最佳橋牌手之一。一切都砸了鍋。」　　伯利納服完兵役後，想返回學校。他接著回憶說：「我未能完成物理學學業，因為我的平均學分太低，因此我轉修心理學。看來這是個廣闊的研究領域，因為全是些有興趣的事。」伯利納是從物理學轉來的，他期望能把事實歸納成理論，但是他失望地發現，情況恰好不是那樣。　　1954年，伯利納結婚了，在家庭生活與新工作之餘，幾乎沒有時間打橋牌，不過他還是想方設法繼續下國際象棋。他接著說道：「我在美國海軍研究實驗室從事稱為人類工程的工作。那是非常嚴肅的工作，牽涉到心理學與物理學，與設備的設計有關。那是在1955年，當時計算機剛剛問世，實驗室里也造出一部。我曾修過一門程序設計課程，大概編寫過20行有關加數的程序，但是除此之外，我沒有接觸過計算機。」　　「因為沒有時間旅行去參加國際象棋比賽，我決定參加通信國際象棋活動。這又是另一項重大錯誤。它無休止地在棋盤上花去我更多的時間。隨後的13年內，我參加了許多國際象棋的通信比賽，並且贏得了所有比賽。在世界通信錦標賽中，我必須下16盤棋。我估計，要思考每一步棋，平均需要花去4個小時的時間，一盤棋大約需要走35步，這就意味著，要贏得該比賽冠軍，我要投入2，200多小時的時間。接著，我實際上還是放棄了該項比賽。」他考慮為了保持該項冠軍還得再花2，200多小時的時間，是很不值的。　　1961年，伯利納進了美國馬里蘭州貝塞斯達的國際商業機器公司（IBM），成為一名系統分析家，並且主要工作是面向軍界。雖然他在那裡工作了8年，而且奮力進取，升任了經理，但他仍覺得這項工作得不償失：「如果你很認真地工作，這是一種可怕的生活。作為一名經理，你必須對上下都要負責任。你有一批人為你工作，但他們的確對工作毫不關心。還有一個傢伙來自軍界，他其實什麼都不懂，還對你指手畫腳，或提出一些無理要求。後來又有一個人接替了這個傢伙的工作，他根本不知道第一個人想要什麼，於是命令改變一切。我開始覺得，我所要做的工作應該是，在我回首往事時，能使我感到驕傲的工作。我希望從事研究工作。」　　伯利納繼續進行用計算機遠距離下棋的探索，但他看到進展很慢，感到失望。在50年代期間，學者們曾做過樂觀的預測，但它與實驗室內的成功不相吻合；例如，1957年，美國卡內基-梅隆大學現代諾貝爾榮譽獲得者羅伯特·西蒙就曾聲稱數字計算機將在10年內成為世界的國際象棋冠軍。　　計算機程序設計的重要性還沒有完全得到認識。按照公眾的看法，國際象棋大師就像一種人類的計算機：當他選擇一步棋時，他在心目中還要探索幾百步後續棋，如果我上了王前兵，那麼他將同時攻我兩車，而後我將捉他的後……都以驚人準確的閃電速度下棋。計算本來是計算機的主要功能，因此它們在國際象棋上似乎應該是天生的冠軍。問題在於公眾的這種看法是錯誤的，對於國標象棋大師來說，計算不是惟一的甚至不是成功的主要的秘訣。他們的成功更多地取決於對棋局的判斷，而不是研究那些令人頭痛的棋步。　　荷蘭的心理學家安德里安·德格魯特發現，在典型的棋法中約有38步可能的法定棋步，而國際象棋大師平均只考慮其中的1．76棋步。換句話說，一位象棋大師通常根據自己曾經下過或看到別人曾經下過的成千上萬步棋，在他所能判斷的兩個候選棋步中進行選擇，這種選擇對實現該棋步的眼下和長遠目標有利。美國的一位國際象棋特級大師威廉·隆巴迪老人曾經寫道：「在實現目的之後，即取勝的布局轉變成為數學上的強力取勝的時刻，計算最為常見。」只要花一兩秒鐘，就能一眼認出所熟悉的布局，這是象棋大師們在棋賽中具有驚人優勢的根本原因。在動態的棋局中，簡直沒有時間進行預測。　　許多早期的計算機程序都只局限於考慮選擇候選棋步的數量（儘管它根本就不會是1．76這麼小的數）。應用選擇搜索方法的問題在於沒有人知道如何用計算機語言，更不用說是用英語，來表示用於選擇候選棋步的一般失效保險原理。 1966年，由美國麻省理工學院的理查德·格林布拉特研究的早期選擇搜索程序MacHack最為成功，它已成為在比賽中擊敗人類棋手（即使是最弱的一名棋手）的第一部國際象棋計算機。MacHack程序還有幸駁倒了休伯特·德賴弗斯的看法，德賴弗斯是《計算機不能做些什麼》一書的作者，他曾靠貶低計算機的能力而出了名。　　然而MacHack的功能一般說來還有嚴重的缺陷。雖然它在下棋時能夠勝任持續時間很長的棋局，但它還是易於突然犯下某種可笑的錯誤，而這種錯誤多少是由編入該計算機程序的象棋原理造成的。此外，它有時也會對某些巧妙但卻顯然違背了象棋原理的棋步視而不見。但是它已在比賽中擊敗了人類棋手，因而是計算機國際象棋的里程碑。　　伯利納回憶說：「我的上帝！當我聽到有關MacHack程序取得勝利的消息時，我認為，儘管計算機國際象棋受到如此冷遇，儘管人們做了種種努力卻收效甚微，但還是有希望的。我去拜訪格林布拉特先生，雖然我還不完全理解計算機真的會按他所希望的去做，但我還是留下了深刻的印象。由於我離了婚，還沒有再婚，我又一次有了許多時間，因而我自學計算機程序設計，並花去許多晚上和周末時間編寫計算機國際象棋程序。我向美國國際商業機器公司申請讓我到該公司在紐約的約克頓海特斯研究機構中從事計算機國際象棋的工作。他們答覆說："我們不資助這類項目。而且，你還沒有博士學位，因此，如果你能做些對公司有益的其他事的話，我們頂多讓你稍微做一點這方面的工作。』」　　「我認為，要達到我的目的，惟一的途徑是獲得博士學位，以便進入該公司。我對自己的基本情況很自負。我向幾個學校提出了申請，但只有卡內基-梅隆大學接受我。」他在1968年獲得世界通信國際象棋比賽冠軍的勝利顯然有助於他進入該校。　　「因此，我是在1969年秋季40歲時成為一名學生的。這對我是多麼大的震驚。我覺得我需要學習的東西實在太多了，像自動化理論、各種不同的程序設計語言、多種多樣的硬體配置、以及人工智慧本身等等。」伯利納早年在高等學校中不喜歡的許多課程，現在反而都要修讀它們。　　在卡內基-梅隆大學時，伯利納繼續進行他在國際商業機器公司空餘時間內開始的計算機程序設計工作。1970年，在美國紐約市舉行的第一屆美國計算機國際象棋錦標賽上，一種叫做J．Biit的計算機程序（其英文發音與「正好由於它在那兒」的英文首字母縮寫詞的發音相近）做出相當不錯的表演。J．Biit程序也和MacHack程序一樣，用選擇搜索法工作。該程序的實力就是它的估值函數，即它所考慮每步棋的實力強弱如何都以數值來權衡，但是由於它是選擇性搜索，因此有時甚至都不考慮某種正確棋步，更不用說去走它了。伯利納說道：「在某些具體情況下，它很有下棋的才華。但是這還不夠。在所有不同類型的棋局中，你都必須是始終如一的正確。J．Biit程序還不具備強大的實力，足以成功地應付整盤比賽。」　　在第一屆美國計算機國際象棋錦標賽上，J，Biit程序敗於國際象棋3．0程序，後者是美國西北大學研究生戴維·斯萊特和勞倫斯·阿特金設計的。3．0程序的後來版本執行的不是選擇搜索法，而是全方位搜索法：對所有可能的續步進行徹底的分析，一直到規定的某種深度。雖然全方位搜索法總是包含它看到的候選棋步中的正確棋步（因為它看到了所有棋步！），但在選擇一步棋時效率卻很低。很多時間都浪費在令人吃驚地探索無價值的棋步上，即使是最笨的人類推木式棋手對此也不會給予片刻的考慮。要是計算機能夠看清博弈的最後結局，比方說像它能夠在三連棋中所做的那樣，那麼，這些無用的努力將是毫無意義的。　　國際象棋的數學可以證明全方位搜索的低效性。在人類國際象棋大師之間的對弈，典型的是對弈了84著棋（1著棋即指定的一方走一步棋）。由於每個棋位平均有38步法定棋步，因此窮舉搜索法必須考慮38⁸⁴個可能的棋位。那是一個龐大的數字：38⁸⁴大於10¹³²，即1的後面有132個0。宇宙已經存在了大約10¹⁸秒，因此，即使讓計算機能夠工作像宇宙年齡那麼長的時間，每秒鐘也要分析10¹¹⁴個國標象棋棋位，才能看清博弈的結局。　　在國際象棋比賽中，計算機也和人一樣，不允許進行無限期的思考；40步棋大約只能給定120分鐘，每步棋平均3分鐘。即使計算機減小了胃口，僅探索出後續幾步棋所有可能的棋步，數學上也是不允許的。在只走兩著棋之後，即每方各走一步棋之後，可能的棋勢數就會超過1，000。而走了4著棋之後，就可能有超過100萬可能的棋勢。　　計算機不僅生成所有這些棋勢，而且還要求出它們的值。計算機是通過數值加權的方法來相當粗略地達到上述目的，諸如考慮實力（即各方的子與兵的數量與特點）、機動性、中心方格與縱列的控制、兵的結構、王的安全性、等等。比方說，在3分鐘結束時，無論走什麼棋步都要使對手的潛在的最大增益降至最低的程度；這種策略，是從有關競賽的數學理論借鑒而來的，它設想對方可看出你所看出的一切，力求確保自身的利益。　　如果不是發現了a－β演算法，全方位搜索法即使只局限於幾著棋的深度，也是不實用的。a－β演算法是一種巧妙的求值方法，可以讓計算機無需求出每種可能棋勢的值就能選擇它所要走的棋步。然而令人驚奇的是，所選擇的棋步正是計算機考慮了每一種續步後所要走的同一步棋。這怎麼可能呢？　　假設計算機首先在一定範圍內探索稱之為A的某一特定棋步的所有後續棋步。設想兩方都走最佳的弈法，計算機給A定的極小極大值比方說為1。（在這種方案中，正值相當於計算機所具有的優勢，而負值相當於計算機所處的劣勢。優勢值為1，表示比對手多一兵，其他條件都相同。）現在，計算機開始對另一個叫做B的可選棋步求值，B是特別愚蠢的一步棋，表示將後置於可以立即被對手的弱兵捉住的方格中。如果計算機現在分析對手的正常應著棋步——以兵捉後，並排除掉一種微小的可能性，即為了一次銳不可擋的進攻而英勇犧牲了後，那麼，計算機將定這個棋勢的數值為-9，它表示其對手已具有強大的優勢。

求極小極大值　　現代的計算機國際象棋靠的是極小極大值法：所走的棋步應使對手的可能最大增益降至最小程度。假設計算機可選擇的棋步為A和B。它看出了對手對A的最佳反應是走一步棋a（圖中的數目表示按照計算機的觀點所產生的棋勢的優劣程度如何）。這時計算機又考慮棋步B，並看出了對手將應以d，從而能保證時B取得比對A更好的結果。這時計算機有足夠理由選擇A，而對手反應e或f的結果是什麼都無關緊要。　　計算機不需要考慮所有其他應著棋步的結果，其中也包括對手不能吃後，因為計算機已能識別對手的走棋路線是確保它自己對B步棋的應步能優於對A步棋的應步。因此，計算機根據自己的觀點，知道走A步棋比走B步棋更為可取。　　要有效地執行a－β演算法，計算機必須按順序考慮各種棋步：在上述例子中，它必須先檢驗A，再檢驗B，並且在分析B時，必須先檢驗捉後的棋步，再考慮其他的應步。審查各種棋步的順序取決於各種不同的探試法或一般經驗。　　例如，捉子探試法指令程序對那些涉及捉子的各種棋步給予最優先考慮。（這樣捉子成為一著好棋的機會將更多一些，特別是如果被捉的子未受到保護時。這種方法還能幫助計算機減輕負擔，對機器大有稗益。而棋盤上少了一個子，計算機考慮的應著棋步也就相應減少。）　　殺子探試法始終監視著對手的哪一步棋被殺或被駁倒（一種特殊的棋步）。當計算機仔細考慮了另一步棋時，首先要研究殺方的反應。現舉一特殊例子。計算機發現它所考慮的捉對方車的一步已被對手弈出將軍棋步所駁倒，在仔細考慮替代的棋步時，它將首先決定是否要走避免被將軍的棋步。換句話說，殺子探試法可用來識別並監視這種威脅，這裡所指的是能立即將軍的致命威脅。另一次探試優先考慮那些能將軍的棋步，從而應了一句古老的格言：「常將，就能將死。」簡單地說，這時計算機的做法就有些更像人了。　　在全方位搜索法中，要是採用漸進地深入考慮所有的續步，而不是每次一步地充分考慮這些續步，那麼就能做到省時省事。從棋盤上的某種棋勢著手，首先分析所有可能的續步，然後分析某一特定的棋步，根據目前所進行的搜索，就能看到最佳的一步棋。再從這步棋開始，對其餘的所有續步進行有效的分析，一直到兩著棋的深度，並且再次找到其中最佳的一步棋。這種過程叫做迭代深化法，它不斷重複下去，直到達到所期望的深度時為止。　　有一種表記錄了計算機已經求出值的棋勢、對這些棋勢所給定的數值、以及迄今已搜索到的最佳一步棋，通過這個表就可以提高全方位搜索法的有效性。在全方位搜索法中，各種棋勢都往往會不止一次地出現，只要程序設計好，查找所求的數值的時間自然比重新計算的時間少，因此，這種表在節省時間方面是很有用的。　　在70年代，美國西北大學的斯萊特和阿特金已能夠利用變最大為最小求值法、a－β演算法、捉子探試法與殺子探試法、迭代深化法和已經檢驗過的棋勢表等各種方法成功地用國際象棋3．0程序的後來版本進行工作，而且，它也像圖靈的紙上下棋機一樣，深入地搜索了下國際象棋的戰術棋路，直到走到走不動的棋勢為止。這就是國際象棋4．7程序，它下國際象棋的能力略低於國際象棋大師的水平。　　1981年，全方位搜索程序Belle由美國電話電報公司貝爾實驗室的肯·湯姆森和喬·康登共同開發出來，它已成為第一部達到國際象棋大師級水平的計算機，進入全美國際象棋比賽最高棋手1％的行列。Belle程序的成功應歸功於專為進行國際象棋運算而定製的硬體。華盛頓的官員顯然很重視Belle程序。1981年，當湯姆森和康登試圖攜帶Belle程序去蘇聯莫斯科參加國際象棋表演比賽時，聯邦局人員拘捕了他們。里根當局擔心該程序會泄露軍事秘密。而湯姆森卻堅持認為，Belle程序所知道的事情只是如何去下國際象棋。湯姆森告訴新聞界說：「在軍事上可以使用Belle程序的惟一方式就是可以把它從飛機中扔出，也許你可以以此殺死某一個人。」這些日子，華盛頓已不大注意了，因為Belle程序的等級已滑落在國際象棋大師的水平之下，然而它仍然可以探索平均8著棋的深度，每秒鐘分析120，000種棋勢，弈出比較難對付的國際象棋。　　當斯萊特、阿特金、湯姆森、康登及其他人應用全方位搜索法進行工作時，伯利納卻集中精力於求值函數上。伯利納回憶說：「當時我正考慮德格魯特關於國際象棋大師怎樣弈棋的著名的研究——他們如何觀察弈至一半的棋局變化，然後如何轉向考慮別的方面，再如何回到考慮最初的棋局變化。看來那是正確的。至少那是我所考慮的如何下棋的方法。」另一方面，現有的計算機下國際象棋的程序，不會在變化中來回移動。它們隨著特定的變化到達一定的深度，給最後的棋勢求出數值，再轉到另一種變化。　　伯利納接著說：「給定某一具體值的困難在於你不能出錯。你可以弈出犧牲兩子兵，以換取具有極強攻擊力的棋勢。如果你使用類似α-β的演算法，你就能夠弈出最後一種棋勢，對此你必須賦值；要麼為換取攻勢值得拋棄兩兵子，要麼就不值得。無論你持哪種看法，都會在一定時間內出現錯誤。更確切地說，"我還不能肯定。我已經丟掉兩兵但擁有強攻勢。也許實際上我可以將死王或者贏回的多於兩兵，而我也許只是丟了兩兵』，所以你先擺出問題，再進一步深入研究，看你能否解決它。」　　「對於這類問題以及如何把計算機程序編寫得更深入，我思考得很多。一個晚上，我忽然有一靈感：對於一種棋勢，可以給定一個值，為什麼不能以一系列的值取而代之？」　　一系列值中最高值意味著棋勢處於最佳狀態，而最低值則相當於可能出現最壞的情況，計算機程序要對一系列值而不是對單一值進行比較，而且當這些值的範圍太寬時，它還可以比較深入地考慮棋勢，以便把最高值和最低值都包括進去。伯利納說道：「這種想法是遺漏的組成要素。它是許多不可思議的事物之一，這類事在科學上隔一段時間就發生一次。你提出某一方案，那麼突然間，一切都迎刃而解了。」使用系列值的想法已經成為眾所周知的B*演算法（發音為「B-星」），而且伯利納還把它列為他的訣竅。　　1975年，當伯利納完成計算機國際象棋博士論義時，他決定為計算機編寫下15子棋的程序，這種棋是他最近向新岳父學習的。他發現15子棋對研究求值法是一個很吸引人的領域，因為在這種棋中進行搜索，不會讓你探索得太深。在典型的15子棋棋勢中，約有400多種可能性（21組擲骰點數和每組點數的約20種走棋法），與之相比，在典型的國際象棋棋勢中，則「僅有」38種可能性。　　在15子棋的計算機程序BKG中，伯利納沒有沿用人工智慧中按規則求值的一般做法，他注意到「在醫療診斷體系中，也許還有一種慣例，比如說，如果有一位患者，他有這樣那樣的疾病，而且其年齡已超過6周歲，那麼可以給他以如此這般的治療。可是忽然間來了一位患同樣病的患者，但他的年齡僅為5周歲9個月，按照慣例，不能對他進行那種治療。當然，那是錯誤的。因為你真正需要考慮的不是黑白分明的年齡截止點，而是由於某種原因需要考慮諸如年齡、體重以及一般健康情況等因素的平緩函數。在上述特定病例中，可以開出降低劑量的藥方」。　　「當你首次設計智能系統時，這幾項考慮已不很重要了。它們遠不及把基本信息輸進計算機中那麼重要。但是，如果你想與最佳的人競爭，那麼你就不能按照一套完全不靈活的規則去工作。」　　當然，伯利納想以他的15子棋計算機程序與人類最佳棋手博奔，因此他沒有認真地考慮較為慣用的方法，擯棄了把棋勢分為幾種類型而且每類都有不同求值函數的通則。相反，他卻依賴數學上的單一複雜函數，這個函數包括大約50個不同的變數，與具有不同程度重要性的特定部分相一致，其重要性取決於博弈階段。每個變數都由一個數值來替代，來衡量存在於已知棋勢中相應特點的重要程度。這樣一來每個數都是加權的：它們都乘以另一個數，這個數稱為係數，用以表示對該點的特點所給予的注意力有多大（或多小）。隨著博弈進程的變化，這些係數也平緩地變化著。　　這種成功的方法叫做SNAC法（帶有應用係數的非線性平緩函數法）。在SNAC法提出後，只有幾個月的時間，BKG程序就擊敗了人類15子棋冠軍選手，這顯然表明SNAC法是成功的。雖然BKG程序有一些擲骰子般的幸運，而且也曾有過少量較小的錯誤，但它還是一個強勁的棋手。　　伯利納根據他在計算機15子棋上獲得的成功，知道找到一種平緩變化的函數對國際象棋上的有效求值法也是很關鍵的。在這一點上，慣用的一種方法也與通則有關。考慮一下王的棋勢。當博弈到中盤時，你想把王躲藏在角落裡，那裡很可能少受騷擾。求值函數可以對王的實際位置與角落之間的棋盤方格進行計數；這個數愈大時，你的處境也愈壞。然而，在弈至殘局時，那時只剩下幾個子，將死的危險性甚微，於是王應該處於棋盤的中央，它在那裡還可以起著很強的戰子作用。所以在殘局時，求值函數可以對王的實際位置與中央之間的間隔數進行計數。如果你採用了如下通則：BKG程序在與人類的世界15子棋冠軍盧吉·維拉對弈時贏得了勝利

　　BKG程序在與維拉比賽的第一局中，擲出一個 4點和一個2點。這時，BKG程序（黑方）具有優勢，但不得不留下一個暴露棋子。它走了9-5步和9-7步，在7點處，留有一個暴露棋子，它可能受到13組擲骰點數的攻擊。從表面上看，好像走5-1步和4-2步比較安全，在5點處留下一個暴露棋子，它只可能受到11組擲骰點數的攻擊，但這卻是糟糕的走法，因為它在9點處會留下兩子，當它們必須走步時，就有可能成為後來的暴露棋子。　　「當棋盤上還有一定數目的子和兵時，棋局就是中盤，而當其只有很少幾個子時，則是殘局」，那麼，你幾乎要患精神分裂症了。　　伯利納接著說道：「你當然不想這樣，棋勢是連續性的——中盤是逐步轉為殘局的。由於殘局的逐漸接近，你不再那麼執意要讓王走到角落，而是容許王緩慢地移到棋盤的中部。每當人人都承認殘局終於來到時，王應該靠近棋盤的中央，而不是藏在角落裡。」達到這一目的的方法是需要有一種緩慢變化的求值函數，而在中盤與殘局之間不應有任意的差別，而且兩者也不應有不同的求值函數。

　　BKG程序在與維拉最後一局的比賽中，如圖所示，擲出一個5點和一個1點。這時，BKG程序走出了引起轟動的13-8步和3-2步。如果BKG程序的暴露棋子中任何一子受到進攻，那麼它將有更多的時間去組成棋步，以阻止對方的棋子前進。反之，如果它們未受攻擊，那麼就能夠在本方棋盤中形成據點，使維拉的棋子更難於回到本方的棋盤中，然後再逃脫掉。　　的信息而工作，太陽牌計算機是Hitech程序的國際象棋的知識源。　　Hitech程序的成功秘訣在於它能更好地思考（由於Oracle程序）以及比呆板的對手快50％的求值速度（因為它可以同時對一步以上的棋步順序求值）。Hitech程序執行全方位搜索法，平均每秒可以觀察驚人的175，000種不同棋勢，換句話說，每步棋3分鐘內可以均攤到3，000萬種棋勢分析。伯利納說道：「毫無疑問，人們要考慮3，000萬種棋勢需要花去他們一生的時間。」　　Hitech程序的速度及其智力水平已使它成為世界上最高級的國際象棋程序，優於幾乎全部的蘇聯人棋手。伯利納認為， Hitech程序或其新一代程序在1990年的國際象棋對弈中擊敗人類棋王的可能性有50％。為了達到這一目的，它計劃把更多的知識輸進Oracle程序，並使Hitech程序試用選擇搜索法，或許還得用B*演算法。　　Hitech程序下國際象棋能下得多好？就此而言，任何一種計算機在某項智能活動中究竟能有多好？伯利納說道：「我認為，我們將會發現，在輸入計算機的一些信息開始與另一些信息相抵觸之前，你能輸入計算機的信息量是有限度的。」某些研究工作者試圖藉助於一種信任系統，來消除這種可能性。計算機對相抵觸的信息不大注意，因為它的來源不可靠。　　伯利納接著說道：「但是我不認為信任系統就是答案。我認為，我們需要製造一種學習機，把它擺在架子上，觀看錄像帶，並從基礎學起。開始，可能學得很慢。也許要花20年時間，才能達到成年人的理解水平，那也就很好了。如果所得到的成果是有價值的，那麼學習機本身也是值得的。然而，我不會屏息不語。學習機最終必定會出現，不是在80年代，或許是在90年代
推薦閱讀：