阿基米德的報復(fù)第十章 計(jì)算機(jī)——未來的象棋之王
第十章計(jì)算機(jī)——未來的象棋之王
到此為止，我們所注意的大部分是計(jì)算機(jī)科學(xué)中的理論問題，計(jì)算機(jī)和人在原則上能進(jìn)行哪些類型的計(jì)算。我們已經(jīng)討論的限制都是無條件的。如果綜合性理論學(xué)家能夠證明他們的推測是真實(shí)的，那么旅行推銷員問題就不可能找到有效的解法。這既不是因?yàn)閿?shù)學(xué)家的問題，也不是計(jì)算機(jī)缺少適當(dāng)?shù)倪\(yùn)算工具；而是根本沒有這種工具，將來也決不會有。
大多數(shù)的數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家都不會遇到理論上難以超越的限制。他們所面臨的障礙都是自我設(shè)置的，而且都是可以超越的，至少在原理上是可以超越的。一個主要的障礙——在數(shù)學(xué)之外的許多工作中也很突出——就是這樣一種傾向：穩(wěn)妥的做法是照搬被普遍接受的他人的解題方法，即使這些方法不是那么圓滿。那些想靠自己的努力取得成就的人，最好一下子就能搞出名堂來，否則就會招來他人的嘲笑。本章內(nèi)，讓我們看看漢斯·伯利納的開拓性工作，他制造了一臺能夠下好國際象棋的計(jì)算機(jī)。下一章，我們則將探討W．丹尼爾·希利斯的工作，他試圖用他自己的改革性設(shè)計(jì)取代曾很好地為電子計(jì)算機(jī)服務(wù)了40年的基本體系結(jié)構(gòu)。
漢斯·伯利納是美國匹茲堡市卡內(nèi)基-梅隆大學(xué)計(jì)算機(jī)學(xué)科的研究人員，他本人態(tài)度文雅，還很想躋身于世界佼佼者行列。他曾經(jīng)有過這樣的榮譽(yù)，現(xiàn)在也想為他的計(jì)算機(jī)成果贏得同樣的榮譽(yù)。1968年，他曾以42步一盤棋的卓越成績擊敗了蘇聯(lián)足智多謀的國際象棋策略家J．埃斯特林，成為國際象棋通信比賽的世界冠軍，為此他曾撲在棋盤上琢磨戰(zhàn)術(shù)整整500小時。1979年，他又設(shè)計(jì)了稱為BKG（15子棋）9．8的計(jì)算機(jī)程序，并在蒙特卡洛城舉行的大做廣告的15子棋①比賽中，以7－1的壓倒比分擊敗了世界15子棋冠軍意大利的盧吉·維拉。伯利納也和他自豪的父親一樣，他很高興，BKG9．8程序已成為第一臺能在任何棋盤上或紙牌游戲比賽中擊敗人類世界冠軍的機(jī)器。
現(xiàn)在，BKG9．8程序已被擱置起來，世界15子棋聯(lián)合會已禁止在正式比賽中應(yīng)用計(jì)算機(jī)，但是，由伯利納和他的研究生卡爾·埃貝林設(shè)計(jì)的一種稱為Hitech（高科技）的新計(jì)算機(jī)程序卻在另一種棋盤競賽場所中保持了計(jì)算機(jī)的榮譽(yù)。1985年10月，Hitech程序贏得了北美計(jì)算機(jī)國標(biāo)象棋的冠軍稱號。這項(xiàng)成功與其他一連串擊敗人類天才的勝利一起，完全證明了Hitech程序在下國際象棋方面優(yōu)于任何其他計(jì)算機(jī)，也優(yōu)于參加美國國際象棋協(xié)會認(rèn)可的各種比賽的30，000名高明棋手（“思維”人）的99％。
現(xiàn)在，伯利納已注視著弗雷德金獎金，這項(xiàng)10萬美元的獎金將給能擊敗人類世界冠軍的第一臺計(jì)算機(jī)的設(shè)計(jì)師。Hitech程序目前要擊敗人類世界冠軍力量尚不足。但就伯利納的頑強(qiáng)性格、教育情況與比賽紀(jì)錄來看，其程序的前途是不可低估的。
若按年月順序來看，伯利納早先熱愛國際象棋，而后才愛他的計(jì)算機(jī)。他1929年出生于德國， 8歲時隨父母遷居美國，定居在首都華盛頓。他發(fā)現(xiàn)那里的學(xué)校的要求比德國松得多，因此他尋求課堂外的挑戰(zhàn)。在1942年的夏令營時，他看到了一些年輕人在下國際象棋，就向他們請教比賽規(guī)則。伯利納回憶說：“甚至就在第一天，已有些棋手成為我的手下敗將，情況就是這樣。我從此著了迷。”
兩年以后，他是他所在地區(qū)國際象棋俱樂部的冠軍，并且保住華盛頓地區(qū)最佳國際象棋俱樂部冠軍的稱號。伯利納說道：“我父母從不鼓勵我。他們警告我說，如果我把時間都花在下棋上，我將沒有什么前途。如果沒有人告訴我，誰知道我將成為什么樣的人？”不過在短期內(nèi)，伯利納未控制自己的棋癮。到了1949年，他終于贏得了人人盼望的華盛頓市國際象棋冠軍稱號，那時他剛剛20歲，這是個破紀(jì)錄的年齡。
同年，美國數(shù)學(xué)家克勞德·香農(nóng)發(fā)表了一篇頗有影響的論文，他在論文中概括地論述了如何編制計(jì)算機(jī)下國際象棋的程序。當(dāng)時電子計(jì)算機(jī)剛剛問世，但是，下國際象棋已被作為在新生的人工智能領(lǐng)域中的一個重要的目標(biāo)。它與其他智力游戲不同，國際象棋引起人們的興趣是因?yàn)樵诳刂频臈l件下，通過讓計(jì)算機(jī)與人類選手對陣就可以精確判斷出計(jì)算機(jī)在國際象棋上的能力。參加比賽的棋手都有數(shù)字的等級，這是根據(jù)他們與其他等級對手比賽時的成績?nèi)绾味ǖ摹Ｓ?jì)算機(jī)也要取得等級，以反映它與人的等級棋手比賽所獲得的成績。
當(dāng)計(jì)算機(jī)科學(xué)的先驅(qū)們努力把香農(nóng)的想法付諸實(shí)踐時，年輕的伯利納正集中精力于下國際象棋。1954年，他是這個國家中最佳的12名棋手之一，并保持了12年。50年代初期，他閱讀有關(guān)計(jì)算機(jī)下棋的第一批研究成果。他回憶說：“他們的把戲在我看來是相當(dāng)可笑的。”
英國數(shù)學(xué)界杰出人物艾倫·馬西森·圖靈也是計(jì)算機(jī)的開拓者之一，他是人工智能方面有創(chuàng)造性的思想家（已在第八章中論述過），而且，憚精竭慮地窮究數(shù)學(xué)領(lǐng)域的奧秘。他還是一名國際象棋手，和愛因斯坦一樣，即使算不上精通，也至少樂此不疲；也許由于他認(rèn)為國際象棋是少數(shù)幾種他未掌握的智力活動之一，因此他畢生熱愛這項(xiàng)活動。不管情況如何，他至少撰寫了6頁有關(guān)以機(jī)械方式下國際象棋的配方性棋步，這實(shí)際上是一種計(jì)算機(jī)程序。雖然他還沒有花費(fèi)精力把下國際象棋的方法譯成編碼輸入計(jì)算機(jī)，但他曾用這些配方棋步于1952年與阿利克·格倫尼對弈。阿利克·格倫尼是英國曼徹斯特大學(xué)的一名學(xué)生，他也是很有才能的計(jì)算機(jī)程序設(shè)計(jì)者，但卻是一名不大高明的木材推銷員。圖靈的紙上下棋機(jī)（所以這么叫它是因?yàn)樗€只是在紙張上存在）在那次對弈中失敗了，但畢竟是首次用任意一種理想化的或者可以實(shí)現(xiàn)的計(jì)算機(jī)下棋。
圖靈的配方是給每個棋子以數(shù)量價值，像國際象棋教科書所定級的那樣，以便大體上反映各棋子的相對實(shí)力：王1，000，后10，車5，象3．5、馬3和兵1。在選擇棋步時，都是接著走所有后續(xù)棋步，包括捉子在內(nèi)，一直走到兩方既不能吃子也不能給予將死的靜止棋勢時為止。對于每種靜止棋勢，兩方的相對實(shí)力是把棋子的數(shù)值加在一起進(jìn)行計(jì)算的，并把計(jì)算機(jī)的棋子數(shù)值看成正數(shù)，把對方的棋子數(shù)值看成負(fù)數(shù)。選擇導(dǎo)致靜止?fàn)顩r的棋步，在這種狀態(tài)中，機(jī)器能使其相對實(shí)力增加到最大限度。
圖靈的估值方案是能夠找到求勝的棋步的，但是在靜態(tài)情況下則無法使用。例如，它不能判別白方的頭一步如何走，因?yàn)樵诒荣愰_始時，在其20個可能的棋步（16個進(jìn)兵步和4個上馬步）中，沒有一步棋捉子或者可能捉子，因此這20個靜止棋勢都是同樣0值的相對實(shí)力，顯然，要用該方案判斷是很荒謬的。
圖靈還用加權(quán)的方法來克服這個問題，在靜態(tài)棋位中考慮諸如機(jī)動性與王的安全性等因素。例如對兵來說，走兵越過自己的布陣之后，每橫線增加0．2，如果受到別的子而不是本方兵的保衛(wèi)，則另加0．3，如果不受到保衛(wèi)，則要另減0．3。對于車、象、馬和后來說，如果走它們能走的法定棋步，則每走一步棋都增加其數(shù)值的平方根，如果這些棋步中至少有一步棋可以捉子，則另加1點(diǎn)。而且，要是車、象、或馬（不包括后）受到保衛(wèi)，得到保衛(wèi)一次另外獎給1點(diǎn)，兩次或兩次似上另外獎給2點(diǎn)。如果王得到車的保衛(wèi)，則加0．3，如果與車保持均勢，則加0．2，要是以車保王未來仍能出現(xiàn)，則加0．1。
圖靈也考慮王的安全性。在他的估值方案中，王所要損失的點(diǎn)數(shù)取決于它易于受到攻擊的程度。圖靈設(shè)想王是另一個后，并計(jì)算這個后的機(jī)動性，用此來量度其受到攻擊的程度。此外，圖靈還給攻對方王棋的棋步增加0．5，給立即能將對方王棋的威脅性棋步增加1。
在靜態(tài)情況下，紙上下棋機(jī)將按照其求值函數(shù)、最大的機(jī)動性、本方王的安全性以及對方王的易受攻擊性來決定棋步。在1952年與格倫厄博弈時，紙上下棋機(jī)以P－K4開局，即走王前兵兩步，在20個可能棋步中，P－K4棋步具有最大的數(shù)值，這個棋步不僅可以進(jìn)兵到第四橫線，而且還可以提高后、王前象和王前馬的機(jī)動性。早在第三步棋時，紙上下棋機(jī)走了一步軟著的兵出擊，但格倫尼并沒有乘機(jī)利用它。在第二十九步棋時，由于紙上下棋機(jī)的求值函數(shù)示出格倫尼沒有立即有效的捉子應(yīng)步，因此它貪婪地用后吃掉一兵。
紙上下棋機(jī)的程序忽視一個簡單然而可以壓車的棋步，該棋步可以用下棋機(jī)的后看住對方的王，使得后可以強(qiáng)行捉子。最后，圖靈這個安樂死控制論的倡導(dǎo)者，代表紙上下棋機(jī)主動認(rèn)負(fù)。
紙上下棋機(jī)盡管非常原始，仍然有一些獨(dú)到之處。例如，它認(rèn)為，只有在沒有任何捉子的可能時，實(shí)力的研究才有重要性。在棋盤上的某一棋位中，你可能缺少后，這種情況通常是很糟的，但只要是該你走子，你仍有機(jī)會，你可能捉住對方的后。你大概不需要一個估值的過程，它只不過統(tǒng)計(jì)出棋子的相對實(shí)力，卻沒有把可能的捉子考慮進(jìn)去。
當(dāng)圖靈把諸如機(jī)動性與王的安全性等國際象棋知識的一些方面包括在求值函數(shù)之內(nèi)時，他的思路是正確的。在與格倫尼博弈時，紙上下棋機(jī)的棋輸?shù)袅耸怯捎谶@些知識還不夠充分。它不能辨別在特定的棋局中的內(nèi)在的危險性：王與后在同一縱列上。
伯利納和其他國際象棋大師，甚至許多很不熟練的棋手都把這種棋局和不計(jì)其數(shù)的其他棋局牢記在他們腦子里。研究證明，人類國際象棋大師對棋局和棋位都有非凡的記憶力，而且這種優(yōu)異的記憶力不一定會轉(zhuǎn)移到與國際象棋無關(guān)的事物上。站在人的水準(zhǔn)上，伯利納覺得，他在棋盤上所享受到的成功的喜悅沒有延續(xù)到教室中，至少在最初時沒有。
伯利納回憶說：“一些人往往剛上大學(xué)不久，就會遇到麻煩，我就是其中之一。本來，我曾是一名物理學(xué)的優(yōu)等生，但是不知怎么一來，我走上了岔道。我一邊打工，一邊上學(xué)，終于攢夠了錢來付學(xué)費(fèi)，可以不再打工。這是一個關(guān)鍵性的錯誤，忽然間我有了很多時間，因此除了下國際象棋之外，我還打橋牌。很快地，我就成為華盛頓市15名最佳橋牌手之一。一切都砸了鍋。”
伯利納服完兵役后，想返回學(xué)校。他接著回憶說：“我未能完成物理學(xué)學(xué)業(yè)，因?yàn)槲业钠骄鶎W(xué)分太低，因此我轉(zhuǎn)修心理學(xué)。看來這是個廣闊的研究領(lǐng)域，因?yàn)槿切┯信d趣的事。”伯利納是從物理學(xué)轉(zhuǎn)來的，他期望能把事實(shí)歸納成理論，但是他失望地發(fā)現(xiàn)，情況恰好不是那樣。
1954年，伯利納結(jié)婚了，在家庭生活與新工作之余，幾乎沒有時間打橋牌，不過他還是想方設(shè)法繼續(xù)下國際象棋。他接著說道：“我在美國海軍研究實(shí)驗(yàn)室從事稱為人類工程的工作。那是非常嚴(yán)肅的工作，牽涉到心理學(xué)與物理學(xué)，與設(shè)備的設(shè)計(jì)有關(guān)。那是在1955年，當(dāng)時計(jì)算機(jī)剛剛問世，實(shí)驗(yàn)室里也造出一部。我曾修過一門程序設(shè)計(jì)課程，大概編寫過20行有關(guān)加數(shù)的程序，但是除此之外，我沒有接觸過計(jì)算機(jī)。”
“因?yàn)闆]有時間旅行去參加國際象棋比賽，我決定參加通信國際象棋活動。這又是另一項(xiàng)重大錯誤。它無休止地在棋盤上花去我更多的時間。隨后的13年內(nèi)，我參加了許多國際象棋的通信比賽，并且贏得了所有比賽。在世界通信錦標(biāo)賽中，我必須下16盤棋。我估計(jì)，要思考每一步棋，平均需要花去4個小時的時間，一盤棋大約需要走35步，這就意味著，要贏得該比賽冠軍，我要投入2，200多小時的時間。接著，我實(shí)際上還是放棄了該項(xiàng)比賽。”他考慮為了保持該項(xiàng)冠軍還得再花2，200多小時的時間，是很不值的。
1961年，伯利納進(jìn)了美國馬里蘭州貝塞斯達(dá)的國際商業(yè)機(jī)器公司（IBM），成為一名系統(tǒng)分析家，并且主要工作是面向軍界。雖然他在那里工作了8年，而且奮力進(jìn)取，升任了經(jīng)理，但他仍覺得這項(xiàng)工作得不償失：“如果你很認(rèn)真地工作，這是一種可怕的生活。作為一名經(jīng)理，你必須對上下都要負(fù)責(zé)任。你有一批人為你工作，但他們的確對工作毫不關(guān)心。還有一個家伙來自軍界，他其實(shí)什么都不懂，還對你指手畫腳，或提出一些無理要求。后來又有一個人接替了這個家伙的工作，他根本不知道第一個人想要什么，于是命令改變一切。我開始覺得，我所要做的工作應(yīng)該是，在我回首往事時，能使我感到驕傲的工作。我希望從事研究工作。”
伯利納繼續(xù)進(jìn)行用計(jì)算機(jī)遠(yuǎn)距離下棋的探索，但他看到進(jìn)展很慢，感到失望。在50年代期間，學(xué)者們曾做過樂觀的預(yù)測，但它與實(shí)驗(yàn)室內(nèi)的成功不相吻合；例如，1957年，美國卡內(nèi)基-梅隆大學(xué)現(xiàn)代諾貝爾榮譽(yù)獲得者羅伯特·西蒙就曾聲稱數(shù)字計(jì)算機(jī)將在10年內(nèi)成為世界的國際象棋冠軍。
計(jì)算機(jī)程序設(shè)計(jì)的重要性還沒有完全得到認(rèn)識。按照公眾的看法，國際象棋大師就像一種人類的計(jì)算機(jī)：當(dāng)他選擇一步棋時，他在心目中還要探索幾百步后續(xù)棋，如果我上了王前兵，那么他將同時攻我兩車，而后我將捉他的后……都以驚人準(zhǔn)確的閃電速度下棋。計(jì)算本來是計(jì)算機(jī)的主要功能，因此它們在國際象棋上似乎應(yīng)該是天生的冠軍。問題在于公眾的這種看法是錯誤的，對于國標(biāo)象棋大師來說，計(jì)算不是惟一的甚至不是成功的主要的秘訣。他們的成功更多地取決于對棋局的判斷，而不是研究那些令人頭痛的棋步。
荷蘭的心理學(xué)家安德里安·德格魯特發(fā)現(xiàn)，在典型的棋法中約有38步可能的法定棋步，而國際象棋大師平均只考慮其中的1．76棋步。換句話說，一位象棋大師通常根據(jù)自己曾經(jīng)下過或看到別人曾經(jīng)下過的成千上萬步棋，在他所能判斷的兩個候選棋步中進(jìn)行選擇，這種選擇對實(shí)現(xiàn)該棋步的眼下和長遠(yuǎn)目標(biāo)有利。美國的一位國際象棋特級大師威廉·隆巴迪老人曾經(jīng)寫道：“在實(shí)現(xiàn)目的之后，即取勝的布局轉(zhuǎn)變成為數(shù)學(xué)上的強(qiáng)力取勝的時刻，計(jì)算最為常見。”只要花一兩秒鐘，就能一眼認(rèn)出所熟悉的布局，這是象棋大師們在棋賽中具有驚人優(yōu)勢的根本原因。在動態(tài)的棋局中，簡直沒有時間進(jìn)行預(yù)測。
許多早期的計(jì)算機(jī)程序都只局限于考慮選擇候選棋步的數(shù)量（盡管它根本就不會是1．76這么小的數(shù)）。應(yīng)用選擇搜索方法的問題在于沒有人知道如何用計(jì)算機(jī)語言，更不用說是用英語，來表示用于選擇候選棋步的一般失效保險原理。 1966年，由美國麻省理工學(xué)院的理查德·格林布拉特研究的早期選擇搜索程序MacHack最為成功，它已成為在比賽中擊敗人類棋手（即使是最弱的一名棋手）的第一部國際象棋計(jì)算機(jī)。MacHack程序還有幸駁倒了休伯特·德賴弗斯的看法，德賴弗斯是《計(jì)算機(jī)不能做些什么》一書的作者，他曾靠貶低計(jì)算機(jī)的能力而出了名。
然而MacHack的功能一般說來還有嚴(yán)重的缺陷。雖然它在下棋時能夠勝任持續(xù)時間很長的棋局，但它還是易于突然犯下某種可笑的錯誤，而這種錯誤多少是由編入該計(jì)算機(jī)程序的象棋原理造成的。此外，它有時也會對某些巧妙但卻顯然違背了象棋原理的棋步視而不見。但是它已在比賽中擊敗了人類棋手，因而是計(jì)算機(jī)國際象棋的里程碑。
伯利納回憶說：“我的上帝！當(dāng)我聽到有關(guān)MacHack程序取得勝利的消息時，我認(rèn)為，盡管計(jì)算機(jī)國際象棋受到如此冷遇，盡管人們做了種種努力卻收效甚微，但還是有希望的。我去拜訪格林布拉特先生，雖然我還不完全理解計(jì)算機(jī)真的會按他所希望的去做，但我還是留下了深刻的印象。由于我離了婚，還沒有再婚，我又一次有了許多時間，因而我自學(xué)計(jì)算機(jī)程序設(shè)計(jì)，并花去許多晚上和周末時間編寫計(jì)算機(jī)國際象棋程序。我向美國國際商業(yè)機(jī)器公司申請讓我到該公司在紐約的約克頓海特斯研究機(jī)構(gòu)中從事計(jì)算機(jī)國際象棋的工作。他們答復(fù)說：'我們不資助這類項(xiàng)目。而且，你還沒有博士學(xué)位，因此，如果你能做些對公司有益的其他事的話，我們頂多讓你稍微做一點(diǎn)這方面的工作。’”
“我認(rèn)為，要達(dá)到我的目的，惟一的途徑是獲得博士學(xué)位，以便進(jìn)入該公司。我對自己的基本情況很自負(fù)。我向幾個學(xué)校提出了申請，但只有卡內(nèi)基-梅隆大學(xué)接受我。”他在1968年獲得世界通信國際象棋比賽冠軍的勝利顯然有助于他進(jìn)入該校。
“因此，我是在1969年秋季40歲時成為一名學(xué)生的。這對我是多么大的震驚。我覺得我需要學(xué)習(xí)的東西實(shí)在太多了，像自動化理論、各種不同的程序設(shè)計(jì)語言、多種多樣的硬件配置、以及人工智能本身等等。”伯利納早年在高等學(xué)校中不喜歡的許多課程，現(xiàn)在反而都要修讀它們。
在卡內(nèi)基-梅隆大學(xué)時，伯利納繼續(xù)進(jìn)行他在國際商業(yè)機(jī)器公司空余時間內(nèi)開始的計(jì)算機(jī)程序設(shè)計(jì)工作。1970年，在美國紐約市舉行的第一屆美國計(jì)算機(jī)國際象棋錦標(biāo)賽上，一種叫做J．Biit的計(jì)算機(jī)程序（其英文發(fā)音與“正好由于它在那兒”的英文首字母縮寫詞的發(fā)音相近）做出相當(dāng)不錯的表演。J．Biit程序也和MacHack程序一樣，用選擇搜索法工作。該程序的實(shí)力就是它的估值函數(shù)，即它所考慮每步棋的實(shí)力強(qiáng)弱如何都以數(shù)值來權(quán)衡，但是由于它是選擇性搜索，因此有時甚至都不考慮某種正確棋步，更不用說去走它了。伯利納說道：“在某些具體情況下，它很有下棋的才華。但是這還不夠。在所有不同類型的棋局中，你都必須是始終如一的正確。J．Biit程序還不具備強(qiáng)大的實(shí)力，足以成功地應(yīng)付整盤比賽。”
在第一屆美國計(jì)算機(jī)國際象棋錦標(biāo)賽上，J，Biit程序敗于國際象棋3．0程序，后者是美國西北大學(xué)研究生戴維·斯萊特和勞倫斯·阿特金設(shè)計(jì)的。3．0程序的后來版本執(zhí)行的不是選擇搜索法，而是全方位搜索法：對所有可能的續(xù)步進(jìn)行徹底的分析，一直到規(guī)定的某種深度。雖然全方位搜索法總是包含它看到的候選棋步中的正確棋步（因?yàn)樗吹搅怂衅宀剑。谶x擇一步棋時效率卻很低。很多時間都浪費(fèi)在令人吃驚地探索無價值的棋步上，即使是最笨的人類推木式棋手對此也不會給予片刻的考慮。要是計(jì)算機(jī)能夠看清博弈的最后結(jié)局，比方說像它能夠在三連棋中所做的那樣，那么，這些無用的努力將是毫無意義的。
國際象棋的數(shù)學(xué)可以證明全方位搜索的低效性。在人類國際象棋大師之間的對弈，典型的是對弈了84著棋（1著棋即指定的一方走一步棋）。由于每個棋位平均有38步法定棋步，因此窮舉搜索法必須考慮3884個可能的棋位。那是一個龐大的數(shù)字：3884大于10132，即1的后面有132個0。宇宙已經(jīng)存在了大約1018秒，因此，即使讓計(jì)算機(jī)能夠工作像宇宙年齡那么長的時間，每秒鐘也要分析10114個國標(biāo)象棋棋位，才能看清博弈的結(jié)局。
在國際象棋比賽中，計(jì)算機(jī)也和人一樣，不允許進(jìn)行無限期的思考；40步棋大約只能給定120分鐘，每步棋平均3分鐘。即使計(jì)算機(jī)減小了胃口，僅探索出后續(xù)幾步棋所有可能的棋步，數(shù)學(xué)上也是不允許的。在只走兩著棋之后，即每方各走一步棋之后，可能的棋勢數(shù)就會超過1，000。而走了4著棋之后，就可能有超過100萬可能的棋勢。
計(jì)算機(jī)不僅生成所有這些棋勢，而且還要求出它們的值。計(jì)算機(jī)是通過數(shù)值加權(quán)的方法來相當(dāng)粗略地達(dá)到上述目的，諸如考慮實(shí)力（即各方的子與兵的數(shù)量與特點(diǎn)）、機(jī)動性、中心方格與縱列的控制、兵的結(jié)構(gòu)、王的安全性、等等。比方說，在3分鐘結(jié)束時，無論走什么棋步都要使對手的潛在的最大增益降至最低的程度；這種策略，是從有關(guān)競賽的數(shù)學(xué)理論借鑒而來的，它設(shè)想對方可看出你所看出的一切，力求確保自身的利益。
如果不是發(fā)現(xiàn)了a－β算法，全方位搜索法即使只局限于幾著棋的深度，也是不實(shí)用的。a－β算法是一種巧妙的求值方法，可以讓計(jì)算機(jī)無需求出每種可能棋勢的值就能選擇它所要走的棋步。然而令人驚奇的是，所選擇的棋步正是計(jì)算機(jī)考慮了每一種續(xù)步后所要走的同一步棋。這怎么可能呢？
假設(shè)計(jì)算機(jī)首先在一定范圍內(nèi)探索稱之為A的某一特定棋步的所有后續(xù)棋步。設(shè)想兩方都走最佳的弈法，計(jì)算機(jī)給A定的極小極大值比方說為1。（在這種方案中，正值相當(dāng)于計(jì)算機(jī)所具有的優(yōu)勢，而負(fù)值相當(dāng)于計(jì)算機(jī)所處的劣勢。優(yōu)勢值為1，表示比對手多一兵，其他條件都相同。）現(xiàn)在，計(jì)算機(jī)開始對另一個叫做B的可選棋步求值，B是特別愚蠢的一步棋，表示將后置于可以立即被對手的弱兵捉住的方格中。如果計(jì)算機(jī)現(xiàn)在分析對手的正常應(yīng)著棋步——以兵捉后，并排除掉一種微小的可能性，即為了一次銳不可擋的進(jìn)攻而英勇犧牲了后，那么，計(jì)算機(jī)將定這個棋勢的數(shù)值為-9，它表示其對手已具有強(qiáng)大的優(yōu)勢。
求極小極大值
現(xiàn)代的計(jì)算機(jī)國際象棋靠的是極小極大值法：所走的棋步應(yīng)使對手的可能最大增益降至最小程度。假設(shè)計(jì)算機(jī)可選擇的棋步為A和B。它看出了對手對A的最佳反應(yīng)是走一步棋a（圖中的數(shù)目表示按照計(jì)算機(jī)的觀點(diǎn)所產(chǎn)生的棋勢的優(yōu)劣程度如何）。這時計(jì)算機(jī)又考慮棋步B，并看出了對手將應(yīng)以d，從而能保證時B取得比對A更好的結(jié)果。這時計(jì)算機(jī)有足夠理由選擇A，而對手反應(yīng)e或f的結(jié)果是什么都無關(guān)緊要。
計(jì)算機(jī)不需要考慮所有其他應(yīng)著棋步的結(jié)果，其中也包括對手不能吃后，因?yàn)橛?jì)算機(jī)已能識別對手的走棋路線是確保它自己對B步棋的應(yīng)步能優(yōu)于對A步棋的應(yīng)步。因此，計(jì)算機(jī)根據(jù)自己的觀點(diǎn)，知道走A步棋比走B步棋更為可取。
要有效地執(zhí)行a－β算法，計(jì)算機(jī)必須按順序考慮各種棋步：在上述例子中，它必須先檢驗(yàn)A，再檢驗(yàn)B，并且在分析B時，必須先檢驗(yàn)捉后的棋步，再考慮其他的應(yīng)步。審查各種棋步的順序取決于各種不同的探試法或一般經(jīng)驗(yàn)。
例如，捉子探試法指令程序?qū)δ切┥婕白阶拥母鞣N棋步給予最優(yōu)先考慮。（這樣捉子成為一著好棋的機(jī)會將更多一些，特別是如果被捉的子未受到保護(hù)時。這種方法還能幫助計(jì)算機(jī)減輕負(fù)擔(dān)，對機(jī)器大有稗益。而棋盤上少了一個子，計(jì)算機(jī)考慮的應(yīng)著棋步也就相應(yīng)減少。）
殺子探試法始終監(jiān)視著對手的哪一步棋被殺或被駁倒（一種特殊的棋步）。當(dāng)計(jì)算機(jī)仔細(xì)考慮了另一步棋時，首先要研究殺方的反應(yīng)?，F(xiàn)舉一特殊例子。計(jì)算機(jī)發(fā)現(xiàn)它所考慮的捉對方車的一步已被對手弈出將軍棋步所駁倒，在仔細(xì)考慮替代的棋步時，它將首先決定是否要走避免被將軍的棋步。換句話說，殺子探試法可用來識別并監(jiān)視這種威脅，這里所指的是能立即將軍的致命威脅。另一次探試優(yōu)先考慮那些能將軍的棋步，從而應(yīng)了一句古老的格言：“常將，就能將死。”簡單地說，這時計(jì)算機(jī)的做法就有些更像人了。
在全方位搜索法中，要是采用漸進(jìn)地深入考慮所有的續(xù)步，而不是每次一步地充分考慮這些續(xù)步，那么就能做到省時省事。從棋盤上的某種棋勢著手，首先分析所有可能的續(xù)步，然后分析某一特定的棋步，根據(jù)目前所進(jìn)行的搜索，就能看到最佳的一步棋。再從這步棋開始，對其余的所有續(xù)步進(jìn)行有效的分析，一直到兩著棋的深度，并且再次找到其中最佳的一步棋。這種過程叫做迭代深化法，它不斷重復(fù)下去，直到達(dá)到所期望的深度時為止。
有一種表記錄了計(jì)算機(jī)已經(jīng)求出值的棋勢、對這些棋勢所給定的數(shù)值、以及迄今已搜索到的最佳一步棋，通過這個表就可以提高全方位搜索法的有效性。在全方位搜索法中，各種棋勢都往往會不止一次地出現(xiàn)，只要程序設(shè)計(jì)好，查找所求的數(shù)值的時間自然比重新計(jì)算的時間少，因此，這種表在節(jié)省時間方面是很有用的。
在70年代，美國西北大學(xué)的斯萊特和阿特金已能夠利用變最大為最小求值法、a－β算法、捉子探試法與殺子探試法、迭代深化法和已經(jīng)檢驗(yàn)過的棋勢表等各種方法成功地用國際象棋3．0程序的后來版本進(jìn)行工作，而且，它也像圖靈的紙上下棋機(jī)一樣，深入地搜索了下國際象棋的戰(zhàn)術(shù)棋路，直到走到走不動的棋勢為止。這就是國際象棋4．7程序，它下國際象棋的能力略低于國際象棋大師的水平。
1981年，全方位搜索程序Belle由美國電話電報公司貝爾實(shí)驗(yàn)室的肯·湯姆森和喬·康登共同開發(fā)出來，它已成為第一部達(dá)到國際象棋大師級水平的計(jì)算機(jī)，進(jìn)入全美國際象棋比賽最高棋手1％的行列。Belle程序的成功應(yīng)歸功于專為進(jìn)行國際象棋運(yùn)算而定制的硬件。華盛頓的官員顯然很重視Belle程序。1981年，當(dāng)湯姆森和康登試圖攜帶Belle程序去蘇聯(lián)莫斯科參加國際象棋表演比賽時，聯(lián)邦局人員拘捕了他們。里根當(dāng)局擔(dān)心該程序會泄露軍事秘密。而湯姆森卻堅(jiān)持認(rèn)為，Belle程序所知道的事情只是如何去下國際象棋。湯姆森告訴新聞界說：“在軍事上可以使用Belle程序的惟一方式就是可以把它從飛機(jī)中扔出，也許你可以以此殺死某一個人。”這些日子，華盛頓已不大注意了，因?yàn)?/span>Belle程序的等級已滑落在國際象棋大師的水平之下，然而它仍然可以探索平均8著棋的深度，每秒鐘分析120，000種棋勢，弈出比較難對付的國際象棋。
當(dāng)斯萊特、阿特金、湯姆森、康登及其他人應(yīng)用全方位搜索法進(jìn)行工作時，伯利納卻集中精力于求值函數(shù)上。伯利納回憶說：“當(dāng)時我正考慮德格魯特關(guān)于國際象棋大師怎樣弈棋的著名的研究——他們?nèi)绾斡^察弈至一半的棋局變化，然后如何轉(zhuǎn)向考慮別的方面，再如何回到考慮最初的棋局變化。看來那是正確的。至少那是我所考慮的如何下棋的方法。”另一方面，現(xiàn)有的計(jì)算機(jī)下國際象棋的程序，不會在變化中來回移動。它們隨著特定的變化到達(dá)一定的深度，給最后的棋勢求出數(shù)值，再轉(zhuǎn)到另一種變化。
伯利納接著說：“給定某一具體值的困難在于你不能出錯。你可以弈出犧牲兩子兵，以換取具有極強(qiáng)攻擊力的棋勢。如果你使用類似α-β的算法，你就能夠弈出最后一種棋勢，對此你必須賦值；要么為換取攻勢值得拋棄兩兵子，要么就不值得。無論你持哪種看法，都會在一定時間內(nèi)出現(xiàn)錯誤。更確切地說，'我還不能肯定。我已經(jīng)丟掉兩兵但擁有強(qiáng)攻勢。也許實(shí)際上我可以將死王或者贏回的多于兩兵，而我也許只是丟了兩兵’，所以你先擺出問題，再進(jìn)一步深入研究，看你能否解決它。”
“對于這類問題以及如何把計(jì)算機(jī)程序編寫得更深入，我思考得很多。一個晚上，我忽然有一靈感：對于一種棋勢，可以給定一個值，為什么不能以一系列的值取而代之？”
一系列值中最高值意味著棋勢處于最佳狀態(tài)，而最低值則相當(dāng)于可能出現(xiàn)最壞的情況，計(jì)算機(jī)程序要對一系列值而不是對單一值進(jìn)行比較，而且當(dāng)這些值的范圍太寬時，它還可以比較深入地考慮棋勢，以便把最高值和最低值都包括進(jìn)去。伯利納說道：“這種想法是遺漏的組成要素。它是許多不可思議的事物之一，這類事在科學(xué)上隔一段時間就發(fā)生一次。你提出某一方案，那么突然間，一切都迎刃而解了。”使用系列值的想法已經(jīng)成為眾所周知的B*算法（發(fā)音為“B-星”），而且伯利納還把它列為他的訣竅。
1975年，當(dāng)伯利納完成計(jì)算機(jī)國際象棋博士論義時，他決定為計(jì)算機(jī)編寫下15子棋的程序，這種棋是他最近向新岳父學(xué)習(xí)的。他發(fā)現(xiàn)15子棋對研究求值法是一個很吸引人的領(lǐng)域，因?yàn)樵谶@種棋中進(jìn)行搜索，不會讓你探索得太深。在典型的15子棋棋勢中，約有400多種可能性（21組擲骰點(diǎn)數(shù)和每組點(diǎn)數(shù)的約20種走棋法），與之相比，在典型的國際象棋棋勢中，則“僅有”38種可能性。
在15子棋的計(jì)算機(jī)程序BKG中，伯利納沒有沿用人工智能中按規(guī)則求值的一般做法，他注意到“在醫(yī)療診斷體系中，也許還有一種慣例，比如說，如果有一位患者，他有這樣那樣的疾病，而且其年齡已超過6周歲，那么可以給他以如此這般的治療。可是忽然間來了一位患同樣病的患者，但他的年齡僅為5周歲9個月，按照慣例，不能對他進(jìn)行那種治療。當(dāng)然，那是錯誤的。因?yàn)槟阏嬲枰紤]的不是黑白分明的年齡截止點(diǎn)，而是由于某種原因需要考慮諸如年齡、體重以及一般健康情況等因素的平緩函數(shù)。在上述特定病例中，可以開出降低劑量的藥方”。
“當(dāng)你首次設(shè)計(jì)智能系統(tǒng)時，這幾項(xiàng)考慮已不很重要了。它們遠(yuǎn)不及把基本信息輸進(jìn)計(jì)算機(jī)中那么重要。但是，如果你想與最佳的人競爭，那么你就不能按照一套完全不靈活的規(guī)則去工作。”
當(dāng)然，伯利納想以他的15子棋計(jì)算機(jī)程序與人類最佳棋手博奔，因此他沒有認(rèn)真地考慮較為慣用的方法，擯棄了把棋勢分為幾種類型而且每類都有不同求值函數(shù)的通則。相反，他卻依賴數(shù)學(xué)上的單一復(fù)雜函數(shù)，這個函數(shù)包括大約50個不同的變量，與具有不同程度重要性的特定部分相一致，其重要性取決于博弈階段。每個變量都由一個數(shù)值來替代，來衡量存在于已知棋勢中相應(yīng)特點(diǎn)的重要程度。這樣一來每個數(shù)都是加權(quán)的：它們都乘以另一個數(shù)，這個數(shù)稱為系數(shù)，用以表示對該點(diǎn)的特點(diǎn)所給予的注意力有多大（或多小）。隨著博弈進(jìn)程的變化，這些系數(shù)也平緩地變化著。
這種成功的方法叫做SNAC法（帶有應(yīng)用系數(shù)的非線性平緩函數(shù)法）。在SNAC法提出后，只有幾個月的時間，BKG程序就擊敗了人類15子棋冠軍選手，這顯然表明SNAC法是成功的。雖然BKG程序有一些擲骰子般的幸運(yùn)，而且也曾有過少量較小的錯誤，但它還是一個強(qiáng)勁的棋手。
伯利納根據(jù)他在計(jì)算機(jī)15子棋上獲得的成功，知道找到一種平緩變化的函數(shù)對國際象棋上的有效求值法也是很關(guān)鍵的。在這一點(diǎn)上，慣用的一種方法也與通則有關(guān)?？紤]一下王的棋勢。當(dāng)博弈到中盤時，你想把王躲藏在角落里，那里很可能少受騷擾。求值函數(shù)可以對王的實(shí)際位置與角落之間的棋盤方格進(jìn)行計(jì)數(shù)；這個數(shù)愈大時，你的處境也愈壞。然而，在弈至殘局時，那時只剩下幾個子，將死的危險性甚微，于是王應(yīng)該處于棋盤的中央，它在那里還可以起著很強(qiáng)的戰(zhàn)子作用。所以在殘局時，求值函數(shù)可以對王的實(shí)際位置與中央之間的間隔數(shù)進(jìn)行計(jì)數(shù)。如果你采用了如下通則：BKG程序在與人類的世界15子棋冠軍盧吉·維拉對弈時贏得了勝利
BKG程序在與維拉比賽的第一局中，擲出一個 4點(diǎn)和一個2點(diǎn)。這時，BKG程序（黑方）具有優(yōu)勢，但不得不留下一個暴露棋子。它走了9-5步和9-7步，在7點(diǎn)處，留有一個暴露棋子，它可能受到13組擲骰點(diǎn)數(shù)的攻擊。從表面上看，好像走5-1步和4-2步比較安全，在5點(diǎn)處留下一個暴露棋子，它只可能受到11組擲骰點(diǎn)數(shù)的攻擊，但這卻是糟糕的走法，因?yàn)樗?/span>9點(diǎn)處會留下兩子，當(dāng)它們必須走步時，就有可能成為后來的暴露棋子。
“當(dāng)棋盤上還有一定數(shù)目的子和兵時，棋局就是中盤，而當(dāng)其只有很少幾個子時，則是殘局”，那么，你幾乎要患精神分裂癥了。
伯利納接著說道：“你當(dāng)然不想這樣，棋勢是連續(xù)性的——中盤是逐步轉(zhuǎn)為殘局的。由于殘局的逐漸接近，你不再那么執(zhí)意要讓王走到角落，而是容許王緩慢地移到棋盤的中部。每當(dāng)人人都承認(rèn)殘局終于來到時，王應(yīng)該靠近棋盤的中央，而不是藏在角落里。”達(dá)到這一目的的方法是需要有一種緩慢變化的求值函數(shù)，而在中盤與殘局之間不應(yīng)有任意的差別，而且兩者也不應(yīng)有不同的求值函數(shù)。
BKG程序在與維拉最后一局的比賽中，如圖所示，擲出一個5點(diǎn)和一個1點(diǎn)。這時，BKG程序走出了引起轟動的13-8步和3-2步。如果BKG程序的暴露棋子中任何一子受到進(jìn)攻，那么它將有更多的時間去組成棋步，以阻止對方的棋子前進(jìn)。反之，如果它們未受攻擊，那么就能夠在本方棋盤中形成據(jù)點(diǎn)，使維拉的棋子更難于回到本方的棋盤中，然后再逃脫掉。
的信息而工作，太陽牌計(jì)算機(jī)是Hitech程序的國際象棋的知識源。
Hitech程序的成功秘訣在于它能更好地思考（由于Oracle程序）以及比呆板的對手快50％的求值速度（因?yàn)樗梢酝瑫r對一步以上的棋步順序求值）。Hitech程序執(zhí)行全方位搜索法，平均每秒可以觀察驚人的175，000種不同棋勢，換句話說，每步棋3分鐘內(nèi)可以均攤到3，000萬種棋勢分析。伯利納說道：“毫無疑問，人們要考慮3，000萬種棋勢需要花去他們一生的時間。”
Hitech程序的速度及其智力水平已使它成為世界上最高級的國際象棋程序，優(yōu)于幾乎全部的蘇聯(lián)人棋手。伯利納認(rèn)為， Hitech程序或其新一代程序在1990年的國際象棋對弈中擊敗人類棋王的可能性有50％。為了達(dá)到這一目的，它計(jì)劃把更多的知識輸進(jìn)Oracle程序，并使Hitech程序試用選擇搜索法，或許還得用B*算法。
Hitech程序下國際象棋能下得多好？就此而言，任何一種計(jì)算機(jī)在某項(xiàng)智能活動中究竟能有多好？伯利納說道：“我認(rèn)為，我們將會發(fā)現(xiàn)，在輸入計(jì)算機(jī)的一些信息開始與另一些信息相抵觸之前，你能輸入計(jì)算機(jī)的信息量是有限度的。”某些研究工作者試圖借助于一種信任系統(tǒng)，來消除這種可能性。計(jì)算機(jī)對相抵觸的信息不大注意，因?yàn)樗膩碓床豢煽俊?/span>
伯利納接著說道：“但是我不認(rèn)為信任系統(tǒng)就是答案。我認(rèn)為，我們需要制造一種學(xué)習(xí)機(jī)，把它擺在架子上，觀看錄像帶，并從基礎(chǔ)學(xué)起。開始，可能學(xué)得很慢。也許要花20年時間，才能達(dá)到成年人的理解水平，那也就很好了。如果所得到的成果是有價值的，那么學(xué)習(xí)機(jī)本身也是值得的。然而，我不會屏息不語。學(xué)習(xí)機(jī)最終必定會出現(xiàn)，不是在80年代，或許是在90年代
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點(diǎn)擊舉報。
