David.Ko

摘要


本文通過研究幾個最出色的電腦圍棋程序，從認知科學的角度介紹了電腦圍棋，并特別針對電腦圍棋編程人員（或有意投身于此的程序員）揭示圍棋作為一個認知科學研究領(lǐng)域的日益增長的重要性。對手談，Go4++，Many Faces of Go，Go Intellect 和Explorer幾個目前最優(yōu)秀的電腦圍棋程序，我們概括了它們用到的人工智能技術(shù)，必須面對的關(guān)鍵性挑戰(zhàn)和博弈樹搜索中牽涉的問題，以此揭示為什么計算機國際象棋技術(shù)不能被很好的移植到圍棋領(lǐng)域。


1． 挑戰(zhàn)圍棋的程序
作為正規(guī)游戲之一的圍棋領(lǐng)域，過去即便是應付一般的人類棋手計算機也難以有所作為。幾個一年一度的電腦圍棋賽事，如FOST杯賽為第一名提供2，000，000日元獎金，臺灣的應氏基金為第一個能在分先七番棋中擊敗頂尖職業(yè)棋手的圍棋程序許諾40萬美元的獎金。
最早以圍棋為對象把電腦圍棋納入研究工作是在1962年，盡管第一次由程序下一盤完整的棋是發(fā)生在1968年（Zobrist，1970）。隨著電腦圍棋賽事的舉行和第一個商業(yè)程序的發(fā)放，電腦圍棋作為一個領(lǐng)域于80年代被正式創(chuàng)立，并在90年代變得興旺起來。目前活躍在電腦圍棋競賽中的頂尖程序有Explorer，Go Intellect，Go4++，手談和The Many Faces of Go，它們的水平大致在4-8級之間。

2． 圍棋中的博弈樹搜索
二人完美信息博弈中典型的人工智能方法是搜索博弈樹以決定走哪一步。標準博弈樹搜索由四部分組成：1．狀態(tài)表示，2．候選走法產(chǎn)生，3．確定目標狀態(tài)，以及4．一個確定相對優(yōu)勢狀態(tài)的靜態(tài)評估函數(shù)。有效的博弈樹剪枝方法（比如α-β）增強了程序的表現(xiàn)。
博弈樹這條途徑很成功，如我們在國際象棋程序中所看到的，基于典型的完全廣度α-β剪枝博弈樹搜索的程序甚至擊敗了世界冠軍。這一節(jié)我們從透視電腦圍棋的角度檢查博弈樹搜索的四個構(gòu)件。

2.1 狀態(tài)表示
從完全信息的角度看，圍棋盤面有19X19的3次方格，每個交叉點要么空要么被黑子或白子占據(jù)。狀態(tài)空間的大小（例如可能的位置數(shù)）是3的361次方（或10的172次方），相比之下國際象棋大致為10的50次方而Othello棋為10的30次方（Allis，1994）。另外，博弈樹的大小（例如可能的博弈數(shù)）在10的575次方和10的620次方之間，對比國際象棋的10的123次方和Othello棋的10的55次方（Allis，1994）。
由于空間的組合尺寸，用19X19格的形式嚴格表示狀態(tài)空間對人或機器來說都層次太低而不能有效使用。接下來的層面的描述是把正交的鄰接棋子組成串（或鏈）。所有的程序把串搜集到更大的單元，然而沒有通用的處理方法——即便是對專業(yè)棋手來說——把串組合到更大的單元中。依靠他們的圍棋理論，程序員開發(fā)了他們自己的啟發(fā)式，當串有效的連接在一起時用做評估之用（叫做模糊組或塊）。
另外，恰當層次的表示能改變對運行時子任務的依賴，例如，戰(zhàn)術(shù)分析，死活分析，或?qū)嵉卦u估。

2.2 走子
棋手在禁止自殺和同型反復（劫）的規(guī)則限制下輪流把棋子投放在空的交叉點（包括角和邊）。象國際象棋一樣，圍棋在給定位置的上下文中只有所有合法走法中的一部分是有效的。圍棋的平均分枝因子是很大的，大約是國際象棋的六倍（200對35，Burmeister & Wiles，1995）。
注意這個分枝因子在全盤中的考慮。而在某些情形下只有局部的考慮是重要的。例如，直接目標搜索被用來判斷通常只有一兩種可能走法卻可以多達60手深度的征子。
實際的走子是個復雜的問題：參見3.4部分。

2.3 目標狀態(tài)
圍棋的最終目標是獲得比對手更多的實地。有兩種方法用來爭取實地：建棋子城墻圍空以及用棋子包圍并吃掉敵方的棋串。實際上很難確定目標狀態(tài)，因為實地的獲得是靠慢慢積累起來的（不象國際象棋那樣將軍的最終的目標是突然死亡并且集中在一個子上）。由于在接近終局前很難精確地計算實地，故啟發(fā)式估計用的較多。這樣的啟發(fā)方式通常要歸并組件和指示領(lǐng)地安全潛力的（例如死活組和影響）次要目標（例如國際象棋里的材料優(yōu)勢）。
當對局雙方依次棄權(quán)時結(jié)束。棋手通常在沒有走法能增加所得和/或無論怎么走都會減少所得時選擇棄權(quán)。實際上，要確定對局結(jié)束（即何時棄權(quán)）是相當困難的。人們下棋，計算結(jié)果時如果遇到有關(guān)死活的爭執(zhí)要通過繼續(xù)下直到最終結(jié)果出現(xiàn)。在電腦圍棋比賽中，如果程序出現(xiàn)算法不能解決的得分爭執(zhí)，計分就由組織比賽的人員來做。

2.4 評估函數(shù)
在判斷盤面的形勢優(yōu)劣時棋塊的死活是個重要的考慮點。死活判斷是很費時間的，并且是典型的通過戰(zhàn)術(shù)搜索（參見3.5部分）或死活搜索（參見3.6部分）來獲得的。有意思的是，另一評估棋塊死活的復雜之處在于它可能需要評估全盤的形勢：如果要一個棋塊在劫爭中是可活的（即它必須贏得打劫來使自己活下來），就必須估算所有和對手相比用來決定棋塊死活的劫材的數(shù)量和大小。如果出現(xiàn)雙重或三重劫的形勢，打劫分析會變得更復雜。
評估的結(jié)果有時不確定，因為明確的死活定義在受限的戰(zhàn)術(shù)搜索里也許是不可能的，即一個絕對的死活回答可能超出了戰(zhàn)術(shù)或死活搜索的范圍。
從復雜的類型分析看，由一個絕對位置來確定贏家是P空間難題（Lichtenstein & Sipser，1980），決定一個棋手能否左右輸贏需指數(shù)時間來完成（Robson，1983），由此也就不奇怪要用到啟發(fā)式了。這些理論結(jié)果顯示不存在從一個絕對局勢出發(fā)決定領(lǐng)地結(jié)果的多項式時間算法。

3． 參賽程序里的博弈樹搜索和人工智能技術(shù)
當前活躍在各電腦圍棋賽事里的程序有Martin Muller（1995）的Explorer（EX），陳懇（陳，1989；1990；1992）的Go Intellect（GI），Michael Reiss 的Go4++（Go4），陳志行的HandTalk（HT）以及David Fotland 的Many Faces of Go（MFG）。針對第2節(jié)討論的博弈樹搜索和圍棋專用的人工智能技術(shù)：戰(zhàn)術(shù)搜索，死活搜索和勢函數(shù)，我們報告這些程序的細節(jié)。

3.1 位置表示
所有的程序都有子、串、塊的表示，確認串屬于某個組的典型方式是采用基于模式的啟發(fā)來確定串與串之間的關(guān)聯(lián)性。敵方（或塊）表示也被用在EX和GI 中，啟發(fā)式用來確定敵方的影響（GI）和領(lǐng)地區(qū)域（EX）。
盤面（例如棋塊、敵方）表示的對象屬性包括它們的死活狀態(tài)（也指安全性或生命力）、實地數(shù)、眼數(shù)和勢。某些情況下這些屬性值由戰(zhàn)術(shù)搜索決定。
MFG的表示方式中一些組件由評估函數(shù)控制（例如塊、聯(lián)接、眼、實地和勢）。Go4的盤面只是簡單的由評估函數(shù)（例如塊、眼、安全性、實地）來表示。

3.2 候選走法
通常，由模式或更常見的是由基于規(guī)則的專家系統(tǒng)產(chǎn)生候選走法。走子產(chǎn)生過程最后是通過（線性的或加權(quán)求和的）相加棋盤上所有點的參考值為合適的走法給出一個分值。全盤評估一般選最高得分點作為下一手的落子點。
不同程序由全局水平變量估值得出的候選走法數(shù)也有所不同：GI（陳，1997）有12手，MFG有10手，而Go4至少有50手。程序變量保持的規(guī)則數(shù)：EX大約100，MFG大約200。GI含有約20個走子算法，它們或者基于模式庫，或者基于面向目標的搜索，或者基于啟發(fā)式規(guī)則（可能含有大量的規(guī)則）。
模式通常既包含低級信息也包含高級信息。低級信息與黑白子的位置有關(guān)，那些點必須是空著的，已經(jīng)被子占據(jù)的點不在此列。高級信息則是關(guān)于氣的數(shù)量、安全性、眼位和領(lǐng)地的信息。模式匹配不僅與子的配置匹配，而且跟包含在子或串里的任何高級需求有關(guān)。大量的模式匹配計算是很耗時的，并且由于棋盤上的對稱性而變得更復雜。這已經(jīng)導致了發(fā)展特殊算法來克服與模式匹配有關(guān)的問題（比如MFG的哈希函數(shù)，EX的串匹配）。
知識以不同的方式組合到程序當中：一些程序幾乎完全依據(jù)第一原則工作，另一些根據(jù)存儲的模式匹配當前位置。不同的程序其模式數(shù)量相差很大：Go4約有15個；MFG大約2000個；而EX則在3000個左右。有些程序也包含開放的走法模式數(shù)據(jù)庫（定式）（例如，MFG含有約45，000個定式模式）。

3.3 目標 
多數(shù)情況下，大量的實地比起少量的實地加相應的外勢更合乎需要。盡管有時也存在著實地和外勢間地轉(zhuǎn)化（特別是在布局和中盤階段）。然而，雖然實地的啟發(fā)式評估是可能的，實地依然不總是形勢優(yōu)劣最好的指示明燈。在對局的早期階段，占有大量的實地可能表明一種過于集中的形勢，從實地安全的角度看，這樣的形對對局的后面階段或許是有害的。開局造就最大可能的勢而不是實地通常導致局末對更多實地的追求。外勢是可能用來確定形勢優(yōu)劣的子目標的一個例子。
用來確定形勢優(yōu)劣的大量子目標的相對優(yōu)先度在電腦圍棋中看來沒有一致性可言。典型的塊和實地的死活狀態(tài)（安全性）被包含在目標和子目標中。在手談中，戰(zhàn)術(shù)手段是重點，而MFG集中在聯(lián)接性、眼和塊的生命力。Go4則好像完全貫注于聯(lián)接性上，幾乎任何東西都是從聯(lián)接概率圖上派生（直接或間接地）出來。

3.4 評估過程
評估圍棋的形勢是個很慢的過程（例如，比起國際象棋程序的每秒10,000-100,000次評估，MFG是以低于每秒10次的速度完成對整局棋不超過10,000種全盤形勢的評估）。由于比賽時間的限制，程序執(zhí)行的全局評估數(shù)通常是有限的（例如，MFG在選擇下一步時全局的評估數(shù)不超過100）。
Go4的50種候選走法中每一個都通過一個六步的過程來評估：1.啟用一個聯(lián)接概率圖。對于盤面上的每一個黑子和白子，計算它與32個（實際的或假定的）友好點的聯(lián)接概率（要處理大量的數(shù)據(jù)）。確定聯(lián)接性還要用到戰(zhàn)術(shù)搜索；2.棋塊由聯(lián)接圖和戰(zhàn)術(shù)搜索來確定；3.眼位（利用模式）由聯(lián)接性和棋塊數(shù)據(jù)確定；4.眼位的數(shù)量確定了棋塊的安全性；5.每個子的安全性按聯(lián)接概率圖的比率輻射并在所有棋子上相加；6.黑白領(lǐng)地由輻射值估計。黑白領(lǐng)地的差別作為一個給定走法的評估結(jié)果返回。
MFG的評估是個多步過程，并且在很大程度上依賴于戰(zhàn)術(shù)搜索。戰(zhàn)術(shù)搜索檢查所有少于四口和一部分有四口氣的串以確定是不是死串。戰(zhàn)術(shù)搜索也被用來鑒別聯(lián)接性和眼位。在這一環(huán)節(jié)，串組成了棋塊。棋塊的生命力由基于死活的考慮（例如，聯(lián)接、眼位等）決定，并且用來確定黑白子在盤面每個點（在-50至+50的范圍之間）行使控制的總量統(tǒng)計。在總和每個點的值的基礎(chǔ)上確定領(lǐng)地，給出最終的估計值。多達6輪的靜態(tài)搜索可以被執(zhí)行，有時用一個特殊的模式集找出能使形勢穩(wěn)定下來的局部走法。
GI的評估用在做全局搜索時。如果所有候選走法中有一種走法的得分要明顯高于其它的走法，它就被選為要走的下一步。如果候選走法中有些走法的得分大致相等，靠評估帶來方便的全局搜索決定選擇走哪一步。評估時，敵子的安全性是為盤上每個點指定一個在-64到+64之間的黑白控度的基礎(chǔ)，所有點的分值加起來返回一個評估值。全局搜索檢查的步數(shù)不多于6到7步，搜索的深度不超過6層。

3.5 戰(zhàn)術(shù)搜索
戰(zhàn)術(shù)搜索是有選擇的、面向目標的搜索，并且為一大堆目的而使用，包括確定串是死是活（Go4，MFG，EX，GI）、聯(lián)接是安全的還是可被切斷的（Go4，MFG）、是否可以形成眼位（MFG）、產(chǎn)生候選走法（GI）和確定棋塊的死活（EX）。就是在全局的水平，戰(zhàn)術(shù)搜索也要用來做棋步產(chǎn)生和評估。戰(zhàn)術(shù)評估和全盤評估有區(qū)別，這跟搜索的目標（例如，一個串的氣的數(shù)量）有關(guān)。由于時間上的制約，戰(zhàn)術(shù)搜索通常在節(jié)點數(shù)、枝因子和層的深度上受到限制。因此，盡管象死活這類的問題通常被認為是戰(zhàn)術(shù)性的，棋子卻可以在戰(zhàn)略上就死去了，即使它們可能不能通過戰(zhàn)術(shù)手段被抓獲。由此，從圍棋評估的方方面面看，戰(zhàn)術(shù)搜索只是一種啟發(fā)式裝備而已。
MFG提供了一個戰(zhàn)術(shù)搜索操作的很好的例證（通過“戰(zhàn)術(shù)家”）：每個有三口或更少的氣的串和許多有四口氣的串被“戰(zhàn)術(shù)家”檢查過。每個串檢查兩次，一次白先走一次黑先走。“戰(zhàn)術(shù)家”決定一個串是否被抓（比如，即使它先走也不能活）、被威脅（比如，如果它先走則活，后走則死），或者是牢固的。“戰(zhàn)術(shù)家”依靠簡單的啟發(fā)式（例如，氣數(shù)和聯(lián)接性）。
“戰(zhàn)術(shù)家”有兩個分離的走子器；一個執(zhí)行攻擊走法，一個執(zhí)行防衛(wèi)走法。走子器建議的走法按一些規(guī)則分類，這些規(guī)則包括二次氣（氣的氣）、切點和簡單的眼形。一旦分類，根據(jù)依賴走法分類的質(zhì)量的搜索的表現(xiàn)，一種α-β深度優(yōu)先搜索被派上用場。走子和分類解釋了多數(shù)時間依靠戰(zhàn)術(shù)搜索的原因。
戰(zhàn)術(shù)搜索直接針對目標并被限制一個最大節(jié)點數(shù)。抓子時這個限制是大約100，然而當只有一步可走時就不考慮這個限制。采用這種方式，可以毫不費力地確定征子的勝方。根據(jù)第一層走子產(chǎn)生賦予走法的分值，一次搜索的節(jié)點數(shù)分配到樹枝中，因此不同的樹枝可能在不同的深度結(jié)束。每一成功的層的枝因子被“戰(zhàn)術(shù)家”逐步強化；枝因子從第一層5降到第五層的1或2。
對局過程中，MFG作大約100,000-150,000次戰(zhàn)術(shù)搜索，以每秒2,000-2,500個節(jié)點的速度遍歷1.5-2百萬個節(jié)點。平均起來每次戰(zhàn)術(shù)搜索訪問約10-20個節(jié)點，盡管由于一些搜索因節(jié)點限制而終止，許多搜索訪問過節(jié)點數(shù)要少于5個。

3.6 死活搜索
不是所有的程序都做明確的死活分析，很多程序?qū)Υ耸褂昧藨?zhàn)術(shù)搜索。MFG用與它的戰(zhàn)術(shù)搜索過程類似的方式作死活分析，除了它是在塊上作死活分析而不是分析串。
一個靜態(tài)死活評估器在多步過程中確定每個塊的死活狀態(tài)，而沒有以從簡單的結(jié)構(gòu)中進一步產(chǎn)生復雜結(jié)構(gòu)的方式向前搜索。靜態(tài)死活評估器使用“戰(zhàn)術(shù)家”并且為棋塊中的每個合適的串至少調(diào)用兩次。
死活搜索是直接面向目標的（例如，拯救或殺死一個棋塊）。如果在一個特定點沒有獲得搜索目標，合適走法由死活搜索引擎自身的走法器產(chǎn)生，并繼續(xù)搜索。為了在一次死活搜索期間確定目標是否已經(jīng)達到，靜態(tài)死活評估器在每個點被調(diào)用。死活搜索引擎使用深度優(yōu)先α、β搜索，每一個特定的枝的搜索深度由啟發(fā)式?jīng)Q定。搜索樹的大小是強制性的，通常可以達到7層的深度和20個節(jié)點的大小。死活搜索是很慢的，整棵樹要裝到緩存里以減少花在重復搜索上的開銷。死活搜索的緩慢也意味著它不會被用在全盤評估中。

3.7 勢函數(shù)
勢是一種圍棋概念，它表明了每一方棋子對空點的最大可能的控制潛力。通過確保開局時子力投放不過于集中，棋手在后面的對局中將取得最大限度獲得領(lǐng)地的機會。
勢通過勢函數(shù)建立可計算模型（Zobrist，1969；Ryder，1971；Chen，1989）。通常，子力以盤上每個點的輻射影響值的和（黑白子輻射正負相反的值）對周邊的點施加輻射影響（MFG的黑白子的勢是分離的）。子力輻射按距離函數(shù)遞減：GI是2的距離次方分之一，MFG是距離分之一。但過于依賴勢函數(shù)的程序表現(xiàn)不佳（EX和Go4不再使用勢函數(shù)，盡管Go4的輻射函數(shù)很象一個勢函數(shù)，EX采取另一些措施，象同色點或可聯(lián)接點的距離）。
應用勢的啟發(fā)包括確定聯(lián)接性和敵子（GI），以及確定領(lǐng)地（MFG）。MFG的塊勢初始值依賴于塊的強度等，強壯的塊比弱塊或?qū)⑺赖膲K輻射更大的影響。這也意味著死塊輻射負影響等，因為它對敵方有利。在MFG和GI中勢都沒有通過子輻射；MFG也沒有通過敵鏈輻射影響。

4． 討論
當前的圍棋程序都使用了一定量的“知識”。由于建立在設(shè)計者下棋成功經(jīng)驗的啟發(fā)之上，每個程序都可被看作一種（可能是含蓄的）圍棋理論的一次以經(jīng)驗為依據(jù)的實驗。圍棋理論成立的關(guān)鍵要靠數(shù)據(jù)結(jié)構(gòu)的選擇，因為它們決定了編碼不同類型知識的難易和應用這些知識的計算開銷。隨著程序員同時在圍棋和電腦圍棋方面獲得技能，程序會有發(fā)展（例如，在過去的十五年中隨著 Fotland 的棋力從15級發(fā)展到2段，MFG也增長了棋力并且代碼長度增加到目前的4萬行）。程序的性能由它最弱的部件決定，而向程序增加新知識的難易是提高程序性能的重要部分。
由此可見，電腦圍棋領(lǐng)域在關(guān)于怎樣構(gòu)筑一個圍棋程序或者指配不同圍棋知識的優(yōu)先性（例如，Go4注重聯(lián)接性而MFG注重死活）方面還沒有一致性可言。必須提到的一點是：關(guān)于人類是怎樣下圍棋的至今也沒個一致的說法，這是目前認知科學研究的一個課題（見Saito & Yoshikawa，1977，作為回顧）。這個領(lǐng)域的任何進展都會對圍棋理論有個直接的促進，并可能導致電腦圍棋程序算法的改進。
本文對目前比較成功的幾個程序作了比較。通過這項工作，我們在博弈樹搜索的框架內(nèi)分析了圍棋，并通過對示例電腦圍棋編程的觀察把有關(guān)的問題暴露出來。這種困難在電腦圍棋領(lǐng)域是常識，但在更為廣泛的人工智能范疇卻很少被人們認識和接受。圍棋全盤評估需要確定棋塊的死活狀態(tài)，不管是通過死活搜索還是戰(zhàn)術(shù)搜索，評估是非常消耗計算資源的。缺乏快速有效的評估函數(shù)是電腦圍棋遭遇的一個基本問題，并且和巨大的樹枝因素、用戶和電腦比賽的實時需求（一般來說，相對于國際象棋的每秒180步圍棋每秒只有24步）等攪和在一起。因此，計算機國際象棋通常要用到的完全廣度博弈樹搜索在電腦圍棋里是行不通的。
除了所列出的圍棋領(lǐng)域固有的問題外，本文還探討當前的程序怎樣地處理這些問題，由此為未來的圍棋程序員提供一個跳板。請注意電腦圍棋是個商業(yè)的領(lǐng)域，程序本身（不是學術(shù)論文）就是它的主要產(chǎn)品。跟其它的參考不同的是，這里報告的細節(jié)都已經(jīng)通過個人交流征詢了（慷慨貢獻自己的知識的）程序作者本人的意見，并且有相關(guān)的電腦圍棋郵件列表<computer-go@anu.edu.au>和FTP站點<ftp://igs.nuri.net/Go/comp/>的信息為依據(jù)。
電腦圍棋的挑戰(zhàn)性在于要擴展當前的圍棋理論或發(fā)展新理論——特別是與評估有關(guān)的，針對實時限制設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)和算法，解決知識瓶頸。目前還沒有一個有力的程序使用學習技術(shù)，盡管有過幾次這樣的嘗試（如，Pell，1991；Schraudolph, Dayan & Sejnowski，1994；Donnelly, Corr & Crookes，1994）。回顧這些程序已經(jīng)超出了本文的范圍，但我們推測這些程序也沒有成功，因為它們的設(shè)計者的含蓄的圍棋理論缺乏對圍棋復雜性的必要理解。怎樣把學習能力賦予現(xiàn)有的程序（或者它們暗示的圍棋理論）是個等待解決的問題。