一个幻影围棋计算机博弈系统的设计与实现

摘要：

幻影围棋作为一个刚兴起不久的棋类游戏，属于不完全信息博弈，目前对幻影围棋的研究与开发较少，在国内才刚刚起步。分析了幻影围棋计算机博弈系统的模型与结构，结合Alpha-Beta搜索算法和蒙特卡洛算法的优势，依据棋盘状态采用不同的搜索算法，调用搜索引擎产生下子，在此基础上开发实现了一个幻影围棋博弈系统，能有效的交互和处理信息，并通过了运行测试。

关键词：

计算机博弈；幻影围棋；不完全信息博弈；Alpha-Beta；蒙特卡洛

中图分类号：TP18 文献标识码：A 文章编号：1005-3824（2014）01-0001-06

0 引 言

计算机博弈是人工智能领域的重要课题，目前，对于像国际象棋、九路围棋等棋类游戏的研究已相对成熟，幻影围棋作为一个刚兴起不久的棋类游戏，属于不完全信息博弈。该棋是在围棋规则的基础上加入了信息不完全的限制，即双方均无法获取对手的棋子位置信息，由裁判根据双方棋盘状态返回的命令进行操作[1]。国际计算机奥林匹克从2007年开始加入幻影围棋项目，由中国人工智能学会举办的中国计算机博弈锦标赛于2012年加入计算机幻影围棋比赛。

在过去的半个多世纪里，世界各地的学者投入了大量的精力来研究基于棋类游戏的计算机博弈，产生了很多理论和算法。对于计算机围棋，其博弈求解的主要方法就是在其博弈树中搜索，博弈搜索的目标就是搜索最佳路径，搜索当前的最佳着法，并且亦步亦趋地进行下去[2]。搜索的算法包括极大极小搜索[3]、Alpha-Beta剪枝搜索[4]、迭代加深[5]、置换表[6]、负极大值搜索[7]、蒙特卡洛模拟[8]和UCT算法[9]等。针对不完全信息博弈的幻影围棋，文献[10]中提出了与围棋中类似的蒙特卡洛算法，为处理隐藏信息，需要在每次模拟前随机地猜测对手棋子的位置，并放上对手的棋子。文献[11]中提出了4种不同的蒙特卡洛方法，通过实验验证了文献[10]中所提方法的有效性[11]。但该搜索方法存在较大的随机性，无法获取较为完整的对手棋子信息。

本文探讨了Alpha-Beta剪枝搜索算法和蒙特卡洛算法，引入了搜寻对方棋子信息的策略，通过此探寻策略获取更多的对手棋子信息，然后结合2种算法在完全信息与不完全信息博弈的优势，依据棋盘状态采用不同的搜索算法，并在此基础上开发出了一个完整的幻影围棋博弈系统。

1 系统的结构与功能模块

幻影围棋博弈系统的结构如图1所示，主要分为3部分：一是当前棋盘状态控制部分，其中应该包含己方棋子的所有信息和经过逻辑判断所得出的对方棋子的部分信息；另一个部分是信息交互和处理，对于选手机，主要是接受裁判返回的各种信息以及生成信息，然后通过这些信息对自己所掌握的信息进行更新。对于裁判机，主要是接受选手机发来的信息，然后根据幻影围棋规则返回相应的信息；第三个部分就是评估搜索，该部分会根据目前的棋盘状态，采用搜索算法和估值策略，并从所有着法中选择最优的着法作为当前着法。

1）棋盘状态控制模块：该模块包括棋盘界面的绘制，棋谱的绘制及计时等功能。

2）信息交互和处理模块：该模块主要包括选手机与裁判机的通信，选手机或裁判收到信息后，针对不同信息进行相应的处理。

3）评估搜索模块：该模块包括静态棋盘估值、Alpha-Beta剪枝搜索算法和蒙特卡洛算法。

盘面评估与博弈搜索是计算机博弈的2个重要组成部分，是计算机博弈系统智能化的重要方法[12]。要实现对战就必须加载能让机器走子的策略，要实现效果比较好的对弈结果，就必须加载智能化的搜索策略。本文采用Alpha-Beta剪枝搜索算法和蒙特卡洛算法相结合的策略，根据两者的优势，依据棋盘状态采用不同的搜索算法。

Alpha-Beta剪枝搜索算法在极大极小搜索算法的基础上加入了剪枝策略，减少了博弈树的节点数，提高了搜索效率。在完全信息博弈的条件下，该算法能配合静态棋盘估值函数找到估值最大的着法。该方法在本系统中的应用：先通过盘面扫描搜索所有可下点，然后针对每个可下点通过展开博弈树，运用递归的算法对深度为3层的节点进行估值，返回估值最大的根节点所对应的着法。图2（a）和2（b）分别是Alpha剪枝和Beta剪枝的过程。由图2（a）可知，根节点下面有3个子节点和9个孙节点（叶节点），搜索从左路分枝开始，根节点所在的MAX层的值是由该分支的叶子节点倒推得到的，记为Alpha，值为6。然后中路分支搜索到叶子节点发现值为5，小于Alpha值，则减掉该分枝，同理右路分枝也做相同的处理，此类剪枝是Alpha剪枝。

从图2b可知，根节点下面有3个子节点和9个孙节点（叶节点），搜索从左路分枝开始，根节点所在的MIN层的值是由该分支的叶子节点倒推得到的，记为Beta，值为6。然后中路分支搜索到叶子节点发现值为8，大于Beta值，则减掉该分枝，同理右路分枝也做相同的处理，此类剪枝是Beta剪枝。

蒙特卡洛算法能有效处理信息隐藏，通过估算游戏中的随机数据（如对方棋子信息）来寻找最优走法。该算法在幻影围棋中应用的思路：首先，根据当前棋盘信息，将对手余下的相应数量未知棋子随机放在棋盘的空点上；然后，双方都进行随机的模拟落子，直到双方棋子数和眼的总数等于棋盘总坐标点数，则该回合模拟结束。记录每方棋子与眼的数量之和，和较大一方取胜且得1分。当大量模拟之后，通过计算双方的得分之差，差值最高的招法就会被采用。

本文所示系统的盘面评估主要采用了静态估值，通过静态估值函数来评估。影响静态估值函数的因素有很多，主要有“串”、“活眼”、“活棋块”等[13]，这些因素通过合理的评估函数组织在一起，为围棋的着法估值提供依据。

2 幻影围棋计算机博弈系统的实现

幻影围棋计算机博弈系统是采用VS2010作为开发工具，C#语言编写的窗体应用程序。根据上一节的系统结构分析，实现了的主要功能是：控制功能、信息交互和处理功能以及评估搜索功能。

2.1 控制功能实现

控制功能包括棋盘界面的绘制、棋谱绘制和计时。棋盘由9×9的网格组成，横轴用大写字母A-I标示，纵轴用数字1-9标示，系统主界面如图3所示。右侧为一些控制功能按钮，便于单机操作时实现裁判命令，联机操作时则由程序自动接收并处理裁判命令。

2.2 信息交互和处理功能

信息交互和处理功能包括通信功能和信息处理。联机操作时，裁判机和客户机之间通过网络实现信息的交互，主要采用SOCKET方式，发送和监听来自对方的网络数据流。

于选手机主要是接受裁判返回的各种信息（legal； illegal； take，color，N，x1 y1， x2 y2，……， xn yn）以及生成信息（move，x y； pass），然后通过这些信息对自己所掌握的信息进行更新。裁判机主要是接受选手机发来的棋子坐标信息，然后根据幻影围棋规则和棋盘状态做出处理，如果该点为空且不为禁着点，则返回legal，若在该点下子后能提掉对方的棋子，则返回提子信息。

其中关于禁着点的判断是最为复杂的：棋盘上的任何一空点，若某方下子后，该棋子立即呈无气状态，同时又不能提取对方的棋子，这个点叫做“禁着点”。系统程序根据上述定义来做出判断。Judge类中信息处理函数代码如下：

//裁判机处理选手发来的下子信息

public void DataProcess（User user，string str）{

string[] splitStr=str.Split（'，'）；

Position po=Position.ToInt（splitStr[1]）；

//复制棋盘

color[，] tempBoard=new color[11， 11]；

VV.boardCopy（tempBoard，VV.board.ChessBoard）；

tempBoard[po.x， po.y]=user.UserColor；

if（VV.board.IsEmpty（po）） //棋盘该点是否为空

{

Listcleanlist=new List（）；

cleanlist=VV.group.GetCleanList（po，VV.OppColor，tempBoard）；

if （cleanlist.Count==0） //因下该子而被提掉的对方棋子数

{//该点所在的串是否为活串

if（！VV.group.live（po，VV.MyColor，tempBoard））

{

SendToOne（user， "illegal，"）；//禁着点，返回非法信息

return；

}

SendToOne（user， "legal，"）；//发送给选手机

VV.chessmove.MakeMove（po，user.UserColor）；

return；

}//存在提子情况

VV.chessmove.MakeMove（po，user.UserColor）；

string s；

s="take，" + VV.OppColor.ToString（）+"，"+cleanlist.Count.ToString（）+"，"；

foreach （Position pt in cleanlist）

{

s +=pt.ToString（）；

}

SendToAllUser（s）；//将提子链表发给双方选手

return；

}

SendToOne（user， "illegal，"）；

return；

}。

2.3 Monte-Carlo算法

幻影围棋博弈系统中应用的Monte-Carlo（MC）算法思路如下：通过数千盘的模拟随机对战到终局，并统计所有着法的双方胜负盘数之差，差值最高且满足一定胜率的着法即为当前最佳着法。易知基于大量随机事件的招法模拟可以保证Monte-Carlo方法的有效性，且在模拟次数足够多的情况下，随机产生招法的方法是有效的。受限于计算机硬件的性能和编程语言的效率，无法进行上千盘的模拟对局。本系统中为了避免搜索时间过长，保证在比赛规定的时间内产生下子，只设置了50次的搜索次数，置信值设置为10，即50次中只要胜负分数差值大于10则该点就有效。Monte-Carlo算法主要实现代码在类Monte-Carlo中，类中所有方法如表1所示，并列出了部分关键代码。

Monte- Carlo 算法核心代码如下：

public bool MonteCarloSearch（ref Position pMove）

{

int num， point， max_point=0；

int Max；

int pcol=（VV.MyColor==color.black） ？ 0 ： 1；

color oppcolor=（VV.MyColor==color.black） ？ color.white ： color.black；

Position temp=new Position（）；

List apt=new List（）；

apt=SearchAvailablePoint（board.ChessBoard）；//获取所有可下点

foreach （Position begin_stone in apt） //遍历所有可下点

{

boardCopy（）；

if （！check（begin_stone， VV.MyColor））

continue；

if （isEye（begin_stone， tempBoard）） //该点为眼则跳过

continue；

point=0；

// MCMAX为蒙特卡洛模拟次数 初值为50

for （int i=0； i < MCMAX； i++）

{

boardCopy（）；

tempBoard[begin_stone.x， begin_stone.y]=VV.MyColor；

//本方下子数

stone_num[pcol]=board.ChessPlayer[pcol].total+1；

//已知对方棋子数

stone_num[1-pcol]=board.ChessPlayer[pcol].know；

while （board.ChessPlayer[1-pcol].total > stone_num[1-pcol]）

{

Random rd=new Random（）；//产生随机数

Max=81-stone_num[0]-stone_num[1]-eyes[0]-eyes[1]；

num=rd.Next（Max）；

for （temp.x=1； temp.x

{

for（temp.y=1；temp.y

{

if （tempBoard[temp.x， temp.y]==color.empty）

{

num--；

if（num==1 && check（temp，oppcolor））

{

tempBoard[temp.x，temp.y]=oppcolor；

stone_num[1-pcol]++；

temp.x=10；

break；

}

}

}

}//end for

}//end while

//随机下子到终局后的胜负

point +=MonteCarloMove（oppcolor）；//胜则加1，负则减1

VV.gameform.Invoke（myDelegate，"Clear+"）；

}//end for MCMAX=50

if （point > max_point && begin_stone.x ！=pMove.x

&& begin_stone.y ！=pMove.y）

{

max_point=point；

pMove.x=begin_stone.x；

pMove.y=begin_stone.y；

VV.gameform.Invoke（myDelegate，"End+当前最优可下点：

（" + pMove.x + "，" + pMove.y + "）" + "value：" + point）；

}

}//end foreach

if （max_point > believePoint） //胜率最大的点胜率是否大于置信值

{

return true；

}

return false；

}。

2.4 2种搜索方法的结合

Alpha-Beta 剪枝搜索算法（A-B）在完全信息博弈中已经被广泛采用，而幻影围棋属于不完全信息博弈，单独采用会因为获取的对方棋子信息不完整，对局面的估值有所偏差，进而无法找出最优的着法。Monte-Carlo算法为处理隐藏的对方棋子信息，需要多回合的随机模拟，且每次均模拟到终局，搜索耗时长，同时产生的着法的优劣性受模拟次数的限制。

由上可知，信息的不完全制约了前一种算法的效果，而后一种算法为处理不完信息花费了大量的时间，损失了效率。针对未知的棋子信息，本博弈系统中采用了一定的探寻策略：若收到裁判的非法下子点的命令，则该非法点及其周围存在对方的棋子的可能较大，通过增加估值，下次搜索可下点时优先选择该点周边的空点，进而通过对裁判的信息的分析，获取更多未知的对方棋子信息。

假设博弈进行到中局，双方都通过裁判返回的命令获取了部分对方棋子的信息，若已知的对方棋子数与对方棋盘棋子总数的差值（DIFF），小于等于某个阈值，则此时可以采用A-B算法，进行完全信息博弈搜索。当大于该阈值时，系统又启用MC算法进行随机模拟来寻找最佳着法。

3 幻影围棋计算机博弈系统的测试

为评估上述2种算法的结合对幻影围棋计算机博弈系统性能的影响，进行如下实验：采用2种不同搜索引擎的幻影围棋计算机博弈系统，一种只采用Monte-Carlo算法，另一种则采用了上述2种算法（MC+A-B），先后手分别对战5 局，记录最终胜负和每手棋的搜索时间。