張 瑋， 王 俊， 閆 桐， 孟 坤

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

引言

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

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

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

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

1.1 雙方棋子種類的分類

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

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

1.2 棋子武力值(見表1)

表1 棋子與價(jià)值對(duì)照表Tab. 1 Comparison table of pieces name and piece value

1.3 變量名定義

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

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

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

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

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

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

2 工兵飛功能的改進(jìn)

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

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

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

然后，就運(yùn)用頭插法將表建立起來。頭插法如下：

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è)計(jì)

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

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

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

3.2 局面評(píng)估

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

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

3.2.1 棋子的基本價(jià)值

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

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

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

{

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

{

if(棋盤上這個(gè)點(diǎn)沒有對(duì)方棋子)

{

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

{

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

}

OpponentScore=OpponentScore+

tempscore;

tempscore=0;

}

}

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

軍棋是一種不完全信息博弈。因?yàn)椴恢缹?duì)方的布局，以及不同棋種的配放位置，這時(shí)就需要統(tǒng)計(jì)各個(gè)棋子在棋盤上的出現(xiàn)概率，最終獲得棋子布防的大致判斷。

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

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

進(jìn)攻局面主要是針對(duì)己方第31步未碰棋判負(fù)，和在己方局面占據(jù)贏面情況下進(jìn)一步擴(kuò)大優(yōu)勢進(jìn)攻而設(shè)定的。如何判斷己方局面為優(yōu)，主要根據(jù)局面評(píng)估函數(shù)，設(shè)定己方評(píng)估值，比對(duì)方高出53或敵方司令已經(jīng)被吃掉時(shí)即為優(yōu)勢，因?yàn)樵跀撤剿玖钗幢怀缘魰r(shí)，軍長加上一個(gè)師長的價(jià)值就等于53，這在比賽中已經(jīng)相差很多了，因?yàn)槠渌遄拥膬r(jià)值更低，同等要輸?shù)舾嗟钠渌遄樱员鞠到y(tǒng)則暫定為53這個(gè)數(shù)值。

31步問題，一般是因?yàn)殡p方的最佳走法固定，導(dǎo)致雙方行棋循環(huán)，這種情況下，如果是己方先行沒有交棋，即ismy為1時(shí)，規(guī)定己方在第7步還未吃子的情況下，調(diào)用31步函數(shù)，進(jìn)行交棋，防止己方因?yàn)?1步未能交棋而輸?shù)舯荣?。相反，如果ismy不為1時(shí)，則不需要打破這個(gè)循環(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)勢，且對(duì)方司令未被吃時(shí)，己方可以先行去占領(lǐng)對(duì)方的一個(gè)大本營，將優(yōu)勢擴(kuò)大。偽代碼如下：

for(m=0;m

{

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

{

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

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

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ì)

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

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

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

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

for(己方每一種走法){

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

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

}

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

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

3.5.1 特殊設(shè)計(jì)1

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

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

for(所有走法){

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

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

3.5.2 特殊設(shè)計(jì)2

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

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

for(所有走法){

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

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

3.5.3 特殊設(shè)計(jì)3

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

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

for(所有走法){

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

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

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

4 實(shí)驗(yàn)對(duì)比

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

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

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

5 結(jié)束語

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

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

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

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

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

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