RTS游戏中搜索算法的应用研究

发布时间：2021-02-22 22:20

　　实时战略游戏（RTS）目前已经被证明是在人工智能研究中一个极具挑战性的应用领域。RTS游戏以巨大的动作状态空间,敏捷的反应速度,以及细微巧妙的游戏状况而备受关注。选取动作是RTS游戏中最重要的操作,而选择动作主要依靠于游戏树搜索算法。游戏树应用于博弈论,通常使用游戏树表示游戏中的各种后续可能性。起始节点代表游戏中任一场景,而子节点是在父节点的游戏状态下,执行一步操作产生的后续可能性。在RTS游戏中,游戏树搜索的质量对于最终结果至关重要。随着单位数量的增加,RTS游戏的搜索时间呈指数增长,以至于在严格实时约束下,无法完全搜索游戏树。现有的人工智能解决方案受到动作空间以及实时约束的限制,多数方法虽然能够有效解决战术战略子问题,但仍然没有足够高效的算法应对大型问题集。为此,本文以实时性为原则,以准确性为目标提出新的树模型—T（α,β）及新的搜索算法—τ-AlphaBeta搜索算法,保证在严格时间限制下,返回较优解。论文的主要工作包括:（1）分析极大极小值搜索算法和AlphaBeta搜索算法的搜索原理。在实时战略游戏中,极大极小值搜索算法和AlphaBeta搜索算法在严格时间限制下,无法进行完... 

【文章来源】：中国地质大学(北京)北京市 211工程院校 教育部直属院校

【文章页数】：53 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
1 绪论
    1.1 研究背景
    1.2 研究内容及意义
    1.3 国内外研究现状与分析
    1.4 论文组织结构
    1.5 本章小结
2 游戏树搜索
    2.1 游戏树概述
    2.2 极大极小值搜索算法
    2.3 AlphaBeta搜索算法
        2.3.1 AlphaBeta搜索算法剪枝原理
        2.3.2 AlphaBeta搜索算法优缺点
        2.3.3 AlphaBeta搜索算法复杂度
    2.4 UCT搜索算法
    2.5 本章小结
3 τ-AlphaBeta搜索算法
τ（α, β）树模型">    3.1 T_τ（α, β）树模型
    3.2 τ-AlphaBeta搜索原理
    3.3 τ-AlphaBeta搜索算法剪枝过程
    3.4 评估修正因子τ对搜索时间的影响
    3.5 RTS游戏中τ-AlphaBeta搜索算法
        3.5.1 评估函数
        3.5.2 对战模型
        3.5.3 搜索算法描述
    3.6 本章小结
4 τ-AlphaBeta搜索算法在星际争霸中的应用
    4.1 实验环境
    4.2 实验设置
        4.2.1 战争场景设置
        4.2.2 环境设置
        4.2.3 搜索算法参数设置
        4.2.4 胜率计算方法
    4.3 实验结果分析
        4.3.1 对比τ-AlphaBeta与 AlphaBeta搜索算法
            4.3.1.1 胜率结果对比分析
            4.3.1.2 搜索时间对比分析
        4.3.2 对比τ-AlphaBeta与 UCT搜索算法
    4.4 本章小结
5 结论
致谢
参考文献
附录1 个人简介
附录2 论文发表


【参考文献】：
期刊论文
[1]基于博弈树搜索算法的中国象棋游戏的设计与实现[J]. 刘淑琴,刘淑英.  自动化与仪器仪表. 2017(10)
[2]基于alpha-beta剪枝搜索算法的中国象棋游戏设计[J]. 刘淑英,穆远彪,李红.  信息通信. 2015(08)
[3]基于Alpha-Beta剪枝法的中国象棋博弈系统研究[J]. 黎利辉.  福建电脑. 2014(03)
[4]机器博弈中搜索算法的研究[J]. 廖景亮,陈冬强.  福建电脑. 2012(10)
[5]五子棋中Alpha-Beta搜索算法的研究与改进[J]. 程宇,雷小锋.  计算机工程. 2012(17)
[6]基于Alpha-Beta搜索算法的中国象棋人机对战的设计与实现[J]. 陈业鹏.  计算机光盘软件与应用. 2012(04)

硕士论文
[1]基于贝叶斯均衡和搜索算法的博弈模型研究[D]. 张彦革.东北大学 2010
[2]六子棋计算机博弈关键技术研究[D]. 闵文杰.重庆交通大学 2010



本文编号：3046627