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

doi:10.11959/j.issn.2096-6652.201935

Abstract

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

CLC Number:

TP391

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.

Figures/Tables 3

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

General game AI with statistical forward planning algorithms

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 33

Related Articles 1

Metrics

Recommended 0