On balance and dynamism in procedural content generation with self-adaptive evolutionary algorithms
Tóm tắt
We consider search-based procedural content generation in the context of Planet Wars, an RTS game. The objective of this work is to generate maps for the aforementioned game, that result in an interesting game-play. In order to characterize interestingness we focus on the properties of balance and dynamism. The former captures the fact that no player is overwhelmed by the opponent during the game, whereas the latter tries to model the fact that there is a lot of action during the game. To measure these properties on a given map, we conduct several games on them using top AI bots and collect statistics which are, in turn, used as inputs of a fuzzy rule base. This system is embedded within an evolutionary algorithm that features self-adaptation of mutation parameters as well as variable-length chromosomes (thus implying maps of different sizes). The experimentation focuses both on the optimization of balance and dynamism as stand-alone properties and in the analysis of the different tradeoffs attainable through them. To reach this goal a multi objective approach is used. We analyze both the usefulness of map-size self-adaptation in each scenario, as well as the properties of maps leading to different tradeoffs between dynamism and balance.
Tài liệu tham khảo
Browne C, Maire F (2010) Evolutionary game design. IEEE Trans Comput Intell AI Games 2:1–16
Czikszentmihalyi M (1990) Flow: the psychology of optimal experience. Harper Collins, New York, United States
Deb K, Agrawal S, Pratab A, Meyarivan T (2000) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Schoenauer M et al (eds) Parallel problem solving from Nature VI, vol 1917. Lecture Notes in Computer Science. Springer, Berlin, pp 849–858
Entertainment Software Association (2012) Essential facts about the computer and video game industry. http://www.theesa.com/facts/pdfs/esa_ef_2012.pdf. Accessed 13 March 2014
Fortin FA, Rainville FMD, Gardner MA, Parizeau M, Gagné C (2012) DEAP: evolutionary algorithms made easy. J Mach Learn Res 13:2171–2175
Frade M, de Vega FF, Cotta C (2008) Modelling video games’ landscapes by means of genetic terrain programming—a new approach for improving users’ experience. In: Giacobini M et al. (eds) Applications of evolutionary computing, vol 4974. Lecture Notes in Computer Science. Springer, Berlin, pp 485–490
Frade M, de Vega FF, Cotta C (2009) Breeding terrains with genetic terrain programming: the evolution of terrain generators. Int J Comput Games Technol 2009:1–13
Frade M, de Vega F, Cotta C (2010) Evolution of artificial terrains for video games based on accessibility. In: Di Chio C et al. (eds) Applications of evolutionary computation, vol 6024. Lecture Notes in Computer Science. Springer, Berlin, pp 90–99
Frade M, de Vega FF, Cotta C (2010) Evolution of artificial terrains for video games based on obstacles edge length. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp 1–8
Gearbox Software (2009) Borderlands, 2K Games
Gutiérrez JAG, Cotta C, Leiva AJF (2011) Design of emergent and adaptive virtual players in a war RTS game. In: Ferrández JM, Sánchez JRÁ, de la Paz F, Toledo FJ (eds) Proceedings of the 4th international work-conference on the interplay between natural and artificial computation (IWINAC 2011), vol 6686. Lecture Notes in Computer Science. Springer, La Palma, Canary Islands, Spain, pp 372–382
Hansen M, Jaszkiewicz A (1998) Evaluating the quality of approximations to the nondominated set. Technical Report IMM-REP-1998-7, Institute of Mathematical Modelling, Technical University of Denmark
Koster R (2004) A theory of fun for game design. Paraglyph, Phoenix, Arizona, United States
Lara-Cabrera R, Cotta C, Fernández-Leiva AJ (2013) A procedural balanced map generator with self-adaptive complexity for the real-time strategy game planet wars. In: Esparcia-Alcázar A et al (eds) Applications of evolutionary computation, vol 7835. Lecture Notes in Computer Science. Springer, Berlin, pp 274–283
Li R (2009) Mixed-integer evolution strategies for parameter optimization and their applications to medical image analysis. Ph.D. thesis, Leiden University
Lucas SM (2009) Computational intelligence and AI in games: a new IEEE transactions. IEEE Trans Comput Intell AI Games 1:1–3
Lucas SM, Mateas M, Preuss M, Spronck P, Togelius J (2012) Artificial and computational intelligence in games (Dagstuhl Seminar 12191). Dagstuhl Rep 2(5):43–70
Mahlmann T, Togelius J, Yannakakis GN (2012) Spicing up map generation. In: Chio CD et al. (eds) Applications of evolutionary computation, vol 7248. Lecture Notes in Computer Science. Springer, Málaga, Spain, pp 224–233
Malone T (1980) What makes things fun to learn? heuristics for designing instructional computer games. In: Proceedings of the 3rd ACM SIGSMALL symposium and the first SIGPC symposium on small systems, vol. 162, pp 162–169
Maxis (2008) Spore. Electronic arts
Mojang (2011) Minecraft, Mojang
Nogueira M, Cotta C, Fernández-Leiva AJ (2012) On modeling, evaluating and increasing players’ satisfaction quantitatively: steps towards a taxonomy. In: Chio CD et al. (eds) Applications of evolutionary computation, vol 7248. Lecture Notes in Computer Science. Springer, Málaga, Spain, pp 245–254
Rudolph G (1994) An evolutionary algorithm for integer programming. In: Davidor Y, Schwefel HP, Männer R (eds) Parallel problem solving from Nature III, vol 866. Lecture Notes in Computer Science. Springer, Jerusalem, Israel, pp 139–148
Szita I, Ponsen MJV, Spronck P (2009) Effective and diverse adaptive game AI. IEEE Trans Comput Intell AI Games 1:16–27
Togelius J, Yannakakis GN, Stanley KO, Browne C (2011) Search-based procedural content generation: a taxonomy and survey. IEEE Trans Comput Intell AI Games 3(3):172–186
Togelius J, De Nardi R, Lucas S (2007) Towards automatic personalised content creation for racing games. In: IEEE symposium on computational intelligence and games, CIG 2007, pp 252–259
Togelius J, Preuss M, Beume N, Wessing S, Hagelback J, Yannakakis G (2010) Multiobjective exploration of the starcraft map space. In: IEEE symposium on computational intelligence and games, CIG 2010, pp 265–272
Togelius J, Preuss M, Yannakakis GN (2010) Towards multiobjective procedural map generation. In: Proceedings of the 2010 workshop on procedural content generation in games, pp 3:1–3:8
Yannakakis G (2008) How to model and augment player satisfaction: a review. In: Proceedings of the 1st workshop on child, computer and interaction. ACM
Yannakakis GN (2012) Game AI revisited. In: Proceedings of the 9th conference on computing frontiers, CF’12ACM, New York, USA, pp 285–292
Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms—a comparative case study. In: Eiben AE et al. (eds) Parallel problem solving from Nature V, vol 1498. Lecture Notes in Computer Science. Springer, Berlin, pp 292–301