Constrained Optimization

Unlike other forms of art, games are bound by playability concerns: a level is not playable if the avatar can't reach the exit and a virtual car is not playable if it has negative mass. My research focuses on satisfying playability constraints either in objective-driven genetic search problems or via novelty search.

Multi-segment Evolution of Dungeon Game Levels

Antonios Liapis

Abstract: This paper presents a generative technique for game levels, focusing on expansive dungeon levels. The proposed two-step evolutionary process creates a high-level overview of the map, which is then used to specify constraints and objectives on multiple constrained optimization algorithms which generate the high-resolution segments of the map. Results show how different types of segments are possible, and how the different connectivity constraints and objectives affect the performance of the algorithm. The modular approach, which allows for a high-level specification of the level first and the subsequent compartmentalized generation of the final map's components, is both scalable and more computationally efficient than a direct encoding, while it allows for more control and user intervention on either level of detail.

In Proceedings of the Genetic and Evolutionary Computation Conference, 2017. BibTex

Constrained Surprise Search for Content Generation

Daniele Gravina, Antonios Liapis and Georgios N. Yannakakis

Abstract: In procedural content generation, it is often desirable to create artifacts which not only fulfill certain playability constraints but are also able to surprise the player with unexpected potential uses. This paper applies a divergent evolutionary search method based on surprise to the constrained problem of generating balanced and efficient sets of weapons for the Unreal Tournament III shooter game. The proposed constrained surprise search algorithm ensures that pairs of weapons are sufficiently balanced and effective while also rewarding unexpected uses of these weapons during game simulations with artificial agents. Results in the paper demonstrate that searching for surprise can create functionally diverse weapons which require new gameplay patterns of weapon use in the game.

in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG). 2016. BibTex

Exploring the Visual Styles of Arcade Game Assets

Antonios Liapis

Abstract: This paper describes a method for evolving assets for video games based on their visuals properties. Focusing on assets for a space shooter game, a genotype consisting of turtle commands is transformed into a spaceship image composed of human-authored sprite components. Due to constraints on the final spaceships' plausibility, the paper investigates two-population constrained optimization and constrained novelty search methods. A sample of visual styles is tested, each a combination of visual metrics which primarily evaluate balance and shape complexity. Experiments with constrained optimization of a visual style demonstrate that a visually consistent set of spaceships can be generated, while experiments with constrained novelty search demonstrate that several distinct visual styles can be discovered by exploring along select, or all, visual dimensions.

in Proceedings of Evolutionary and Biologically Inspired Music, Sound, Art and Design (EvoMusArt). Springer, 2016. BibTex

Refining the Paradigm of Sketching in AI-Based Level Design

Antonios Liapis, Georgios N. Yannakakis

Abstract: This paper describes computational processes which can simulate how human designers sketch and then iteratively refine their work. The paper uses the concept of a map sketch as an initial, low-resolution and low-fidelity prototype of a game level, and suggests how such map sketches can be refined computationally. Different case studies with map sketches of different genres showcase how refinement can be achieved via increasing the resolution of the game level, increasing the fidelity of the function which evaluates it, or a combination of the two. While these case studies use genetic algorithms to automatically generate levels at different degrees of refinement, the general method described in this paper can be used with most procedural generation methods, as well as for AI-assisted design alongside a human creator.

in Proceedings of the AAAI Artificial Intelligence for Interactive Digital Entertainment Conference, 2015. BibTex

Procedural Personas as Critics for Dungeon Generation

Antonios Liapis, Christoffer Holmgard, Georgios N. Yannakakis, Julian Togelius

Abstract: This paper introduces a constrained optimization method which uses procedural personas to evaluate the playability and quality of evolved dungeon levels. Procedural personas represent archetypical player behaviors, and their controllers have been evolved to maximize a specific utility which drives their decisions. A "baseline" persona evaluates whether a level is playable by testing if it can survive in a worst-case scenario of the playthrough. On the other hand, a Monster Killer persona or a Treasure Collector persona evaluates playable levels based on how many monsters it can kill or how many treasures it can collect, respectively. Results show that the implemented two-population genetic algorithm discovers playable levels quickly and reliably, while the different personas affect the layout, difficulty level and tactical depth of the generated dungeons.

in Applications of Evolutionary Computation, vol. 9028, LNCS. Springer, 2015. BibTex

Towards a Generic Method of Evaluating Game Levels

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Abstract: This paper addresses the problem of evaluating the quality of game levels across different games and even genres, which is of key importance for making procedural content generation and assisted game design tools more generally applicable. Three game design patterns are identified for having high generality while being easily quantifiable: area control, exploration and balance. Formulas for measuring the extent to which a level includes these concepts are proposed, and evaluation functions are derived for levels in two different game genres: multiplayer strategy game maps and single-player roguelike dungeons. To illustrate the impact of these evaluation functions, and the similarity of impact across domains, sets of levels for each function are generated using a constrained genetic algorithm. The proposed measures can easily be extended to other game genres.

in Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2013. BibTex

Sentient Sketchbook: Computer-Aided Game Level Authoring

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Abstract: This paper introduces the Sentient Sketchbook, a tool which supports a designer in the creation of game levels. Using map sketches to alleviate designer effort, the tool automates playability checks and evaluations and visualizes significant gameplay properties. This paper also introduces constrained novelty search via a two-population paradigm for generating, in real-time, alternatives to the author's design and evaluates its potential against current approaches. The paper concludes with a small-scale user study in which industry experts interact with the Sentient Sketchbook to design game levels. Results demonstrate the tool's potential and provide directions for its improvement.

in Proceedings of the 8th Conference on the Foundations of Digital Games, 2013, pp. 213-220. BibTex

Generating Map Sketches for Strategy Games

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Abstract: How can a human and an algorithm productively collaborate on generating game content? In this paper, we try to answer this question in the context of generating balanced and interesting low-resolution sketches for game levels. We introduce six important criteria for successful strategy game maps, and present map sketches optimized for one or more of these criteria via a constrained evolutionary algorithm. The sketch-based map representation and the computationally lightweight evaluation methods are geared towards the integration of the evolutionary algorithm within a mixed-initiative tool, allowing for the co-creation of game content by a human and an artificial designer.

in Proceedings of Applications of Evolutionary Computation, vol. 7835, LNCS. Springer, 2013, pp. 264-273. BibTex

Neuroevolutionary Constrained Optimization for Content Creation

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Abstract: This paper presents a constraint-based procedural content generation (PCG) framework used for the creation of novel and high-performing content. Specifically, we examine the efficiency of the framework for the creation of spaceship design (hull shape and spaceship attributes such as weapon and thruster types and topologies) independently of game physics and steering strategies. According to the proposed framework, the designer picks a set of requirements for the spaceship that a constrained optimizer attempts to satisfy. The constraint satisfaction approach followed is based on neuroevolution; Compositional Pattern-Producing Networks (CPPNs) which represent the spaceship's design are trained via a constrain-based evolutionary algorithm. Results obtained in a number of evolutionary runs using a set of constraints and objectives show that the generated spaceships perform well in movement, combat and survival tasks and are also visually appealing.

in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG), 2011, pp. 71-78. BibTex