Enhancements to constrained novelty search: two-population novelty search for generating game content

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Referenz

Liapis, Antonios, Yannakakis, G., Togelius, J.: Enhancements to constrained novelty search: two-population novelty search for generating game content. In: Proceedings of Genetic and Evolutionary Computation Conference (2013)

DOI

http://dx.doi.org/10.1145/2463372.2463416

Abstract

Novelty search is a recent algorithm geared to explore search spaces without regard to objectives; minimal criteria novelty search is a variant of this algorithm for constrained search spaces. For large search spaces with multiple constraints, however, it is hard to find a set of feasible individuals that is both large and diverse. In this paper, we present two new methods of novelty search for constrained spaces, Feasible-Infeasible Novelty Search and Feasible-Infeasible Dual Novelty Search. Both algorithms keep separate populations of feasible and infeasible individuals, inspired by the FI-2pop genetic algorithm. These algorithms are applied to the problem of creating diverse and feasible game levels, representative of a large class of important problems in procedural content generation for games. Results show that the new algorithms under certain conditions can produce larger and more diverse sets of feasible strategy game maps than existing algorithms. However, the best algorithm is contingent on the particularities of the search space and the genetic operators used. It is also shown that the proposed enhancement of offspring boosting increases performance in all cases.

Extended Abstract

Bibtex

@inproceedings{Liapis:2013:ECN:2463372.2463416,
author = {Liapis, Antonios and Yannakakis, Georgios N. and Togelius, Julian},
title = {Enhancements to Constrained Novelty Search: Two-population Novelty Search for Generating Game Content},
booktitle = {Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation},
series = {GECCO '13},
year = {2013},
isbn = {978-1-4503-1963-8},
location = {Amsterdam, The Netherlands},
pages = {343--350},
numpages = {8},
url = {http://doi.acm.org/10.1145/2463372.2463416},
doi = {10.1145/2463372.2463416},
acmid = {2463416},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {constrained novelty search, feasible-infeasible two-population ga, level design, procedural content generation},
}


Used References

1 D. Ashlock, C. Lee, and C. McGuinness. Search-based procedural generation of maze-like levels. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):260--273, 2011.

2 C. Browne and F. Maire. Evolutionary game design. IEEE Transactions on Computational Intelligence and AI in Games, 2(1):1--16, 2010.

3 Luigi Cardamone , Daniele Loiacono , Pier Luca Lanzi, Interactive evolution for the procedural generation of tracks in a high-end racing game, Proceedings of the 13th annual conference on Genetic and evolutionary computation, July 12-16, 2011, Dublin, Ireland http://doi.acm.org/10.1145/2001576.2001631

4 Carlos A. Coello Coello, Constraint-handling techniques used with evolutionary algorithms, Proceedings of the 12th annual conference companion on Genetic and evolutionary computation, July 07-11, 2010, Portland, Oregon, USA http://doi.acm.org/10.1145/1830761.1830910

5 O. Dunn. Multiple comparisons among means. Journal of the American Statistical Association, 56:52--64, 2012.

6 Erin J. Hastings , Ratan K. Guha , Kenneth O. Stanley, Evolving content in the galactic arms race video game, Proceedings of the 5th international conference on Computational Intelligence and Games, p.241-248, September 07-10, 2009, Milano, Italy

7 S. O. Kimbrough, G. J. Koehler, M. Lu, and D. H. Wood. On a feasible-infeasible two-population (fi-2pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch. European Journal of Operational Research, 190(2):310--327, 2008.

8 O. Kramer , H.-P. Schwefel, On three new approaches to handle constraints within evolution strategies, Natural Computing: an international journal, v.5 n.4, p.363-385, November 2006 http://dx.doi.org/10.1007/s11047-006-0001-x

9 Joel Lehman , Kenneth O. Stanley, Revising the evolutionary computation abstraction: minimal criteria novelty search, Proceedings of the 12th annual conference on Genetic and evolutionary computation, July 07-11, 2010, Portland, Oregon, USA http://doi.acm.org/10.1145/1830483.1830503

10 Joel Lehman , Kenneth O. Stanley, Abandoning objectives: Evolution through the search for novelty alone, Evolutionary Computation, v.19 n.2, p.189-223, Summer 2011 http://dx.doi.org/10.1162/EVCO_a_00025

11 Antonios Liapis , Georgios N. Yannakakis , Julian Togelius, Generating map sketches for strategy games, Proceedings of the 16th European conference on Applications of Evolutionary Computation, April 03-05, 2013, Vienna, Austria http://dx.doi.org/10.1007/978-3-642-37192-9_27

12 A. Liapis, G. Yannakakis, and J. Togelius. Sentient sketchbook: Computer-aided game level authoring. In Proceedings of ACM Conference on Foundations of Digital Games, 2013. In Print.

13 A. Liapis, G. N. Yannakakis, and J. Togelius. Neuroevolutionary constrained optimization for content creation. In Proceedings of IEEE Conference on Computational Intelligence and Games, pages 71--78, 2011.

14 A. Liapis, G. N. Yannakakis, and J. Togelius. Adapting models of visual aesthetics for personalized content creation. IEEE Transactions on Computational Intelligence and AI in Games, 4(3):213--228, 2012.

15 Z. Michalewicz. Do not kill unfeasible individuals. In Proceedings of the Fourth Intelligent Information Systems Workshop, pages 110--123, 1995.

16 Z. Michalewicz. A survey of constraint handling techniques in evolutionary computation methods. In Proceedings of the 4th Annual Conference on Evolutionary Programming, pages 135--155, 1995.

17 Zbigniew Michalewicz , Dipankar Dasgupta , Rodolphe G. Le Riche , Marc Schoenauer, Evolutionary algorithms for constrained engineering problems, Computers and Industrial Engineering, v.30 n.4, p.851-870, Sept. 1996 http://dx.doi.org/10.1016/0360-8352(96)00037-X

18 Marc Schoenauer , Zbigniew Michalewicz, Evolutionary Computation at the Edge of Feasibility, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.245-254, September 22-26, 1996

19 A. M. Smith and M. Mateas. Answer set programming for procedural content generation: A design space approach. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):187--200, 2011.

20 N. Sorenson, P. Pasquier, and S. DiPaola. 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, 2011.

21 J. Togelius, G. Yannakakis, K. Stanley, and C. Browne. Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, (99), 2011.

22 Geogios N. Yannakakis, Game AI revisited, Proceedings of the 9th conference on Computing Frontiers, May 15-17, 2012, Cagliari, Italy http://doi.acm.org/10.1145/2212908.2212954


Links

Full Text

internal file


Sonstige Links

http://antoniosliapis.com/research/novsearch.php