A dynamic balanced level generator for video games based on deep convolutional generative adversarial networks

Document Type : Article

Authors

Computer Games Research Laboratory, School of Computer Engineering, Iran University of Science and Technology, Tehran, Iran

Abstract

In the gaming industry, creating well-balanced games is one of the major challenges developers are currently facing. Balance in games has different meanings depending on the game type. But, most of the existing definitions are esteemed from the flow theory. Flow theory in video games is stating that the level of challenge existing in the game must be neither too easy nor too difficult for the player. Games that are not balanced will have a high churn rate and will suffer in terms of monetization. Hence, nowadays a trending research area is focused on establishing mechanisms to create automatic balance in an algorithmic way. In this research, we have used generative adversarial networks (GANs) to automatically create balanced levels. In the proposed work, a level of a 2D platformer game is fed to the network. Finally, the network automatically generates new balanced levels and the levels are checked to see if they have the game’s minimum necessary requirements and also to check if they can be solved by the reinforcement learning agent. In the series of performed evaluations, it is shown that after the training process, the proposed approach is capable of generating levels that are well-balanced with considerable accuracy.

Keywords

References

References:
[1]    Jaffe, A., Miller, A., Andersen, E., et al. "Evaluating competitive game balance with restricted play", 8th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, Stanford, California, U. S., pp. 26-31 (2012).   
[2]    Lopez, S.J., Snyder, C.R. "Oxford handbook of positive psychology", Oxford Library of Psychology, Oxford University Press, UK (2009).
[3]    E. Adams. "Fundamentals of game design", Pearson Education, New York, U.S. (2014). 
[4]    Kavanagh, W.J., Miller, A., Norman, G, et al. "Balancing turn-based games with chained strategy generation", IEEE Transactions on Games (2019).
[5]    Pérez, L.J.F., Calla, L.A.R., Valente, L., et al. "Dynamic game difficulty balancing in real time using evolutionary fuzzy cognitive maps", 14th Brazilian Symposium Conference on Computer Games and Digital Entertainment (SBGames), Rio de Janeiro, Brazil, pp. 24-32 (2015). 
[6]    Silva, M.P., do Nascimento Silva, V. and Chaimowicz, L. "Dynamic difficulty adjustment through an adaptive AI" 14th Brazilian Symposium Conference on Computer Games and Digital Entertainment (SBGames), Rio de Janeiro, Brazil, pp. 173-182 (2015).
[7]    Yu, X., He, S., Gao, Y., et al. "Dynamic difficulty adjustment of game AI for video game Dead-End", 3rd International Conference on Information Sciences and Interaction Sciences, Chengdu, China, pp. 583-587 (2010). 
[8]    Bosc, G., Tan, P., Boulicaut, J.F., et al. "A pattern mining approach to study strategy balance in RTS games" IEEE Transactions on Computational Intelligence and AI in Games, 9(2), pp. 123-132 (2017).
[9]    Makin, O., Bangay, S. "Orthogonal analysis of StarCraft II for game balance", Australasian Computer Science Week Multiconference, Geelong, Australia, Article No. 30 (2017).
[10]    Schell, J. "The Art of Game Design: A book of lenses", 2nd Edn, AK Peters/CRC Press, Florida, U.S. (2014).
[11]    Karavolos, D., Liapis, A. and Yannakakis, G. "Learning the patterns of balance in a multi-player shooter game", 12th International Conference on the Foundations of Digital Games, New York, U. S., Article No. 70 (2017).
[12]    Olesen, J. K., Yannakakis, G. N. and Hallam, J. "Real-time challenge balance in an RTS game using rtNEAT", 2008 IEEE Symposium On Computational Intelligence and Games, Perth, Australia, pp. 87-94 (2008).
[13]    Morosan, M. and Poli, R. "Evolving a designer-balanced neural network for Ms PacMan", 9th Computer Science and Electronic Engineering (CEEC), Colchester, England, pp. 100-105 (2017).
[14]    Bangay, S. and Makin, O. "Generating an attribute space for analyzing balance in single unit RTS game combat", 2014 IEEE Conference on Computational Intelligence and Games, Dortmund, Germany, pp. 1-8 (2014).
[15]    Uriarte, A. and Ontanón, S. "Psmage: Balanced map generation for starcraft", 2013 IEEE Conference on Computational Inteligence in Games (CIG), Niagara Falls, Canada, pp. 1-8 (2013).
[16]    Goodfellow, I., Pouget-Abadie, J., Mirza, M., et al. "Generative adversarial nets", Neural Information Processing Systems, Montreal, Canada, pp. 2672-2680 (2014).
[17]    Liu, G.C., Wang, J., Youn, G. and Kim, J. "Multi-scale multi-class conditional generative adversarial network for handwritten character generation" The Journal of Supercomputing, 73(12), pp. 1-19 (2017).
[18]    Tran, L., Yin, X. and Liu, X.  "Disentangled representation learning gan for pose-invariant face recognition", Computer Vision and Pattern Recognition, 3(6), pp. 1415-1424 (2017).
[19]    Song, F. Y. Z. S. and Xiao, A. S. J. "Construction of a large-scale image dataset using deep learning with humans in the loop", arXiv preprint arXiv:1506.03365 (2015).
[20]    Mathieu, M., Couprie, C. and LeCun, Y. "Deep multi-scale video prediction beyond mean square error", arXiv preprint arXiv:1511.05440 (2016).
[21]    Baddar, W.J., Gu, G., Lee, S., et al. "Dynamics transfer GAN: generating video by transferring arbitrary temporal dynamics from a source video to a single target image", arXiv preprint arXiv:1712.03534 (2017).
[22]    Yang, L.C., Chou, S.Y. and Yang, Y.H. "MidiNet: A convolutional generative adversarial network for symbolic-domain music generation", 18th International Society for Music Information Retrieval Conference (ISMIR’2017), Suzhou, China, pp. 1-8 (2017).
[23]    Sutton, R.S.  and Barto, A.G. "Reinforcement Learning: An Introduction", MIT Press, Cambridge, England (2018).
[24]    Zhang, C., Vinyals, O., Munos, R., et al. "A study on overfitting in deep reinforcement learning", arXiv preprint arXiv: 1804.06893 (2018).
[25]    Summerville, A.J., Snodgrass, S., Mateas, M., et al. "The vglc: The video game level corpus", arXiv preprint arXiv:1606.07487 (2016).
[26]    Volz, V., Schrum, J., Liu, J., et al. "Evolving Mario Levels in the Latent Space of a Deep Convolutional Generative Adversarial Network", arXiv preprint arXiv:1805.00728 (2018).
[27]    Bontrager, P., Roy, A., Togelius, J., et al. "DeepMasterPrint: Fingerprint Spoofing via Latent Variable Evolution", arXiv preprint arXiv:1705.07386 (2017).
[28]    Hansen, N., Müller, S.D. and Koumoutsakos, P. "Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)", Evolutionary Computation, 11(1), pp. 1-18 (2003).
[29]    Shaker, N., and Togelius, J., and Nelson, M.J. "Procedural content generation in games", Springer International Publishing, Switzerland (2016).
[30]    Togelius, J., Yannakakis, G. N., Stanley, K.O., et al. "Search-based procedural content generation: A taxonomy and survey", IEEE Transactions on Computational Intelligence and AI in Games, 3(3), pp. 172-186 (2011).
[31]    McCormack. J. "Interactive evolution of L-system grammars for computer graphics modelling", Complex Systems: From Biology to Computation, ISO Press (1993).
[32]    Mizuno, K., Nishihara, S. "Constructive generation of very hard 3-colorability instances", Discrete Applied Mathematics, 156(2), pp. 218-229 (2008).
[33]    Belhadj, F. "Terrain modeling: a constrained fractal model", 5th International Conference on Computer graphics, Virtual reality, Visualisation and Interaction, Grahamstown, South Africa, pp. 197-204 (2007).
[34]    Papageorgiou, E. I. and Salmeron, J. L. "A review of fuzzy cognitive maps research during the last decade", IEEE Transactions on Fuzzy Systems, 21(1), pp. 66-79 (2013).
[35]    Kyriakarakos, G., Dounis, A.I., Arvanitis, K.G., et al. "Design of a fuzzy cognitive maps variable-load energy management system for autonomous PV-reverse osmosis desalination systems: A simulation survey", Applied Energy, 187, pp. 575-584 (2017).
[36]    Back, T. "Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms", Oxford University Press (1996).
[37]    Crepinšek, M., Liu, S. H. and Mernik, M. "Exploration and exploitation in evolutionary algorithms: A survey", ACM Computing Surveys, 45(3), pp. 1-33 (2013).
[38]    Morosan, M., and Poli, R. "Automated game balancing in Ms. PacMan and StarCraft using Evolutionary Algorithms", European Conference the Applications of Evolutionary Computation, Amsterdam, The Netherlands, pp. 377-392 (2017).
[39]    Espejo, P. G., Ventura, S. and Herrera, F. "A survey on the application of genetic programming to classification", IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 40(2), pp. 121-144 (2010).
[40]    Gunturu, M., Shakarad, G.N., and Singh, S. "Fitness Function to find Game Equilibria using Genetic Algorithms", 6th International Conference on Advances in Computing, Communications and Informatics (ICACCI'17), University in Manipal, India, pp. 1531-1534 (2017).
[41]    Xia, W., and Anand, B. "Game balancing with ecosystem mechanism", International Conference on Data Mining and Advanced Computing (SAPIENCE), Ernakulam, India, pp. 317-324 (2016).
[42]    Hendrikx, M., Meijer, S., Van Der Velden J, et al. "Procedural content generation for games: A survey", ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 9(1), pp. 1-24 (2013).
[43]    Kennedy, J. "Particle swarm optimization", Encyclopedia of Machine Learning, Springer, U. S., (2011).
[44]    Giusti, R., Hullett, K. and Whitehead, J. "Weapon design patterns in shooter games", first Workshop on Design Patterns in Games, Carolina, U. S., Article No. 3 (2012).
[45]    Cachia, W., Liapis, A. and Yannakakis, G.N. "Multi-level evolution of shooter levels", 11th Artificial Intelligence and Interactive Digital Entertainment Conference, California, U.S., pp. 115-121 (2015).
[46]    Giacomello, E., Lanzi, P.L. and Loiacono, D. "DOOM level generation using generative adversarial networks", arXiv preprint arXiv:1804.09154 (2018).
[47]    Filatov, A., Filatov, A., Krinkin, K., et al. "2D SLAM quality evaluation methods", arXiv preprint arXiv:1708.02354 (2017). 
[48]    Ponti, M.A., Ribeiro, L.S., Nazare, T.S., et al. "Generative Adversarial Networks", Presentation Content Inspired by Ian Goodfellow’s Tutorial on NIPS (2016).
[49]    Calderone, D. and Sastry, S.S. "Markov decision process routing games", 8th International Conference on Cyber-Physical Systems (ICCPS), Pittsburgh, U. S., pp. 273-280 (2017).
[50]    Van Hasselt, H., Guez, A. and Silver, D. "Deep reinforcement learning with double Q-Learning", 30th  Artificial Intelligence Conference, Phoenix, Arizona, U.S., pp. 2094-2100 (2016).
[51]    Kulkarni, T.D., Narasimhan, K., Saeedi, A., et al. "Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation", Advances in Neural Information Processing Systems Conference, Barcelona, Spain, pp. 3675-3683 (2016).
[52]    Cloud Compuing Center, Iran University of Science and Technology, Available: https://ccc.iust.ac.ir/
[53]    He, F.S., Liu, Y., Schwing, A.G., et al. "Learning to play in a day: Faster deep reinforcement learning by optimality tightening", arXiv preprint arXiv:1611.0160 (2016).
[54]    Berner, C., Brockman, G., Chan, B., et al. "Dota 2 with large scale deep reinforcement learning", arXiv preprint arXiv:1912.06680 (2019).
Scientia Iranica
Volume 28, Special issue on collective behavior of nonlinear dynamical networks
Transactions on Computer Science & Engineering and Electrical Engineering (D)
June 2021
Pages 1497-1514

Files

History

  • Receive Date: 31 October 2019
  • Revise Date: 20 August 2020
  • Accept Date: 16 November 2020

Share

How to cite

Statistics