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

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

1、第４１卷第１期数字通信Ｖｏｌ４１，Ｎｏ．１２０１４年２月２５日ＤｉｇｉｔａｌＣｏｍｍｕｎｉｃａｔｉｏｎＦｅｂ．２５２０１４１ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００５３８２４．２０１４．０１．００１一个幻影围棋计算机博弈系统的设计与实现１１２胡强，谢显中，张小川（１．重庆邮电大学宽带接入网络研究所，重庆４０００６５；２．重庆理工大学人工智能系统研究所，重庆４０００５４）摘要：幻影围棋作为一个刚兴起不久的棋类游戏，属于不完全信息博弈，目前对幻影围棋的研究与开发较少，在国内才刚刚起步。分析了幻影围棋

2、计算机博弈系统的模型与结构，结合ＡｌｐｈａＢｅｔａ搜索算法和蒙特卡洛算法的优势，依据棋盘状态采用不同的搜索算法，调用搜索引擎产生下子，在此基础上开发实现了一个幻影围棋博弈系统，能有效的交互和处理信息，并通过了运行测试。关键词：计算机博弈；幻影围棋；不完全信息博弈；ＡｌｐｈａＢｅｔａ；蒙特卡洛中图分类号：ＴＰ１８文献标识码：Ａ文章编号：１００５３８２４（２０１４）０１０００１０６息。０引言本文探讨了ＡｌｐｈａＢｅｔａ剪枝搜索算法和蒙特卡计算机博弈是人工智能领域的重要课题，目前，洛算法，引入了

3、搜寻对方棋子信息的策略，通过此探对于像国际象棋、九路围棋等棋类游戏的研究已相寻策略获取更多的对手棋子信息，然后结合２种算对成熟，幻影围棋作为一个刚兴起不久的棋类游戏，法在完全信息与不完全信息博弈的优势，依据棋盘属于不完全信息博弈。该棋是在围棋规则的基础上状态采用不同的搜索算法，并在此基础上开发出了加入了信息不完全的限制，即双方均无法获取对手一个完整的幻影围棋博弈系统。的棋子位置信息，由裁判根据双方棋盘状态返回的［１］１系统的结构与功能模块命令进行操作。国际计算机奥林匹克从２００７年开始加入幻影围棋项目

4、，由中国人工智能学会举办幻影围棋博弈系统的结构如图１所示，主要分的中国计算机博弈锦标赛于２０１２年加入计算机幻为３部分：一是当前棋盘状态控制部分，其中应该包影围棋比赛。含己方棋子的所有信息和经过逻辑判断所得出的对在过去的半个多世纪里，世界各地的学者投入方棋子的部分信息；另一个部分是信息交互和处理，了大量的精力来研究基于棋类游戏的计算机博弈，对于选手机，主要是接受裁判返回的各种信息以及产生了很多理论和算法。对于计算机围棋，其博弈生成信息，然后通过这些信息对自己所掌握的信息求解的主要方法就是在其博弈树中搜

5、索，博弈搜索进行更新。对于裁判机，主要是接受选手机发来的的目标就是搜索最佳路径，搜索当前的最佳着法，并信息，然后根据幻影围棋规则返回相应的信息；第三［２］且亦步亦趋地进行下去。搜索的算法包括极大个部分就是评估搜索，该部分会根据目前的棋盘状［３］［４］［５］极小搜索、ＡｌｐｈａＢｅｔａ剪枝搜索、迭代加深、态，采用搜索算法和估值策略，并从所有着法中选择［６］［７］［８］置换表、负极大值搜索、蒙特卡洛模拟和最优的着法作为当前着法。［９］ＵＣＴ算法等。针对不完全信息博弈的幻影围棋，文献［１０］中提出了与围棋

6、中类似的蒙特卡洛算法，为处理隐藏信息，需要在每次模拟前随机地猜测对手棋子的位置，并放上对手的棋子。文献［１１］中提出了４种不同的蒙特卡洛方法，通过实验验证了文图１博弈系统结构图［１１］献［１０］中所提方法的有效性。但该搜索方法存１）棋盘状态控制模块：该模块包括棋盘界面的在较大的随机性，无法获取较为完整的对手棋子信绘制，棋谱的绘制及计时等功能。收稿日期：２０１３１１１７修回日期：２０１３１２２５２数字通信第４１卷２）信息交互和处理模块：该模块主要包括选手从图２ｂ可知，根节点下面有３个子节点和９个

7、机与裁判机的通信，选手机或裁判收到信息后，针对孙节点（叶节点），搜索从左路分枝开始，根节点所不同信息进行相应的处理。在的ＭＩＮ层的值是由该分支的叶子节点倒推得到３）评估搜索模块：该模块包括静态棋盘估值、的，记为Ｂｅｔａ，值为６。然后中路分支搜索到叶子节ＡｌｐｈａＢｅｔａ剪枝搜索算法和蒙特卡洛算法。点发现值为８，大于Ｂｅｔａ值，则减掉该分枝，同理右路盘面评估与博弈搜索是计算机博弈的２个重要分枝也做相同的处理，此类剪枝是Ｂｅｔａ剪枝。组成部分，是计算机博弈系统智能化的重要方蒙特卡洛算法能有效处理信息隐藏

8、，通过估算［１２］法。要实现对战就必须加载能让机器走子的策游戏中的随机数据（如对方棋子信息）来寻找最优略，要实现效果比较好的对弈结果，就必须加载智能走法。该算法在幻影围棋中应用的思路：首先，根据化的搜索策略。本文采用ＡｌｐｈａＢｅｔａ剪枝搜索算法当前棋盘信息，将对手余下的相应数量未知棋子随和蒙特卡洛算法相结合的策略，根据两者的优势，依机放在棋盘的空点上；然后，双方都进行随机的模拟据棋盘状态采用不同的搜索算法。落子，直到双方棋子数和眼的总数等于棋盘总坐标