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

《一个幻影围棋计算机博弈系统设计和实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一个幻影围棋计算机博弈系统设计和实现摘要:幻影围棋作为一个刚兴起不久的棋类游戏，属于不完全信息博弈，目前对幻影围棋的研究与开发较少，在国内才刚刚起步。分析了幻影围棋计算机博弈系统的模型与结构，结合Alpha-Eeta搜索算法和蒙特卡洛算法的优势，依据棋盘状态采用不同的搜索算法，调用搜索引擎产生下子，在此基础上开发实现了一个幻影围棋博弈系统，能有效的交互和处理信息，并通过了运行测试。关键词：计算机博弈；幻影围棋；不完全信息博弈；Alpha-Beta；蒙特卡洛中图分类号:TP18文献标识码：A文章编号:1005-3824(

2、2014)01—0001—060引言计算机博弈是人工智能领域的重要课题，目前，对于像国际象棋、九路围棋等棋类游戏的研究已相对成熟，幻影围棋作为一个刚兴起不久的棋类游戏，属于不完全信息博弈。该棋是在围棋规则的基础上加入了信息不完全的限制，即双方均无法获取对手的棋子位置信息，由裁判根据双方棋盘状态返回的命令进行操作［1］。国际计算机奥林匹克从2007年开始加入幻影围棋项目，由中国人工智能学会举办的中国计算机博弈锦标赛于2012年加入计算机幻影围棋比赛。在过去的半个多世纪里，世界各地的学者投入了大量的精力来研究基于棋类游戏的

3、计算机博弈，产生了很多理论和算法。对于计算机围棋，其博弈求解的主要方法就是在其博弈树中搜索，博弈搜索的目标就是搜索最佳路径，搜索当前的最佳着法，并且亦步亦趋地进行下去［2］。搜索的算法包括极大极小搜索［3］,Alpha-Beta剪枝搜索［4］、迭代加深［5］、置换表［6］、负极大值搜索［7］、蒙特卡洛模拟［8］和UCT算法［9］等。针对不完全信息博弈的幻影围棋，文献［10］中提出了与围棋中类似的蒙特卡洛算法，为处理隐藏信息，需要在每次模拟前随机地猜测对手棋子的位置，并放上对手的棋子。文献［11］中提出了4种不同的蒙特卡

4、洛方法，通过实验验证了文献［10］中所提方法的有效性［11］。但该搜索方法存在较大的随机性，无法获取较为完整的对手棋子信息。本文探讨了Alpha-Beta剪枝搜索算法和蒙特卡洛算法,引入了搜寻对方棋子信息的策略，通过此探寻策略获取更多的对手棋子信息，然后结合2种算法在完全信息与不完全信息博弈的优势，依据棋盘状态采用不同的搜索算法，并在此基础上开发出了一个完整的幻影围棋博弈系统。1系统的结构与功能模块幻影围棋博弈系统的结构如图1所示，主要分为3部分:一是当前棋盘状态控制部分，其中应该包含己方棋子的所有信息和经过逻辑判断所

5、得出的对方棋子的部分信息；另一个部分是信息交互和处理，对于选手机，主要是接受裁判返回的各种信息以及生成信息，然后通过这些信息对自己所掌握的信息进行更新。对于裁判机，主要是接受选手机发来的信息，然后根据幻影围棋规则返回相应的信息；第三个部分就是评估搜索，该部分会根据目前的棋盘状态，采用搜索算法和估值策略，并从所有着法中选择最优的着法作为当前着法。1）棋盘状态控制模块:该模块包括棋盘界面的绘制,棋谱的绘制及计时等功能。2）信息交互和处理模块：该模块主要包括选手机与裁判机的通信，选手机或裁判收到信息后，针对不同信息进行相应的

6、处理。3）评估搜索模块：该模块包括静态棋盘估值、IBIIAlpha-Beta剪枝搜索算法和蒙特卡洛算法。盘面评估与博弈搜索是计算机博弈的2个重要组成部分，是计算机博弈系统智能化的重要方法[12]o要实现对战就必须加载能让机器走子的策略，要实现效果比较好的对弈结果，就必须加载智能化的搜索策略。本文采用Alpha-Beta剪枝搜索算法和蒙特卡洛算法相结合的策略，根据两者的优势，依据棋盘状态采用不同的搜索算法。Alpha-Beta剪枝搜索算法在极大极小搜索算法的基础上加入了剪枝策略，减少了博弈树的节点数，提高了搜索效率。在完

7、全信息博弈的条件下，该算法能配合静态棋盘估值函数找到估值最大的着法。该方法在本系统中的应用：先通过盘面扫描搜索所有可下点，然后针对每个可下点通过展开博弈树，运用递归的算法对深度为3层的节点进行估值，返回估值最大的根节点所对应的着法。图2(a)和2(b)分别是Alpha剪枝和Beta剪枝的过程。由图2(a)可知，根节点下面有3个子节点和9个孙节点(叶节点)，搜索从左路分枝开始，根节点所在的MAX层的值是由该分支的叶子节点倒推得到的，记为Alpha,值为6o然后中路分支搜索到叶子节点发现值为5,小于Alpha值，则减掉该分

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