一种基于局面形势的军棋博弈系统

张 玮， 王 俊， 闫 桐， 孟 坤

(1 北京信息科技大学 计算机学院， 北京 100101; 2 北京信息科技大学 感知与计算智能联合实验室， 北京 100101)

引言

计算机博弈又称机器博弈，是人工智能领域的一个重要研究方向，也是具备高度智能挑战性的研究内容。不完全信息博弈作为计算机博弈的一个分支,相对于双方信息透明的完备信息博弈,更接近于在现实世界中不确定条件下的判别决策,具有更强的研究价值。特别地，军棋是广受欢迎的棋类游戏之一,也是一种典型的不完全信息博弈，对其研究即呈现出卓然可观的现实意义与价值。军棋的行棋规则就是军长>师长>旅长>团长>营长>连长>排长。军棋中，地雷不可移动，工兵在铁路可以飞，棋子在公路上时只可走一步。终场时，最先将对方军旗挖掉的一方即可获得本场比赛的胜利，关于军棋的具体理论知识和详细规则请参照文献[1]。

综合往届参加计算机博弈大赛的军棋博弈系统以及原有的军棋博弈系统的研究可知[2]，有的程序只是一味追求进攻、防守，导致最终进入残局后，仍然囿于某些原因而战败失利。本系统在这一方面做出了重大改进。其中，改善了基于经验知识的搜索算法，并加入了新的局面评估，将局面分为3种形势，使程序的智能性大大提高。

1 军棋博弈系统中的基本表示

为了下面表述方便，本节将后文中用到的棋子的符号表示，变量名称以及函数名进行了统一处理，具体内容如下。

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//记录未吃子步数

(2)ismy//标识是否为己方先未吃子

(3)havebest//标识是否有最佳走法

(4)bestmove//记录最佳走法

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

(6)cMap[12][5] //整个棋盘局面12*5的相应位置

2 工兵飞功能的改进

工兵飞即为工兵沿铁路线移动时可不限格数直行或转弯到达铁路线上未被阻挡的任何兵站。本文运用了数据结构中图的思想，将棋盘中的整个铁路看作是一张图，运用邻接表存储方式将铁路图存储。并在每个点上赋予值，然后当点上的棋子不为空时，将该点标记为1，再运用深度遍历的方法，将整张图完整遍历一次，以实现工兵飞的功能。改进后的设计过程可阐释如下。

首先，将铁路上的所有点用横纵坐标表示出来，结果展现如图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;

工兵在铁路上的走法的研发代码可详见如下：

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

//深度遍历

if(checkGet==1)

{

checkGet=0;

return 1;

}

else

{

return 0;

}

3 基于局面形势的设计

3.1 基于局面形势的总体设计

本文将局面分为3种不同类型：进攻、防守、特殊。并且利用α-β剪枝技术将不同局面下的所有走法进行剪枝，搜索出最优的解法。用havebest标识是否为最佳走法：havebest=0为没有最佳走法，havebest=1为有最佳走法。基于局面形势的总体设计如图2所示。

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

3.2 局面评估

判断整个局面的形势就需要用到局面评估函数。本文重点就在于根据不同的局面形势进行评估，然后做出相应的对策。这里的局面评估主要分为2类，即对方的局面评估和己方局面评估。

局面评估研究中，通常需要涉及一些关键因素，现对其给出如下设计解析。

3.2.1 棋子的基本价值

棋子的价值是指某棋子本身的价值。在局面评估时，首先要考虑的就是双方棋子武力总和的比较。这就需要得到双方棋子武力总和。

这里，关于对方局面评估函数，研发推得代码如下：

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 对方不同棋子在棋盘上出现的概率

军棋是一种不完全信息博弈。因为不知道对方的布局，以及不同棋种的配放位置，这时就需要统计各个棋子在棋盘上的出现概率，最终获得棋子布防的大致判断。

研究中，可通过查找不同的棋局，进而统计出棋子在棋盘上的概率。

3.3 进攻局面的设计

进攻局面主要是针对己方第31步未碰棋判负，和在己方局面占据赢面情况下进一步扩大优势进攻而设定的。如何判断己方局面为优，主要根据局面评估函数，设定己方评估值，比对方高出53或敌方司令已经被吃掉时即为优势，因为在敌方司令未被吃掉时，军长加上一个师长的价值就等于53，这在比赛中已经相差很多了，因为其它棋子的价值更低，同等要输掉更多的其它棋子，所以本系统则暂定为53这个数值。

31步问题，一般是因为双方的最佳走法固定，导致双方行棋循环，这种情况下，如果是己方先行没有交棋，即ismy为1时，规定己方在第7步还未吃子的情况下，调用31步函数，进行交棋，防止己方因为31步未能交棋而输掉比赛。相反，如果ismy不为1时，则不需要打破这个循环。

由此得到伪代码如下：

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];

}

}

}

在己方局面为优势，且对方司令未被吃时，己方可以先行去占领对方的一个大本营，将优势扩大。伪代码如下：

for(m=0;m

{

if(走法器中有占领(0，1)的走法)

{

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

当对方司令已经被吃，如果己方占领的大本营中不是对方军旗的位置，就需要迅速改变行棋走法，更换为另一个大本营。此时的基本设计代码为：

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 防守局面的设计

防守局面主要针对于己方军棋左、右和上方三点有对方棋子，己方下三行有敌方棋子，和局面劣势时进行防守。局面劣势的判定，主要根据己方司令是否被吃和局面评估值比对方少于53来衡量判定。

军旗附近有对方棋子情况，表明对于己方来说已迫在眉睫了，很有可能几回合后己方军旗就会被吃掉，从而输掉比赛。所以要从所有的走法中，搜索是否存在走法m_MoveList[0][m]可以叫对方的棋子吃掉，然后将其设为最佳走法。伪代码如下：

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

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

for(己方每一种走法){

if(该步可吃掉对方处在该cMap[x][n]位置棋子X){

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

}

3.5 特殊情况的设计

本节设计就是针对一些相对特殊的局面研发编写的，根据日常行棋时遇到的特殊情况而定制的特殊函数，有时却可能是取得胜利的关键。针对这一内容，设计得到论述内容如下。

3.5.1 特殊设计1

先设对方未知棋子类型为X，当对方棋子X在对方非后两行(军旗和军旗下方两行)吃了己方军长b或师长c时，则说明对方棋子的武力值force(X)大于己方棋子的武力值force(b或c)。由此可推得对方棋子有很大概率为司令或军长，这时即可搜索己方所有走法，若有己方炸弹可以炸掉该棋子的走法，则将其设为最佳走法。伪代码如下：

if(己方军长b或师长c被吃掉){

for(所有走法){

if(己方炸弹炸掉对方该棋子){

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

3.5.2 特殊设计2

在对方两侧除了底线和大本营都没有棋子时，可以先行去占领对方底角，因为底角已经是致命之地，很有可能就是旗侧，基本宣布对方的死亡。伪代码如下：

If(对方左侧或右侧除底线和大本营两行外没有其他棋子){

for(所有走法){

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

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

3.5.3 特殊设计3

当占领对方两侧的底角时，很有可能己方的大棋子，如军、师、旅被吃掉时，该位置很有可能为地雷，如果在己方所有的走法中，存在己方工兵或炸弹即m_MoveList[0][m].ChessID==’i’||m_MoveList[0][m].ChessID==’k’，可以去挖掉地雷时，则将其设置为最佳走法。伪代码如下：

If(己方军、师、旅占领对方底角时被吃){

for(所有走法){

if(己方工兵或炸弹可以到达底角){

havebest= 1;

bestmove=m_MoveList[0][m];

}

}

}

同时，如果对方左侧或右侧为地雷，则可以说明该点即为旗侧，对方军旗就在旁边，将其占领将可以获得全盘胜利。

4 实验对比

该系统在vs2017的集成环境下，利用C++语言编写完成。最终在Windows环境下将本程序与往届参赛的程序分别进行100局先手以及100局后手对战。对战详情结果具体可见表2。

表2 对战结果表Tab. 2 The result table of experiment

由对战结果可以看出，改进后的程序相比于原始程序胜率上高出了很多，有较大的提升。

5 结束语

本文设计实现了一个军棋博弈系统。本系统通过判断局面形势以及一些特殊的局面，提高了机器博弈的智能水准。同时将工兵飞的功能融入了设计改进，在走法上增加了一些军棋比赛时的主体经验，使系统的智能化更趋完善。目前，该系统还有一些不足之处，例如走法产生器给出的走法还未臻至理想，虽然经过修改，已经获得了明显进步，但是通过

2017年的全国大学生计算机博弈大赛，与其它参赛选手的程序相比，发现仍然存在较大拓展提升空间。下一步将参考UCT相关算法来寻求研发、并获得本系统的更佳运行效果。

[1] 中国人工智能学会机器博弈专业委员会. 军棋竞赛规则[2016-11-18]. [EB/OL]. http://computergames.caai.cn.

[2] 孟坤， 王俊， 闫桐. 一种基于经验知识的军棋博弈算法设计与实现[J]. 智能计算机与应用,2017, 7(2):66-69.

[3] 齐玉东. 军棋游戏中的工兵寻径算法的实现[J]. 电脑编程技巧与维护,2016(8):71-73.

[4] 罗涛. 中国象棋博弈·局面评估研究[D]. 南昌：南昌大学,2009.