Top

Published in:

2017 | OriginalPaper | Chapter

Analysis of Vanilla Rolling Horizon Evolution Parameters in General Video Game Playing

Authors : Raluca D. Gaina, Jialin Liu, Simon M. Lucas, Diego Pérez-Liébana

Published in: Applications of Evolutionary Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Monte Carlo Tree Search techniques have generally dominated General Video Game Playing, but recent research has started looking at Evolutionary Algorithms and their potential at matching Tree Search level of play or even outperforming these methods. Online or Rolling Horizon Evolution is one of the options available to evolve sequences of actions for planning in General Video Game Playing, but no research has been done up to date that explores the capabilities of the vanilla version of this algorithm in multiple games. This study aims to critically analyse the different configurations regarding population size and individual length in a set of 20 games from the General Video Game AI corpus. Distinctions are made between deterministic and stochastic games, and the implications of using superior time budgets are studied. Results show that there is scope for the use of these techniques, which in some configurations outperform Monte Carlo Tree Search, and also suggest that further research in these methods could boost their performance.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Relief Camp Manager: A Serious Game Using the World Health Organization’s Relief Camp Guidelines

next chapter Darwin’s Demons: Does Evolution Improve the Game?

www.gvgai.net.

Using these forward model calls instead of real execution time is more robust to fluctuations on the machine used to run the experiments, making it time independent and results comparable across different architectures.

Al-Khateeb, B., Kendall, G.: The importance of a piece difference feature to blondie 24. In: UK Workshop on Computational Intelligence (UKCI), pp. 1–6 (2010)

Babadi, A., Omoomi, B., Kendall, G.: EnHiC: An enforced hill climbing based system for general game playing. In: IEEE Conference on Computational Intelligence and Games (CIG), vol. 1, pp. 193–199 (2015)

Bellemare, M.G., Naddaf, Y., Veness, J., Bowling, M.: The arcade learning environment: an evaluation platform for general agents. J. Artif. Intell. Res. 47, 253–279 (2013)

Bontrager, P., Khalifa, A., Mendes, A., Togelius, J.: Matching games and algorithms for General Video Game Playing. In: Twelfth Artificial Intelligence and Interactive Digital Entertainment Conference, pp. 122–128 (2016)

Browne, C.B., Powley, E., Whitehouse, D., Lucas, S.M., Cowling, P.I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., Colton, S.: A survey of Monte Carlo Tree Search methods. IEEE Trans. Comput. Intell. AI Games 4, 1–43 (2014)CrossRef

Chu, C.Y., Hashizume, H., Guo, Z., Harada, T., Thawonmas, R.: Combining pathfmding algorithm with knowledge-based monte-carlo tree search in General Video Game Playing. In: IEEE Conference on Computational Intelligence and Games (CIG), vol. 1, pp. 523–529 (2015)

Gaina, R.D., Perez-Liebana, D., Lucas, S.M.: General video game for 2 players: framework and competition. In: Proceedings of the IEEE Computer Science and Electronic Engineering Conference (CEEC) (2016)

Genesereth, M., Love, N., Pell, B.: General game playing: overview of the AAAI competition. AI Mag. 26, 62 (2005)

Horn, H., Volz, V., Perez-Liebana, D., Preuss, M.: MCTS/EA hybrid GVGAI players and game difficulty estimation. In: Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG) (2016)

10.

Justesen, N., Mahlmann, T., Togelius, J.: Online evolution for multi-action adversarial games. In: Squillero, G., Burelli, P. (eds.) EvoApplications 2016. LNCS, vol. 9597, pp. 590–603. Springer, Cham (2016). doi:10.1007/978-3-319-31204-0_38CrossRef

11.

Khalifa, A., Perez-Liebana, D., Lucas, S., and J.T.: General video game level generation. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) (2016)

12.

Levine, J., Lucas, S.M., Mateas, M., Preuss, M., Spronck, P., Togelius, J.: General Video Game Playing. In: Artificial and Computational Intelligence in Games, Dagstuhl Follow-Ups, vol. 6, pp. 1–7 (2013)

13.

Liu, J., Liebana, D.P., Lucas, S.M.: Bandit-Based Random Mutation Hill-Climbing. CoRR abs/1606.06041 (2016). http://arxiv.org/abs/1606.06041

14.

Lucas, S.M., Samothrakis, S., Perez, D.: Fast evolutionary adaptation for Monte Carlo Tree Search. In: EvoGames (2014)

15.

Mitchell, M.: An Introduction to Genetic Algorithms. MIT Press, Cambridge (1998)MATH

16.

Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., Hassabis, D.: Human-level control through deep reinforcement learning. Nature 518(7540), 529–533 (2015)CrossRef

17.

Nelson, M.J.: Investigating vanilla MCTS scaling on the GVG-AI game corpus. In: Proceedings of the 2016 IEEE Conference on Computational Intelligence and Games (2016)

18.

Park, H., Kim, K.J.: MCTS with influence map for General Video Game Playing. In: IEEE Conference on Computational Intelligence and Games (CIG), vol. 1, pp. 534–535 (2015)

19.

Perez, D., Samothrakis, S., Lucas, S.M.: Knowledge-based fast evolutionary MCTS for General Video Game Playing. In: IEEE Conference on Computational Intelligence and Games, pp. 1–8 (2014)

20.

Perez-Liebana, D., Dieskau, J., Hnermund, M., Mostaghim, S., Lucas, S.M.: Open loop search for General Video Game Playing. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 337–344 (2015)

21.

Perez-Liebana, D., Samothrakis, S., Lucas, S.M., Rolfshagen, P.: Rolling Horizon Evolution versus tree search for navigation in single-player real-time games. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 351–358 (2013)

22.

Perez-Liebana, D., Samothrakis, S., Togelius, J., Lucas, S.M., Schaul, T.: General video game AI: competition, challenges and opportunities. In: Thirtieth AAAI Conference on Artificial Intelligence (2016)

23.

Perez-Liebana, D., Samothrakis, S., Togelius, J., Schaul, T., Lucas, S., Couetoux, A., Lee, J., Lim, C.U., Thompson, T.: The 2014 General Video Game Playing competition. IEEE Trans. Comput. Intell. AI Games PP, 1 (2015)

24.

Samothrakis, S., Roberts, S.A., Perez, D., Lucas, S.: Rolling Horizon methods for games with continuous states and actions. In: Proceedings of the Conference on Computational Intelligence and Games (CIG), August 2014

25.

Sharma, S., Kobti, Z., Goodwin, S.D.: General game playing: an overview and open problems. In: IEEE International Conference on Computing, Engineering and Information, pp. 257–260 (2009)

26.

Tesauro, G.J.: Temporal difference learning and TD-gammon. In: IEEE Conference on Computational Intelligence and Games, pp. 58–68 (1995)

27.

Wang, C., Chen, P., Li, Y., Holmgård, C., Togelius, J.: Portfolio online evolution in starcraft. In: Twelfth Artificial Intelligence and Interactive Digital Entertainment Conference (2016)

Title: Analysis of Vanilla Rolling Horizon Evolution Parameters in General Video Game Playing
Authors: Raluca D. Gaina
Jialin Liu
Simon M. Lucas
Diego Pérez-Liébana
Publisher: Springer International Publishing
Book: Applications of Evolutionary Computation
Print ISBN: 978-3-319-55848-6

Electronic ISBN: 978-3-319-55849-3

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-55849-3_28

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner