張 瑋， 王 俊， 閆 桐， 孟 坤

(1 北京信息科技大學(xué) 計算機學(xué)院， 北京 100101; 2 北京信息科技大學(xué) 感知與計算智能聯(lián)合實驗室， 北京 100101)

引言

計算機博弈又稱機器博弈，是人工智能領(lǐng)域的一個重要研究方向，也是具備高度智能挑戰(zhàn)性的研究內(nèi)容。不完全信息博弈作為計算機博弈的一個分支,相對于雙方信息透明的完備信息博弈,更接近于在現(xiàn)實世界中不確定條件下的判別決策,具有更強的研究價值。特別地，軍棋是廣受歡迎的棋類游戲之一,也是一種典型的不完全信息博弈，對其研究即呈現(xiàn)出卓然可觀的現(xiàn)實意義與價值。軍棋的行棋規(guī)則就是軍長>師長>旅長>團長>營長>連長>排長。軍棋中，地雷不可移動，工兵在鐵路可以飛，棋子在公路上時只可走一步。終場時，最先將對方軍旗挖掉的一方即可獲得本場比賽的勝利，關(guān)于軍棋的具體理論知識和詳細規(guī)則請參照文獻[1]。

綜合往屆參加計算機博弈大賽的軍棋博弈系統(tǒng)以及原有的軍棋博弈系統(tǒng)的研究可知[2]，有的程序只是一味追求進攻、防守，導(dǎo)致最終進入殘局后，仍然囿于某些原因而戰(zhàn)敗失利。本系統(tǒng)在這一方面做出了重大改進。其中，改善了基于經(jīng)驗知識的搜索算法，并加入了新的局面評估，將局面分為3種形勢，使程序的智能性大大提高。

1 軍棋博弈系統(tǒng)中的基本表示

為了下面表述方便，本節(jié)將后文中用到的棋子的符號表示，變量名稱以及函數(shù)名進行了統(tǒng)一處理，具體內(nèi)容如下。

1.1 雙方棋子種類的分類

(1) 己方棋子編碼約定:/*a司令,b軍長,c師長,d旅長,e團長,f營長,g連長,h排長,i工兵,j地雷,k炸彈,l軍旗*/

(2) 對方棋子編碼約定:/*A司令,B軍長,C師長,D旅長,E團長,F營長,G連長,H排長,I工兵,J地雷,K炸彈,L軍旗*/

1.2 棋子武力值(見表1)

表1 棋子與價值對照表Tab. 1 Comparison table of pieces name and piece value

1.3 變量名定義

(1)bushu//記錄未吃子步數(shù)

(2)ismy//標(biāo)識是否為己方先未吃子

(3)havebest//標(biāo)識是否有最佳走法

(4)bestmove//記錄最佳走法

(5)m_MoveList[m][n] //存儲所有走法

(6)cMap[12][5] //整個棋盤局面12*5的相應(yīng)位置

2 工兵飛功能的改進

工兵飛即為工兵沿鐵路線移動時可不限格數(shù)直行或轉(zhuǎn)彎到達鐵路線上未被阻擋的任何兵站。本文運用了數(shù)據(jù)結(jié)構(gòu)中圖的思想，將棋盤中的整個鐵路看作是一張圖，運用鄰接表存儲方式將鐵路圖存儲。并在每個點上賦予值，然后當(dāng)點上的棋子不為空時，將該點標(biāo)記為1，再運用深度遍歷的方法，將整張圖完整遍歷一次，以實現(xiàn)工兵飛的功能。改進后的設(shè)計過程可闡釋如下。

首先，將鐵路上的所有點用橫縱坐標(biāo)表示出來，結(jié)果展現(xiàn)如圖1所示。

圖1 軍棋棋盤棋位編碼圖示Fig. 1 The chessboard position coding of the stand of colors

然后，就運用頭插法將表建立起來。頭插法如下：

ptrEdgeNode->adjvex=j;

ptrEdgeNode->next=G->adjList[i].firstedge;

G->adjList[i].firstedge=ptrEdgeNode;

工兵在鐵路上的走法的研發(fā)代碼可詳見如下：

DFSTraverse(G,x1,y1,x2,y2);

//深度遍歷

if(checkGet==1)

{

checkGet=0;

return 1;

}

else

{

return 0;

}

3 基于局面形勢的設(shè)計

3.1 基于局面形勢的總體設(shè)計

本文將局面分為3種不同類型：進攻、防守、特殊。并且利用α-β剪枝技術(shù)將不同局面下的所有走法進行剪枝，搜索出最優(yōu)的解法。用havebest標(biāo)識是否為最佳走法：havebest=0為沒有最佳走法，havebest=1為有最佳走法?；诰置嫘蝿莸目傮w設(shè)計如圖2所示。

圖2 搜索算法整體流程圖Fig. 2 The integral flow chart of search algorithm

3.2 局面評估

判斷整個局面的形勢就需要用到局面評估函數(shù)。本文重點就在于根據(jù)不同的局面形勢進行評估，然后做出相應(yīng)的對策。這里的局面評估主要分為2類，即對方的局面評估和己方局面評估。

局面評估研究中，通常需要涉及一些關(guān)鍵因素，現(xiàn)對其給出如下設(shè)計解析。

3.2.1 棋子的基本價值

棋子的價值是指某棋子本身的價值。在局面評估時，首先要考慮的就是雙方棋子武力總和的比較。這就需要得到雙方棋子武力總和。

這里，關(guān)于對方局面評估函數(shù)，研發(fā)推得代碼如下：

for(i=0;i<12;i++)

{

for(j=0;j<5;j++)

{

if(棋盤上這個點沒有對方棋子)

{

for(k=0;k<12;k++)

{

tempscore=該位置的不同棋種的概率*棋子武力值+tempscore; }

}

OpponentScore=OpponentScore+

tempscore;

tempscore=0;

}

}

3.2.2 對方不同棋子在棋盤上出現(xiàn)的概率

軍棋是一種不完全信息博弈。因為不知道對方的布局，以及不同棋種的配放位置，這時就需要統(tǒng)計各個棋子在棋盤上的出現(xiàn)概率，最終獲得棋子布防的大致判斷。

研究中，可通過查找不同的棋局，進而統(tǒng)計出棋子在棋盤上的概率。

3.3 進攻局面的設(shè)計

進攻局面主要是針對己方第31步未碰棋判負，和在己方局面占據(jù)贏面情況下進一步擴大優(yōu)勢進攻而設(shè)定的。如何判斷己方局面為優(yōu)，主要根據(jù)局面評估函數(shù)，設(shè)定己方評估值，比對方高出53或敵方司令已經(jīng)被吃掉時即為優(yōu)勢，因為在敵方司令未被吃掉時，軍長加上一個師長的價值就等于53，這在比賽中已經(jīng)相差很多了，因為其它棋子的價值更低，同等要輸?shù)舾嗟钠渌遄?，所以本系統(tǒng)則暫定為53這個數(shù)值。

31步問題，一般是因為雙方的最佳走法固定，導(dǎo)致雙方行棋循環(huán)，這種情況下，如果是己方先行沒有交棋，即ismy為1時，規(guī)定己方在第7步還未吃子的情況下，調(diào)用31步函數(shù)，進行交棋，防止己方因為31步未能交棋而輸?shù)舯荣?。相反，如果ismy不為1時，則不需要打破這個循環(huán)。

由此得到偽代碼如下：

if(ismy== 1&&bushu>=7)//31步走法

{

for(intm=0;m

{

if(cMap[m_MoveList[0][m].To.x][m_MoveList[0][m].To.y].chessname==’X’)

{

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

在己方局面為優(yōu)勢，且對方司令未被吃時，己方可以先行去占領(lǐng)對方的一個大本營，將優(yōu)勢擴大。偽代碼如下：

for(m=0;m

{

if(走法器中有占領(lǐng)(0，1)的走法)

{

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

當(dāng)對方司令已經(jīng)被吃，如果己方占領(lǐng)的大本營中不是對方軍旗的位置，就需要迅速改變行棋走法，更換為另一個大本營。此時的基本設(shè)計代碼為：

for(m=0;m

{

if(cMap[m_MoveList[0][m].To.x] [m_MoveList[0][m].To.y].chessname==’L’)

{

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

3.4 防守局面的設(shè)計

防守局面主要針對于己方軍棋左、右和上方三點有對方棋子，己方下三行有敵方棋子，和局面劣勢時進行防守。局面劣勢的判定，主要根據(jù)己方司令是否被吃和局面評估值比對方少于53來衡量判定。

軍旗附近有對方棋子情況，表明對于己方來說已迫在眉睫了，很有可能幾回合后己方軍旗就會被吃掉，從而輸?shù)舯荣?。所以要從所有的走法中，搜索是否存在走法m_MoveList[0][m]可以叫對方的棋子吃掉，然后將其設(shè)為最佳走法。偽代碼如下：

for(n=0;n<5;n++){

if(己方下面三行有對方棋子){

for(己方每一種走法){

if(該步可吃掉對方處在該cMap[x][n]位置棋子X){

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

}

3.5 特殊情況的設(shè)計

本節(jié)設(shè)計就是針對一些相對特殊的局面研發(fā)編寫的，根據(jù)日常行棋時遇到的特殊情況而定制的特殊函數(shù)，有時卻可能是取得勝利的關(guān)鍵。針對這一內(nèi)容，設(shè)計得到論述內(nèi)容如下。

3.5.1 特殊設(shè)計1

先設(shè)對方未知棋子類型為X，當(dāng)對方棋子X在對方非后兩行(軍旗和軍旗下方兩行)吃了己方軍長b或師長c時，則說明對方棋子的武力值force(X)大于己方棋子的武力值force(b或c)。由此可推得對方棋子有很大概率為司令或軍長，這時即可搜索己方所有走法，若有己方炸彈可以炸掉該棋子的走法，則將其設(shè)為最佳走法。偽代碼如下：

if(己方軍長b或師長c被吃掉){

for(所有走法){

if(己方炸彈炸掉對方該棋子){

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

3.5.2 特殊設(shè)計2

在對方兩側(cè)除了底線和大本營都沒有棋子時，可以先行去占領(lǐng)對方底角，因為底角已經(jīng)是致命之地，很有可能就是旗側(cè)，基本宣布對方的死亡。偽代碼如下：

If(對方左側(cè)或右側(cè)除底線和大本營兩行外沒有其他棋子){

for(所有走法){

if(己方棋子可以到達底角){

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

3.5.3 特殊設(shè)計3

當(dāng)占領(lǐng)對方兩側(cè)的底角時，很有可能己方的大棋子，如軍、師、旅被吃掉時，該位置很有可能為地雷，如果在己方所有的走法中，存在己方工兵或炸彈即m_MoveList[0][m].ChessID==’i’||m_MoveList[0][m].ChessID==’k’，可以去挖掉地雷時，則將其設(shè)置為最佳走法。偽代碼如下：

If(己方軍、師、旅占領(lǐng)對方底角時被吃){

for(所有走法){

if(己方工兵或炸彈可以到達底角){

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

同時，如果對方左側(cè)或右側(cè)為地雷，則可以說明該點即為旗側(cè)，對方軍旗就在旁邊，將其占領(lǐng)將可以獲得全盤勝利。

4 實驗對比

該系統(tǒng)在vs2017的集成環(huán)境下，利用C++語言編寫完成。最終在Windows環(huán)境下將本程序與往屆參賽的程序分別進行100局先手以及100局后手對戰(zhàn)。對戰(zhàn)詳情結(jié)果具體可見表2。

表2 對戰(zhàn)結(jié)果表Tab. 2 The result table of experiment

由對戰(zhàn)結(jié)果可以看出，改進后的程序相比于原始程序勝率上高出了很多，有較大的提升。

5 結(jié)束語

本文設(shè)計實現(xiàn)了一個軍棋博弈系統(tǒng)。本系統(tǒng)通過判斷局面形勢以及一些特殊的局面，提高了機器博弈的智能水準(zhǔn)。同時將工兵飛的功能融入了設(shè)計改進，在走法上增加了一些軍棋比賽時的主體經(jīng)驗，使系統(tǒng)的智能化更趨完善。目前，該系統(tǒng)還有一些不足之處，例如走法產(chǎn)生器給出的走法還未臻至理想，雖然經(jīng)過修改，已經(jīng)獲得了明顯進步，但是通過

2017年的全國大學(xué)生計算機博弈大賽，與其它參賽選手的程序相比，發(fā)現(xiàn)仍然存在較大拓展提升空間。下一步將參考UCT相關(guān)算法來尋求研發(fā)、并獲得本系統(tǒng)的更佳運行效果。

[1] 中國人工智能學(xué)會機器博弈專業(yè)委員會. 軍棋競賽規(guī)則[2016-11-18]. [EB/OL]. http://computergames.caai.cn.

[2] 孟坤， 王俊， 閆桐. 一種基于經(jīng)驗知識的軍棋博弈算法設(shè)計與實現(xiàn)[J]. 智能計算機與應(yīng)用,2017, 7(2):66-69.

[3] 齊玉東. 軍棋游戲中的工兵尋徑算法的實現(xiàn)[J]. 電腦編程技巧與維護,2016(8):71-73.

[4] 羅濤. 中國象棋博弈·局面評估研究[D]. 南昌：南昌大學(xué),2009.