圍棋中電腦人智能技術
時間：2008-11-21 01:37:00
來源：UltraLAB圖形工作站方案網站
人氣：5355
作者：admin
電腦圍棋中的人工智能技術
摘要：本文通過研究幾個最出色的電腦圍棋程序，從認知科學的角度介紹了電腦圍棋，并特別針對電腦圍棋編程人員（或有意投身于此的程序員）揭示圍棋作為一個 認知科學研究領域的日益增長的重要性。對手談，Go4++，Many Faces of Go，Go Intellect 和Explorer幾個目前最優(yōu)秀的電腦圍棋程序，我們概括了它們用到的人工智能技術，必須面對的關鍵性挑戰(zhàn)和博弈樹搜索中牽涉的問題，以此揭示為什么計算機國際象棋技術不能被很好的移植到圍棋領域。
奇境小站 (WonderLand)1998.06 -- 2000.06 Webmaster: Kerry Jia
電腦圍棋中的人工智能技術 作者:Jay Burmeister 和 Janet Wiles
澳大利亞昆士蘭大學心理學與信息技術學院 jay@it.uq.edu.au http://www.psy.uq.edu.au/~jay/ 翻譯：Lookingfor
1． 挑戰(zhàn)圍棋的程序
作為正規(guī)游戲之一的圍棋領域，過去即便是應付一般的人類棋手計算機也難以有所作為。幾個一年一度的電腦圍棋賽事，如FOST杯賽為第一名提供2，000，000日元獎金，臺灣的應氏基金為第一個能在分先七番棋中擊敗頂尖職業(yè)棋手的圍棋程序許諾40萬美元的獎金。
最早以圍棋為對象把電腦圍棋納入研究工作是在1962年，盡管第一次由程序下一盤完整的棋是發(fā)生在1968年（Zobrist，1970）。隨著電腦圍棋 賽事的舉行和第一個商業(yè)程序的發(fā)放，電腦圍棋作為一個領域于80年代被正式創(chuàng)立，并在90年代變得興旺起來。目前活躍在電腦圍棋競賽中的頂尖程序有 Explorer，Go Intellect，Go4++，手談和The Many Faces of Go，它們的水平大致在4-8級之間。
2． 圍棋中的博弈樹搜索
二人完美信息博弈中典型的人工智能方法是搜索博弈樹以決定走哪一步。標準博弈樹搜索由四部分組成：
1．狀態(tài)表示，2．候選走法產生，3．確定目標狀態(tài)，以及4．一個確定相對優(yōu)勢狀態(tài)的靜態(tài)評估函數。有效的博弈樹剪枝方法（比如α-β）增強了程序的表現。
博弈樹這條途徑很成功，如我們在國際象棋程序中所看到的，基于典型的完全廣度α-β剪枝博弈樹搜索的程序甚至擊敗了世界冠軍。這一節(jié)我們從透視電腦圍棋的角度檢查博弈樹搜索的四個構件。
2.1 狀態(tài)表示
從完全信息的角度看，圍棋盤面有19X19的3次方格，每個交叉點要么空要么被黑子或白子占據。狀態(tài)空間的大?。ɡ缈赡艿奈恢脭担┦?的361次方（或 10的172次方），相比之下國際象棋大致為10的50次方而Othello棋為10的30次方（Allis，1994）。另外，博弈樹的大?。ɡ缈赡?nbsp;的博弈數）在10的575次方和10的620次方之間，對比國際象棋的10的123次方和Othello棋的10的55次方（Allis，1994）。 [Page]
由于空間的組合尺寸，用19X19格的形式嚴格表示狀態(tài)空間對人或機器來說都層次太低而不能有效使用。接下來的層面的描述是把正交的鄰接棋子組成串（或 鏈）。所有的程序把串搜集到更大的單元，然而沒有通用的處理方法——即便是對專業(yè)棋手來說——把串組合到更大的單元中。依靠他們的圍棋理論，程序員開發(fā)了 他們自己的啟發(fā)式，當串有效的連接在一起時用做評估之用（叫做模糊組或塊）。 #p#page_title#e#
另外，恰當層次的表示能改變對運行時子任務的依賴，例如，戰(zhàn)術分析，死活分析，或實地評估。
2.2 走子
棋手在禁止自殺和同型反復（劫）的規(guī)則限制下輪流把棋子投放在空的交叉點（包括角和邊）。象國際象棋一樣，圍棋在給定位置的上下文中只有所有合法走法中的 一部分是有效的。圍棋的平均分枝因子是很大的，大約是國際象棋的六倍（200對35，Burmeister & Wiles，1995）。
注意這個分枝因子在全盤中的考慮。而在某些情形下只有局部的考慮是重要的。例如，直接目標搜索被用來判斷通常只有一兩種可能走法卻可以多達60手深度的征子。
實際的走子是個復雜的問題：參見3.4部分。
2.3 目標狀態(tài)
圍棋的最終目標是獲得比對手更多的實地。有兩種方法用來爭取實地：建棋子城墻圍空以及用棋子包圍并吃掉敵方的棋串。實際上很難確定目標狀態(tài)，因為實地的獲 得是靠慢慢積累起來的（不象國際象棋那樣將軍的最終的目標是突然死亡并且集中在一個子上）。由于在接近終局前很難精確地計算實地，故啟發(fā)式估計用的較多。 這樣的啟發(fā)方式通常要歸并組件和指示領地安全潛力的（例如死活組和影響）次要目標（例如國際象棋里的材料優(yōu)勢）。
當對局雙方依次棄權時結束。棋手通常在沒有走法能增加所得和/或無論怎么走都會減少所得時選擇棄權。實際上，要確定對局結束（即何時棄權）是相當困難的。 人們下棋，計算結果時如果遇到有關死活的爭執(zhí)要通過繼續(xù)下直到最終結果出現。在電腦圍棋比賽中，如果程序出現算法不能解決的得分爭執(zhí)，計分就由組織比賽的 人員來做。
2.4 評估函數
在判斷盤面的形勢優(yōu)劣時棋塊的死活是個重要的考慮點。死活判斷是很費時間的，并且是典型的通過戰(zhàn)術搜索（參見3.5部分）或死活搜索（參見3.6部分）來 獲得的。有意思的是，另一評估棋塊死活的復雜之處在于它可能需要評估全盤的形勢：如果要一個棋塊在劫爭中是可活的（即它必須贏得打劫來使自己活下來），就 必須估算所有和對手相比用來決定棋塊死活的劫材的數量和大小。如果出現雙重或三重劫的形勢，打劫分析會變得更復雜
摘要：本文通過研究幾個最出色的電腦圍棋程序，從認知科學的角度介紹了電腦圍棋，并特別針對電腦圍棋編程人員（或有意投身于此的程序員）揭示圍棋作為一個 認知科學研究領域的日益增長的重要性。對手談，Go4++，Many Faces of Go，Go Intellect 和Explorer幾個目前最優(yōu)秀的電腦圍棋程序，我們概括了它們用到的人工智能技術，必須面對的關鍵性挑戰(zhàn)和博弈樹搜索中牽涉的問題，以此揭示為什么計算機國際象棋技術不能被很好的移植到圍棋領域。
奇境小站 (WonderLand)1998.06 -- 2000.06 Webmaster: Kerry Jia
電腦圍棋中的人工智能技術 作者:Jay Burmeister 和 Janet Wiles
澳大利亞昆士蘭大學心理學與信息技術學院 jay@it.uq.edu.au http://www.psy.uq.edu.au/~jay/ 翻譯：Lookingfor
1． 挑戰(zhàn)圍棋的程序
作為正規(guī)游戲之一的圍棋領域，過去即便是應付一般的人類棋手計算機也難以有所作為。幾個一年一度的電腦圍棋賽事，如FOST杯賽為第一名提供2，000，000日元獎金，臺灣的應氏基金為第一個能在分先七番棋中擊敗頂尖職業(yè)棋手的圍棋程序許諾40萬美元的獎金。
最早以圍棋為對象把電腦圍棋納入研究工作是在1962年，盡管第一次由程序下一盤完整的棋是發(fā)生在1968年（Zobrist，1970）。隨著電腦圍棋 賽事的舉行和第一個商業(yè)程序的發(fā)放，電腦圍棋作為一個領域于80年代被正式創(chuàng)立，并在90年代變得興旺起來。目前活躍在電腦圍棋競賽中的頂尖程序有 Explorer，Go Intellect，Go4++，手談和The Many Faces of Go，它們的水平大致在4-8級之間。
2． 圍棋中的博弈樹搜索
二人完美信息博弈中典型的人工智能方法是搜索博弈樹以決定走哪一步。標準博弈樹搜索由四部分組成：
1．狀態(tài)表示，2．候選走法產生，3．確定目標狀態(tài)，以及4．一個確定相對優(yōu)勢狀態(tài)的靜態(tài)評估函數。有效的博弈樹剪枝方法（比如α-β）增強了程序的表現。
博弈樹這條途徑很成功，如我們在國際象棋程序中所看到的，基于典型的完全廣度α-β剪枝博弈樹搜索的程序甚至擊敗了世界冠軍。這一節(jié)我們從透視電腦圍棋的角度檢查博弈樹搜索的四個構件。
2.1 狀態(tài)表示
從完全信息的角度看，圍棋盤面有19X19的3次方格，每個交叉點要么空要么被黑子或白子占據。狀態(tài)空間的大?。ɡ缈赡艿奈恢脭担┦?的361次方（或 10的172次方），相比之下國際象棋大致為10的50次方而Othello棋為10的30次方（Allis，1994）。另外，博弈樹的大?。ɡ缈赡?nbsp;的博弈數）在10的575次方和10的620次方之間，對比國際象棋的10的123次方和Othello棋的10的55次方（Allis，1994）。 [Page]
由于空間的組合尺寸，用19X19格的形式嚴格表示狀態(tài)空間對人或機器來說都層次太低而不能有效使用。接下來的層面的描述是把正交的鄰接棋子組成串（或 鏈）。所有的程序把串搜集到更大的單元，然而沒有通用的處理方法——即便是對專業(yè)棋手來說——把串組合到更大的單元中。依靠他們的圍棋理論，程序員開發(fā)了 他們自己的啟發(fā)式，當串有效的連接在一起時用做評估之用（叫做模糊組或塊）。 #p#page_title#e#
另外，恰當層次的表示能改變對運行時子任務的依賴，例如，戰(zhàn)術分析，死活分析，或實地評估。
2.2 走子
棋手在禁止自殺和同型反復（劫）的規(guī)則限制下輪流把棋子投放在空的交叉點（包括角和邊）。象國際象棋一樣，圍棋在給定位置的上下文中只有所有合法走法中的 一部分是有效的。圍棋的平均分枝因子是很大的，大約是國際象棋的六倍（200對35，Burmeister & Wiles，1995）。
注意這個分枝因子在全盤中的考慮。而在某些情形下只有局部的考慮是重要的。例如，直接目標搜索被用來判斷通常只有一兩種可能走法卻可以多達60手深度的征子。
實際的走子是個復雜的問題：參見3.4部分。
2.3 目標狀態(tài)
圍棋的最終目標是獲得比對手更多的實地。有兩種方法用來爭取實地：建棋子城墻圍空以及用棋子包圍并吃掉敵方的棋串。實際上很難確定目標狀態(tài)，因為實地的獲 得是靠慢慢積累起來的（不象國際象棋那樣將軍的最終的目標是突然死亡并且集中在一個子上）。由于在接近終局前很難精確地計算實地，故啟發(fā)式估計用的較多。 這樣的啟發(fā)方式通常要歸并組件和指示領地安全潛力的（例如死活組和影響）次要目標（例如國際象棋里的材料優(yōu)勢）。
當對局雙方依次棄權時結束。棋手通常在沒有走法能增加所得和/或無論怎么走都會減少所得時選擇棄權。實際上，要確定對局結束（即何時棄權）是相當困難的。 人們下棋，計算結果時如果遇到有關死活的爭執(zhí)要通過繼續(xù)下直到最終結果出現。在電腦圍棋比賽中，如果程序出現算法不能解決的得分爭執(zhí)，計分就由組織比賽的 人員來做。
2.4 評估函數
在判斷盤面的形勢優(yōu)劣時棋塊的死活是個重要的考慮點。死活判斷是很費時間的，并且是典型的通過戰(zhàn)術搜索（參見3.5部分）或死活搜索（參見3.6部分）來 獲得的。有意思的是，另一評估棋塊死活的復雜之處在于它可能需要評估全盤的形勢：如果要一個棋塊在劫爭中是可活的（即它必須贏得打劫來使自己活下來），就 必須估算所有和對手相比用來決定棋塊死活的劫材的數量和大小。如果出現雙重或三重劫的形勢，打劫分析會變得更復雜
評估的結果有時不確定，因為明確的死活定義在受限的戰(zhàn)術搜索里也許是不可能的，即一個絕對的死活回答可能超出了戰(zhàn)術或死活搜索的范圍。 [Page]
從復雜的類型分析看，由一個絕對位置來確定贏家是P空間難題（Lichtenstein & Sipser，1980），決定一個棋手能否左右輸贏需指數時間來完成（Robson，1983），由此也就不奇怪要用到啟發(fā)式了。這些理論結果顯示不存 在從一個絕對局勢出發(fā)決定領地結果的多項式時間算法。
3． 參賽程序里的博弈樹搜索和人工智能技術
當前活躍在各電腦圍棋賽事里的程序有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é)討論的博弈樹搜索和圍棋專用的人工智能技術：戰(zhàn)術搜索，死活搜索和勢函數，我們報告這些程序的細節(jié)。
3.1 位置表示
所有的程序都有子、串、塊的表示，確認串屬于某個組的典型方式是采用基于模式的啟發(fā)來確定串與串之間的關聯性。敵方（或塊）表示也被用在EX和GI 中，啟發(fā)式用來確定敵方的影響（GI）和領地區(qū)域（EX）。 #p#page_title#e#
盤面（例如棋塊、敵方）表示的對象屬性包括它們的死活狀態(tài)（也指安全性或生命力）、實地數、眼數和勢。某些情況下這些屬性值由戰(zhàn)術搜索決定。
MFG的表示方式中一些組件由評估函數控制（例如塊、聯接、眼、實地和勢）。Go4的盤面只是簡單的由評估函數（例如塊、眼、安全性、實地）來表示。
3.2 候選走法
通常，由模式或更常見的是由基于規(guī)則的專家系統(tǒng)產生候選走法。走子產生過程最后是通過（線性的或加權求和的）相加棋盤上所有點的參考值為合適的走法給出一個分值。全盤評估一般選最高得分點作為下一手的落子點。
不同程序由全局水平變量估值得出的候選走法數也有所不同：GI（陳，1997）有12手，MFG有10手，而Go4至少有50手。程序變量保持的規(guī)則數： EX大約100，MFG大約200。GI含有約20個走子算法，它們或者基于模式庫，或者基于面向目標的搜索，或者基于啟發(fā)式規(guī)則（可能含有大量的規(guī) 則）。
模式通常既包含低級信息也包含高級信息。低級信息與黑白子的位置有關，那些點必須是空著的，已經被子占據的點不在此列。高級信息則是關于氣的數量、安全 性、眼位和領地的信息。模式匹配不僅與子的配置匹配，而且跟包含在子或串里的任何高級需求有關。大量的模式匹配計算是很耗時的，并且由于棋盤上的對稱性而 變得更復雜。這已經導致了發(fā)展特殊算法來克服與模式匹配有關的問題（比如MFG的哈希函數，EX的串匹配）。
知識以不同的方式組合到程序當中：一些程序幾乎完全依據第一原則工作，另一些根據存儲的模式匹配當前位置。不同的程序其模式數量相差很大：Go4約有15 個；MFG大約2000個；而EX則在3000個左右。有些程序也包含開放的走法模式數據庫（定式）（例如，MFG含有約45，000個定式模式）。 [Page]
3.3 目標
多數情況下，大量的實地比起少量的實地加相應的外勢更合乎需要。盡管有時也存在著實地和外勢間地轉化（特別是在布局和中盤階段）。然而，雖然實地的啟發(fā)式 評估是可能的，實地依然不總是形勢優(yōu)劣最好的指示明燈。在對局的早期階段，占有大量的實地可能表明一種過于集中的形勢，從實地安全的角度看，這樣的形對對 局的后面階段或許是有害的。開局造就最大可能的勢而不是實地通常導致局末對更多實地的追求。外勢是可能用來確定形勢優(yōu)劣的子目標的一個例子。
用來確定形勢優(yōu)劣的大量子目標的相對優(yōu)先度在電腦圍棋中看來沒有一致性可言。典型的塊和實地的死活狀態(tài)（安全性）被包含在目標和子目標中。在手談中，戰(zhàn)術 手段是重點，而MFG集中在聯接性、眼和塊的生命力。Go4則好像完全貫注于聯接性上，幾乎任何東西都是從聯接概率圖上派生（直接或間接地）出來。
3.4 評估過程
評估圍棋的形勢是個很慢的過程（例如，比起國際象棋程序的每秒10,000-100,000次評估，MFG是以低于每秒10次的速度完成對整局棋不超過 10,000種全盤形勢的評估）。由于比賽時間的限制，程序執(zhí)行的全局評估數通常是有限的（例如，MFG在選擇下一步時全局的評估數不超過100）。
Go4的50種候選走法中每一個都通過一個六步的過程來評估：1.啟用一個聯接概率圖。對于盤面上的每一個黑子和白子，計算它與32個（實際的或假定的） 友好點的聯接概率（要處理大量的數據）。確定聯接性還要用到戰(zhàn)術搜索；2.棋塊由聯接圖和戰(zhàn)術搜索來確定；3.眼位（利用模式）由聯接性和棋塊數據確定； 4.眼位的數量確定了棋塊的安全性；5.每個子的安全性按聯接概率圖的比率輻射并在所有棋子上相加；6.黑白領地由輻射值估計。黑白領地的差別作為一個給 定走法的評估結果返回。 #p#page_title#e#
MFG的評估是個多步過程，并且在很大程度上依賴于戰(zhàn)術搜索。戰(zhàn)術搜索檢查所有少于四口和一部分有四口氣的串以確定是不是死串。戰(zhàn)術搜索也被用來鑒別聯接 性和眼位。在這一環(huán)節(jié)，串組成了棋塊。棋塊的生命力由基于死活的考慮（例如，聯接、眼位等）決定，并且用來確定黑白子在盤面每個點（在-50至+50的范 圍之間）行使控制的總量統(tǒng)計。在總和每個點的值的基礎上確定領地，給出最終的估計值。多達6輪的靜態(tài)搜索可以被執(zhí)行，有時用一個特殊的模式集找出能使形勢 穩(wěn)定下來的局部走法。
GI的評估用在做全局搜索時。如果所有候選走法中有一種走法的得分要明顯高于其它的走法，它就被選為要走的下一步。如果候選走法中有些走法的得分大致相 等，靠評估帶來方便的全局搜索決定選擇走哪一步。評估時，敵子的安全性是為盤上每個點指定一個在-64到+64之間的黑白控度的基礎，所有點的分值加起來 返回一個評估值。全局搜索檢查的步數不多于6到7步，搜索的深度不超過6層。
3.5 戰(zhàn)術搜索 [Page]
戰(zhàn)術搜索是有選擇的、面向目標的搜索，并且為一大堆目的而使用，包括確定串是死是活（Go4，MFG，EX，GI）、聯接是安全的還是可被切斷的 （Go4，MFG）、是否可以形成眼位（MFG）、產生候選走法（GI）和確定棋塊的死活（EX）。就是在全局的水平，戰(zhàn)術搜索也要用來做棋步產生和評 估。戰(zhàn)術評估和全盤評估有區(qū)別，這跟搜索的目標（例如，一個串的氣的數量）有關。由于時間上的制約，戰(zhàn)術搜索通常在節(jié)點數、枝因子和層的深度上受到限制。 因此，盡管象死活這類的問題通常被認為是戰(zhàn)術性的，棋子卻可以在戰(zhàn)略上就死去了，即使它們可能不能通過戰(zhàn)術手段被抓獲。由此，從圍棋評估的方方面面看，戰(zhàn) 術搜索只是一種啟發(fā)式裝備而已。
MFG提供了一個戰(zhàn)術搜索操作的很好的例證（通過“戰(zhàn)術家”）：每個有三口或更少的氣的串和許多有四口氣的串被“戰(zhàn)術家”檢查過。每個串檢查兩次，一次白 先走一次黑先走。“戰(zhàn)術家”決定一個串是否被抓（比如，即使它先走也不能活）、被威脅（比如，如果它先走則活，后走則死），或者是牢固的。“戰(zhàn)術家”依靠 簡單的啟發(fā)式（例如，氣數和聯接性）。
“戰(zhàn)術家”有兩個分離的走子器；一個執(zhí)行攻擊走法，一個執(zhí)行防衛(wèi)走法。走子器建議的走法按一些規(guī)則分類，這些規(guī)則包括二次氣（氣的氣）、切點和簡單的眼 形。一旦分類，根據依賴走法分類的質量的搜索的表現，一種α-β深度優(yōu)先搜索被派上用場。走子和分類解釋了多數時間依靠戰(zhàn)術搜索的原因。
戰(zhàn)術搜索直接針對目標并被限制一個最大節(jié)點數。抓子時這個限制是大約100，然而當只有一步可走時就不考慮這個限制。采用這種方式，可以毫不費力地確定征 子的勝方。根據第一層走子產生賦予走法的分值，一次搜索的節(jié)點數分配到樹枝中，因此不同的樹枝可能在不同的深度結束。每一成功的層的枝因子被“戰(zhàn)術家”逐 步強化；枝因子從第一層5降到第五層的1或2。
對局過程中，MFG作大約100,000-150,000次戰(zhàn)術搜索，以每秒2,000-2,500個節(jié)點的速度遍歷1.5-2百萬個節(jié)點。平均起來每次戰(zhàn)術搜索訪問約10-20個節(jié)點，盡管由于一些搜索因節(jié)點限制而終止，許多搜索訪問過節(jié)點數要少于5個。
3.6 死活搜索
不是所有的程序都做明確的死活分析，很多程序對此使用了戰(zhàn)術搜索。MFG用與它的戰(zhàn)術搜索過程類似的方式作死活分析，除了它是在塊上作死活分析而不是分析串。 #p#page_title#e#
一個靜態(tài)死活評估器在多步過程中確定每個塊的死活狀態(tài)，而沒有以從簡單的結構中進一步產生復雜結構的方式向前搜索。靜態(tài)死活評估器使用“戰(zhàn)術家”并且為棋塊中的每個合適的串至少調用兩次。
死活搜索是直接面向目標的（例如，拯救或殺死一個棋塊）。如果在一個特定點沒有獲得搜索目標，合適走法由死活搜索引擎自身的走法器產生，并繼續(xù)搜索。為了 在一次死活搜索期間確定目標是否已經達到，靜態(tài)死活評估器在每個點被調用。死活搜索引擎使用深度優(yōu)先α、β搜索，每一個特定的枝的搜索深度由啟發(fā)式決定。 搜索樹的大小是強制性的，通常可以達到7層的深度和20個節(jié)點的大小。死活搜索是很慢的，整棵樹要裝到緩存里以減少花在重復搜索上的開銷。死活搜索的緩慢 也意味著它不會被用在全盤評估中。 [Page]
3.7 勢函數
勢是一種圍棋概念，它表明了每一方棋子對空點的最大可能的控制潛力。通過確保開局時子力投放不過于集中，棋手在后面的對局中將取得最大限度獲得領地的機會。
勢通過勢函數建立可計算模型（Zobrist，1969；Ryder，1971；Chen，1989）。通常，子力以盤上每個點的輻射影響值的和（黑白子 輻射正負相反的值）對周邊的點施加輻射影響（MFG的黑白子的勢是分離的）。子力輻射按距離函數遞減：GI是2的距離次方分之一，MFG是距離分之一。但 過于依賴勢函數的程序表現不佳（EX和Go4不再使用勢函數，盡管Go4的輻射函數很象一個勢函數，EX采取另一些措施，象同色點或可聯接點的距離）。
應用勢的啟發(fā)包括確定聯接性和敵子（GI），以及確定領地（MFG）。MFG的塊勢初始值依賴于塊的強度等，強壯的塊比弱塊或將死的塊輻射更大的影響。這 也意味著死塊輻射負影響等，因為它對敵方有利。在MFG和GI中勢都沒有通過子輻射；MFG也沒有通過敵鏈輻射影響。
4． 討論
當前的圍棋程序都使用了一定量的“知識”。由于建立在設計者下棋成功經驗的啟發(fā)之上，每個程序都可被看作一種（可能是含蓄的）圍棋理論的一次以經驗為依據 的實驗。圍棋理論成立的關鍵要靠數據結構的選擇，因為它們決定了編碼不同類型知識的難易和應用這些知識的計算開銷。隨著程序員同時在圍棋和電腦圍棋方面獲 得技能，程序會有發(fā)展（例如，在過去的十五年中隨著 Fotland 的棋力從15級發(fā)展到2段，MFG也增長了棋力并且代碼長度增加到目前的4萬行）。程序的性能由它最弱的部件決定，而向程序增加新知識的難易是提高程序性 能的重要部分。
由此可見，電腦圍棋領域在關于怎樣構筑一個圍棋程序或者指配不同圍棋知識的優(yōu)先性（例如，Go4注重聯接性而MFG注重死活）方面還沒有一致性可言。必須 提到的一點是：關于人類是怎樣下圍棋的至今也沒個一致的說法，這是目前認知科學研究的一個課題（見Saito & Yoshikawa，1977，作為回顧）。這個領域的任何進展都會對圍棋理論有個直接的促進，并可能導致電腦圍棋程序算法的改進。
本文對目前比較成功的幾個程序作了比較。通過這項工作，我們在博弈樹搜索的框架內分析了圍棋，并通過對示例電腦圍棋編程的觀察把有關的問題暴露出來。這種 困難在電腦圍棋領域是常識，但在更為廣泛的人工智能范疇卻很少被人們認識和接受。圍棋全盤評估需要確定棋塊的死活狀態(tài)，不管是通過死活搜索還是戰(zhàn)術搜索， 評估是非常消耗計算資源的。缺乏快速有效的評估函數是電腦圍棋遭遇的一個基本問題，并且和巨大的樹枝因素、用戶和電腦比賽的實時需求（一般來說，相對于國 際象棋的每秒180步圍棋每秒只有24步）等攪和在一起。因此，計算機國際象棋通常要用到的完全廣度博弈樹搜索在電腦圍棋里是行不通的 #p#page_title#e#
除了所列出的圍棋領域固有的問題外，本文還探討當前的程序怎樣地處理這些問題，由此為未來的圍棋程序員提供一個跳板。請注意電腦圍棋是個商業(yè)的領域，程序 本身（不是學術論文）就是它的主要產品。跟其它的參考不同的是，這里報告的細節(jié)都已經通過個人交流征詢了（慷慨貢獻自己的知識的）程序作者本人的意見，并 且有相關的電腦圍棋郵件列表和FTP站點的信息為依據。 [Page]
電腦圍棋的挑戰(zhàn)性在于要擴展當前的圍棋理論或發(fā)展新理論——特別是與評估有關的，針對實時限制設計合適的數據結構和算法，解決知識瓶頸。目前還沒有一個有 力的程序使用學習技術，盡管有過幾次這樣的嘗試（如，Pell，1991；Schraudolph, Dayan & Sejnowski，1994；Donnelly, Corr & Crookes，1994）?；仡欉@些程序已經超出了本文的范圍，但我們推測這些程序也沒有成功，因為它們的設計者的含蓄的圍棋理論缺乏對圍棋復雜性的必 要理解。怎樣把學習能力賦予現有的程序（或者它們暗示的圍棋理論）是個等待解決的問題。
致謝
感謝Ken Chen、陳志行、David Fotland、Martin Muller 和Mick Reiss，他們向我們提供了有關程序的細節(jié)和對本文不無裨益的反饋。
參考文獻
Allis, V.Searching for solutions in games and artificial intelligence. PhD thesis, University of Limburg, Maastricht, 1994.
Burmeister, J.&Wiles, J. The challenge of Go as a domain for AI research: a comparison between Go and chess. In proceedings of the Third Australian and New Zealand Conference on Intelligent Information System, pages 181-186, Perth, November 1995. IEEE Western Australia Section.
Chen, K. Group Identification in Computer Go. In D.N.L.Levy and B.F.Beal, (eds), Heuristic Programming in Aritificial Intelligence: the First Computer Olympiad, pages 195-210. Ellis Horwood, Chichester, 1989.
Chen, K. The move decision process of Go Intellect. In David Erbach, editor, Computer Go, 14: 9-17, 1990.
Chen, K. Attack and defence. In H. J. Van den Herik and L. V. Allis,(ed)s, Heuristic Programming in Artificial Intelligence 3 - The Third Computer Olympiad, pages 146-156. Ellis Horwood, Chichester, 1992.
Donnelly, P., Corr, P., and Crookes, D. Evolving Go playing strategy in neurl networks, 1994. Available on the Internet at ftp://igs.nuri.net/Go/comp/egpsnn.ps.z. [Page]
Fotland, D. Knowledge representation in The Many Faces of Go,1993. Available on the Internet at ftp://igs.nuri.net/Go/comp/mfg.z. #p#page_title#e#
Lishtenstein, D. & Sipser, M. Go is polynomial-space hard. Journal of the ACM, 27(2):393-401, 1980.
Muller, M. Computer Go as a sum of local games: an application of combinatorial game theory. PhD thesis, Swiss Federal Institute of Technology Zurich, 1995.
Pell, B. Exploratory learning in the game of Go. In D. N. L. Levy and D.F. F. Beal,(eds), Heuristic Programming in Artificial Intelligence 2 - The Second Computer Olympiad, volume 2. Ellis Horwood, 1991
Robson, J. The complexity of Go. In R. E. A. Mason, (ed), Proceedings of the IFIP 9th World Computer Congress, pages 413-417, North Holland, 1983. IFIP, Elsevier Science Publishers.
Ryder, J. Heuristic analysis of large trees as generated in the game of Go. Phd thesis, Department of Computer Science, Standford University, 1971.
Saito, Y. & Yoshikawa, A. Go as a testbed for Cognitive Science studies. In IJCAI Workshop Proceedings Using Games as an Experimental Testbed for AI Research, 1997.
Schraudolph, N., Dayan, P. and Sejnowski, T. Temporal difference learning of position evaluation in the game of Go. In J. D. Cowan, G. Tesauro and J. Alspector, (eds), Advances in Neural Information Processing 6, pages 817-824. Morgan Kaufmann, San Francisco, 1994. Zorbrist, A. Amodel of visual organization for game Go. In Proceedings of the Spring Joint Computer Conference, 34: 103-112, 1969.
從復雜的類型分析看，由一個絕對位置來確定贏家是P空間難題（Lichtenstein & Sipser，1980），決定一個棋手能否左右輸贏需指數時間來完成（Robson，1983），由此也就不奇怪要用到啟發(fā)式了。這些理論結果顯示不存 在從一個絕對局勢出發(fā)決定領地結果的多項式時間算法。
3． 參賽程序里的博弈樹搜索和人工智能技術
當前活躍在各電腦圍棋賽事里的程序有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é)討論的博弈樹搜索和圍棋專用的人工智能技術：戰(zhàn)術搜索，死活搜索和勢函數，我們報告這些程序的細節(jié)。
3.1 位置表示
所有的程序都有子、串、塊的表示，確認串屬于某個組的典型方式是采用基于模式的啟發(fā)來確定串與串之間的關聯性。敵方（或塊）表示也被用在EX和GI 中，啟發(fā)式用來確定敵方的影響（GI）和領地區(qū)域（EX）。 #p#page_title#e#
盤面（例如棋塊、敵方）表示的對象屬性包括它們的死活狀態(tài)（也指安全性或生命力）、實地數、眼數和勢。某些情況下這些屬性值由戰(zhàn)術搜索決定。
MFG的表示方式中一些組件由評估函數控制（例如塊、聯接、眼、實地和勢）。Go4的盤面只是簡單的由評估函數（例如塊、眼、安全性、實地）來表示。
3.2 候選走法
通常，由模式或更常見的是由基于規(guī)則的專家系統(tǒng)產生候選走法。走子產生過程最后是通過（線性的或加權求和的）相加棋盤上所有點的參考值為合適的走法給出一個分值。全盤評估一般選最高得分點作為下一手的落子點。
不同程序由全局水平變量估值得出的候選走法數也有所不同：GI（陳，1997）有12手，MFG有10手，而Go4至少有50手。程序變量保持的規(guī)則數： EX大約100，MFG大約200。GI含有約20個走子算法，它們或者基于模式庫，或者基于面向目標的搜索，或者基于啟發(fā)式規(guī)則（可能含有大量的規(guī) 則）。
模式通常既包含低級信息也包含高級信息。低級信息與黑白子的位置有關，那些點必須是空著的，已經被子占據的點不在此列。高級信息則是關于氣的數量、安全 性、眼位和領地的信息。模式匹配不僅與子的配置匹配，而且跟包含在子或串里的任何高級需求有關。大量的模式匹配計算是很耗時的，并且由于棋盤上的對稱性而 變得更復雜。這已經導致了發(fā)展特殊算法來克服與模式匹配有關的問題（比如MFG的哈希函數，EX的串匹配）。
知識以不同的方式組合到程序當中：一些程序幾乎完全依據第一原則工作，另一些根據存儲的模式匹配當前位置。不同的程序其模式數量相差很大：Go4約有15 個；MFG大約2000個；而EX則在3000個左右。有些程序也包含開放的走法模式數據庫（定式）（例如，MFG含有約45，000個定式模式）。 [Page]
3.3 目標
多數情況下，大量的實地比起少量的實地加相應的外勢更合乎需要。盡管有時也存在著實地和外勢間地轉化（特別是在布局和中盤階段）。然而，雖然實地的啟發(fā)式 評估是可能的，實地依然不總是形勢優(yōu)劣最好的指示明燈。在對局的早期階段，占有大量的實地可能表明一種過于集中的形勢，從實地安全的角度看，這樣的形對對 局的后面階段或許是有害的。開局造就最大可能的勢而不是實地通常導致局末對更多實地的追求。外勢是可能用來確定形勢優(yōu)劣的子目標的一個例子。
用來確定形勢優(yōu)劣的大量子目標的相對優(yōu)先度在電腦圍棋中看來沒有一致性可言。典型的塊和實地的死活狀態(tài)（安全性）被包含在目標和子目標中。在手談中，戰(zhàn)術 手段是重點，而MFG集中在聯接性、眼和塊的生命力。Go4則好像完全貫注于聯接性上，幾乎任何東西都是從聯接概率圖上派生（直接或間接地）出來。
3.4 評估過程
評估圍棋的形勢是個很慢的過程（例如，比起國際象棋程序的每秒10,000-100,000次評估，MFG是以低于每秒10次的速度完成對整局棋不超過 10,000種全盤形勢的評估）。由于比賽時間的限制，程序執(zhí)行的全局評估數通常是有限的（例如，MFG在選擇下一步時全局的評估數不超過100）。
Go4的50種候選走法中每一個都通過一個六步的過程來評估：1.啟用一個聯接概率圖。對于盤面上的每一個黑子和白子，計算它與32個（實際的或假定的） 友好點的聯接概率（要處理大量的數據）。確定聯接性還要用到戰(zhàn)術搜索；2.棋塊由聯接圖和戰(zhàn)術搜索來確定；3.眼位（利用模式）由聯接性和棋塊數據確定； 4.眼位的數量確定了棋塊的安全性；5.每個子的安全性按聯接概率圖的比率輻射并在所有棋子上相加；6.黑白領地由輻射值估計。黑白領地的差別作為一個給 定走法的評估結果返回。 #p#page_title#e#
MFG的評估是個多步過程，并且在很大程度上依賴于戰(zhàn)術搜索。戰(zhàn)術搜索檢查所有少于四口和一部分有四口氣的串以確定是不是死串。戰(zhàn)術搜索也被用來鑒別聯接 性和眼位。在這一環(huán)節(jié)，串組成了棋塊。棋塊的生命力由基于死活的考慮（例如，聯接、眼位等）決定，并且用來確定黑白子在盤面每個點（在-50至+50的范 圍之間）行使控制的總量統(tǒng)計。在總和每個點的值的基礎上確定領地，給出最終的估計值。多達6輪的靜態(tài)搜索可以被執(zhí)行，有時用一個特殊的模式集找出能使形勢 穩(wěn)定下來的局部走法。
GI的評估用在做全局搜索時。如果所有候選走法中有一種走法的得分要明顯高于其它的走法，它就被選為要走的下一步。如果候選走法中有些走法的得分大致相 等，靠評估帶來方便的全局搜索決定選擇走哪一步。評估時，敵子的安全性是為盤上每個點指定一個在-64到+64之間的黑白控度的基礎，所有點的分值加起來 返回一個評估值。全局搜索檢查的步數不多于6到7步，搜索的深度不超過6層。
3.5 戰(zhàn)術搜索 [Page]
戰(zhàn)術搜索是有選擇的、面向目標的搜索，并且為一大堆目的而使用，包括確定串是死是活（Go4，MFG，EX，GI）、聯接是安全的還是可被切斷的 （Go4，MFG）、是否可以形成眼位（MFG）、產生候選走法（GI）和確定棋塊的死活（EX）。就是在全局的水平，戰(zhàn)術搜索也要用來做棋步產生和評 估。戰(zhàn)術評估和全盤評估有區(qū)別，這跟搜索的目標（例如，一個串的氣的數量）有關。由于時間上的制約，戰(zhàn)術搜索通常在節(jié)點數、枝因子和層的深度上受到限制。 因此，盡管象死活這類的問題通常被認為是戰(zhàn)術性的，棋子卻可以在戰(zhàn)略上就死去了，即使它們可能不能通過戰(zhàn)術手段被抓獲。由此，從圍棋評估的方方面面看，戰(zhàn) 術搜索只是一種啟發(fā)式裝備而已。
MFG提供了一個戰(zhàn)術搜索操作的很好的例證（通過“戰(zhàn)術家”）：每個有三口或更少的氣的串和許多有四口氣的串被“戰(zhàn)術家”檢查過。每個串檢查兩次，一次白 先走一次黑先走。“戰(zhàn)術家”決定一個串是否被抓（比如，即使它先走也不能活）、被威脅（比如，如果它先走則活，后走則死），或者是牢固的。“戰(zhàn)術家”依靠 簡單的啟發(fā)式（例如，氣數和聯接性）。
“戰(zhàn)術家”有兩個分離的走子器；一個執(zhí)行攻擊走法，一個執(zhí)行防衛(wèi)走法。走子器建議的走法按一些規(guī)則分類，這些規(guī)則包括二次氣（氣的氣）、切點和簡單的眼 形。一旦分類，根據依賴走法分類的質量的搜索的表現，一種α-β深度優(yōu)先搜索被派上用場。走子和分類解釋了多數時間依靠戰(zhàn)術搜索的原因。
戰(zhàn)術搜索直接針對目標并被限制一個最大節(jié)點數。抓子時這個限制是大約100，然而當只有一步可走時就不考慮這個限制。采用這種方式，可以毫不費力地確定征 子的勝方。根據第一層走子產生賦予走法的分值，一次搜索的節(jié)點數分配到樹枝中，因此不同的樹枝可能在不同的深度結束。每一成功的層的枝因子被“戰(zhàn)術家”逐 步強化；枝因子從第一層5降到第五層的1或2。
對局過程中，MFG作大約100,000-150,000次戰(zhàn)術搜索，以每秒2,000-2,500個節(jié)點的速度遍歷1.5-2百萬個節(jié)點。平均起來每次戰(zhàn)術搜索訪問約10-20個節(jié)點，盡管由于一些搜索因節(jié)點限制而終止，許多搜索訪問過節(jié)點數要少于5個。
3.6 死活搜索
不是所有的程序都做明確的死活分析，很多程序對此使用了戰(zhàn)術搜索。MFG用與它的戰(zhàn)術搜索過程類似的方式作死活分析，除了它是在塊上作死活分析而不是分析串。 #p#page_title#e#
一個靜態(tài)死活評估器在多步過程中確定每個塊的死活狀態(tài)，而沒有以從簡單的結構中進一步產生復雜結構的方式向前搜索。靜態(tài)死活評估器使用“戰(zhàn)術家”并且為棋塊中的每個合適的串至少調用兩次。
死活搜索是直接面向目標的（例如，拯救或殺死一個棋塊）。如果在一個特定點沒有獲得搜索目標，合適走法由死活搜索引擎自身的走法器產生，并繼續(xù)搜索。為了 在一次死活搜索期間確定目標是否已經達到，靜態(tài)死活評估器在每個點被調用。死活搜索引擎使用深度優(yōu)先α、β搜索，每一個特定的枝的搜索深度由啟發(fā)式決定。 搜索樹的大小是強制性的，通常可以達到7層的深度和20個節(jié)點的大小。死活搜索是很慢的，整棵樹要裝到緩存里以減少花在重復搜索上的開銷。死活搜索的緩慢 也意味著它不會被用在全盤評估中。 [Page]
3.7 勢函數
勢是一種圍棋概念，它表明了每一方棋子對空點的最大可能的控制潛力。通過確保開局時子力投放不過于集中，棋手在后面的對局中將取得最大限度獲得領地的機會。
勢通過勢函數建立可計算模型（Zobrist，1969；Ryder，1971；Chen，1989）。通常，子力以盤上每個點的輻射影響值的和（黑白子 輻射正負相反的值）對周邊的點施加輻射影響（MFG的黑白子的勢是分離的）。子力輻射按距離函數遞減：GI是2的距離次方分之一，MFG是距離分之一。但 過于依賴勢函數的程序表現不佳（EX和Go4不再使用勢函數，盡管Go4的輻射函數很象一個勢函數，EX采取另一些措施，象同色點或可聯接點的距離）。
應用勢的啟發(fā)包括確定聯接性和敵子（GI），以及確定領地（MFG）。MFG的塊勢初始值依賴于塊的強度等，強壯的塊比弱塊或將死的塊輻射更大的影響。這 也意味著死塊輻射負影響等，因為它對敵方有利。在MFG和GI中勢都沒有通過子輻射；MFG也沒有通過敵鏈輻射影響。
4． 討論
當前的圍棋程序都使用了一定量的“知識”。由于建立在設計者下棋成功經驗的啟發(fā)之上，每個程序都可被看作一種（可能是含蓄的）圍棋理論的一次以經驗為依據 的實驗。圍棋理論成立的關鍵要靠數據結構的選擇，因為它們決定了編碼不同類型知識的難易和應用這些知識的計算開銷。隨著程序員同時在圍棋和電腦圍棋方面獲 得技能，程序會有發(fā)展（例如，在過去的十五年中隨著 Fotland 的棋力從15級發(fā)展到2段，MFG也增長了棋力并且代碼長度增加到目前的4萬行）。程序的性能由它最弱的部件決定，而向程序增加新知識的難易是提高程序性 能的重要部分。
由此可見，電腦圍棋領域在關于怎樣構筑一個圍棋程序或者指配不同圍棋知識的優(yōu)先性（例如，Go4注重聯接性而MFG注重死活）方面還沒有一致性可言。必須 提到的一點是：關于人類是怎樣下圍棋的至今也沒個一致的說法，這是目前認知科學研究的一個課題（見Saito & Yoshikawa，1977，作為回顧）。這個領域的任何進展都會對圍棋理論有個直接的促進，并可能導致電腦圍棋程序算法的改進。
本文對目前比較成功的幾個程序作了比較。通過這項工作，我們在博弈樹搜索的框架內分析了圍棋，并通過對示例電腦圍棋編程的觀察把有關的問題暴露出來。這種 困難在電腦圍棋領域是常識，但在更為廣泛的人工智能范疇卻很少被人們認識和接受。圍棋全盤評估需要確定棋塊的死活狀態(tài)，不管是通過死活搜索還是戰(zhàn)術搜索， 評估是非常消耗計算資源的。缺乏快速有效的評估函數是電腦圍棋遭遇的一個基本問題，并且和巨大的樹枝因素、用戶和電腦比賽的實時需求（一般來說，相對于國 際象棋的每秒180步圍棋每秒只有24步）等攪和在一起。因此，計算機國際象棋通常要用到的完全廣度博弈樹搜索在電腦圍棋里是行不通的 #p#page_title#e#
除了所列出的圍棋領域固有的問題外，本文還探討當前的程序怎樣地處理這些問題，由此為未來的圍棋程序員提供一個跳板。請注意電腦圍棋是個商業(yè)的領域，程序 本身（不是學術論文）就是它的主要產品。跟其它的參考不同的是，這里報告的細節(jié)都已經通過個人交流征詢了（慷慨貢獻自己的知識的）程序作者本人的意見，并 且有相關的電腦圍棋郵件列表和FTP站點的信息為依據。 [Page]
電腦圍棋的挑戰(zhàn)性在于要擴展當前的圍棋理論或發(fā)展新理論——特別是與評估有關的，針對實時限制設計合適的數據結構和算法，解決知識瓶頸。目前還沒有一個有 力的程序使用學習技術，盡管有過幾次這樣的嘗試（如，Pell，1991；Schraudolph, Dayan & Sejnowski，1994；Donnelly, Corr & Crookes，1994）?；仡欉@些程序已經超出了本文的范圍，但我們推測這些程序也沒有成功，因為它們的設計者的含蓄的圍棋理論缺乏對圍棋復雜性的必 要理解。怎樣把學習能力賦予現有的程序（或者它們暗示的圍棋理論）是個等待解決的問題。
致謝
感謝Ken Chen、陳志行、David Fotland、Martin Muller 和Mick Reiss，他們向我們提供了有關程序的細節(jié)和對本文不無裨益的反饋。
參考文獻
Allis, V.Searching for solutions in games and artificial intelligence. PhD thesis, University of Limburg, Maastricht, 1994.
Burmeister, J.&Wiles, J. The challenge of Go as a domain for AI research: a comparison between Go and chess. In proceedings of the Third Australian and New Zealand Conference on Intelligent Information System, pages 181-186, Perth, November 1995. IEEE Western Australia Section.
Chen, K. Group Identification in Computer Go. In D.N.L.Levy and B.F.Beal, (eds), Heuristic Programming in Aritificial Intelligence: the First Computer Olympiad, pages 195-210. Ellis Horwood, Chichester, 1989.
Chen, K. The move decision process of Go Intellect. In David Erbach, editor, Computer Go, 14: 9-17, 1990.
Chen, K. Attack and defence. In H. J. Van den Herik and L. V. Allis,(ed)s, Heuristic Programming in Artificial Intelligence 3 - The Third Computer Olympiad, pages 146-156. Ellis Horwood, Chichester, 1992.
Donnelly, P., Corr, P., and Crookes, D. Evolving Go playing strategy in neurl networks, 1994. Available on the Internet at ftp://igs.nuri.net/Go/comp/egpsnn.ps.z. [Page]
Fotland, D. Knowledge representation in The Many Faces of Go,1993. Available on the Internet at ftp://igs.nuri.net/Go/comp/mfg.z. #p#page_title#e#
Lishtenstein, D. & Sipser, M. Go is polynomial-space hard. Journal of the ACM, 27(2):393-401, 1980.
Muller, M. Computer Go as a sum of local games: an application of combinatorial game theory. PhD thesis, Swiss Federal Institute of Technology Zurich, 1995.
Pell, B. Exploratory learning in the game of Go. In D. N. L. Levy and D.F. F. Beal,(eds), Heuristic Programming in Artificial Intelligence 2 - The Second Computer Olympiad, volume 2. Ellis Horwood, 1991
Robson, J. The complexity of Go. In R. E. A. Mason, (ed), Proceedings of the IFIP 9th World Computer Congress, pages 413-417, North Holland, 1983. IFIP, Elsevier Science Publishers.
Ryder, J. Heuristic analysis of large trees as generated in the game of Go. Phd thesis, Department of Computer Science, Standford University, 1971.
Saito, Y. & Yoshikawa, A. Go as a testbed for Cognitive Science studies. In IJCAI Workshop Proceedings Using Games as an Experimental Testbed for AI Research, 1997.
Schraudolph, N., Dayan, P. and Sejnowski, T. Temporal difference learning of position evaluation in the game of Go. In J. D. Cowan, G. Tesauro and J. Alspector, (eds), Advances in Neural Information Processing 6, pages 817-824. Morgan Kaufmann, San Francisco, 1994. Zorbrist, A. Amodel of visual organization for game Go. In Proceedings of the Spring Joint Computer Conference, 34: 103-112, 1969.
下一篇：沒有了
