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

LUCAS Simon; 沈甜雨; 王晓; 张杰

doi:10.11959/j.issn.2096-6652.201935

您当前的位置：

首页 >

文章列表页 >

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

综述 | 更新时间：2024-06-05

- 基于统计前向规划算法的游戏通用人工智能
- General game AI with statistical forward planning algorithms
- 智能科学与技术学报 2019年1卷第3期页码：219-227
- 作者机构：
  
  1. 伦敦玛丽女王大学，英国伦敦 E1 4NS
  2. 中国科学院自动化研究所复杂系统管理与控制国家重点实验室，北京 100190
  3. 中国科学院大学人工智能学院，北京100049
  4. 青岛智能产业技术研究院，山东青岛 266109
- 作者简介：
  
  [ "LUCAS Simon（1972- ），男，博士，伦敦玛丽女王大学教授，主要研究方向为基于计算智能技术的游戏AI、基于AI的游戏设计、通用人工智能。" ]
  [ "沈甜雨（1996- ），女，湖北天门人，中国科学院自动化研究所复杂系统管理与控制国家重点实验室博士生，主要研究方向为机器学习、深度学习和计算机视觉。" ]
  [ "王晓（1988- ），女，博士，山东滨州人，中国科学院自动化研究所复杂系统管理与控制国家重点实验室副研究员，主要研究方向为社会交通、动态网群组织、人工智能和社交网络分析。" ]
  [ "张杰（1982- ），男，博士，中国科学院自动化研究所复架系统管理与控制国家重点实验室副研究员，主要研究方向为最优控制、博弈论与平行控制。" ]
- 基金信息：
  
  中国科协青年人才托举工程基金资助项目;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)
- DOI：10.11959/j.issn.2096-6652.201935
  中图分类号： TP391
- 网络出版日期：2019-09，
  
  纸质出版日期：2019-09-20
- 稿件说明：
移动端阅览
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.
LUCAS Simon, 沈甜雨, 王晓, 等. 基于统计前向规划算法的游戏通用人工智能[J]. 智能科学与技术学报, 2019,1(3):219-227. DOI： 10.11959/j.issn.2096-6652.201935.

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. DOI： 10.11959/j.issn.2096-6652.201935.

摘要

统计前向规划（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.

关键词

Keywords

references

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.

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 .

SHEPPARD B . World-championship-caliber scrabble [J ] . Artificial Intelligence , 2002 , 134 ( 1-2 ): 241 - 275 .

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 .

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 .

BANZHAF W , KOZA J R , RYAN C , et al . Genetic programming [J ] . IEEE Intelligent Systems , 2000 , 15 ( 3 ): 74 - 84 .

GILL A . Introduction to the theory of finite-state machines [M ] . New York:McGraw-Hi1l , 1962 .

ZADEH L A . Fuzzy sets * [J ] . Information ＆ Control , 1965 , 8 ( 3 ): 338 - 353 .

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 .

QUINLAN J R . Induction of decision trees [J ] . Machine Learning , 1986 , 1 ( 1 ): 81 - 106 .

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 .

HAGAN M T , DEMUTH H B , BEALE M . Neural network design [M ] . Beijing : China Machine PressPress , 2002 .

GOLDBERG D E . Genetic algorithms in search,optimization and machine learning [J ] . Addison-Wesley , 1989 .

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 .

ORLOVSKY S A . Decision-making with a fuzzy preference relation [J ] . Fuzzy Sets ＆ Systems , 1978 , 1 ( 3 ): 155 - 167 .

FREELING A N S . Fuzzy sets and decision analysis [J ] . IEEE Transactions on Systems Man ＆ Cybernetics , 1984 , 10 ( 7 ): 341 - 354 .

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 .

SAFAVIAN S R , LANDGREBE D . A survey of decision tree classifier methodology [J ] . IEEE Transactions on Systems Man ＆ Cybernetics , 2002 , 21 ( 3 ): 660 - 674 .

KONISHI M , OKUBO S , NISHINO T , et al . Decision tree analysis in game informatics [J ] . Applied Computing ＆ Information Technology , 2017 .

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 .

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 .

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 .

VINYALS O , EWALDS T , BARTUNOV S , et al . StarCraft II:a new challenge for reinforcement learning [J ] . Science , 2017 , 359 ( 6374 ):1733.

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.

BROWN N , SANDHOLM T . Superhuman AI for heads-up no-limit poker:libratus beats top professionals [J ] . Science , 2017 , 359 ( 6374 ):1733.

MNIH V , KAVUKCUOGLU K , SILVER D , et al . Human-level control through deep reinforcement learning [J ] . Nature , 2015 , 518 ( 7540 ):529.

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 .

DOCKHORN A , LUCAS S M , VOLZ V , et al . Learning local forward models on unforgiving games [J ] . arXiv Preprint , 2019 .

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 .

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 .

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 .

WILLIAMS G M J . Determining game quality through UCT tree shape analysis [D ] . London:Imperial College , 2010 .

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 .

浏览量

1678

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据