Evolving Levels for Super Mario Bros Using Grammatical Evolution

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche

Reference

Noor Shaker and Miguel Nicolau and Georgios N. Yannakakis and Julian Togelius and Michael O'Neill: Evolving Levels for Super Mario Bros Using Grammatical Evolution. In: IEEE Conference on Computational Intelligence and Games CIG 2012, pp. 304-311, IEEE, 11-14 September 2012.

DOI

http://dx.doi.org/10.1109/CIG.2012.6374170

Abstract

This paper presents the use of design grammars to evolve playable 2D platform levels through grammatical evolution (GE). Representing levels using design grammars allows simple encoding of important level design constraints, and allows remarkably compact descriptions of large spaces of levels. The expressive range of the GE-based level generator is analyzed and quantitatively compared to other feature-based and the original level generators by means of aesthetic and similarity based measures. The analysis reveals strengths and shortcomings of each generator and provides a general framework for comparing content generated by different generators. The approach presented can be used as an assistive tool by game designers to compare and analyze generators' capabilities within the same game genre.

Extended Abstract

Bibtex

Used References

J. Koza and R. Poli, "Genetic programming," Search Methodologies, pp. 127-164, 2005. [CrossRef]

M. O'Neill and C. Ryan, "Grammatical evolution," Evolutionary Computation, IEEE Transactions on, vol. 5, no. 4, pp. 349-358, 2001. Abstract | Full Text: PDF (172KB) | Full Text: HTML

N. Shaker, G. Yannakakis, and J. Togelius, "Feature analysis for modeling game content quality," in Computational Intelligence and Games (CIG), 2011 IEEE Conference on. IEEE, 2011, pp. 126-133. Abstract | Full Text: PDF (1121KB) | Full Text: HTML

A. M. Smith and M. Mateas, "Variations Forever: Flexibly Generating Rulesets from a Sculptable Design Space of Mini-Games," IEEE Transactions on Computational Intelligence and AI in Games, 2010. Abstract | Full Text: PDF (661KB) | Full Text: HTML

J. Togelius and J. Schmidhuber, "An experiment in automatic game design," pp. 111-118, 2009.

L. Cardamone, G. Yannakakis, J. Togelius, and P. Lanzi, "Evolving interesting maps for a first person shooter," Applications of Evolutionary Computation, pp. 63-72, 2011. [CrossRef]

J. Togelius, M. Preuss, and G. Yannakakis, "Towards multiobjective procedural map generation," in Proceedings of the 2010 Workshop on Procedural Content Generation in Games. ACM, 2010, p. 3.

G. Smith, J. Whitehead, and M. Mateas, "Tanagra: A mixed-initiative level design tool," in Proceedings of the Fifth International Conference on the Foundations of Digital Games. ACM, 2010, pp. 209-216. Full Text: Access at ACM

C. Pedersen, J. Togelius, and G. N. Yannakakis, "Modeling player experience for content creation," IEEE Transactions on Computational Intelligence and AI in Games, vol. 2, no. 1, pp. 54-67, 2010. Abstract | Full Text: PDF (844KB) | Full Text: HTML

N. Sorenson, P. Pasquier, and S. DiPaola, "A generic approach to challenge modeling for the procedural creation of video game levels," Computational Intelligence and AI in Games, IEEE Transactions on, vol. 3, no. 3, pp. 229-244, 2011. Abstract | Full Text: PDF (1234KB) | Full Text: HTML

L. Cardamone, D. Loiacono, and P. L. Lanzi, "Interactive evolution for the procedural generation of tracks in a high-end racing game," Interface, pp. 395-402, 2011. [CrossRef]

J. Togelius, R. De Nardi, and S. Lucas, "Towards automatic personalised content creation for racing games," in IEEE Symposium on Computational Intelligence and Games, 2007. IEEE, 2007, pp. 252-259. Abstract | Full Text: PDF (373KB) | Full Text: HTML

C. Browne and F. Maire, "Evolutionary game design," IEEE Transactions on Computational Intelligence and AI in Games., vol. 2, no. 1, pp. 1-16, 2010. Abstract | Full Text: PDF (1190KB) | Full Text: HTML

M. Cook and S. Colton, "Multi-faceted evolution of simple arcade games," in IEEE Conference on Computational Intelligence and Games (CIG). IEEE, 2011, pp. 289-296. Abstract | Full Text: PDF (723KB) | Full Text: HTML

E. J. Hastings, R. K. Guha, and K. O. Stanley, "Evolving content in the galactic arms race video game," in Proceedings of the 5th international conference on Computational Intelligence and Games, ser. CIG'09. Piscataway, NJ, USA: IEEE Press, 2009, pp. 241-248. Abstract | Full Text: PDF (1743KB) | Full Text: HTML

N. Shaker, G. N. Yannakakis, and J. Togelius, "Towards Automatic Personalized Content Generation for Platform Games," in Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE). AAAI Press, October 2010.

G. Yannakakis and J. Togelius, "Experience-driven procedural content generation," Affective Computing, IEEE Transactions on, vol. 2, no. 3, pp. 147-161, 2011. Abstract | Full Text: PDF (643KB) | Full Text: HTML

J. Togelius, G. Yannakakis, K. Stanley, and C. Browne, "Search-based procedural content generation," Applications of Evolutionary Computation, pp. 141-150, 2010.

J. Koza, M. Keane, M. Streeter, W. Mydlowec, J. Yu, and G. Lanza, Genetic programming IV. Kluwer Academic Publishers, 2003.

P. Bentley, Evolutionary design by computers. Morgan Kaufmann, 1999, vol. 1.

G. Hornby and J. Pollack, "The advantages of generative grammatical encodings for physical design," in Proceedings of the 2001 Congress on Evolutionary Computation, 2001., vol. 1. IEEE, 2001, pp. 600-607. Abstract | Full Text: PDF (1300KB) | Full Text: HTML

J. Byrne, M. Fenton, E. Hemberg, J. McDermott, M. ONeill, E. Shotton, and C. Nally, "Combining structural analysis and multi-objective criteria for evolutionary architectural design," Applications of Evolutionary Computation, pp. 204-213, 2011. [CrossRef]

M. O'Neill, J. Swafford, J. McDermott, J. Byrne, A. Brabazon, E. Shotton, C. McNally, and M. Hemberg, "Shape grammars and grammatical evolution for evolutionary design," in Proceedings of the 11th Annual conference on Genetic and evolutionary computation. ACM, 2009, pp. 1035-1042. Full Text: Access at ACM

G. Smith and J. Whitehead, "Analyzing the expressive range of a level generator," in Proceedings of the 2010 Workshop on Procedural Content Generation in Games. ACM, 2010, p. 4. Full Text: Access at ACM

J. Togelius, S. Karakovskiy, J. Koutník, and J. Schmidhuber, "Super mario evolution," in Proceedings of the 5th international conference on Computational Intelligence and Games, ser. CIG'09. Piscataway, NJ, USA: IEEE Press, 2009, pp. 156-161. Abstract | Full Text: PDF (1333KB)

N. Shaker, G. Yannakakis, and J. Togelius, "Digging deeper into platform game level design: session size and sequential features," Applications of Evolutionary Computation, pp. 275-284, 2012. [CrossRef]

P. Morel, H. Hamda, and M. Schoenauer, "Computational chair design using genetic algorithms," Concept, vol. 71, no. 3, pp. 95-99, 2005.

M. O'Neill, E. Hemberg, C. Gilligan, E. Bartley, J. McDermott, and A. Brabazon, "Geva: grammatical evolution in java," ACM SIGEVOlution, vol. 3, no. 2, pp. 17-22, 2008. Full Text: Access at ACM

M. Li, X. Chen, X. Li, B. Ma, and P. Vitányi, "The similarity metric," IEEE Transactions on Information Theory, vol. 50, no. 12, pp. 3250-3264, 2004. Abstract | Full Text: PDF (416KB) | Full Text: HTML

M. ONeill, R. Cleary, and N. Nikolov, "Solving knapsack problems with attribute grammars," in Proceedings of the Third Grammatical Evolution Workshop (GEWS04). Citeseer, 2004.


Links

Full Text

http://julian.togelius.com/Shaker2012Evolving.pdf

intern file

Sonstige Links