國際象棋程序的逐步演進

回顧人工智能的發展史，棋類一直就是一個熱門領域，原因很簡單，因為下棋被稱為智力競技運動，所以通過棋類的勝負和等級分，可以很好地來對比和測量人工智能系統的智能水平。

偉大的香農，最早提出了利用計算機編寫國際象棋程序的設想，并于1950年發表了論文《為計算機編程下國際象棋》（Programming a computer for playing chess），其內容奠定了現代弈棋機的基礎。1956年，他在洛斯阿拉莫斯的MANIAC計算機上實現了一個國際象棋的下棋程序。在一篇關于計算機象棋的早期論文中，紐厄爾、西蒙和約翰·肖（John Cliff Shaw）提出：“如果一個人能夠設計出一臺成功的弈棋機，他似乎就滲入了人類智力活動的核心。”受這些大師們的激勵，無數的計算機專業人士、國際象棋棋手和各行業的業余愛好者開始研究和開發一代又一代的下棋系統，有些人追求勝負和獎金，有些人把下棋系統作為實驗工具，研究人類智能的工作原理。圖2.3是電腦象棋界的一次聚會，左四為香農，左三為肯·湯普森（Ken Thompson）。

人類思考棋類問題的核心智慧就是找到妙招，而找到妙招的關鍵就是推算出若干步之內無論對方如何應對，本方都處于局面變好的態勢。轉換到國際象棋程序編程，核心都必須有兩部分：博弈搜索和局面評估。

博弈搜索是一個招法（下一步棋）向著后續招法分叉，形成了一棵樹形結構，稱為博弈樹。最簡單的搜索法稱為暴力搜索法（Brute force）或者A（Alpha、阿爾法）方法，這種方法全面生成所有可能的招法，并選擇最優的一個，也就是盡可能對博弈樹窮盡搜索。另一種策略稱為B（Beta、貝塔）方法，基本思想是剔除某些樹枝。

暴力搜索法程序遇到的主要難題是博弈樹所包含的局面數量實在太多太多了。國際象棋每個局面平均有40步符合規則的著法。如果你對每步著法都考慮應著就會遇到40×40=1600個局面。而4步之后是250萬個，6步之后是41億個。平均一局棋大約走40回合80步，于是所有可能局面就有10的128次方個，這個數字遠遠多于已知宇宙世界的原子總數目（大約10的80次方）！

紐厄爾、西蒙和約翰·肖發展的Alpha-Beta算法可以從搜索樹中剔除相當大的部分而不影響最后結果。它的基本思想是，如果有些著法將自己引入了很差的局面，這個著法的所有后續著法就都不用繼續分析了。也就是說，如果有一個完美的局面評估方法，只要把最好的一個著法留下來就可以了。當然這種完美的評估方法不存在，不過只要有一個足夠好的評估方法，那么也可以在每一層分析時只保留幾個比較好的著法，這就大大減少了搜索法的負擔。Alpha-Beta算法和優秀人類棋手下棋時的思考過程已經非常接近了。

20世紀70年代，曾經創造UNIX系統的計算機行業大腕肯·湯普森開始進入電腦國際象棋領域，他和貝爾實驗室的同事喬·康登（Joe Condon）一起決定建造一臺專門用于下國際象棋的機器，他們把這臺機器叫作Belle，使用了價值大約2萬美元的幾百個芯片。Belle能夠每秒搜索大約18萬個局面，而當時的百萬美元級超級電腦只能搜索5000個。Belle在比賽中可以搜索八至九層那么深，是第一臺達到國際象棋大師級水平的計算機。從1980年到1983年它戰勝了所有其他電腦，贏得了世界電腦國際象棋競賽冠軍，直到被價錢貴上千倍的克雷巨型機（Cray X-MPs）取代。Belle的成功，開創了通過研發國際象棋專用芯片來提高搜索速度的道路。

湯普森的另一大貢獻是他整理的殘局庫，他在20世紀80年代就開始生成和儲存棋盤上剩四至五子的所有符合規則的殘局。一個典型的五子殘局，比如王雙象對王單馬，包含總數121萬個局面。電腦使用這些殘局數據庫，可以把每個殘局走得絕對完美，就像上帝一樣。

湯普森在20世紀80年代對搜索深度和棋力提高之間的關系做了非常有意義的試驗。他讓Belle象棋機自己跟自己下，但只有一方的搜索深度不斷增加，結果是，根據勝負比率，平均每增加一個搜索深度可大約換算成200個國際象棋等級分。由此推論，可以計算出搜索深度達到14層時，就達到了當時世界冠軍卡斯帕羅夫的水平，即2800分的等級分。當時計算機行業專家的推測是：要與人類世界冠軍爭奪冠軍，必須做一臺每秒運算10億次的電腦（對應于搜索到14層的深度）。

在評估局面方面，早期使用的是憑借經驗制定的簡單規則，后來這些規則逐漸增加，并逐漸加入人類優秀棋手評估棋局的思路。比如，卡內基梅隆大學的漢斯·伯利納（Hans Berliner）教授，他曾經是世界國際象棋通訊賽冠軍，他領導開發了20世紀80年代很強的“Hitech”下棋機，在他的局面評估方法中，局面好壞由50多個因素決定（例如子力、位置、王的安全等），每個因素則是一個變量，為每個變量賦予了一個加權系數，最后加權求和的大小就清晰地表明了當前局面的優劣。