圍棋中電腦人智能技術(shù)
時(shí)間：2008-11-21 01:37:00
來源：UltraLAB圖形工作站方案網(wǎng)站
人氣：4449
作者：admin
電腦圍棋中的人工智能技術(shù)
摘要：本文通過研究幾個(gè)最出色的電腦圍棋程序，從認(rèn)知科學(xué)的角度介紹了電腦圍棋，并特別針對(duì)電腦圍棋編程人員（或有意投身于此的程序員）揭示圍棋作為一個(gè) 認(rèn)知科學(xué)研究領(lǐng)域的日益增長(zhǎng)的重要性。對(duì)手談，Go4++，Many Faces of Go，Go Intellect 和Explorer幾個(gè)目前最優(yōu)秀的電腦圍棋程序，我們概括了它們用到的人工智能技術(shù)，必須面對(duì)的關(guān)鍵性挑戰(zhàn)和博弈樹搜索中牽涉的問題，以此揭示為什么計(jì)算機(jī)國(guó)際象棋技術(shù)不能被很好的移植到圍棋領(lǐng)域。
奇境小站 (WonderLand)1998.06 -- 2000.06 Webmaster: Kerry Jia
電腦圍棋中的人工智能技術(shù) 作者:Jay Burmeister 和 Janet Wiles
澳大利亞昆士蘭大學(xué)心理學(xué)與信息技術(shù)學(xué)院 jay@it.uq.edu.au http://www.psy.uq.edu.au/~jay/ 翻譯：Lookingfor
1． 挑戰(zhàn)圍棋的程序
作為正規(guī)游戲之一的圍棋領(lǐng)域，過去即便是應(yīng)付一般的人類棋手計(jì)算機(jī)也難以有所作為。幾個(gè)一年一度的電腦圍棋賽事，如FOST杯賽為第一名提供2，000，000日元獎(jiǎng)金，臺(tái)灣的應(yīng)氏基金為第一個(gè)能在分先七番棋中擊敗頂尖職業(yè)棋手的圍棋程序許諾40萬美元的獎(jiǎng)金。
最早以圍棋為對(duì)象把電腦圍棋納入研究工作是在1962年，盡管第一次由程序下一盤完整的棋是發(fā)生在1968年（Zobrist，1970）。隨著電腦圍棋 賽事的舉行和第一個(gè)商業(yè)程序的發(fā)放，電腦圍棋作為一個(gè)領(lǐng)域于80年代被正式創(chuàng)立，并在90年代變得興旺起來。目前活躍在電腦圍棋競(jìng)賽中的頂尖程序有 Explorer，Go Intellect，Go4++，手談和The Many Faces of Go，它們的水平大致在4-8級(jí)之間。
2． 圍棋中的博弈樹搜索
二人完美信息博弈中典型的人工智能方法是搜索博弈樹以決定走哪一步。標(biāo)準(zhǔn)博弈樹搜索由四部分組成：
1．狀態(tài)表示，2．候選走法產(chǎn)生，3．確定目標(biāo)狀態(tài)，以及4．一個(gè)確定相對(duì)優(yōu)勢(shì)狀態(tài)的靜態(tài)評(píng)估函數(shù)。有效的博弈樹剪枝方法（比如α-β）增強(qiáng)了程序的表現(xiàn)。
博弈樹這條途徑很成功，如我們?cè)趪?guó)際象棋程序中所看到的，基于典型的完全廣度α-β剪枝博弈樹搜索的程序甚至擊敗了世界冠軍。這一節(jié)我們從透視電腦圍棋的角度檢查博弈樹搜索的四個(gè)構(gòu)件。
2.1 狀態(tài)表示
從完全信息的角度看，圍棋盤面有19X19的3次方格，每個(gè)交叉點(diǎn)要么空要么被黑子或白子占據(jù)。狀態(tài)空間的大?。ɡ缈赡艿奈恢脭?shù)）是3的361次方（或 10的172次方），相比之下國(guó)際象棋大致為10的50次方而Othello棋為10的30次方（Allis，1994）。另外，博弈樹的大?。ɡ缈赡?nbsp;的博弈數(shù)）在10的575次方和10的620次方之間，對(duì)比國(guó)際象棋的10的123次方和Othello棋的10的55次方（Allis，1994）。 [Page]
由于空間的組合尺寸，用19X19格的形式嚴(yán)格表示狀態(tài)空間對(duì)人或機(jī)器來說都層次太低而不能有效使用。接下來的層面的描述是把正交的鄰接棋子組成串（或 鏈）。所有的程序把串搜集到更大的單元，然而沒有通用的處理方法——即便是對(duì)專業(yè)棋手來說——把串組合到更大的單元中。依靠他們的圍棋理論，程序員開發(fā)了 他們自己的啟發(fā)式，當(dāng)串有效的連接在一起時(shí)用做評(píng)估之用（叫做模糊組或塊）。 #p#page_title#e#
另外，恰當(dāng)層次的表示能改變對(duì)運(yùn)行時(shí)子任務(wù)的依賴，例如，戰(zhàn)術(shù)分析，死活分析，或?qū)嵉卦u(píng)估。
2.2 走子
棋手在禁止自殺和同型反復(fù)（劫）的規(guī)則限制下輪流把棋子投放在空的交叉點(diǎn)（包括角和邊）。象國(guó)際象棋一樣，圍棋在給定位置的上下文中只有所有合法走法中的 一部分是有效的。圍棋的平均分枝因子是很大的，大約是國(guó)際象棋的六倍（200對(duì)35，Burmeister & Wiles，1995）。
注意這個(gè)分枝因子在全盤中的考慮。而在某些情形下只有局部的考慮是重要的。例如，直接目標(biāo)搜索被用來判斷通常只有一兩種可能走法卻可以多達(dá)60手深度的征子。
實(shí)際的走子是個(gè)復(fù)雜的問題：參見3.4部分。
2.3 目標(biāo)狀態(tài)
圍棋的最終目標(biāo)是獲得比對(duì)手更多的實(shí)地。有兩種方法用來爭(zhēng)取實(shí)地：建棋子城墻圍空以及用棋子包圍并吃掉敵方的棋串。實(shí)際上很難確定目標(biāo)狀態(tài)，因?yàn)閷?shí)地的獲 得是靠慢慢積累起來的（不象國(guó)際象棋那樣將軍的最終的目標(biāo)是突然死亡并且集中在一個(gè)子上）。由于在接近終局前很難精確地計(jì)算實(shí)地，故啟發(fā)式估計(jì)用的較多。 這樣的啟發(fā)方式通常要?dú)w并組件和指示領(lǐng)地安全潛力的（例如死活組和影響）次要目標(biāo)（例如國(guó)際象棋里的材料優(yōu)勢(shì)）。
當(dāng)對(duì)局雙方依次棄權(quán)時(shí)結(jié)束。棋手通常在沒有走法能增加所得和/或無論怎么走都會(huì)減少所得時(shí)選擇棄權(quán)。實(shí)際上，要確定對(duì)局結(jié)束（即何時(shí)棄權(quán)）是相當(dāng)困難的。 人們下棋，計(jì)算結(jié)果時(shí)如果遇到有關(guān)死活的爭(zhēng)執(zhí)要通過繼續(xù)下直到最終結(jié)果出現(xiàn)。在電腦圍棋比賽中，如果程序出現(xiàn)算法不能解決的得分爭(zhēng)執(zhí)，計(jì)分就由組織比賽的 人員來做。
2.4 評(píng)估函數(shù)
在判斷盤面的形勢(shì)優(yōu)劣時(shí)棋塊的死活是個(gè)重要的考慮點(diǎn)。死活判斷是很費(fèi)時(shí)間的，并且是典型的通過戰(zhàn)術(shù)搜索（參見3.5部分）或死活搜索（參見3.6部分）來 獲得的。有意思的是，另一評(píng)估棋塊死活的復(fù)雜之處在于它可能需要評(píng)估全盤的形勢(shì)：如果要一個(gè)棋塊在劫爭(zhēng)中是可活的（即它必須贏得打劫來使自己活下來），就 必須估算所有和對(duì)手相比用來決定棋塊死活的劫材的數(shù)量和大小。如果出現(xiàn)雙重或三重劫的形勢(shì)，打劫分析會(huì)變得更復(fù)雜
摘要：本文通過研究幾個(gè)最出色的電腦圍棋程序，從認(rèn)知科學(xué)的角度介紹了電腦圍棋，并特別針對(duì)電腦圍棋編程人員（或有意投身于此的程序員）揭示圍棋作為一個(gè) 認(rèn)知科學(xué)研究領(lǐng)域的日益增長(zhǎng)的重要性。對(duì)手談，Go4++，Many Faces of Go，Go Intellect 和Explorer幾個(gè)目前最優(yōu)秀的電腦圍棋程序，我們概括了它們用到的人工智能技術(shù)，必須面對(duì)的關(guān)鍵性挑戰(zhàn)和博弈樹搜索中牽涉的問題，以此揭示為什么計(jì)算機(jī)國(guó)際象棋技術(shù)不能被很好的移植到圍棋領(lǐng)域。
奇境小站 (WonderLand)1998.06 -- 2000.06 Webmaster: Kerry Jia
電腦圍棋中的人工智能技術(shù) 作者:Jay Burmeister 和 Janet Wiles
澳大利亞昆士蘭大學(xué)心理學(xué)與信息技術(shù)學(xué)院 jay@it.uq.edu.au http://www.psy.uq.edu.au/~jay/ 翻譯：Lookingfor
1． 挑戰(zhàn)圍棋的程序
作為正規(guī)游戲之一的圍棋領(lǐng)域，過去即便是應(yīng)付一般的人類棋手計(jì)算機(jī)也難以有所作為。幾個(gè)一年一度的電腦圍棋賽事，如FOST杯賽為第一名提供2，000，000日元獎(jiǎng)金，臺(tái)灣的應(yīng)氏基金為第一個(gè)能在分先七番棋中擊敗頂尖職業(yè)棋手的圍棋程序許諾40萬美元的獎(jiǎng)金。
最早以圍棋為對(duì)象把電腦圍棋納入研究工作是在1962年，盡管第一次由程序下一盤完整的棋是發(fā)生在1968年（Zobrist，1970）。隨著電腦圍棋 賽事的舉行和第一個(gè)商業(yè)程序的發(fā)放，電腦圍棋作為一個(gè)領(lǐng)域于80年代被正式創(chuàng)立，并在90年代變得興旺起來。目前活躍在電腦圍棋競(jìng)賽中的頂尖程序有 Explorer，Go Intellect，Go4++，手談和The Many Faces of Go，它們的水平大致在4-8級(jí)之間。
2． 圍棋中的博弈樹搜索
二人完美信息博弈中典型的人工智能方法是搜索博弈樹以決定走哪一步。標(biāo)準(zhǔn)博弈樹搜索由四部分組成：
1．狀態(tài)表示，2．候選走法產(chǎn)生，3．確定目標(biāo)狀態(tài)，以及4．一個(gè)確定相對(duì)優(yōu)勢(shì)狀態(tài)的靜態(tài)評(píng)估函數(shù)。有效的博弈樹剪枝方法（比如α-β）增強(qiáng)了程序的表現(xiàn)。
博弈樹這條途徑很成功，如我們?cè)趪?guó)際象棋程序中所看到的，基于典型的完全廣度α-β剪枝博弈樹搜索的程序甚至擊敗了世界冠軍。這一節(jié)我們從透視電腦圍棋的角度檢查博弈樹搜索的四個(gè)構(gòu)件。
2.1 狀態(tài)表示
從完全信息的角度看，圍棋盤面有19X19的3次方格，每個(gè)交叉點(diǎn)要么空要么被黑子或白子占據(jù)。狀態(tài)空間的大?。ɡ缈赡艿奈恢脭?shù)）是3的361次方（或 10的172次方），相比之下國(guó)際象棋大致為10的50次方而Othello棋為10的30次方（Allis，1994）。另外，博弈樹的大?。ɡ缈赡?nbsp;的博弈數(shù)）在10的575次方和10的620次方之間，對(duì)比國(guó)際象棋的10的123次方和Othello棋的10的55次方（Allis，1994）。 [Page]
由于空間的組合尺寸，用19X19格的形式嚴(yán)格表示狀態(tài)空間對(duì)人或機(jī)器來說都層次太低而不能有效使用。接下來的層面的描述是把正交的鄰接棋子組成串（或 鏈）。所有的程序把串搜集到更大的單元，然而沒有通用的處理方法——即便是對(duì)專業(yè)棋手來說——把串組合到更大的單元中。依靠他們的圍棋理論，程序員開發(fā)了 他們自己的啟發(fā)式，當(dāng)串有效的連接在一起時(shí)用做評(píng)估之用（叫做模糊組或塊）。 #p#page_title#e#
另外，恰當(dāng)層次的表示能改變對(duì)運(yùn)行時(shí)子任務(wù)的依賴，例如，戰(zhàn)術(shù)分析，死活分析，或?qū)嵉卦u(píng)估。
2.2 走子
棋手在禁止自殺和同型反復(fù)（劫）的規(guī)則限制下輪流把棋子投放在空的交叉點(diǎn)（包括角和邊）。象國(guó)際象棋一樣，圍棋在給定位置的上下文中只有所有合法走法中的 一部分是有效的。圍棋的平均分枝因子是很大的，大約是國(guó)際象棋的六倍（200對(duì)35，Burmeister & Wiles，1995）。
注意這個(gè)分枝因子在全盤中的考慮。而在某些情形下只有局部的考慮是重要的。例如，直接目標(biāo)搜索被用來判斷通常只有一兩種可能走法卻可以多達(dá)60手深度的征子。
實(shí)際的走子是個(gè)復(fù)雜的問題：參見3.4部分。
2.3 目標(biāo)狀態(tài)
圍棋的最終目標(biāo)是獲得比對(duì)手更多的實(shí)地。有兩種方法用來爭(zhēng)取實(shí)地：建棋子城墻圍空以及用棋子包圍并吃掉敵方的棋串。實(shí)際上很難確定目標(biāo)狀態(tài)，因?yàn)閷?shí)地的獲 得是靠慢慢積累起來的（不象國(guó)際象棋那樣將軍的最終的目標(biāo)是突然死亡并且集中在一個(gè)子上）。由于在接近終局前很難精確地計(jì)算實(shí)地，故啟發(fā)式估計(jì)用的較多。 這樣的啟發(fā)方式通常要?dú)w并組件和指示領(lǐng)地安全潛力的（例如死活組和影響）次要目標(biāo)（例如國(guó)際象棋里的材料優(yōu)勢(shì)）。
當(dāng)對(duì)局雙方依次棄權(quán)時(shí)結(jié)束。棋手通常在沒有走法能增加所得和/或無論怎么走都會(huì)減少所得時(shí)選擇棄權(quán)。實(shí)際上，要確定對(duì)局結(jié)束（即何時(shí)棄權(quán)）是相當(dāng)困難的。 人們下棋，計(jì)算結(jié)果時(shí)如果遇到有關(guān)死活的爭(zhēng)執(zhí)要通過繼續(xù)下直到最終結(jié)果出現(xiàn)。在電腦圍棋比賽中，如果程序出現(xiàn)算法不能解決的得分爭(zhēng)執(zhí)，計(jì)分就由組織比賽的 人員來做。
2.4 評(píng)估函數(shù)
在判斷盤面的形勢(shì)優(yōu)劣時(shí)棋塊的死活是個(gè)重要的考慮點(diǎn)。死活判斷是很費(fèi)時(shí)間的，并且是典型的通過戰(zhàn)術(shù)搜索（參見3.5部分）或死活搜索（參見3.6部分）來 獲得的。有意思的是，另一評(píng)估棋塊死活的復(fù)雜之處在于它可能需要評(píng)估全盤的形勢(shì)：如果要一個(gè)棋塊在劫爭(zhēng)中是可活的（即它必須贏得打劫來使自己活下來），就 必須估算所有和對(duì)手相比用來決定棋塊死活的劫材的數(shù)量和大小。如果出現(xiàn)雙重或三重劫的形勢(shì)，打劫分析會(huì)變得更復(fù)雜
評(píng)估的結(jié)果有時(shí)不確定，因?yàn)槊鞔_的死活定義在受限的戰(zhàn)術(shù)搜索里也許是不可能的，即一個(gè)絕對(duì)的死活回答可能超出了戰(zhàn)術(shù)或死活搜索的范圍。 [Page]
從復(fù)雜的類型分析看，由一個(gè)絕對(duì)位置來確定贏家是P空間難題（Lichtenstein & Sipser，1980），決定一個(gè)棋手能否左右輸贏需指數(shù)時(shí)間來完成（Robson，1983），由此也就不奇怪要用到啟發(fā)式了。這些理論結(jié)果顯示不存 在從一個(gè)絕對(duì)局勢(shì)出發(fā)決定領(lǐng)地結(jié)果的多項(xiàng)式時(shí)間算法。
3． 參賽程序里的博弈樹搜索和人工智能技術(shù)
當(dāng)前活躍在各電腦圍棋賽事里的程序有Martin Muller（1995）的Explorer（EX），陳懇（陳，1989；1990；1992）的Go Intellect（GI），Michael Reiss 的Go4++（Go4），陳志行的HandTalk（HT）以及David Fotland 的Many Faces of Go（MFG）。針對(duì)第2節(jié)討論的博弈樹搜索和圍棋專用的人工智能技術(shù)：戰(zhàn)術(shù)搜索，死活搜索和勢(shì)函數(shù)，我們報(bào)告這些程序的細(xì)節(jié)。
3.1 位置表示
所有的程序都有子、串、塊的表示，確認(rèn)串屬于某個(gè)組的典型方式是采用基于模式的啟發(fā)來確定串與串之間的關(guān)聯(lián)性。敵方（或塊）表示也被用在EX和GI 中，啟發(fā)式用來確定敵方的影響（GI）和領(lǐng)地區(qū)域（EX）。 #p#page_title#e#
盤面（例如棋塊、敵方）表示的對(duì)象屬性包括它們的死活狀態(tài)（也指安全性或生命力）、實(shí)地?cái)?shù)、眼數(shù)和勢(shì)。某些情況下這些屬性值由戰(zhàn)術(shù)搜索決定。
MFG的表示方式中一些組件由評(píng)估函數(shù)控制（例如塊、聯(lián)接、眼、實(shí)地和勢(shì)）。Go4的盤面只是簡(jiǎn)單的由評(píng)估函數(shù)（例如塊、眼、安全性、實(shí)地）來表示。
3.2 候選走法
通常，由模式或更常見的是由基于規(guī)則的專家系統(tǒng)產(chǎn)生候選走法。走子產(chǎn)生過程最后是通過（線性的或加權(quán)求和的）相加棋盤上所有點(diǎn)的參考值為合適的走法給出一個(gè)分值。全盤評(píng)估一般選最高得分點(diǎn)作為下一手的落子點(diǎn)。
不同程序由全局水平變量估值得出的候選走法數(shù)也有所不同：GI（陳，1997）有12手，MFG有10手，而Go4至少有50手。程序變量保持的規(guī)則數(shù)： EX大約100，MFG大約200。GI含有約20個(gè)走子算法，它們或者基于模式庫(kù)，或者基于面向目標(biāo)的搜索，或者基于啟發(fā)式規(guī)則（可能含有大量的規(guī) 則）。
模式通常既包含低級(jí)信息也包含高級(jí)信息。低級(jí)信息與黑白子的位置有關(guān)，那些點(diǎn)必須是空著的，已經(jīng)被子占據(jù)的點(diǎn)不在此列。高級(jí)信息則是關(guān)于氣的數(shù)量、安全 性、眼位和領(lǐng)地的信息。模式匹配不僅與子的配置匹配，而且跟包含在子或串里的任何高級(jí)需求有關(guān)。大量的模式匹配計(jì)算是很耗時(shí)的，并且由于棋盤上的對(duì)稱性而 變得更復(fù)雜。這已經(jīng)導(dǎo)致了發(fā)展特殊算法來克服與模式匹配有關(guān)的問題（比如MFG的哈希函數(shù)，EX的串匹配）。
知識(shí)以不同的方式組合到程序當(dāng)中：一些程序幾乎完全依據(jù)第一原則工作，另一些根據(jù)存儲(chǔ)的模式匹配當(dāng)前位置。不同的程序其模式數(shù)量相差很大：Go4約有15 個(gè)；MFG大約2000個(gè)；而EX則在3000個(gè)左右。有些程序也包含開放的走法模式數(shù)據(jù)庫(kù)（定式）（例如，MFG含有約45，000個(gè)定式模式）。 [Page]
3.3 目標(biāo)
多數(shù)情況下，大量的實(shí)地比起少量的實(shí)地加相應(yīng)的外勢(shì)更合乎需要。盡管有時(shí)也存在著實(shí)地和外勢(shì)間地轉(zhuǎn)化（特別是在布局和中盤階段）。然而，雖然實(shí)地的啟發(fā)式 評(píng)估是可能的，實(shí)地依然不總是形勢(shì)優(yōu)劣最好的指示明燈。在對(duì)局的早期階段，占有大量的實(shí)地可能表明一種過于集中的形勢(shì)，從實(shí)地安全的角度看，這樣的形對(duì)對(duì) 局的后面階段或許是有害的。開局造就最大可能的勢(shì)而不是實(shí)地通常導(dǎo)致局末對(duì)更多實(shí)地的追求。外勢(shì)是可能用來確定形勢(shì)優(yōu)劣的子目標(biāo)的一個(gè)例子。
用來確定形勢(shì)優(yōu)劣的大量子目標(biāo)的相對(duì)優(yōu)先度在電腦圍棋中看來沒有一致性可言。典型的塊和實(shí)地的死活狀態(tài)（安全性）被包含在目標(biāo)和子目標(biāo)中。在手談中，戰(zhàn)術(shù) 手段是重點(diǎn)，而MFG集中在聯(lián)接性、眼和塊的生命力。Go4則好像完全貫注于聯(lián)接性上，幾乎任何東西都是從聯(lián)接概率圖上派生（直接或間接地）出來。
3.4 評(píng)估過程
評(píng)估圍棋的形勢(shì)是個(gè)很慢的過程（例如，比起國(guó)際象棋程序的每秒10,000-100,000次評(píng)估，MFG是以低于每秒10次的速度完成對(duì)整局棋不超過 10,000種全盤形勢(shì)的評(píng)估）。由于比賽時(shí)間的限制，程序執(zhí)行的全局評(píng)估數(shù)通常是有限的（例如，MFG在選擇下一步時(shí)全局的評(píng)估數(shù)不超過100）。
Go4的50種候選走法中每一個(gè)都通過一個(gè)六步的過程來評(píng)估：1.啟用一個(gè)聯(lián)接概率圖。對(duì)于盤面上的每一個(gè)黑子和白子，計(jì)算它與32個(gè)（實(shí)際的或假定的） 友好點(diǎn)的聯(lián)接概率（要處理大量的數(shù)據(jù)）。確定聯(lián)接性還要用到戰(zhàn)術(shù)搜索；2.棋塊由聯(lián)接圖和戰(zhàn)術(shù)搜索來確定；3.眼位（利用模式）由聯(lián)接性和棋塊數(shù)據(jù)確定； 4.眼位的數(shù)量確定了棋塊的安全性；5.每個(gè)子的安全性按聯(lián)接概率圖的比率輻射并在所有棋子上相加；6.黑白領(lǐng)地由輻射值估計(jì)。黑白領(lǐng)地的差別作為一個(gè)給 定走法的評(píng)估結(jié)果返回。 #p#page_title#e#
MFG的評(píng)估是個(gè)多步過程，并且在很大程度上依賴于戰(zhàn)術(shù)搜索。戰(zhàn)術(shù)搜索檢查所有少于四口和一部分有四口氣的串以確定是不是死串。戰(zhàn)術(shù)搜索也被用來鑒別聯(lián)接 性和眼位。在這一環(huán)節(jié)，串組成了棋塊。棋塊的生命力由基于死活的考慮（例如，聯(lián)接、眼位等）決定，并且用來確定黑白子在盤面每個(gè)點(diǎn)（在-50至+50的范 圍之間）行使控制的總量統(tǒng)計(jì)。在總和每個(gè)點(diǎn)的值的基礎(chǔ)上確定領(lǐng)地，給出最終的估計(jì)值。多達(dá)6輪的靜態(tài)搜索可以被執(zhí)行，有時(shí)用一個(gè)特殊的模式集找出能使形勢(shì) 穩(wěn)定下來的局部走法。
GI的評(píng)估用在做全局搜索時(shí)。如果所有候選走法中有一種走法的得分要明顯高于其它的走法，它就被選為要走的下一步。如果候選走法中有些走法的得分大致相 等，靠評(píng)估帶來方便的全局搜索決定選擇走哪一步。評(píng)估時(shí)，敵子的安全性是為盤上每個(gè)點(diǎn)指定一個(gè)在-64到+64之間的黑白控度的基礎(chǔ)，所有點(diǎn)的分值加起來 返回一個(gè)評(píng)估值。全局搜索檢查的步數(shù)不多于6到7步，搜索的深度不超過6層。
3.5 戰(zhàn)術(shù)搜索 [Page]
戰(zhàn)術(shù)搜索是有選擇的、面向目標(biāo)的搜索，并且為一大堆目的而使用，包括確定串是死是活（Go4，MFG，EX，GI）、聯(lián)接是安全的還是可被切斷的 （Go4，MFG）、是否可以形成眼位（MFG）、產(chǎn)生候選走法（GI）和確定棋塊的死活（EX）。就是在全局的水平，戰(zhàn)術(shù)搜索也要用來做棋步產(chǎn)生和評(píng) 估。戰(zhàn)術(shù)評(píng)估和全盤評(píng)估有區(qū)別，這跟搜索的目標(biāo)（例如，一個(gè)串的氣的數(shù)量）有關(guān)。由于時(shí)間上的制約，戰(zhàn)術(shù)搜索通常在節(jié)點(diǎn)數(shù)、枝因子和層的深度上受到限制。 因此，盡管象死活這類的問題通常被認(rèn)為是戰(zhàn)術(shù)性的，棋子卻可以在戰(zhàn)略上就死去了，即使它們可能不能通過戰(zhàn)術(shù)手段被抓獲。由此，從圍棋評(píng)估的方方面面看，戰(zhàn) 術(shù)搜索只是一種啟發(fā)式裝備而已。
MFG提供了一個(gè)戰(zhàn)術(shù)搜索操作的很好的例證（通過“戰(zhàn)術(shù)家”）：每個(gè)有三口或更少的氣的串和許多有四口氣的串被“戰(zhàn)術(shù)家”檢查過。每個(gè)串檢查兩次，一次白 先走一次黑先走。“戰(zhàn)術(shù)家”決定一個(gè)串是否被抓（比如，即使它先走也不能活）、被威脅（比如，如果它先走則活，后走則死），或者是牢固的。“戰(zhàn)術(shù)家”依靠 簡(jiǎn)單的啟發(fā)式（例如，氣數(shù)和聯(lián)接性）。
“戰(zhàn)術(shù)家”有兩個(gè)分離的走子器；一個(gè)執(zhí)行攻擊走法，一個(gè)執(zhí)行防衛(wèi)走法。走子器建議的走法按一些規(guī)則分類，這些規(guī)則包括二次氣（氣的氣）、切點(diǎn)和簡(jiǎn)單的眼 形。一旦分類，根據(jù)依賴走法分類的質(zhì)量的搜索的表現(xiàn)，一種α-β深度優(yōu)先搜索被派上用場(chǎng)。走子和分類解釋了多數(shù)時(shí)間依靠戰(zhàn)術(shù)搜索的原因。
戰(zhàn)術(shù)搜索直接針對(duì)目標(biāo)并被限制一個(gè)最大節(jié)點(diǎn)數(shù)。抓子時(shí)這個(gè)限制是大約100，然而當(dāng)只有一步可走時(shí)就不考慮這個(gè)限制。采用這種方式，可以毫不費(fèi)力地確定征 子的勝方。根據(jù)第一層走子產(chǎn)生賦予走法的分值，一次搜索的節(jié)點(diǎn)數(shù)分配到樹枝中，因此不同的樹枝可能在不同的深度結(jié)束。每一成功的層的枝因子被“戰(zhàn)術(shù)家”逐 步強(qiáng)化；枝因子從第一層5降到第五層的1或2。
對(duì)局過程中，MFG作大約100,000-150,000次戰(zhàn)術(shù)搜索，以每秒2,000-2,500個(gè)節(jié)點(diǎn)的速度遍歷1.5-2百萬個(gè)節(jié)點(diǎn)。平均起來每次戰(zhàn)術(shù)搜索訪問約10-20個(gè)節(jié)點(diǎn)，盡管由于一些搜索因節(jié)點(diǎn)限制而終止，許多搜索訪問過節(jié)點(diǎn)數(shù)要少于5個(gè)。
3.6 死活搜索
不是所有的程序都做明確的死活分析，很多程序?qū)Υ耸褂昧藨?zhàn)術(shù)搜索。MFG用與它的戰(zhàn)術(shù)搜索過程類似的方式作死活分析，除了它是在塊上作死活分析而不是分析串。 #p#page_title#e#
一個(gè)靜態(tài)死活評(píng)估器在多步過程中確定每個(gè)塊的死活狀態(tài)，而沒有以從簡(jiǎn)單的結(jié)構(gòu)中進(jìn)一步產(chǎn)生復(fù)雜結(jié)構(gòu)的方式向前搜索。靜態(tài)死活評(píng)估器使用“戰(zhàn)術(shù)家”并且為棋塊中的每個(gè)合適的串至少調(diào)用兩次。
死活搜索是直接面向目標(biāo)的（例如，拯救或殺死一個(gè)棋塊）。如果在一個(gè)特定點(diǎn)沒有獲得搜索目標(biāo)，合適走法由死活搜索引擎自身的走法器產(chǎn)生，并繼續(xù)搜索。為了 在一次死活搜索期間確定目標(biāo)是否已經(jīng)達(dá)到，靜態(tài)死活評(píng)估器在每個(gè)點(diǎn)被調(diào)用。死活搜索引擎使用深度優(yōu)先α、β搜索，每一個(gè)特定的枝的搜索深度由啟發(fā)式?jīng)Q定。 搜索樹的大小是強(qiáng)制性的，通?？梢赃_(dá)到7層的深度和20個(gè)節(jié)點(diǎn)的大小。死活搜索是很慢的，整棵樹要裝到緩存里以減少花在重復(fù)搜索上的開銷。死活搜索的緩慢 也意味著它不會(huì)被用在全盤評(píng)估中。 [Page]
3.7 勢(shì)函數(shù)
勢(shì)是一種圍棋概念，它表明了每一方棋子對(duì)空點(diǎn)的最大可能的控制潛力。通過確保開局時(shí)子力投放不過于集中，棋手在后面的對(duì)局中將取得最大限度獲得領(lǐng)地的機(jī)會(huì)。
勢(shì)通過勢(shì)函數(shù)建立可計(jì)算模型（Zobrist，1969；Ryder，1971；Chen，1989）。通常，子力以盤上每個(gè)點(diǎn)的輻射影響值的和（黑白子 輻射正負(fù)相反的值）對(duì)周邊的點(diǎn)施加輻射影響（MFG的黑白子的勢(shì)是分離的）。子力輻射按距離函數(shù)遞減：GI是2的距離次方分之一，MFG是距離分之一。但 過于依賴勢(shì)函數(shù)的程序表現(xiàn)不佳（EX和Go4不再使用勢(shì)函數(shù)，盡管Go4的輻射函數(shù)很象一個(gè)勢(shì)函數(shù)，EX采取另一些措施，象同色點(diǎn)或可聯(lián)接點(diǎn)的距離）。
應(yīng)用勢(shì)的啟發(fā)包括確定聯(lián)接性和敵子（GI），以及確定領(lǐng)地（MFG）。MFG的塊勢(shì)初始值依賴于塊的強(qiáng)度等，強(qiáng)壯的塊比弱塊或?qū)⑺赖膲K輻射更大的影響。這 也意味著死塊輻射負(fù)影響等，因?yàn)樗鼘?duì)敵方有利。在MFG和GI中勢(shì)都沒有通過子輻射；MFG也沒有通過敵鏈輻射影響。
4． 討論
當(dāng)前的圍棋程序都使用了一定量的“知識(shí)”。由于建立在設(shè)計(jì)者下棋成功經(jīng)驗(yàn)的啟發(fā)之上，每個(gè)程序都可被看作一種（可能是含蓄的）圍棋理論的一次以經(jīng)驗(yàn)為依據(jù) 的實(shí)驗(yàn)。圍棋理論成立的關(guān)鍵要靠數(shù)據(jù)結(jié)構(gòu)的選擇，因?yàn)樗鼈儧Q定了編碼不同類型知識(shí)的難易和應(yīng)用這些知識(shí)的計(jì)算開銷。隨著程序員同時(shí)在圍棋和電腦圍棋方面獲 得技能，程序會(huì)有發(fā)展（例如，在過去的十五年中隨著 Fotland 的棋力從15級(jí)發(fā)展到2段，MFG也增長(zhǎng)了棋力并且代碼長(zhǎng)度增加到目前的4萬行）。程序的性能由它最弱的部件決定，而向程序增加新知識(shí)的難易是提高程序性 能的重要部分。
由此可見，電腦圍棋領(lǐng)域在關(guān)于怎樣構(gòu)筑一個(gè)圍棋程序或者指配不同圍棋知識(shí)的優(yōu)先性（例如，Go4注重聯(lián)接性而MFG注重死活）方面還沒有一致性可言。必須 提到的一點(diǎn)是：關(guān)于人類是怎樣下圍棋的至今也沒個(gè)一致的說法，這是目前認(rèn)知科學(xué)研究的一個(gè)課題（見Saito & Yoshikawa，1977，作為回顧）。這個(gè)領(lǐng)域的任何進(jìn)展都會(huì)對(duì)圍棋理論有個(gè)直接的促進(jìn)，并可能導(dǎo)致電腦圍棋程序算法的改進(jìn)。
本文對(duì)目前比較成功的幾個(gè)程序作了比較。通過這項(xiàng)工作，我們?cè)诓┺臉渌阉鞯目蚣軆?nèi)分析了圍棋，并通過對(duì)示例電腦圍棋編程的觀察把有關(guān)的問題暴露出來。這種 困難在電腦圍棋領(lǐng)域是常識(shí)，但在更為廣泛的人工智能范疇卻很少被人們認(rèn)識(shí)和接受。圍棋全盤評(píng)估需要確定棋塊的死活狀態(tài)，不管是通過死活搜索還是戰(zhàn)術(shù)搜索， 評(píng)估是非常消耗計(jì)算資源的。缺乏快速有效的評(píng)估函數(shù)是電腦圍棋遭遇的一個(gè)基本問題，并且和巨大的樹枝因素、用戶和電腦比賽的實(shí)時(shí)需求（一般來說，相對(duì)于國(guó) 際象棋的每秒180步圍棋每秒只有24步）等攪和在一起。因此，計(jì)算機(jī)國(guó)際象棋通常要用到的完全廣度博弈樹搜索在電腦圍棋里是行不通的 #p#page_title#e#
除了所列出的圍棋領(lǐng)域固有的問題外，本文還探討當(dāng)前的程序怎樣地處理這些問題，由此為未來的圍棋程序員提供一個(gè)跳板。請(qǐng)注意電腦圍棋是個(gè)商業(yè)的領(lǐng)域，程序 本身（不是學(xué)術(shù)論文）就是它的主要產(chǎn)品。跟其它的參考不同的是，這里報(bào)告的細(xì)節(jié)都已經(jīng)通過個(gè)人交流征詢了（慷慨貢獻(xiàn)自己的知識(shí)的）程序作者本人的意見，并 且有相關(guān)的電腦圍棋郵件列表和FTP站點(diǎn)的信息為依據(jù)。 [Page]
電腦圍棋的挑戰(zhàn)性在于要擴(kuò)展當(dāng)前的圍棋理論或發(fā)展新理論——特別是與評(píng)估有關(guān)的，針對(duì)實(shí)時(shí)限制設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)和算法，解決知識(shí)瓶頸。目前還沒有一個(gè)有 力的程序使用學(xué)習(xí)技術(shù)，盡管有過幾次這樣的嘗試（如，Pell，1991；Schraudolph, Dayan & Sejnowski，1994；Donnelly, Corr & Crookes，1994）?；仡欉@些程序已經(jīng)超出了本文的范圍，但我們推測(cè)這些程序也沒有成功，因?yàn)樗鼈兊脑O(shè)計(jì)者的含蓄的圍棋理論缺乏對(duì)圍棋復(fù)雜性的必 要理解。怎樣把學(xué)習(xí)能力賦予現(xiàn)有的程序（或者它們暗示的圍棋理論）是個(gè)等待解決的問題。
致謝
感謝Ken Chen、陳志行、David Fotland、Martin Muller 和Mick Reiss，他們向我們提供了有關(guān)程序的細(xì)節(jié)和對(duì)本文不無裨益的反饋。
參考文獻(xiàn)
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.
從復(fù)雜的類型分析看，由一個(gè)絕對(duì)位置來確定贏家是P空間難題（Lichtenstein & Sipser，1980），決定一個(gè)棋手能否左右輸贏需指數(shù)時(shí)間來完成（Robson，1983），由此也就不奇怪要用到啟發(fā)式了。這些理論結(jié)果顯示不存 在從一個(gè)絕對(duì)局勢(shì)出發(fā)決定領(lǐng)地結(jié)果的多項(xiàng)式時(shí)間算法。
3． 參賽程序里的博弈樹搜索和人工智能技術(shù)
當(dāng)前活躍在各電腦圍棋賽事里的程序有Martin Muller（1995）的Explorer（EX），陳懇（陳，1989；1990；1992）的Go Intellect（GI），Michael Reiss 的Go4++（Go4），陳志行的HandTalk（HT）以及David Fotland 的Many Faces of Go（MFG）。針對(duì)第2節(jié)討論的博弈樹搜索和圍棋專用的人工智能技術(shù)：戰(zhàn)術(shù)搜索，死活搜索和勢(shì)函數(shù)，我們報(bào)告這些程序的細(xì)節(jié)。
3.1 位置表示
所有的程序都有子、串、塊的表示，確認(rèn)串屬于某個(gè)組的典型方式是采用基于模式的啟發(fā)來確定串與串之間的關(guān)聯(lián)性。敵方（或塊）表示也被用在EX和GI 中，啟發(fā)式用來確定敵方的影響（GI）和領(lǐng)地區(qū)域（EX）。 #p#page_title#e#
盤面（例如棋塊、敵方）表示的對(duì)象屬性包括它們的死活狀態(tài)（也指安全性或生命力）、實(shí)地?cái)?shù)、眼數(shù)和勢(shì)。某些情況下這些屬性值由戰(zhàn)術(shù)搜索決定。
MFG的表示方式中一些組件由評(píng)估函數(shù)控制（例如塊、聯(lián)接、眼、實(shí)地和勢(shì)）。Go4的盤面只是簡(jiǎn)單的由評(píng)估函數(shù)（例如塊、眼、安全性、實(shí)地）來表示。
3.2 候選走法
通常，由模式或更常見的是由基于規(guī)則的專家系統(tǒng)產(chǎn)生候選走法。走子產(chǎn)生過程最后是通過（線性的或加權(quán)求和的）相加棋盤上所有點(diǎn)的參考值為合適的走法給出一個(gè)分值。全盤評(píng)估一般選最高得分點(diǎn)作為下一手的落子點(diǎn)。
不同程序由全局水平變量估值得出的候選走法數(shù)也有所不同：GI（陳，1997）有12手，MFG有10手，而Go4至少有50手。程序變量保持的規(guī)則數(shù)： EX大約100，MFG大約200。GI含有約20個(gè)走子算法，它們或者基于模式庫(kù)，或者基于面向目標(biāo)的搜索，或者基于啟發(fā)式規(guī)則（可能含有大量的規(guī) 則）。
模式通常既包含低級(jí)信息也包含高級(jí)信息。低級(jí)信息與黑白子的位置有關(guān)，那些點(diǎn)必須是空著的，已經(jīng)被子占據(jù)的點(diǎn)不在此列。高級(jí)信息則是關(guān)于氣的數(shù)量、安全 性、眼位和領(lǐng)地的信息。模式匹配不僅與子的配置匹配，而且跟包含在子或串里的任何高級(jí)需求有關(guān)。大量的模式匹配計(jì)算是很耗時(shí)的，并且由于棋盤上的對(duì)稱性而 變得更復(fù)雜。這已經(jīng)導(dǎo)致了發(fā)展特殊算法來克服與模式匹配有關(guān)的問題（比如MFG的哈希函數(shù)，EX的串匹配）。
知識(shí)以不同的方式組合到程序當(dāng)中：一些程序幾乎完全依據(jù)第一原則工作，另一些根據(jù)存儲(chǔ)的模式匹配當(dāng)前位置。不同的程序其模式數(shù)量相差很大：Go4約有15 個(gè)；MFG大約2000個(gè)；而EX則在3000個(gè)左右。有些程序也包含開放的走法模式數(shù)據(jù)庫(kù)（定式）（例如，MFG含有約45，000個(gè)定式模式）。 [Page]
3.3 目標(biāo)
多數(shù)情況下，大量的實(shí)地比起少量的實(shí)地加相應(yīng)的外勢(shì)更合乎需要。盡管有時(shí)也存在著實(shí)地和外勢(shì)間地轉(zhuǎn)化（特別是在布局和中盤階段）。然而，雖然實(shí)地的啟發(fā)式 評(píng)估是可能的，實(shí)地依然不總是形勢(shì)優(yōu)劣最好的指示明燈。在對(duì)局的早期階段，占有大量的實(shí)地可能表明一種過于集中的形勢(shì)，從實(shí)地安全的角度看，這樣的形對(duì)對(duì) 局的后面階段或許是有害的。開局造就最大可能的勢(shì)而不是實(shí)地通常導(dǎo)致局末對(duì)更多實(shí)地的追求。外勢(shì)是可能用來確定形勢(shì)優(yōu)劣的子目標(biāo)的一個(gè)例子。
用來確定形勢(shì)優(yōu)劣的大量子目標(biāo)的相對(duì)優(yōu)先度在電腦圍棋中看來沒有一致性可言。典型的塊和實(shí)地的死活狀態(tài)（安全性）被包含在目標(biāo)和子目標(biāo)中。在手談中，戰(zhàn)術(shù) 手段是重點(diǎn)，而MFG集中在聯(lián)接性、眼和塊的生命力。Go4則好像完全貫注于聯(lián)接性上，幾乎任何東西都是從聯(lián)接概率圖上派生（直接或間接地）出來。
3.4 評(píng)估過程
評(píng)估圍棋的形勢(shì)是個(gè)很慢的過程（例如，比起國(guó)際象棋程序的每秒10,000-100,000次評(píng)估，MFG是以低于每秒10次的速度完成對(duì)整局棋不超過 10,000種全盤形勢(shì)的評(píng)估）。由于比賽時(shí)間的限制，程序執(zhí)行的全局評(píng)估數(shù)通常是有限的（例如，MFG在選擇下一步時(shí)全局的評(píng)估數(shù)不超過100）。
Go4的50種候選走法中每一個(gè)都通過一個(gè)六步的過程來評(píng)估：1.啟用一個(gè)聯(lián)接概率圖。對(duì)于盤面上的每一個(gè)黑子和白子，計(jì)算它與32個(gè)（實(shí)際的或假定的） 友好點(diǎn)的聯(lián)接概率（要處理大量的數(shù)據(jù)）。確定聯(lián)接性還要用到戰(zhàn)術(shù)搜索；2.棋塊由聯(lián)接圖和戰(zhàn)術(shù)搜索來確定；3.眼位（利用模式）由聯(lián)接性和棋塊數(shù)據(jù)確定； 4.眼位的數(shù)量確定了棋塊的安全性；5.每個(gè)子的安全性按聯(lián)接概率圖的比率輻射并在所有棋子上相加；6.黑白領(lǐng)地由輻射值估計(jì)。黑白領(lǐng)地的差別作為一個(gè)給 定走法的評(píng)估結(jié)果返回。 #p#page_title#e#
MFG的評(píng)估是個(gè)多步過程，并且在很大程度上依賴于戰(zhàn)術(shù)搜索。戰(zhàn)術(shù)搜索檢查所有少于四口和一部分有四口氣的串以確定是不是死串。戰(zhàn)術(shù)搜索也被用來鑒別聯(lián)接 性和眼位。在這一環(huán)節(jié)，串組成了棋塊。棋塊的生命力由基于死活的考慮（例如，聯(lián)接、眼位等）決定，并且用來確定黑白子在盤面每個(gè)點(diǎn)（在-50至+50的范 圍之間）行使控制的總量統(tǒng)計(jì)。在總和每個(gè)點(diǎn)的值的基礎(chǔ)上確定領(lǐng)地，給出最終的估計(jì)值。多達(dá)6輪的靜態(tài)搜索可以被執(zhí)行，有時(shí)用一個(gè)特殊的模式集找出能使形勢(shì) 穩(wěn)定下來的局部走法。
GI的評(píng)估用在做全局搜索時(shí)。如果所有候選走法中有一種走法的得分要明顯高于其它的走法，它就被選為要走的下一步。如果候選走法中有些走法的得分大致相 等，靠評(píng)估帶來方便的全局搜索決定選擇走哪一步。評(píng)估時(shí)，敵子的安全性是為盤上每個(gè)點(diǎn)指定一個(gè)在-64到+64之間的黑白控度的基礎(chǔ)，所有點(diǎn)的分值加起來 返回一個(gè)評(píng)估值。全局搜索檢查的步數(shù)不多于6到7步，搜索的深度不超過6層。
3.5 戰(zhàn)術(shù)搜索 [Page]
戰(zhàn)術(shù)搜索是有選擇的、面向目標(biāo)的搜索，并且為一大堆目的而使用，包括確定串是死是活（Go4，MFG，EX，GI）、聯(lián)接是安全的還是可被切斷的 （Go4，MFG）、是否可以形成眼位（MFG）、產(chǎn)生候選走法（GI）和確定棋塊的死活（EX）。就是在全局的水平，戰(zhàn)術(shù)搜索也要用來做棋步產(chǎn)生和評(píng) 估。戰(zhàn)術(shù)評(píng)估和全盤評(píng)估有區(qū)別，這跟搜索的目標(biāo)（例如，一個(gè)串的氣的數(shù)量）有關(guān)。由于時(shí)間上的制約，戰(zhàn)術(shù)搜索通常在節(jié)點(diǎn)數(shù)、枝因子和層的深度上受到限制。 因此，盡管象死活這類的問題通常被認(rèn)為是戰(zhàn)術(shù)性的，棋子卻可以在戰(zhàn)略上就死去了，即使它們可能不能通過戰(zhàn)術(shù)手段被抓獲。由此，從圍棋評(píng)估的方方面面看，戰(zhàn) 術(shù)搜索只是一種啟發(fā)式裝備而已。
MFG提供了一個(gè)戰(zhàn)術(shù)搜索操作的很好的例證（通過“戰(zhàn)術(shù)家”）：每個(gè)有三口或更少的氣的串和許多有四口氣的串被“戰(zhàn)術(shù)家”檢查過。每個(gè)串檢查兩次，一次白 先走一次黑先走。“戰(zhàn)術(shù)家”決定一個(gè)串是否被抓（比如，即使它先走也不能活）、被威脅（比如，如果它先走則活，后走則死），或者是牢固的。“戰(zhàn)術(shù)家”依靠 簡(jiǎn)單的啟發(fā)式（例如，氣數(shù)和聯(lián)接性）。
“戰(zhàn)術(shù)家”有兩個(gè)分離的走子器；一個(gè)執(zhí)行攻擊走法，一個(gè)執(zhí)行防衛(wèi)走法。走子器建議的走法按一些規(guī)則分類，這些規(guī)則包括二次氣（氣的氣）、切點(diǎn)和簡(jiǎn)單的眼 形。一旦分類，根據(jù)依賴走法分類的質(zhì)量的搜索的表現(xiàn)，一種α-β深度優(yōu)先搜索被派上用場(chǎng)。走子和分類解釋了多數(shù)時(shí)間依靠戰(zhàn)術(shù)搜索的原因。
戰(zhàn)術(shù)搜索直接針對(duì)目標(biāo)并被限制一個(gè)最大節(jié)點(diǎn)數(shù)。抓子時(shí)這個(gè)限制是大約100，然而當(dāng)只有一步可走時(shí)就不考慮這個(gè)限制。采用這種方式，可以毫不費(fèi)力地確定征 子的勝方。根據(jù)第一層走子產(chǎn)生賦予走法的分值，一次搜索的節(jié)點(diǎn)數(shù)分配到樹枝中，因此不同的樹枝可能在不同的深度結(jié)束。每一成功的層的枝因子被“戰(zhàn)術(shù)家”逐 步強(qiáng)化；枝因子從第一層5降到第五層的1或2。
對(duì)局過程中，MFG作大約100,000-150,000次戰(zhàn)術(shù)搜索，以每秒2,000-2,500個(gè)節(jié)點(diǎn)的速度遍歷1.5-2百萬個(gè)節(jié)點(diǎn)。平均起來每次戰(zhàn)術(shù)搜索訪問約10-20個(gè)節(jié)點(diǎn)，盡管由于一些搜索因節(jié)點(diǎn)限制而終止，許多搜索訪問過節(jié)點(diǎn)數(shù)要少于5個(gè)。
3.6 死活搜索
不是所有的程序都做明確的死活分析，很多程序?qū)Υ耸褂昧藨?zhàn)術(shù)搜索。MFG用與它的戰(zhàn)術(shù)搜索過程類似的方式作死活分析，除了它是在塊上作死活分析而不是分析串。 #p#page_title#e#
一個(gè)靜態(tài)死活評(píng)估器在多步過程中確定每個(gè)塊的死活狀態(tài)，而沒有以從簡(jiǎn)單的結(jié)構(gòu)中進(jìn)一步產(chǎn)生復(fù)雜結(jié)構(gòu)的方式向前搜索。靜態(tài)死活評(píng)估器使用“戰(zhàn)術(shù)家”并且為棋塊中的每個(gè)合適的串至少調(diào)用兩次。
死活搜索是直接面向目標(biāo)的（例如，拯救或殺死一個(gè)棋塊）。如果在一個(gè)特定點(diǎn)沒有獲得搜索目標(biāo)，合適走法由死活搜索引擎自身的走法器產(chǎn)生，并繼續(xù)搜索。為了 在一次死活搜索期間確定目標(biāo)是否已經(jīng)達(dá)到，靜態(tài)死活評(píng)估器在每個(gè)點(diǎn)被調(diào)用。死活搜索引擎使用深度優(yōu)先α、β搜索，每一個(gè)特定的枝的搜索深度由啟發(fā)式?jīng)Q定。 搜索樹的大小是強(qiáng)制性的，通?？梢赃_(dá)到7層的深度和20個(gè)節(jié)點(diǎn)的大小。死活搜索是很慢的，整棵樹要裝到緩存里以減少花在重復(fù)搜索上的開銷。死活搜索的緩慢 也意味著它不會(huì)被用在全盤評(píng)估中。 [Page]
3.7 勢(shì)函數(shù)
勢(shì)是一種圍棋概念，它表明了每一方棋子對(duì)空點(diǎn)的最大可能的控制潛力。通過確保開局時(shí)子力投放不過于集中，棋手在后面的對(duì)局中將取得最大限度獲得領(lǐng)地的機(jī)會(huì)。
勢(shì)通過勢(shì)函數(shù)建立可計(jì)算模型（Zobrist，1969；Ryder，1971；Chen，1989）。通常，子力以盤上每個(gè)點(diǎn)的輻射影響值的和（黑白子 輻射正負(fù)相反的值）對(duì)周邊的點(diǎn)施加輻射影響（MFG的黑白子的勢(shì)是分離的）。子力輻射按距離函數(shù)遞減：GI是2的距離次方分之一，MFG是距離分之一。但 過于依賴勢(shì)函數(shù)的程序表現(xiàn)不佳（EX和Go4不再使用勢(shì)函數(shù)，盡管Go4的輻射函數(shù)很象一個(gè)勢(shì)函數(shù)，EX采取另一些措施，象同色點(diǎn)或可聯(lián)接點(diǎn)的距離）。
應(yīng)用勢(shì)的啟發(fā)包括確定聯(lián)接性和敵子（GI），以及確定領(lǐng)地（MFG）。MFG的塊勢(shì)初始值依賴于塊的強(qiáng)度等，強(qiáng)壯的塊比弱塊或?qū)⑺赖膲K輻射更大的影響。這 也意味著死塊輻射負(fù)影響等，因?yàn)樗鼘?duì)敵方有利。在MFG和GI中勢(shì)都沒有通過子輻射；MFG也沒有通過敵鏈輻射影響。
4． 討論
當(dāng)前的圍棋程序都使用了一定量的“知識(shí)”。由于建立在設(shè)計(jì)者下棋成功經(jīng)驗(yàn)的啟發(fā)之上，每個(gè)程序都可被看作一種（可能是含蓄的）圍棋理論的一次以經(jīng)驗(yàn)為依據(jù) 的實(shí)驗(yàn)。圍棋理論成立的關(guān)鍵要靠數(shù)據(jù)結(jié)構(gòu)的選擇，因?yàn)樗鼈儧Q定了編碼不同類型知識(shí)的難易和應(yīng)用這些知識(shí)的計(jì)算開銷。隨著程序員同時(shí)在圍棋和電腦圍棋方面獲 得技能，程序會(huì)有發(fā)展（例如，在過去的十五年中隨著 Fotland 的棋力從15級(jí)發(fā)展到2段，MFG也增長(zhǎng)了棋力并且代碼長(zhǎng)度增加到目前的4萬行）。程序的性能由它最弱的部件決定，而向程序增加新知識(shí)的難易是提高程序性 能的重要部分。
由此可見，電腦圍棋領(lǐng)域在關(guān)于怎樣構(gòu)筑一個(gè)圍棋程序或者指配不同圍棋知識(shí)的優(yōu)先性（例如，Go4注重聯(lián)接性而MFG注重死活）方面還沒有一致性可言。必須 提到的一點(diǎn)是：關(guān)于人類是怎樣下圍棋的至今也沒個(gè)一致的說法，這是目前認(rèn)知科學(xué)研究的一個(gè)課題（見Saito & Yoshikawa，1977，作為回顧）。這個(gè)領(lǐng)域的任何進(jìn)展都會(huì)對(duì)圍棋理論有個(gè)直接的促進(jìn)，并可能導(dǎo)致電腦圍棋程序算法的改進(jìn)。
本文對(duì)目前比較成功的幾個(gè)程序作了比較。通過這項(xiàng)工作，我們?cè)诓┺臉渌阉鞯目蚣軆?nèi)分析了圍棋，并通過對(duì)示例電腦圍棋編程的觀察把有關(guān)的問題暴露出來。這種 困難在電腦圍棋領(lǐng)域是常識(shí)，但在更為廣泛的人工智能范疇卻很少被人們認(rèn)識(shí)和接受。圍棋全盤評(píng)估需要確定棋塊的死活狀態(tài)，不管是通過死活搜索還是戰(zhàn)術(shù)搜索， 評(píng)估是非常消耗計(jì)算資源的。缺乏快速有效的評(píng)估函數(shù)是電腦圍棋遭遇的一個(gè)基本問題，并且和巨大的樹枝因素、用戶和電腦比賽的實(shí)時(shí)需求（一般來說，相對(duì)于國(guó) 際象棋的每秒180步圍棋每秒只有24步）等攪和在一起。因此，計(jì)算機(jī)國(guó)際象棋通常要用到的完全廣度博弈樹搜索在電腦圍棋里是行不通的 #p#page_title#e#
除了所列出的圍棋領(lǐng)域固有的問題外，本文還探討當(dāng)前的程序怎樣地處理這些問題，由此為未來的圍棋程序員提供一個(gè)跳板。請(qǐng)注意電腦圍棋是個(gè)商業(yè)的領(lǐng)域，程序 本身（不是學(xué)術(shù)論文）就是它的主要產(chǎn)品。跟其它的參考不同的是，這里報(bào)告的細(xì)節(jié)都已經(jīng)通過個(gè)人交流征詢了（慷慨貢獻(xiàn)自己的知識(shí)的）程序作者本人的意見，并 且有相關(guān)的電腦圍棋郵件列表和FTP站點(diǎn)的信息為依據(jù)。 [Page]
電腦圍棋的挑戰(zhàn)性在于要擴(kuò)展當(dāng)前的圍棋理論或發(fā)展新理論——特別是與評(píng)估有關(guān)的，針對(duì)實(shí)時(shí)限制設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)和算法，解決知識(shí)瓶頸。目前還沒有一個(gè)有 力的程序使用學(xué)習(xí)技術(shù)，盡管有過幾次這樣的嘗試（如，Pell，1991；Schraudolph, Dayan & Sejnowski，1994；Donnelly, Corr & Crookes，1994）?；仡欉@些程序已經(jīng)超出了本文的范圍，但我們推測(cè)這些程序也沒有成功，因?yàn)樗鼈兊脑O(shè)計(jì)者的含蓄的圍棋理論缺乏對(duì)圍棋復(fù)雜性的必 要理解。怎樣把學(xué)習(xí)能力賦予現(xiàn)有的程序（或者它們暗示的圍棋理論）是個(gè)等待解決的問題。
致謝
感謝Ken Chen、陳志行、David Fotland、Martin Muller 和Mick Reiss，他們向我們提供了有關(guān)程序的細(xì)節(jié)和對(duì)本文不無裨益的反饋。
參考文獻(xiàn)
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.
