Constrained novelty search: a study on game content generation
Inhaltsverzeichnis
Referenz
Liapis, A., Yannakakis, G.N., Togelius, J.: Constrained novelty search: a study on game content generation. Evol. Comput. 23(1), 101–129 (2015)
DOI
http://dx.doi.org/10.1162/EVCO_a_00123
Abstract
Novelty search is a recent algorithm geared toward exploring search spaces without regard to objectives. When the presence of constraints divides a search space into feasible space and infeasible space, interesting implications arise regarding how novelty search explores such spaces. This paper elaborates on the problem of constrained novelty search and proposes two novelty search algorithms which search within both the feasible and the infeasible space. Inspired by the FI-2pop genetic algorithm, both algorithms maintain and evolve two separate populations, one with feasible and one with infeasible individuals, while each population can use its own selection method. The proposed algorithms are applied to the problem of generating diverse but playable game levels, which is representative of the larger problem of procedural game content generation. Results show that the two-population constrained novelty search methods can create, under certain conditions, larger and more diverse sets of feasible game levels than current methods of novelty search, whether constrained or unconstrained. However, the best algorithm is contingent on the particularities of the search space and the genetic operators used. Additionally, the proposed enhancement of offspring boosting is shown to enhance performance in all cases of two-population novelty search.
Extended Abstract
Bibtex
@article{liapis2015ecj,
author = {Antonios Liapis and Georgios N. Yannakakis and Julian Togelius},
title = {Constrained Novelty Search: A Study on Game Content Generation},
journal = {Evolutionary Computation},
volume = {23},
number = {1},
pages = {101-129},
year = {2015},
doi={http://dx.doi.org/10.1162/EVCO_a_00123},
url={http://antoniosliapis.com/papers/constrained_novelty_search.pdf http://de.evo-art.org/index.php?title=Constrained_novelty_search:_a_study_on_game_content_generation},
}
Used References
Boden, M. (1990). The Creative Mind. Abacus.
Browne, C. and Maire, F. (2010). Evolutionary game design. IEEE Transactions on Computational Intelligence and AI in Games, 2(1):1–16.
Cardamone, L., Yannakakis, G. N., Togelius, J., and Lanzi, P. L. (2011). Evolving interesting maps for a first person shooter. In EvoApplications (1), pages 63–72.
Coello Coello, C. A. (2010). Constraint-handling techniques used with evolutionary algorithms. In Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation, pages 2603–2624. ACM.
De Bono, E. (1970). Lateral thinking: creativity step by step. Harper & Row.
Dunn, O. (2012). Multiple comparisons among means. Journal of the American Statistical Association, 56:52–64.
Grace, K., Gero, J., and Saunders, R. (2013). Learning how to reinterpret creative problems. In Proceedings of the Fourth International Conference on Computational Creativity, pages 113–117.
Kimbrough, S. O., Koehler, G. J., Lu, M., and Wood, D. H. (2008). On a feasible-infeasible twopopulation (fi-2pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch. European Journal of Operational Research, 190(2):310–327.
Kramer, O. and Schwefel, H.-P. (2006). On three new approaches to handle constraints within evolution strategies. Natural Computing, 5(4):363–385.
Lehman, J. and Stanley, K. O. (2008). Exploiting open-endedness to solve problems through the search for novelty. In Proceedings of the International Conference on Artificial Life (ALIFE XI), pages 329–336. MIT Press.
Lehman, J. and Stanley, K. O. (2010). Revising the evolutionary computation abstraction: Minimal criteria novelty search. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 103–110.
Lehman, J. and Stanley, K. O. (2011a). Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation, 19(2):189–223.
Lehman, J. and Stanley, K. O. (2011b). Improving evolvability through novelty search and selfadaptation. In IEEE Congress on Evolutionary Computation, pages 2693–2700.
Lewis, M. (2008). Evolutionary visual art and design. In The Art of Artificial Evolution, pages 3–37.
Liapis, A., Mart´ınez, H. P., Togelius, J., and Yannakakis, G. N. (2013a). Adaptive game level creation through rank-based interactive evolution. In Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG).
Liapis, A., Mart´ınez, H. P., Togelius, J., and Yannakakis, G. N. (2013b). Transforming exploratory creativity with DeLeNoX. In Proceedings of the Fourth International Conference on Computational Creativity, pages 56–63.
Liapis, A., Yannakakis, G., and Togelius, J. (2013c). Enhancements to constrained novelty search: Two-population novelty search for generating game content. In Proceedings of Genetic and Evolutionary Computation Conference, pages 343–350.
Liapis, A., Yannakakis, G., and Togelius, J. (2013d). Sentient sketchbook: Computer-aided game level authoring. In Proceedings of ACM Conference on Foundations of Digital Games, pages 213– 220.
Liapis, A., Yannakakis, G. N., and Togelius, J. (2011). Neuroevolutionary constrained optimization for content creation. In Proceedings of IEEE Conference on Computational Intelligence and Games, pages 71–78.
Liapis, A., Yannakakis, G. N., and Togelius, J. (2012). Adapting models of visual aesthetics for personalized content creation. IEEE Transactions on Computational Intelligence and AI in Games, 4(3):213–228.
Liapis, A., Yannakakis, G. N., and Togelius, J. (2013e). Generating map sketches for strategy games. In Proceedings of Applications of Evolutionary Computation, volume 7835, LNCS, pages 264–273. Springer.
Liapis, A., Yannakakis, G. N., and Togelius, J. (2013f). Sentient world: Human-based procedural cartography. In Proceedings of Evolutionary and Biologically Inspired Music, Sound, Art and Design (EvoMusArt), volume 7834, LNCS, pages 180–191. Springer.
Liapis, A., Yannakakis, G. N., and Togelius, J. (2013g). Towards a generic method of evaluating game levels. In Proceedings of the AAAI Artificial Intelligence for Interactive Digital Entertainment Conference.
Michalewicz, Z. (1995a). Do not kill unfeasible individuals. In Proceedings of the Fourth Intelligent Information Systems Workshop, pages 110–123.
Michalewicz, Z. (1995b). A survey of constraint handling techniques in evolutionary computation methods. In Proceedings of the 4th Annual Conference on Evolutionary Programming, pages 135–155.
Michalewicz, Z., Dasgupta, D., Le Riche, R., and Schoenauer, M. (1996). Evolutionary algorithms for constrained engineering problems. Computers & Industrial Engineering Journal, 30:851–870.
Moraglio, A. (2011). Abstract convex evolutionary search. In Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms, pages 151–162. ACM.
Morse, G., Risi, S., Snyder, C. R., and Stanley, K. O. (2013). Single-unit pattern generators for quadruped locomotion. In Proceeding of the Genetic and Evolutionary Computation Conference, pages 719–726. ACM.
Risi, S., Lehman, J., D’Ambrosio, D. B., Hall, R., and Stanley, K. O. (2012). Combining searchbased procedural content generation and social gaming in the petalz video game. In Proceedings of the Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE 2012).
Risi, S. and Stanley, K. O. (2013). Confronting the challenge of learning a flexible neural controller for a diversity of morphologies. In Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference, pages 255–262. ACM.
Schoenauer, M. and Michalewicz, Z. (1996). Evolutionary computation at the edge of feasibility. In Proceedings of the 4th Parallel Problem Solving from Nature, pages 245–254.
Shaker, N., Yannakakis, G. N., and Togelius, J. (2010). Towards automatic personalized content generation for platform games. In Proceedings of the AAAI Artificial Intelligence for Interactive Digital Entertainment Conference, pages 63–68.
Sorenson, N., Pasquier, P., and DiPaola, S. (2011). A generic approach to challenge modeling for the procedural creation of video game levels. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):229–244.
Stanley, K. O., D’Ambrosio, D. B., and Gauci, J. (2009). A hypercube-based encoding for evolving large-scale neural networks. Artifiicial Life, 15(2):185–212.
Togelius, J., Preuss, M., Beume, N., Wessing, S., Hagelb¨ack, J., Yannakakis, G. N., and Grappiolo, C. (2013). Controllable procedural map generation via multiobjective evolution. Genetic Programming and Evolvable Machines, 14(2):245–277.
Togelius, J., Yannakakis, G., Stanley, K., and Browne, C. (2011). Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):172–186.
Yannakakis, G. N. (2012). Game AI revisited. In Proceedings of ACM Computing Frontiers Conference, pages 285–292.
Yannakakis, G. N., Liapis, A., and Alexopoulos, C. (2014). Mixed-initiative co-creativity. In Proceedings of the ACM Conference on Foundations of Digital Games.
Yannakakis, G. N. and Togelius, J. (2011). Experience-driven procedural content generation. IEEE Transactions on Affective Computing, 2(3):147–161.
Links
Full Text
http://antoniosliapis.com/papers/constrained_novelty_search.pdf
