計算機(jī)圍棋相關(guān)問題研究

摘要：在對計算機(jī)圍棋存在的問題進(jìn)行分析的基礎(chǔ)上，描述了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，提出了塊、氣、評估函數(shù)等的算法思路。

關(guān)鍵詞：計算機(jī)圍棋；棋子；搜索

1 引言

圍棋是二人零和有限確定完全信息游戲的一種。二人，指游戲有兩個參與者；零和，一方勝則另一方負(fù)；有限，游戲不會無限進(jìn)行下去；確定，不存在類似骰子游戲中那樣不確定的因素；全信息，雙方都知道對局的局面。

圍棋的規(guī)則非常簡單：

①棋盤為19×19道；

②黑先、白后，輪流在空白交叉點上下子；

③氣盡提?。]有“氣”的棋子要從棋盤上拿走）；

④禁止全局同形再現(xiàn)；

⑤最后占據(jù)交叉點多的一方為勝。

計算機(jī)圍棋是研究如何讓計算機(jī)下圍棋的問題，它是人工智能領(lǐng)域中的一個重要研究課題。目前，計算機(jī)圍棋的發(fā)展還很緩慢，棋力最高僅約二級（相當(dāng)于初學(xué)者水平）。1997年，計算機(jī)“深藍(lán)”就已經(jīng)擊敗了國際象棋世界冠軍卡斯帕羅夫，其它棋類計算機(jī)也可以達(dá)到很高的水平，只有圍棋例外，這主要是由圍棋的獨特之處造成的。

2 圍棋的特點

2.1 圍棋搜索空間大

圍棋棋盤為19×19，大于國際象棋的8×8；圍棋棋局的平均手?jǐn)?shù)約240步，大于國際象棋的約80步；圍棋每步棋的選擇（分支因子）平均約200個，大于國際象棋的約40個。開局的時候，國際象棋有38種選擇，而圍棋有361種選擇（考慮到對稱的問題，實際有55種選擇；但從第二步開始，很多情況下又有360種選擇……）。全部可能的局面數(shù)國際象棋數(shù)量級約10120，圍棋約10300。

2.2 圍棋需判斷死活

對國際象棋來說，棋子基本不存在死活問題，而圍棋的棋子就有死活之分。對死活的判斷牽涉到很多復(fù)雜的問題。另外，圍棋棋子的價值在不同狀態(tài)下是不斷變化的，前后差距有時非常巨大（所謂的“要子”與“廢子”）。

2.3 圍棋的系統(tǒng)性

圍棋中棋子的價值不是孤立存在的，而是與所處的棋塊密切相關(guān)，“塊”是一組有關(guān)聯(lián)的同色棋子，它構(gòu)成了圍棋對局中的戰(zhàn)術(shù)單元。若把整個棋局看成一場戰(zhàn)爭，則塊可看成是一支部隊。

2.4 圍棋的模糊性

圍棋中充滿模糊信息，有很多術(shù)語如“棋形”、“急所”、“大場”、“模樣”等，很容易產(chǎn)生對棋局的不同理解。下圍棋是一種融抽象思維和形象思維為一體的決策過程，除了對計算能力的要求以外，也需要憑借一定的“感覺”來行棋。

3 計算機(jī)圍棋需解決的問題

3.1 數(shù)據(jù)結(jié)構(gòu)

3.1.1 棋盤

棋局狀態(tài)用一個19×19的二維數(shù)組表示：

byte Board[19][19]

其中，0表示沒有棋子，1表示有黑子，-1表示有白子。

3.1.2 棋子位置

棋子位置用一個結(jié)構(gòu)表示：

struct Position

{

byte x;//棋子的列號

byte y;//棋子的行號

int value;//下此位置時局面的評估函數(shù)值

}

3.1.3 下棋順序

下棋順序用棧表示，以便于悔棋及復(fù)盤研究。

3.2 算法

3.2.1 塊的劃分

塊是圍棋對局中的戰(zhàn)術(shù)單元，計算機(jī)圍棋的一個基本任務(wù)就是塊的劃分。好的分塊算法能使計算機(jī)對當(dāng)前的局面有比較正確的評估。它可用于判斷棋子的安危，確定戰(zhàn)術(shù)搜索的范圍，從而產(chǎn)生相應(yīng)的攻防著點。

塊的劃分主要依據(jù)棋子之間的位置關(guān)系來確定。

首先，判斷棋子是否連接，連接指的是對方不可切斷棋子之間的聯(lián)絡(luò)，如雙關(guān)、尖、虎口等。

其次，棋盤上每個棋子都會對整個盤面發(fā)生影響，其中對相鄰的棋子影響最大，隨著距離的增加相應(yīng)衰減。為此，可以給棋子周圍的空位賦一個影響值，并且不同棋子對同一個空位的影響值可以疊加。若某個空位的影響值不小于一個給定的值，則認(rèn)為該空位被相應(yīng)顏色的棋子控制。

相連的棋子、連接的棋子及與本方控制的空位相連的棋子都被認(rèn)為屬于同一塊。

3.2.2 氣的計算

可以用遞歸算法，分別計算棋串中每個棋子上、下、左、右氣的數(shù)目，累加得到整個棋串的氣數(shù)[1]。

3.2.3 評估函數(shù)

首先，可以通過死活搜索來判斷塊的死活；其次，計算雙方明確的地域；最后，考慮棋子對周圍的輻射，也就是“勢”的影響。綜合以上三個要素，可以對棋局給出一個比較準(zhǔn)確的評估值。

3.2.4 搜索算法

3.2.4.1 極大極小搜索

二人完全信息博弈中典型的人工智能方法是利用搜索博弈樹以決定下一步，在國際象棋中已取得了非常好的效果。但在圍棋中，由于圍棋的復(fù)雜性，全寬度搜索不切實際。在此，把目標(biāo)定位為如何尋找一步相對好的著法，這種情況下，搜索深度和廣度可根據(jù)情況進(jìn)行調(diào)整，搜索范圍限制在局部搜索樹中。這種搜索策略可通過極大極?。∕INIMAX）搜索來實現(xiàn)。

極大極小搜索具體算法描述如下。

①從起始局面出發(fā)，生成規(guī)定深度的博弈樹（每個結(jié)點對應(yīng)一個局面）。

②用靜態(tài)評估函數(shù)給出每個葉結(jié)點的估值。

③對該博弈樹，自底向上逐級計算每個結(jié)點的值。具體方法為：根據(jù)下一層結(jié)點的值得到博弈樹上一層結(jié)點的值，若輪己方下子，結(jié)點值取下一層的最大值；若輪對方下子，則取下一層的最小值。

④根結(jié)點選擇分枝值最大的著法。

3.2.4.2 α-β剪枝

MINIMAX過程是把搜索樹的生成和格局估值這兩個過程分開來進(jìn)行，即先生成全部搜索樹，然后再進(jìn)行結(jié)點靜態(tài)估值和倒推計算。如果把生成搜索樹和倒推估值結(jié)合起來進(jìn)行，再根據(jù)一定的條件判定，就有可能盡早修剪掉一些無用的分枝，這就是α-β過程的基本思想。

α-β過程的剪枝規(guī)則描述如下。

①α剪枝：若任一極小值層結(jié)點的β值小于或等于它任一先輩極大值層結(jié)點的α值，即α（先輩層）≥β（后繼層），則可中止該極小值層中這個MIN結(jié)點以下的搜索過程。這個MIN結(jié)點最終的倒推值就確定為這個β值。

②β剪枝：若任一極大值層結(jié)點的α值大于或等于它任一先輩極小值層結(jié)點的β值，即α（后繼層）≥β（先輩層），則可中止該極大值層中這個MAX結(jié)點以下的搜索過程。這個MAX結(jié)點最終的倒推值就確定為這個α值[2]。

α-β剪枝方法搜索得到的最佳著法與極大極小方法得到的結(jié)果是一致的，α-β剪枝并沒有因為提高效率，而降低搜索的效果。在實際搜索時，并不是先生成指定深度的搜索樹，再在搜索樹上進(jìn)行剪枝。如果這樣，就失去了α-β剪枝方法的意義。在實際實現(xiàn)時，首先規(guī)定一個搜索深度，然后按照類似于深度優(yōu)先搜索的方式，生成結(jié)點。在結(jié)點的生成過程中，如果在某一個結(jié)點處發(fā)生了剪枝，則其余未生成的結(jié)點就不再生成了。

α-β剪枝過程是二人博弈問題的一般搜索方法，實踐證明，該方法可以有效地減少在搜索過程中生成的結(jié)點數(shù)，提高搜索效率。

4 結(jié)束語

圍棋充滿了無窮的奧妙和永恒的魅力，將人工智能技術(shù)應(yīng)用于計算機(jī)圍棋實踐中，對圍棋本身的理論研究以及人工智能科學(xué)的發(fā)展都有著重要的意義。

參考文獻(xiàn)

[1]曹永忠. 基于互聯(lián)網(wǎng)的圍棋對弈及著手搜索系統(tǒng)的研究[DB/OL]. 萬方數(shù)據(jù), 2009.

[2]林堯瑞，馬少平．人工智能導(dǎo)論[M]．北京：清華大學(xué)出版社，1989：120.

作者簡介：張全中，1969年生，男，碩士，工程師，圍棋業(yè)余5段，研究方向為計算機(jī)應(yīng)用。