基于统计前向规划算法的游戏通用人工智能

doi:10.11959/j.issn.2096-6652.201935

智能科学与技术学报 ›› 2019, Vol. 1 ›› Issue (3): 219-227.doi: 10.11959/j.issn.2096-6652.201935

基于统计前向规划算法的游戏通用人工智能

LUCAS Simon¹,沈甜雨^2,³,王晓^2,⁴(),张杰^2,⁴

¹ 伦敦玛丽女王大学，英国伦敦 E1 4NS
² 中国科学院自动化研究所复杂系统管理与控制国家重点实验室，北京 100190
³ 中国科学院大学人工智能学院，北京100049
⁴ 青岛智能产业技术研究院，山东青岛 266109

修回日期:2019-08-16 出版日期:2019-09-20 发布日期:2019-12-17
作者简介:LUCAS Simon（1972- ），男，博士，伦敦玛丽女王大学教授，主要研究方向为基于计算智能技术的游戏AI、基于AI的游戏设计、通用人工智能。|沈甜雨（1996- ），女，湖北天门人，中国科学院自动化研究所复杂系统管理与控制国家重点实验室博士生，主要研究方向为机器学习、深度学习和计算机视觉。|王晓（1988- ），女，博士，山东滨州人，中国科学院自动化研究所复杂系统管理与控制国家重点实验室副研究员，主要研究方向为社会交通、动态网群组织、人工智能和社交网络分析。|张杰（1982- ），男，博士，中国科学院自动化研究所复架系统管理与控制国家重点实验室副研究员，主要研究方向为最优控制、博弈论与平行控制。
基金资助:
中国科协青年人才托举工程基金资助项目(2017QNRC001);国家自然科学基金资助项目(61702519);国家自然科学基金资助项目(71402178)

General game AI with statistical forward planning algorithms

LUCAS Simon¹,Tianyu SHEN^2,³,Xiao WANG^2,⁴(),Jie ZHANG^2,⁴

¹ Queen Mary University of London,London E1 4NS,UK
² The State Key Laboratory of Management and Control for Complex Systems,Institute of Automation,Chinese Academy of Sciences,Beijing 100190,China
³ School of Artificial Intelligence,University of Chinese Academy of Sciences,Beijing 100049,China
⁴ Qingdao Academy of Intelligent Industries,Qingdao 266109,China

Revised:2019-08-16 Online:2019-09-20 Published:2019-12-17
Supported by:
The Young Elite Scientists Sponsorship Program of China Association of Science and Technology(2017QNRC001);The National Natural Science Foundation of China(61702519);The National Natural Science Foundation of China(71402178)

摘要/Abstract

摘要：

统计前向规划（statistical forward planning，SFP）算法使用仿真模型（也称为前向模型）自适应地搜索有效的动作序列，此类算法提供了一种简单通用的方法，为各种游戏提供快速自适应的 AI 控制。介绍了两种常用的 SFP 算法：蒙特x卡罗树搜索和滚动层进化，并证明了在没有任何事先训练的情况下，SPF 算法就可以在各种视频游戏中出色地运行。

关键词: 统计前向规划, 游戏智能, 滚动层进化

Abstract:

Statistical forward planning (SFP) algorithms use a simulation model (also called forward model) to adaptively search for effective sequences of actions.They offer a simple and general way to provide rapidly adaptive AI controllers for a variety of games.The two powerful SFP example algorithms:Monte Carlo tree search and rolling horizon evolution were introduced in this paper and key insights into their working principles were provided.It is demonstrated that the algorithms are able to play a variety of video games surprisingly well without the need for any prior training.

Key words: statistical forward planning, game AI, rolling horizon evolution

中图分类号:

TP391

LUCAS Simon, 沈甜雨, 王晓, 等. 基于统计前向规划算法的游戏通用人工智能[J]. 智能科学与技术学报, 2019, 1(3): 219-227.

LUCAS Simon, Tianyu SHEN, Xiao WANG, et al. General game AI with statistical forward planning algorithms[J]. Chinese Journal of Intelligent Science and Technology, 2019, 1(3): 219-227.

图/表 3

参考文献 33

[1]	SILVER D , HUANG A , MADDISON C J ,et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016,529(7587):484.
[2]	GAINA R D , LUCAS S M ， PéREZ-LIéBANA D . Tackling sparse rewards in real-time games with statistical forward planning methods[C]// Proceedings of the AAAI Conference on Artificial Intelligence.January 27-February 1,2019,Hawaii,USA. California:AAAI Press, 2019，33： 1691-1698.
[3]	SHEPPARD B . World-championship-caliber scrabble[J]. Artificial Intelligence, 2002,134(1-2): 241-275.
[4]	GELLY S , WANG Y . Exploration exploitation in go:UCT for Monte-Carlo go[C]// NIPS:Neural Information Processing Systems Conference On-line trading of Exploration and Exploitation Workshop,December 4-7,2006,Vancouver,Canada. Cambridge:MIT Press, 2007.
[5]	PEREZ D , SAMOTHRAKIS S , LUCAS S ,et al. Rolling horizon evolution versus tree search for navigation in single-player real- time games[C]// Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation,July 6-10,2013,Amsterdam,The Netherlands. New York:ACM Press, 2013: 351-358.
[6]	BANZHAF W , KOZA J R , RYAN C ,et al. Genetic programming[J]. IEEE Intelligent Systems, 2000,15(3): 74-84.
[7]	GILL A . Introduction to the theory of finite-state machines[M]. New York:McGraw-Hi1l, 1962.
[8]	ZADEH L A . Fuzzy sets *[J]. Information ＆ Control, 1965,8(3): 338-353.
[9]	TAKAGI T , SUGENO M . Fuzzy identification of systems and its applications to modeling and control[J]. IEEE Transactions on Systems Man ＆ Cybernetics, 2012,SMC-15(1): 116-132.
[10]	QUINLAN J R . Induction of decision trees[J]. Machine Learning, 1986,1(1): 81-106.
[11]	HECHT-NIELSEN .Theory of the backpropagation neural network[C]// International Joint Conference on Neural Networks,May 12-17,2002,Honolulu,USA. Piscataway:IEEE Press, 2002.
[12]	HAGAN M T , DEMUTH H B , BEALE M . Neural network design[M]. Beijing: China Machine PressPress, 2002.
[13]	GOLDBERG D E . Genetic algorithms in search,optimization and machine learning[J]. Addison-Wesley, 1989.
[14]	DIANTY R E , AZHARI A M , HAKIM M F A ,et al. First aid simulation game with finite state machine model[C]// International Conference on Information ＆ Communication Technology ＆ Systems,October 12,2016,Surabaya,Indonesia. Piscataway:IEEE Press, 2016.
[15]	ORLOVSKY S A . Decision-making with a fuzzy preference relation[J]. Fuzzy Sets ＆ Systems, 1978,1(3): 155-167.
[16]	FREELING A N S . Fuzzy sets and decision analysis[J]. IEEE Transactions on Systems Man ＆ Cybernetics, 1984,10(7): 341-354.
[17]	STOICA M , DAN N , ANDREICA A ,et al. Fuzzy sets and their applications[C]// Proceedings of the 9th WSEAS International Conference on Mathematics ＆ Computers in Business and Economics (Mcbe '08),June 24-26,2008,Bucharest,Romania.[S.l.:s.n]. 2008.
[18]	SAFAVIAN S R , LANDGREBE D . A survey of decision tree classifier methodology[J]. IEEE Transactions on Systems Man ＆ Cybernetics, 2002,21(3): 660-674.
[19]	KONISHI M , OKUBO S , NISHINO T ,et al. Decision tree analysis in game informatics[J]. Applied Computing ＆ Information Technology, 2017.
[20]	LIU D , LI H , DING W . Neural-network-based zero-sum game for discrete-time nonlinear systems via iterative adaptive dynamic programming algorithm[J]. Neurocomputing, 2013,110(8): 92-100.
[21]	REVELLO T E , MCCARTNEY R . Generating war game strategies using a genetic algorithm[C]// Congress on Evolutionary Computation,May 12-17,2002,Honolulu,Hawaii,USA. Piscataway:IEEE Press, 2002.
[22]	KUN S , YUANHENG Z , DONGBIN Z . StarCraft micromanagement with reinforcement learning and curriculum transfer learning[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2018: 1-12.
[23]	VINYALS O , EWALDS T , BARTUNOV S ,et al. StarCraft II:a new challenge for reinforcement learning[J]. Science, 2017,359(6374):1733.
[24]	MORAV?íK M , SCHMID M , BURCH N ,et al. DeepStack:expert-level artificial intelligence in heads-up no-limit poker[J]. Science, 2017,356(6337):508.
[25]	BROWN N , SANDHOLM T . Superhuman AI for heads-up no-limit poker:libratus beats top professionals[J]. Science, 2017,359(6374):1733.
[26]	MNIH V , KAVUKCUOGLU K , SILVER D ,et al. Human-level control through deep reinforcement learning[J]. Nature, 2015,518(7540):529.
[27]	DOCKHORN A , APELDOORN D . forward model approximation for general video game learning[C]// 2018 IEEE Conference on Computational Intelligence and Games (CIG),August 14-17,2018,Maastricht,The Netherlands. Piscataway:IEEE Press, 2018: 1-8.
[28]	DOCKHORN A , LUCAS S M , VOLZ V ,et al. Learning local forward models on unforgiving games[J]. arXiv Preprint, 2019.
[29]	BROWNE C B , POWLEY E , WHITEHOUSE D ,et al. A survey of monte carlo tree search methods[J]. IEEE Transactions on Computational Intelligence and AI in games, 2012,4(1): 1-43.
[30]	LUCAS S M , . Game AI Research with fast planet wars variants[C]// 2018 IEEE Conference on Computational Intelligence and Games (CIG),August 14-17,2018,Maastricht,The Netherlands. Piscataway:IEEE Press, 2018: 1-4.
[31]	DRAKE P , UURTAMO S . Move ordering vs heavy playouts:where should heuristics be applied in Monte Carlo Go[C]// Proceedings of the 3rd North American Conference on Games, 2007: 171-175.
[32]	WILLIAMS G M J . Determining game quality through UCT tree shape analysis[D]. London:Imperial College, 2010.
[33]	PEREZ-LIEBANA D , GAINA R D , DRAGESET O ,et al. Analysis of statistical forward planning methods in Pommerman[J]. Proceedings of the 15th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,October 8-12,2019,Atlanta,Georgia.Palo Alto,California:The AAAI Press, 2019.

基于统计前向规划算法的游戏通用人工智能

General game AI with statistical forward planning algorithms

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 33

相关文章 1

Metrics

推荐阅读 0