基于PAGA的RTS游戏多单元控制方法研究

计算机科学 ›› 2018, Vol. 45 ›› Issue (11A): 101-104.

基于PAGA的RTS游戏多单元控制方法研究

杨震, 张万鹏, 刘鸿福, 魏占阳

国防科技大学智能科学学院长沙410000

出版日期:2019-02-26 发布日期:2019-02-26
通讯作者: 杨震(1994-),男,硕士生,主要研究方向为任务规划、博弈推理,E-mail:yangzhen7319@163.com
作者简介:张万鹏(1981-),男,博士,副研究员,主要研究方向为智能规划、博弈推理;刘鸿福(1983-),男,博士,副研究员,主要研究方向为人工智能、任务规划;魏占阳(1994-),男,硕士生,主要研究方向为任务规划、集群对抗。
基金资助:
本文受2017年国家自然科学基金项目(61403411),高动态环境下低可探测性飞行器自主任务规划方法研究项目资助。

Research on Multi-units Control Method in RTS Games Based on PAGA

YANG Zhen, ZHANG Wan-peng, LIU Hong-fu, WEI Zhan-yang

College of Intelligence Science and Engineering,National University of Defense Technology,Changsha 410000,China

Online:2019-02-26 Published:2019-02-26

摘要/Abstract

摘要： 实时战略游戏(RTS)中的单元控制在人工智能(AI)领域是一个具有挑战性的问题。这类游戏是实时约束的,并且具有庞大的状态和行动空间,智能算法已不能很好地解决这类问题。在脚本空间搜索策略对战斗场景中的多单元进行控制,可以有效地克服巨大的分支因子带来的不利影响。文中运用自适应遗传算法(Adaptive Genetic Algorithm)在脚本空间进行搜索,为战斗场景中的多单元提供良好的行动序列,实现了对单元的有效控制。实验结果表明,提出的PAGA(Portfolio Adaptive Genetic Algorithm)是可行且有效的,在大规模单元控制中的性能优于现行算法。

关键词: AI, RTS游戏, 多单元控制, 自适应遗传算法

Abstract: Unit control in real-time strategy games (RTS) is a challenging issue in the field of artificial intelligence (AI).Such games are constrained in real time,and have a large state and action space,which make intelligent algorithms do not solve this type of problem.By controlling the multi-units in the battle scene by searching strategy in the script space,it is possible to effectively overcome the adverse effects caused by the huge branching factor.This paper used adaptive genetic algorithm to search in scripting space to provid a good sequence of actions for multi-units in the battle scene and control the unit.Experiments show that the proposed PAGA (Portable Adaptive Genetic Algorithm) is feasible and effective,and its performance is superior to the current algorithms in large-scale unit control.

Key words: Adaptive genetic algorithm, AI, Multi-units control, RTS game

中图分类号:

TP273+.2

杨震, 张万鹏, 刘鸿福, 魏占阳. 基于PAGA的RTS游戏多单元控制方法研究[J]. 计算机科学, 2018, 45(11A): 101-104. https://doi.org/

YANG Zhen, ZHANG Wan-peng, LIU Hong-fu, WEI Zhan-yang. Research on Multi-units Control Method in RTS Games Based on PAGA[J]. Computer Science, 2018, 45(11A): 101-104. https://doi.org/

参考文献

[1]MISHRA K,SUGANDH N,RAM A.Case-Based Planning and Execution for Real-Time Strategy Games[C]∥International Conference on Case-Based Reasoning:Case-Based Reasoning Research and Development.Springer-Verlag,2007:164-178.
[2]SYNNAEVE G,BESSIERE P.A Bayesian Model for Opening Prediction in RTS Games with Application to StarCraft[J].Proceedings of IEEE Cig Seoul South Korea,2011,32(14):281-288.
[3]FOERSTER J,NARDELLI N,FARQUHAR G,et al.Stabili-sing Experience Replay for Deep Multi-Agent Reinforcement Learning[J].arXiv:1702.08887,2017.
[4]BARRIGA N A,STANESCU M,BURO M.Puppet Search:Enhancing Scripted Behavior by Look-Ahead Search with Applications to Real-Time Strategy Games[C]∥AIIDE.2015.
[5]CHURCHILL D,BURO M.Portfolio greedy search and simulation for large-scale combat in starcraft[C]∥Computational Intelligence in Games.IEEE,2013:1-8.
[6]JUSTESEN N,TILLMAN B,TOGELIUS J,et al.Script- and cluster-based UCT for StarCraft[C]∥Computational Intelligence and Games.IEEE,2014:1-8.
[7]WANG C,CHEN P,LI Y,et al.Portfolio online evolution in Star Craft[C]∥AAAI Conference on Artificial Intelligence and InteractiveDigital Entertainment.2016:114-120.
[8]USUNIER N,SYNNAEVE G,LIN Z,et al.Episodic Exploration for Deep Deterministic Policies:An Application to StarCraft Micromanagement Tasks[J].arXiv:1609.02993,2016.
[9]CHURCHILL D,BURO M.Portfolio greedy search and simulation for large-scale combat in starcraft[C]∥Computational Intelligence in Games.IEEE,2013:1-8.
[10]JUSTESEN N,RISI S.Continual online evolutionary planning for in-game build order adaptation in StarCraft[C]∥the Genetic and Evolutionary Computation Conference.2017:187-194.
[11]Holland J H.Adaptation in natural and artificial systems[M].MIT Press,1992.
[12]沐阿华,周绍磊,于晓丽.一种快速自适应遗传算法及其仿真研究[J].系统仿真学报,2004,16(1):122-125.
[13]姜昌华.遗传算法在物流系统优化中的应用研究[D].中山:华东师范大学,2007.
[14]SRINIVAS M,PATNAIKL M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems Man & Cybernetics,2002,24(4):656-667.
[15]KOVARSKY A,BURO M.Heuristic Search Applied to Ab-stract Combat Games[M]∥Advances in Artificial Intelligence.Berlin:Springer,2005:66-78.

相关文章 15

[1]	王子凯, 朱健, 张伯钧, 胡凯. 区块链与智能合约并行方法研究与实现 Research and Implementation of Parallel Method in Blockchain and Smart Contract 计算机科学, 2022, 49(9): 312-317. https://doi.org/10.11896/jsjkx.210800102
[2]	张翕然, 刘万平, 龙华. 物联网僵尸网络病毒的传播动力学模型与分析 Dynamic Model and Analysis of Spreading of Botnet Viruses over Internet of Things 计算机科学, 2022, 49(6A): 738-743. https://doi.org/10.11896/jsjkx.210300212
[3]	郁舒昊, 周辉, 叶春杨, 王太正. SDFA:基于多特征融合的船舶轨迹聚类方法研究 SDFA:Study on Ship Trajectory Clustering Method Based on Multi-feature Fusion 计算机科学, 2022, 49(6A): 256-260. https://doi.org/10.11896/jsjkx.211100253
[4]	丛颖男, 王兆毓, 朱金清. 关于法律人工智能数据和算法问题的若干思考 Insights into Dataset and Algorithm Related Problems in Artificial Intelligence for Law 计算机科学, 2022, 49(4): 74-79. https://doi.org/10.11896/jsjkx.210900191
[5]	刘华玲, 皮常鹏, 刘梦瑶, 汤新. 一种新的优化机制:Rain New Optimization Mechanism:Rain 计算机科学, 2021, 48(11A): 63-70. https://doi.org/10.11896/jsjkx.201100032
[6]	董海, 徐晓鹏, 谢谢. 多目标优化算法求解多柔性作业车间调度问题 Solving Multi-flexible Job-shop Scheduling by Multi-objective Algorithm 计算机科学, 2020, 47(12): 239-244. https://doi.org/10.11896/jsjkx.191100042
[7]	宋鑫,朱宗良,高银萍,苌道方. 动态阈值结合全局优化的船舶AIS轨迹在线压缩算法 Vessel AIS Trajectory Online Compression Algorithm Combining Dynamic Thresholding and Global Optimization 计算机科学, 2019, 46(7): 333-338. https://doi.org/10.11896/j.issn.1002-137X.2019.07.051
[8]	李轶, 蔡天训, 吴文渊. 基于k阶秩函数的线性赋值循环程序的终止性分析 Termination Analysis of Linear Assignment Loop Program Based on k-ranking Functions 计算机科学, 2018, 45(6): 151-155. https://doi.org/10.11896/j.issn.1002-137X.2018.06.026
[9]	潘吉飞, 黄德才. 区块链技术对人工智能的影响 Impact of Blockchain Technology on AI 计算机科学, 2018, 45(11A): 53-57.
[10]	宋站威,周睿康,赖英旭,范科峰,姚相振,李琳,李巍. 基于行为模型的工控异常检测方法研究 Anomaly Detection Method of ICS Based on Behavior Model 计算机科学, 2018, 45(1): 233-239. https://doi.org/10.11896/j.issn.1002-137X.2018.01.041
[11]	赵鹤,洪玫,杨秋辉,高婉玲. 基于观察者模式的实时系统验证方法 Real-time System Verification Approach Based on Observer Patterns 计算机科学, 2017, 44(12): 156-162. https://doi.org/10.11896/j.issn.1002-137X.2017.12.030
[12]	朱凯龙,陆余良,杨斌. 分布式环境下的路由器级互联网抗毁性研究 Study on Invulnerability of Router-level Internet Based on MapReduce 计算机科学, 2017, 44(11): 168-174. https://doi.org/10.11896/j.issn.1002-137X.2017.11.025
[13]	王惠清,周雷. 基于Paillier加密的数据多副本持有性验证方案 Multiple-replica Provable Data Possession Based on Paillier Encryption 计算机科学, 2016, 43(Z6): 370-373. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.088
[14]	罗频捷,温荷,万里. 基于遗传算法的模糊神经网络公交到站时间预测模型研究 Research on Bus Arrival Time Prediction Model Based on Fuzzy Neural Network with Genetic Algorithm 计算机科学, 2016, 43(Z6): 87-89. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.020
[15]	许华杰,檀洪森,胡小明. 基于自适应遗传算法和多条带策略的排样方法研究 Research of Packing Method Based on Adaptive Genetic Algorithm and Multi-strip Strategy 计算机科学, 2016, 43(4): 274-278. https://doi.org/10.11896/j.issn.1002-137X.2016.04.056

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed