Divergent Search
Divergent search targets unseen or unexpected solutions rather than maximizing an expressly stated objective. For the purposes of my research, I experiment with divergent search for open-ended game content generation as it can break designer fixations and create surprising content.
Dynamic Quality-Diversity Search
Roberto Gallotta, Antonios Liapis, Georgios N. Yannakakis
The Dynamic Lunar Lander environment, where the dynamic QD algorithms are tested. The goal is to land the lander by controlling its thrusters, but dynamically changing the wind strength and turbulence (before in yellow, after in red) can change the lander behavior significantly.
Abstract: Evolutionary search via the quality-diversity (QD) paradigm can discover highly performing solutions in different behavioural niches, showing considerable potential in complex real-world scenarios such as evolutionary robotics. Yet most QD methods only tackle static tasks that are fixed over time, which is rarely the case in the real world. Unlike noisy environments, where the fitness of an individual changes slightly at every evaluation, dynamic environments simulate tasks where external factors at unknown and irregular intervals alter the performance of the individual with a severity that is unknown a priori. Literature on optimisation in dynamic environments is extensive, yet such environments have not been explored in the context of QD search. This paper introduces a novel and generalisable Dynamic QD methodology that aims to keep the archive of past solutions updated in the case of environment changes. Our Dynamic QD intervention is applied on MAP-Elites and CMA-ME, two powerful QD algorithms, and we test their performance on a dynamic variant of the well-known lunar lander environment.
in Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2024. BibTex
MAP-Elites with Transverse Assessment for Multimodal Problems in Creative Domains
Marvin Zammit, Antonios Liapis, Georgios N. Yannakakis
The MEliTA process: an elite is selected from the featuremap, and one of its modalities (image) is altered. Then, this new image is mapped to another row of cells in the featuremap and new candidate solutions are produced by combining the new image and the elites' old text modality. The best combination of new image and older text survives and replaces the previous individual or occupies a new cell.
Abstract: The recent advances in language-based generative models have paved the way for the orchestration of multiple generators of different artefact types (text, image, audio, etc.) into one system. Presently, many open-source pre-trained models combine text with other modalities, thus enabling shared vector embeddings to be compared across different generators. Within this context we propose a novel approach to handle multimodal creative tasks using Quality Diversity evolution. Our contribution is a variation of the MAP-Elites algorithm, MAP-Elites with Transverse Assessment (MEliTA), which is tailored for multimodal creative tasks and leverages deep learned models that assess coherence across modalities. MEliTA decouples the artefacts' modalities and promotes cross-pollination between elites. As a test bed for this algorithm, we generate text descriptions and cover images for a hypothetical video game and assign each artefact a unique modality-specific behavioural characteristic. Results indicate that MEliTA can improve text-to-image mappings within the solution space, compared to a baseline MAP-Elites algorithm that strictly treats each image-text pair as one solution. Our approach represents a significant step forward in multimodal bottom-up orchestration and lays the groundwork for more complex systems coordinating multimodal creative agents in the future.
in Proceedings of the International Conference on Computational Intelligence in Music, Sound, Art and Design (EvoMusArt), 2024. BibTex
Design Space Exploration of Shell Structures Using Quality Diversity Algorithms
Konstantinos Sfikas, Antonios Liapis, Joel Hilmersson, Jeg Dudley, Edoardo Tibuzzi and Georgios N. Yannakakis
Visualisation of all feasible solutions found in a single run of the FI-MAP-Elites algorithm on a complex test case which is comparable to real-world engineering problems. Meshes in yellow have a higher fitness (i.e. lower elastic energy). The two dimensions of diversity are height deviations of the four external arches (BC1), and height deviations of control points near the center of the vault (BC2).
Abstract: Computer-aided optimization algorithms in structural engineering have historically focused on the structural performance of generated forms, often resulting in the selection of a single 'optimal' solution. However, diversity of generated solutions is desirable when those solutions are shown to a human user to choose from. Quality-Diversity (QD) search is an emerging field of Evolutionary Computation which can automate the exploration of the solution space in engineering problems. QD algorithms, such as MAP-Elites, operate by maintaining and expanding an archive of diverse solutions, optimising for quality in local niches of a multidimensional design space. The generated archive of solutions can help engineers gain a better overview of the solution space, illuminating which designs are possible and their trade-offs. In this paper we apply Quality Diversity search to the problem of designing shell structures. Since the design of shell structures comes with physical constraints, we leverage a constrained optimization variant of the MAP-Elites algorithm, FI-MAP-Elites. We implement our proposed methodology within the Rhino/Grasshopper environment and use the Karamba Finite Element Analysis solver for all structural engineering calculations. We test our method on case studies of parametric models of shell structures that feature varying complexity. Our experiments investigate the algorithm's ability to illuminate the solution space and generate feasible and high-quality solutions.
in Proceedings of the International Association for Shell and Spatial Structures Symposium, 2023. BibTex
Controllable Exploration of a Design Space via Interactive Quality Diversity
Konstantinos Sfikas, Antonios Liapis and Georgios N. Yannakakis
Behavioral space exploration for the baseline MAP-Elites (bottom row) and UC-ME, for the first 5 user selections. Their shared color scale (bottom) is the feasible quality. The top row shows coverage differences: red cells are discovered only by the baseline, blue cells are discovered only by UC-ME and gray cells are common.
Abstract: This paper introduces a user-driven evolutionary algorithm based on Quality Diversity (QD) search. During a design session, the user iteratively selects among presented alternatives and their selections affect the upcoming results. We implement a variation of the MAP-Elites algorithm where the presented alternatives are sampled from a small region (window) of the behavioral space. After a user selection, the window is centered on the selected individual’s behavior characterization, evolution selects parents from within this window to produce offspring, and new alternatives are sampled. Essentially we define an adaptive system of local QD search, where the user’s selections guide the search towards specific regions of the behavioral space. The system is tested on the generation of architectural layouts, a constrained optimization task, leveraging QD search through a two-archive approach.
in Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2023. BibTex
A General-Purpose Expressive Algorithm for Room-based Environments
Konstantinos Sfikas, Antonios Liapis and Georgios N. Yannakakis
Examples of different level layouts for design specifications with 8 rooms.
Abstract: This paper presents a generative architecture for general-purpose room layouts that can be treated as geometric definitions of dungeons, mansions, shooter levels and more. The motivation behind this work is to provide a design tool for virtual environments that combines aspects of controllability, expressivity and generality. Towards that end, a two-tier level representation is realized, with a graph-based design specification constraining and guiding the generated geometries, facilitated by constrained evolutionary search. Expressivity is secured through quality-diversity search which can provide the designer with a broad variety of level layouts to choose from. Finally, the generator is general-purpose as it can produce layouts based on different types of static grid structures or as free-form, curved structures through an adaptive Voronoi diagram that is evolved along with the level itself. The method is tested on a variety of design specifications and grid types, and results show that even with complex design constraints or malleable grids the algorithm can produce a broad variety of levels.
in Proceedings of the FDG workshop on Procedural Content Generation, 2022. BibTex
Open-Ended Evolution for Minecraft Building Generation
Matthew Barthet, Antonios Liapis and Georgios N. Yannakakis
The exploration phase performs novelty search on the latent space by encoding the Minecraft buildings that are being evolved.
Abstract: This paper proposes a procedural content generator which evolves Minecraft buildings according to an open-ended and intrinsic definition of novelty. To realize this goal we evaluate individuals' novelty in the latent space using a 3D autoencoder, and alternate between phases of exploration and transformation. During exploration the system evolves multiple populations of CPPNs through CPPN-NEAT and constrained novelty search in the latent space (defined by the current autoencoder). We apply a set of repair and constraint functions to ensure candidates adhere to basic structural rules and constraints during evolution. During transformation, we reshape the boundaries of the latent space to identify new interesting areas of the solution space by retraining the autoencoder with novel content. In this study we evaluate five different approaches for training the autoencoder during transformation and its impact on populations' quality and diversity during evolution. Our results show that by retraining the autoencoder we can achieve better open-ended complexity compared to a static model, which is further improved when retraining using larger datasets of individuals with diverse complexities.
in IEEE Transactions on Games 15(4), 2022. BibTex
Seeding Diversity into AI Art
Marvin Zammit, Antonios Liapis and Georgios N. Yannakakis
Images generated via Novelty Search with Local Competition on a latent vector previously optimized through a Generative Adversarial Algorithm.
Abstract: This paper argues that generative art driven by conformance to a visual and/or semantic corpus lacks the necessary criteria to be considered creative. Among several issues identified in the literature, we focus on the fact that generative adversarial networks (GANs) that create a single image, in a vacuum, lack a concept of novelty regarding how their product differs from previously created ones. We envision that an algorithm that combines the novelty preservation mechanisms in evolutionary algorithms with the power of GANs can deliberately guide its creative process towards output that is both good and novel. In this paper, we use recent advances in image generation based on semantic prompts using OpenAI's CLIP model, interrupting the GAN's iterative process with short cycles of evolutionary divergent search. The results of evolution are then used to continue the GAN's iterative process; we hypothesise that this intervention will lead to more novel outputs. Testing our hypothesis using novelty search with local competition, a quality-diversity evolutionary algorithm that can increase visual diversity while maintaining quality in the form of adherence to the semantic prompt, we explore how different notions of visual diversity can affect both the process and the product of the algorithm. Results show that even a simplistic measure of visual diversity can help counter a drift towards similar images caused by the GAN. This first experiment opens a new direction for introducing higher intentionality and a more nuanced drive for GANs.
in Proceedings of the International Conference on Computational Creativity, 2022. BibTex
Monte Carlo Elites: Quality-Diversity Selection as a Multi-Armed Bandit Problem
Konstantinos Sfikas, Antonios Liapis and Georgios N. Yannakakis
Feature maps at different stages of evolution for the 6D Rastrigin function, showing the different coverage and fitness score of elites when selecting parents uniformly (R), based on the curiosity score (C), or based on a UCB formula that balances exploration and exploitation (U).
Abstract: A core challenge of evolutionary search is the need to balance between exploration of the search space and exploitation of highly fit regions. Quality-diversity search has explicitly walked this tightrope between a population's diversity and its quality. This paper extends a popular quality-diversity search algorithm, MAP-Elites, by treating the selection of parents as a multi-armed bandit problem. Using variations of the upper-confidence bound to select parents from under-explored but potentially rewarding areas of the search space can accelerate the discovery of new regions as well as improve its archive's total quality. The paper tests an indirect measure of quality for parent selection: the survival rate of a parent's offspring. Results show that maintaining a balance between exploration and exploitation leads to the most diverse and high-quality set of solutions in three different testbeds.
in Proceedings of the Genetic and Evolutionary Computation Conference, 2021. BibTex
ARCH-Elites: Quality-Diversity for Urban Design
Theodoros Galanos, Antonios Liapis, Georgios N. Yannakakis and Reinhard Koenig
Evolution in ARCH-Elites: A geographic location is selected by the user (a) and building geometries and metadata are extracted (b). The location is then split into cells (c); two cells are selected and geometric blending takes place (d).
Abstract: This paper introduces ARCH-Elites, a MAP-Elites implementation that can reconfigure large-scale urban layouts at real-world locations via a pre-trained surrogate model instead of costly simulations. In a series of experiments, we generate novel urban designs for two real-world locations in Boston, Massachusetts. Combining the exploration of a possibility space with real-time performance evaluation creates a powerful new paradigm for architectural generative design that can extract and articulate design intelligence.
in Proceedings of the Genetic and Evolutionary Computation Conference, 2021. BibTex
Procedural Content Generation through Quality-Diversity
Daniele Gravina, Ahmed Khalifa, Antonios Liapis, Julian Togelius and Georgios N. Yannakakis
Cases of PCG through Quality Diversity.
Abstract: Quality-diversity (QD) algorithms search for a set of good solutions which cover a space as defined by behavior metrics. This simultaneous focus on quality and diversity with explicit metrics sets QD algorithms apart from standard single- and multi-objective evolutionary algorithms, as well as from diversity preservation approaches such as niching. These properties open up new avenues for artificial intelligence in games, in particular for procedural content generation. Creating multiple systematically varying solutions allows new approaches to creative human-AI interaction as well as adaptivity. In the last few years, a handful of applications of QD to procedural content generation and game playing have been proposed; we discuss these and propose challenges for future work.
in Proceedings of the IEEE Conference on Games, 2019. BibTex
Blending Notions of Diversity for MAP-Elites
Daniele Gravina, Antonios Liapis and Georgios N. Yannakakis
The fitness and feature space of the final MAP-Elites implementation, when using stochastic selection and when using novelty-surprise search based on path divergence.
Abstract: Quality-diversity algorithms focus on discovering multiple diverse and high-performing solutions. MAP-elites is such an algorithm, as it partitions the solution space into bins and searches for the best solution possible for each bin. In this paper, multi-behavior variants of MAP-Elites are tested where the MAP-Elites grid partitions the solution space based on a certain dimension, while selection is guided by measures of diversity on another dimension. Four divergent search algorithms are tested for this selection process, targeting novelty or surprise or their combination, and their performance on a soft robot evolution task is discussed.
in Proceedings of the Genetic and Evolutionary Computation Conference, 2019. BibTex
Quality Diversity Through Surprise
Daniele Gravina, Antonios Liapis and Georgios N. Yannakakis
The key phases of the surprise search algorithm in the maze navigation domain, based on 10 behavioral clusters of robot controllers evolved in the two previous generations.
Abstract: Quality diversity is a recent family of evolutionary search algorithms which focus on finding several well-performing (quality) yet different (diversity) solutions with the aim to maintain an appropriate balance between divergence and convergence during search. While quality diversity has already delivered promising results in complex problems, the capacity of divergent search variants for quality diversity remains largely unexplored. Inspired by the notion of surprise as an effective driver of divergent search and its orthogonal nature to novelty this paper investigates the impact of the former to quality diversity performance. For that purpose we introduce three new quality diversity algorithms which employ surprise as a diversity measure, either on its own or combined with novelty, and compare their performance against novelty search with local competition, the state of the art quality diversity algorithm. The algorithms are tested in a robot navigation task across 60 highly deceptive mazes. Our findings suggest that allowing surprise and novelty to operate synergistically for divergence and in combination with local competition leads to quality diversity algorithms of significantly higher efficiency, speed and robustness.
in Transactions on Evolutionary Computation, vol. 23, no 4, pp. 603-616, 2019. BibTex
Fusing Novelty and Surprise for Evolving Robot Morphologies
Daniele Gravina, Antonios Liapis and Georgios N. Yannakakis
Robot gaits for different lattice resolutions. All robots have been evolved by the novelty-surprise search algorithm.
Abstract: Traditional evolutionary algorithms tend to converge to a single good solution, which can limit their chance of discovering more diverse and creative outcomes. Divergent search, on the other hand, aims to counter convergence to local optima by avoiding selection pressure towards the objective. Forms of divergent search such as novelty or surprise search have proven to be beneficial for both the efficiency and the variety of the solutions obtained in deceptive tasks. Importantly for this paper, early results in maze navigation have shown that combining novelty and surprise search yields an even more effective search strategy due to their orthogonal nature. Motivated by the largely unexplored potential of coupling novelty and surprise as a search strategy, in this paper we investigate how fusing the two can affect the evolution of soft robot morphologies. We test the capacity of the combined search strategy against objective, novelty, and surprise search, by comparing their efficiency and robustness, and the variety of robots they evolve. Our key results demonstrate that novelty-surprise search is generally more efficient and robust across eight different resolutions. Further, surprise search explores the space of robot morphologies more broadly than any other algorithm examined.
in Proceedings of the Genetic and Evolutionary Computation Conference, 2018. BibTex
Coupling Novelty and Surprise for Evolutionary Divergence
Daniele Gravina, Antonios Liapis and Georgios N. Yannakakis
Heatmap of robots' final positions throughout evolution, in the same maze. Robots are evolved towards novelty (left), surprise (middle) and a weighted sum of novelty and surprise (right).
Abstract: Divergent search techniques applied to evolutionary computation, such as novelty search and surprise search, have demonstrated their efficacy in highly deceptive problems compared to traditional objective-based fitness evolutionary processes. While novelty search rewards unseen solutions, surprise search rewards unexpected solutions. As a result these two algorithms perform a different form of search since an expected solution can be novel while an already seen solution can be surprising. As novelty and surprise search have already shown much promise individually, the hypothesis is that an evolutionary process that rewards both novel and surprising solutions will be able to handle deception in a better fashion and lead to more successful solutions faster. In this paper we introduce an algorithm that realises both novelty and surprise search and we compare it against the two algorithms that compose it in a number of robot navigation tasks. The key findings of this paper suggest that coupling novelty and surprise is advantageous compared to each search approach on its own. The introduced algorithm breaks new ground in divergent search as it outperforms both novelty and surprise in terms of efficiency and robustness, and it explores the behavioural space more extensively.
In Proceedings of the Genetic and Evolutionary Computation Conference, 2017. BibTex
Exploring Divergence in Soft Robot Evolution
Daniele Gravina, Antonios Liapis and Georgios N. Yannakakis
Typical soft robot structures evolved through objective-driven search, novelty search, and surprise search.
Abstract: Divergent search is a recent trend in evolutionary computation that does not reward proximity to the objective of the problem it tries to solve. Traditional evolutionary algorithms tend to converge to a single good solution, using a fitness proportional to the quality of the problem's solution, while divergent algorithms aim to counter convergence by avoiding selection pressure towards the ultimate objective. This paper explores how a recent divergent algorithm, surprise search, can affect the evolution of soft robot morphologies, comparing the performance and the structure of the evolved robots.
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
A 'mine-laying' weapon evolved via constrained surprise search.
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
Searching for Surprise
Georgios N. Yannakakis and Antonios Liapis
Card game example which illustrates the differences between high novelty (top) and high surprise (bottom).
Abstract: Inspired by the notion of surprise for unconventional discovery in computational creativity, we introduce a general search algorithm we name surprise search. Surprise search is grounded in the divergent search paradigm and is fabricated within the principles of metaheuristic (evolutionary) search. The algorithm mimics the self-surprise cognitive process of creativity and equips computational creators with the ability to search for outcomes that deviate from the algorithm's expected behavior. The predictive model of expected outcomes is based on historical trails of where the search has been and some local information about the search space. We showcase the basic steps of the algorithm via a problem solving (maze navigation) and a generative art task. What distinguishes surprise search from other forms of divergent search, such as the search for novelty, is its ability to diverge not from earlier and seen outcomes but rather from predicted and unseen points in the creative domain considered.
in Proceedings of the International Conference on Computational Creativity. 2016. BibTex
Surprise Search: Beyond Objectives and Novelty
Daniele Gravina, Antonios Liapis and Georgios N. Yannakakis
Heatmaps of final robot locations in mazes solved after 25,000 evaluations by novelty search (left) and surprise search (right). Surprise search results in higher maze exploration.
Abstract: Grounded in the divergent search paradigm and inspired by the principle of surprise for unconventional discovery in computational creativity, this paper introduces surprise search as a new method of evolutionary divergent search. Surprise search is tested in two robot navigation tasks and compared against objective-based evolutionary search and novelty search. The key findings of this paper reveal that surprise search is advantageous compared to the other two search processes. It outperforms objective search and it is as efficient as novelty search in both tasks examined. Most importantly, surprise search is, on average, faster and more robust in solving the navigation problem compared to objective and novelty search. Our analysis reveals that surprise search explores the behavioral space more extensively and yields higher population diversity compared to novelty search.
in Proceedings of the Genetic and Evolutionary Computation Conference. ACM, 2016. BibTex
Exploring the Visual Styles of Arcade Game Assets
Antonios Liapis
Spaceship styles in different colors, evolved by several fi-2pop genetic algorithms optimizing different style objectives.
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
Searching for Good and Diverse Game Levels
Mike Preuss, Antonios Liapis and Julian Togelius
Strategy game map sketches evolved via NEA 2 using visual impression for niching (top row), via restart-ES with CMA-ES restart criteria (middle row), and via novelty search based on visual impression distance (bottom row).
Abstract: In procedural content generation, one is often interested in generating a large number of artifacts that are not only of high quality but also diverse, in terms of gameplay, visual impression or some other criterion. We investigate several search-based approaches to creating good and diverse game content, in particular approaches based on evolution strategies with or without diversity preservation mechanisms, novelty search and random search. The content domain is game levels, more precisely map sketches for strategy games, which are meant to be used as suggestions in the Sentient Sketchbook design tool. Several diversity metrics are possible for this type of content: we investigate tile-based, objective-based and visual impression distance. We find that evolution with diversity preservation mechanisms can produce both good and diverse content, but only when using appropriate distance measures. Reversely, we can draw conclusions about the suitability of these distance measures for the domain from the comparison of diversity preserving versus blind restart evolutionary algorithms.
in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG), 2014. BibTex
Constrained Novelty Search: A Study on Game Content Generation
Antonios Liapis, Georgios N. Yannakakis and Julian Togelius
Diagrams of the two-population novelty search algorithm: fiNS (bottom left) and fi2NS (bottom right). These algorithms are inspired by fi-2pop GA (top left) and Novelty Search (top right).
Abstract: Novelty search is a recent algorithm geared towards 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.
Evolutionary Computation 21(1), 2015, pp. 101-129. BibTex
Enhancements to Constrained Novelty Search: Two-Population Novelty Search for Generating Game Content
Antonios Liapis, Georgios N. Yannakakis and Julian Togelius
The exploration of a constrained search space, divided into feasible (F) and infeasible (I) using feasible-infeasible novelty search (left) and feasible-infeasible dual novelty search (right).
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.
in Proceedings of the Genetic and Evolutionary Competition Conference, 2013, pp. 343-350. BibTex
Transforming Exploratory Creativity with DeLeNoX
Antonios Liapis, Hector P. Martinez, Julian Togelius and Georgios N. Yannakakis
Progressive complexification of generated spaceships trained with new features in every iteration.
Abstract: We introduce DeLeNoX (Deep Learning Novelty Explorer), a system that autonomously creates artifacts in constrained spaces according to its own evolving interestingness criterion. DeLeNoX proceeds in alternating phases of exploration and transformation. In the exploration phases, a version of novelty search augmented with constraint handling searches for maximally diverse artifacts using a given distance function. In the transformation phases, a deep learning autoencoder learns to compress the variation between the found artifacts into a lower-dimensional space. The newly trained encoder is then used as the basis for a new distance function, transforming the criteria for the next exploration phase. In the current paper, we apply DeLeNoX to the creation of spaceships suitable for use in two-dimensional arcade-style computer games, a representative problem in procedural content generation in games. We also situate DeLeNoX in relation to the distinction between exploratory and transformational creativity, and in relation to Schmidhuber's theory of creativity through the drive for compression progress.
in Proceedings of the Fourth International Conference on Computational Creativity, 2013, pp. 56-63. BibTex
Sentient Sketchbook: Computer-Aided Game Level Authoring
Antonios Liapis, Georgios N. Yannakakis and Julian Togelius
User interface of Sentient Sketchbook, with the user working on the map sketch canvas (left) and the computer generating suggestions in real-time (far right).
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
Sentient World: Human-Based Procedural Cartography
Antonios Liapis, Georgios N. Yannakakis and Julian Togelius
Different steps of the design process of terrain using Sentient World: the user draws a rough terrain sketch using coarse height brushes (top left), which Sentient World refines and shows possible higher-detail maps to the user (top right). The user can manual edit the refined map and submit it for further refinement (bottom left), while the final output is a map of infinite resolution which can be visualized in many different ways (bottom right).
Abstract: This paper presents a first step towards a mixed-initiative tool for the creation of game maps. The tool, named Sentient World, allows the designer to draw a rough terrain sketch, adding extra levels of detail through stochastic and gradient search. Novelty search generates a number of dissimilar artificial neural networks that are trained to approximate a designer's sketch and provide maps of higher resolution back to the designer. As the procedurally generated maps are presented to the designer (to accept, reject, or edit) the terrain sketches are iteratively refined into complete high resolution maps which may diverge from initial designer concepts. The tool supports designer creativity while conforming to designer intentions, and maintains constant designer control through the map selection and map editing options. Results obtained on a number of test maps show that novelty search is beneficial for introducing divergent content to the designer without reducing the speed of iterative map refinement.
in Proceedings of Evolutionary and Biologically Inspired Music, Sound, Art and Design (EvoMusArt), vol. 7834, LNCS. Springer, 2013, pp. 180-191. BibTex