单回合的回合制战棋博弈模型搜索算法研究

发布时间：2018-05-19 03:23

本文选题：战棋 + 机器博弈　；参考：《重庆大学》2016年博士论文

【摘要】：战棋博弈(Turn-Based War Chess,TBW)是回合制策略游戏(Turn-Based Strategy,TBS)的重要成分,但目前其人工智能关注度还不够。受限于战棋具有丰富多样的元素,目前还没有一个标准化的数学模型,从而导致了战棋博弈目前的研究还停留在较为简单的层次上。随着移动端游戏的井喷式发展,战棋博弈类游戏因其触屏操作、轻量级、碎片化时间而拥有更大的发展潜力,然而因其人机博弈部分智能低下,严重影响了用户体验和产品黏性,成为束缚其游戏性的瓶颈。战棋博弈本质上是由横向的组合优化问题和纵向的博弈树搜索问题结合的产物,既可以看作是一个分阶段的多智能体协同作业的规划问题,也可以看作是一个分支系数巨大的树搜索问题。所以,其背后潜藏着的对以上传统问题体系的扩充和发展,其研究意义都超出了对战棋游戏本身的研究。如今,基于大数据、云计算和机器学习的新一轮弱人工智能研究正在蓬勃兴起,使得运用更为有效的技术让战棋博弈的人工智能获得较大程度的提升成为了可能。本论文较为系统的分析了战棋博弈的特性,基于特征选择了从棋类博弈的角度来研究战棋的机器博弈。首先建立战棋游戏的通用博弈模型,提出横向的组合优化和纵向的博弈树搜索的理论框架,阐明横向分支系数巨大的关键难题,其次,针对横向问题提出单回合穷举搜索的按序枚举法和递归枚举法,并深入分析它们的性能和各自的适用性。随后就计算冗余问题提出两套优化策略——单位移动范围的简化和搜索空间的简化,通过理论实验证实了它们在不改变有效搜索空间的前提下能大幅的提高搜索效率。然后就搜索过程中比较耗时的单位移动范围计算,引入动态最短路径树(Dynamic Shortest Path Tree,DSPT)的新的研究方法,提出关于动态删除节点的MRDA_SPT(Multi-node Removed Dynamic Algorithm of Shortest Path Tree)改进算法,并通过理论分析和实验验证,该算法的效率均优于现有其他方法。最后,基于新算法又提出动态更新单位移动范围的DR_SPT(Dynamic Range Shortest Path Tree)算法,通过实验表明它能显著的提高计算移动范围的效率,从而整体上提升了战棋博弈单回合搜索速度。本论文的研究成果包括如下:(1)对战棋博弈进行建模和研究,并提出纵向和横向的研究框架。研究结果表明,本质上,战棋博弈属于二人(或多人)零和完全信息博弈,因其每回合全部棋子都可移动,并且移动顺序敏感的特点,战棋博弈构成了一个分支系数异常庞大的博弈树。本论文对该博弈树的规模进行了理论上的计算,并与其它主流棋类对比,发现战棋的博弈树分支系数会随着棋子的数量和每个棋子的移动范围的增大而急剧增大。最后,在博弈树理论的框架下就纵向和横向的研究路线给予了展望。(2)提出战棋博弈的单回合搜索算法并做完备性证明和性能比较。单回合搜索是战棋博弈树第一层展开的核心算法,其效率也是整个战棋博弈性能的关键指标。针对顺序优先还是行为优先提出了两种单回合搜索算法:1、按序枚举法;2、递归枚举法。它们的主要区别是选择不同的排列算法:前者采用字典序法,后者采用递归法,而它们体现出来了不同的搜索架构:前者基于序列,后者基于行动。从理论上证明了两个算法都是最优解的,并从理论和实验分析了他们效率的差别:棋子在所有位置上的扩展操作(ops1)的次数总和,递归枚举法比按序枚举法在各种条件下都有不同程度的减少。(3)就单回合搜索计算复杂度高、计算冗余的问题提出了两套优化策略——1、简化单位移动范围的计算;2、划分与简化搜索空间。通过理论证明和实验检验,证实了这两种策略可以在不改变有效搜索空间的前提下大幅的提高搜索效率。(4)提出MRDA_SPT改进算法,提升了动态最短路径树(DSPT)关于节点动态删除的效率。首先对动态最短路径树(DSPT)进行了较为系统的研究,并针对前人的工作当中DSPT动态节点删除算法存在冗余的问题提出了新算法——MRDA_SPT改进算法,从理论上分析其复杂度,通过与目前较快的算法做对比实验,表明了MRDA_SPT改进算法具有更高的效率和更快的运行速度。(5)提出高效率动态计算单位移动范围的DR_SPT算法并通过实验验证其高效性。实验分析出战棋博弈搜索的一个重要的耗时计算是对棋子移动范围的计算,根据移动范围在搜索算法中会动态改变这一特点,提出基于动态最短路径树和MRDA_SPT改进算法的DR_SPT算法,该算法对棋子移动范围做增量计算,从而大大提高了搜索中棋子移动范围计算的速度,并从整体上提高战棋博弈搜索的效率。
[Abstract]:This paper analyzes the characteristics of chess game , and then puts forward a new research method for the game of chess game based on the combination of horizontal combination optimization and vertical game tree search . Based on the new algorithm , a DR _ SPT ( Dynamic Range Finding Path Tree ) algorithm based on dynamic update unit moving range is proposed . The results of this paper are as follows : ( 1 ) The game of chess game is modeled and studied . The results of this paper are as follows : ( 1 ) The game of chess game belongs to two ( or many ) zero and complete information games . ( 4 ) The improved algorithm of MRDA _ SPT is proposed to improve the efficiency of dynamic deletion of nodes in dynamic shortest path tree ( DSPT ) .
【学位授予单位】：重庆大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP18

【参考文献】