陳雪健，張利群，曹楊

（遼寧石油化工大學(xué)計算機與通信工程學(xué)院，撫順 113001）

0 引言

近年來，中國大學(xué)生計算機博弈大賽暨中國計算機博弈錦標(biāo)賽開展得越來越好，主要表現(xiàn)在兩個方面，一個是參加大賽的高校代表隊越來越多，另一個是競賽棋種越來越多，截止到2019 年，比賽棋種達(dá)到19 種。

在中國大學(xué)生計算機博弈大賽暨中國計算機博弈錦標(biāo)賽中，不圍棋是在2012 年引入的競賽棋種，當(dāng)年共有8 個代表隊參加不圍棋的比賽[1-4]。2019 年的中國大學(xué)生計算機博弈大賽暨中國計算機博弈錦標(biāo)賽中共有12 個代表隊參加不圍棋的比賽，可見大學(xué)生對不圍棋的參與度不高，原因是多方面的，其一是對不圍棋的研究文獻極少，可借鑒的內(nèi)容不多，其次與不圍棋本身具有的特點有重要關(guān)系，那就是行子策略復(fù)雜、棋局的復(fù)雜度高以及行子可行性判定算法實現(xiàn)困難[5-10]，這些特點限制了許多大學(xué)生組隊參賽。本文介紹了不圍棋博弈程序?qū)崿F(xiàn)過程中的一種策略以及著法可行性的判定算法。

不圍棋（No Go）也是國際計算機奧林匹克競賽棋種，其棋盤、棋子和棋規(guī)定義如下。

（1）棋盤

不圍棋棋盤同九路圍棋棋盤，即9×9 圍棋的棋盤，如圖1 所示。

圖1 不圍棋棋盤

（2）棋子

黑、白兩色圍棋棋子。

（3）棋規(guī)

①黑子先手，雙方輪流落子，落子后棋子不可移動；

②吃子：一個棋子在棋盤上，與它直線緊鄰的空點是這個棋子的“氣”。棋子直線緊鄰的點上，如果有同色棋子存在，則它們便相互連接成一個不可分割的整體，它們的氣也應(yīng)一并計算。棋子直線緊鄰的點上，如果有異色棋子存在，這口氣就不復(fù)存在。如所有的氣均為對方所占據(jù)，便呈無氣狀態(tài)，無氣狀態(tài)的棋子不能在棋盤上存在，應(yīng)當(dāng)提出盤外。當(dāng)一方落子，使得對方的棋子為無氣狀態(tài)，就是吃子。

③對弈的目標(biāo)不是吃掉對方的棋子，不是占領(lǐng)地盤，恰恰相反，如果一方落子后吃掉了對方的棋子，則落子一方判負(fù)；

④對弈禁止自殺，落子自殺一方判負(fù)；

⑤對弈禁止空手（pass），空手一方判負(fù)；

⑥每方用時15 分鐘，超時判負(fù)；

⑦對弈結(jié)果只有勝負(fù)，沒有和棋。

1 一種行棋的策略

從不圍棋的棋規(guī)中可以看出，對弈的目標(biāo)不是吃掉對方的棋子，不是占領(lǐng)地盤，取勝的關(guān)鍵是誰最后有位置可行棋，誰最后取得勝利。

雖然占領(lǐng)地盤大小不決定勝負(fù)，但是從實戰(zhàn)經(jīng)驗來看，往往占用地盤多且眼多的一方在收官階段行棋的位置就多一些，獲勝的概率就大一些，因此在自己成眼的同時，破壞對方成眼，逼迫對方眼少，最終使對方無處可走，直至輸棋。為闡述方便，所有圖示當(dāng)中，以黑子代表我方，白子代表對手方。在實現(xiàn)不圍棋計算機博弈程序時，策略有很多，以下是自己采用的一種策略。

1.1 先占角、再占邊，最后占中間

在不圍棋的行子過程中，構(gòu)成眼最少用兩子，就是角，其次是邊，最后是中間，如圖2 所示。

圖2 三種類型的眼

事實上，由于不圍棋棋規(guī)要求，即使構(gòu)成上述眼的情況，確實限定了對方在眼處行棋，但是自己將來也不一定能在自己構(gòu)成的眼處行棋，還要看周邊的情況，也就是氣的情況，這也是行棋過程中要注意的地方。

如圖3 所示，黑方眼的位置，黑方自己也不可以行棋，因為行棋就是自殺棋。

圖3 黑方無法在自己眼處行棋

最好將兩個以上的眼連在一起，也就是圍棋的做活，迫使對方在自己的眼處無法行棋，而自己在收官階段，由于有兩個眼，至少還有兩口氣在，就能在自己的眼處行棋，如圖4 所示。

圖4 在黑方眼處可以行一個黑子

1.2 攻擊對手的策略

在對弈過程中，要極力破壞對手眼的形成，最好在行棋過程中既能自己形成眼，又能破壞對方眼的形成，這是最佳策略。在破壞對方成眼時，重點考慮如下幾種情況，形成提前預(yù)判。由于各種情況的種類較多，這里僅舉幾個代表性的示例。

（1）行一子，欲形成四個眼，如圖5 所示。

圖5 行一子欲形成四個眼

（2）行一子，欲形成三個眼。

（3）行一子，欲形成兩個眼，如圖6 所示。

圖6 行一子欲形成兩個眼

（4）行一子，欲形成一個眼。

在行棋過程中，還要盡可能不讓對方棋子做活，這樣即使對方形成了單眼也無法在單眼處行棋。

2 不圍棋的存儲結(jié)構(gòu)

針對不圍棋棋盤行和列的特點，其棋盤的物理存儲結(jié)構(gòu)可以采用二維數(shù)組來表示，用C 語言描述如下：

int b[9][9];

不圍棋就有黑白兩種棋子，可以將黑子和白子分別用1 和2 來表示。

假設(shè)目前棋局如圖7 所示，在計算機存儲時，用二維數(shù)組表示如下：

圖7 棋局狀態(tài)圖

b[0][0]～b[0][8]:0，2，0，1，0，1，0，1，0

b[1][0]～b[1][8]:1，0，2，2，0，0，1，0，2

b[2][0]～b[2][8]:0，2，0，2，0，0，0，0，0

b[3][0]～b[3][8]:0，0，1，0，0，0，0，0，0

b[4][0]～b[4][8]:0，0，0，0，1，0，0，0，0

b[5][0]～b[5][8]:0，0，0，0，0，0，0，0，0

b[6][0]～b[6][8]:0，0，0，0，0，0，0，0，0

b[7][0]～b[7][8]:1，0，0，0，0，0，2，0，1

b[8][0]～b[8][8]:0，2，0，0，0，0，2，1，0

也就是，棋盤上行棋位置有黑子的值是1，有白子的值是2，無子的位置為0。

后面算法需要將上述二維數(shù)組的位置存儲到一個棧中，這就需要將二維坐標(biāo)（i，j）轉(zhuǎn)化為一維坐標(biāo)k，轉(zhuǎn)換方法如下：

k=i*9+j

反過來，將存儲起來的一維坐標(biāo)k 轉(zhuǎn)換為二維坐標(biāo)（i，j）的方法如下：

i=k∕9

j=k%9

3 著法可行性算法

在不圍棋的“機-機”博弈過程中，對弈雙方交替行棋，按照棋規(guī)，在行子過程中不能吃對方棋子，也不能自殺，因此，我方在某個位置準(zhǔn)備行棋，就要判斷該位置是否可以行棋，即要判斷在這個位置行棋之后，是否我方連成一片的棋子有氣，同時還要判斷與我方行棋處鄰接的對方棋子是否有氣。

3.1 同色鄰接棋子位置入棧遞歸函數(shù)

為了能夠判斷在b[i][j]處我方落黑子之后，是否吃掉了對方棋子，就要看這個黑子鄰接的白子是否有氣，沒有氣就是吃子了，如圖8 所示，假設(shè)b[i][j]為b[5][3]。

圖8 黑子行棋位置

如何判斷鄰接的白子是否有氣？這就需要把與黑子鄰接的上下左右四個方向的白子塊，存儲起來，再計算其氣數(shù)，只要有一個白子塊的氣數(shù)為零，則說明吃子發(fā)生了，這樣我方在這個b[i][j]處就不能行棋。判斷黑棋是否是自殺，道理與這個相同，不再贅述。用于存儲白子塊、黑子塊的線性表如下，采用的是棧的存儲方式[11-14]。

int wstack[81]，wtop=-1;

int bstack[81]，btop=-1;

采用深度優(yōu)先算法將所有鄰接的白子所在位置全部存儲在一維數(shù)組wstack 中，且存儲過程中，每一位置都不重復(fù)存儲。函數(shù)int Isunique（int x）用于判定位置x 是否在棧中出現(xiàn)，若出現(xiàn)函數(shù)值為0，否則函數(shù)值為1，函數(shù) Isunique（int x）實現(xiàn)簡單，在此略去。

鄰接白棋子的位置入棧遞歸函數(shù)如下：

與（i，j）處鄰接的黑子入棧函數(shù)，與函數(shù)Adwpush（）的類型及參數(shù)一致，可參照函數(shù)Adwpush（）實現(xiàn)，不妨叫做 Adbpush（）。

3.2 氣的計算算法

把鄰接的白子塊存儲在了棧wstack[]中，該白子塊是否有氣，只需檢查白子塊中每個棋子的上下左右是否有空位置，只要有一個白色棋子鄰接一個空位置，這個白子塊就有氣。

計算白子塊氣的算法如圖9 所示，稱之為Haswqi（）算法，返回值是1，就代表有氣，算法返回值是0，就代表無氣。

對于鄰接b[i][j]的黑子，只有一個黑子塊，其氣的計算算法與此類似，不再贅述，稱之為Hasbqi（）算法。

圖9 Haswqi（）算法

3.3 著法可行性判定算法

有了上述算法，就可以給出我方在b[i][j]處著法可行性判定算法，如圖10 所示。若在b[i][j]處可行棋，算法返回值為1，不可行棋，算法返回值為0。

當(dāng)我方要在b[i][j]處行子，根據(jù)i、j 的值，最多需要判斷四個白子塊的氣，這四個白子塊是分別從b[i-1][j]、b[i+1][j]、b[i][j-1]及 b[i][j+1]處進行深度優(yōu)先遍歷得到的。其中Initwstack（）是白子塊棧初始化函數(shù)，Initb?stack（）是黑子塊棧初始化函數(shù)。

4 結(jié)語

由于不圍棋的復(fù)雜性，無法生成及存儲完整的博弈樹，因此采用什么樣的方法來準(zhǔn)確評估當(dāng)前局面的好壞一直是不圍棋博弈程序設(shè)計者研究的一個問題，而著法可行性判定算法又是局面評估的基礎(chǔ)。

在中國大學(xué)生計算機博弈大賽暨中國計算機博弈錦標(biāo)賽中，使用上述策略和算法實現(xiàn)的不圍棋博弈程序，得到了檢驗。實踐證明，博弈程序運行正確，速度快，安全可靠，不僅順利完成全部比賽，而且達(dá)到了預(yù)期效果。

圖10 著法可行性判定算法