We are in the midst of large-scale industrial and academic efforts to automate the processes of scientific, technological and creative production through AI-driven assistants. Historically, a fundamental property of these processes in their human form has been their open-endedness: their capacity for generating a seemingly endless supply of novel and meaningful new forms. Do artificial agents have any capacity for such fruitful unguided discovery? To answer this question, we turn to Picbreeder, the canonical exemplar of human-driven open-ended search, in which users collaboratively generated a diverse library of images through interactive evolution of small neural networks. We replicate Picbreeder, replacing human users with frontier Vision Language Models (VLMs). We observe clear qualitative differences between the output of our system and the historical human baseline, and attempt to characterize them using metrics of phylogenetic complexity and visual and semantic salience and novelty. In an effort to identify some of the causal factors contributing these differences, we study the addition of exploratory noise to the agents' selection process, of behavioral diversity between agents, and of narrative momentum in the form of memory of past actions. We make our code available at https://github.com/smearle/picbreeder-vlm.

We present Mortar, a system for autonomously evolving game mechanics for automatic game design. Game mechanics define the rules and interactions that govern gameplay, and designing them manually is a time-consuming and expert-driven process. Mortar combines a quality-diversity algorithm with a large language model to explore a diverse set of mechanics, which are evaluated by synthesising complete games that incorporate both evolved mechanics and those drawn from an archive. The mechanics are evaluated by composing complete games through a tree search procedure, where the resulting games are evaluated by their ability to preserve a skill-based ordering over players—that is, whether stronger players consistently outperform weaker ones. We assess the mechanics based on their contribution towards the skill-based ordering score in the game. We demonstrate that Mortar produces games that appear diverse and playable, and mechanics that contribute more towards the skill-based ordering score in the game. We perform ablation studies to assess the role of each system component and a user study to evaluate the games based on human feedback.

This paper presents a framework called Program Search for Financial Trading (ProFiT), a large-language-model-driven evolutionary algorithm for automated discovery and continual improvement of trading strategies in financial markets. These markets are inherently non-stationary and thus resist static modeling or prediction, suggesting the need for a more open-ended and adaptive evolutionary approach. ProFiT integrates code-level mutation on a complexifying representation, self-analysis, and walk-forward validation within a closed feedback loop, enabling trading strategies to autonomously evolve in response to changing market conditions. ProFiT consistently outperforms both Random and Buy-and-Hold strategies, which are used as both academic and industry-standard baselines, across seven futures assets. Specifically, it outperforms Random in 100% of cases and surpasses Buy-and-Hold in over 77% of all evolved strategy-asset combinations. Collectively, these results demonstrate that the ProFiT framework yields robust, statistically significant, and risk-adjusted gains across diverse types of financial assets and market dynamics, establishing a practical pathway toward open-ended self-improving algorithmic trading systems.

Procedural Content Generation via Machine Learning (PCGML) has enhanced game content creation, yet challenges in controllability and limited training data persist. This study addresses these issues by distilling a constructive PCG algorithm into a controllable PCGML model. We first generate a large amount of content with a constructive algorithm and label it using a Large Language Model (LLM). We use these synthetic labels to condition two PCGML models for content-specific generation, a diffusion model and the five-dollar model. This neural network distillation process ensures that the generation aligns with the original algorithm while introducing controllability through plain text. We define this text-conditioned PCGML as a Text-to-game-Map (T2M) task, offering an alternative to prevalent text-to-image multi-modal tasks. We compare our distilled models with the baseline constructive algorithm. Our analysis of the variety, accuracy, and quality of our generation demonstrates the efficacy of distilling constructive methods into controllable text-conditioned PCGML models.

There is much interest in using large pre-trained models in Automatic Game Design (AGD), whether via the generation of code, assets, or more abstract conceptualization of design ideas. But so far, this interest largely stems from the ad hoc use of such generative models under persistent human supervision. Much work remains to show how these tools can be integrated into longer-time-horizon AGD pipelines, in which systems interface with game engines to test generated content autonomously. To this end, we introduce ScriptDoctor, a Large Language Model (LLM)-driven system for automatically generating and testing games in PuzzleScript, an expressive but highly constrained description language for turn-based puzzle games over 2D gridworlds. ScriptDoctor generates and tests game design ideas in an iterative loop, where human-authored examples are used to ground the system's output, compilation errors from the PuzzleScript engine are used to elicit functional code, and search-based agents play-test generated games. ScriptDoctor serves as a concrete example of the potential of automated, openended LLM-based workflows in generating novel game content.

How can we use generative AI, in particular textguided generation of key game content, be used as a core game mechanic? This paper describes the design, implementation, and and initial playtesting of a game designed around prompt-driven map generation. Our game God's Innovation Project - a god game in the tradition of Populous - allows the player to reshape parts of the game world with a promptable generative model. We further gamify the prompting process, creating a novel resource system where words must harvested via gameplay. We explore how recent advances in the field of Procedural Content Generation via Machine learning enable new types of AI-based game design, and assess the impact of AI on the gameplay experience using a small-scale playtest.

Diffusion models are prone to exactly reproduce images from the training data. This exact reproduction of the training data is concerning as it can lead to copyright infringement and/or leakage of privacy-sensitive information. In this paper, we present a novel perspective on the memorization phenomenon and propose a simple yet effective approach to mitigate it. We argue that memorization occurs because of an attraction basin in the denoising process which steers the diffusion trajectory towards a memorized image. However, this can be mitigated by guiding the diffusion trajectory away from the attraction basin by not applying classifier-free guidance until an ideal transition point occurs from which classifier-free guidance is applied. This leads to the generation of non-memorized images that are high in image quality and well-aligned with the conditioning mechanism. To further improve on this, we present a new guidance technique, opposite guidance, that escapes the attraction basin sooner in the denoising process. We demonstrate the existence of attraction basins in various scenarios in which memorization occurs, and we show that our proposed approach successfully mitigates memorization. Our codebase is publicly available at https://github.com/SonyResearch/mitigating_memorization.

This paper introduces the Procedural Content Generation Benchmark for evaluating generative algorithms on different game content creation tasks.The benchmark comes with 12 game-related problems with multiple variants on each problem.Problems vary from creating levels of different kinds to creating rule sets for simple arcade games.Each problem has its own content representation, control parameters, and evaluation metrics for quality, diversity, and controllability.This benchmark is intended as a first step towards a standardized way of comparing generative algorithms.We use the benchmark to score three baseline algorithms: a random generator, an evolution strategy, and a genetic algorithm.Results show that some problems are easier to solve than others, as well as the impact the chosen objective has on quality, diversity, and controllability of the generated artifacts.

Deep generative models require large amounts of training data. This often poses a problem as the collection of datasets can be expensive and difficult, in particular datasets that are representative of the appropriate underlying distribution (e.g. demographic). This introduces biases in datasets which are further propagated in the models. We present an approach to construct an unbiased generative adversarial network (GAN) from an existing biased GAN by rebalancing the model distribution. We do so by generating balanced data from an existing imbalanced deep generative model using an evolutionary algorithm and then using this data to train a balanced generative model. Additionally, we propose a bias mitigation loss function that minimizes the deviation of the learned class distribution from being equiprobable. We show results for the StyleGAN2 models while training on the Flickr Faces High Quality (FFHQ) dataset for racial fairness and see that the proposed approach improves on the fairness metric by almost 5 times, whilst maintaining image quality. We further validate our approach by applying it to an imbalanced CIFAR10 dataset where we show that we can obtain comparable fairness and image quality as when training on a balanced CIFAR10 dataset which is also twice as large. Lastly, we argue that the traditionally used image quality metrics such as Frechet inception distance (FID) are unsuitable for scenarios where the class distributions are imbalanced and a balanced reference set is not available.

Artificial intelligence (AI) has enabled agents to master complex video games, from first-person shooters likeCounter-Striketo real-time strategy games such asStarCraft IIand racing games likeGran Turismo. While these achievements are notable, applying these AI methods in commercial video game production remains challenging due to computational constraints. In commercial scenarios, the majority of computational resources are allocated to 3D rendering, leaving limited capacity for AI methods, which often demand high computational power, particularly those relying on pixel-based sensors. Moreover, the gaming industry prioritizes creating human-like behavior in AI agents to enhance player experience, unlike academic models that focus on maximizing game performance. This paper introduces a novel methodology for training neural networks via imitation learning to play a complex, commercial-standard, VALORANT-like 2v2 tactical shooter game, requiring only modest CPU hardware during inference. Our approach leverages an innovative, pixel-free perception architecture using a small set of ray-cast sensors, which capture essential spatial information efficiently. These sensors allow AI to perform competently without the computational overhead of traditional methods. Models are trained to mimic human behavior using supervised learning on human trajectory data, resulting in realistic and engaging AI agents. Human evaluation tests confirm that our AI agents provide human-like gameplay experiences while operating efficiently under computational constraints. This offers a significant advancement in AI model development for tactical shooter games and possibly other genres.

We introduce the Amorphous Fortress-an abstract, open-ended artificial life simulation framework. In this system, entities are represented as finite-state machines (FSMs) which allow for multi-agent interaction within a constrained space. These agents are created by randomly generating and evolving the FSMs; sampling from pre-defined states and transitions. This environment was designed to explore the emergent AI behaviors found implicitly in simulation games such as Dwarf Fortress or The Sims. We apply two evolutionary algorithms to this environment, hill-climber and MAP-Elites, to explore the various levels of depth and interaction from the generated FSMs and to generate diverse sets of environments that exhibit dynamics estimated to be complex by analyses of agents' FSM architecture and activation. This paper combines the work of two previous non-archival workshop papers.

Procedural Content Generation via Reinforcement Learning (PCGRL) has been introduced as a means by which controllable designer agents can be trained based only on a set of computable metrics acting as a proxy for the level’s quality and key characteristics. While PCGRL offers a unique set of affordances for game designers, it is constrained by the compute-intensive process of training RL agents, and has so far been limited to generating relatively small levels. To address this issue of scale, we implement several PCGRL environments in Jax so that all aspects of learning and simulation happen in parallel on the GPU, resulting in faster environment simulation; removing the CPU-GPU transfer of information bottleneck during RL training; and ultimately resulting in significantly improved training speed. We replicate several key results from prior works in this new framework, letting models train for much longer than previously studied, and evaluating their behavior after 1 billion timesteps. Aiming for greater control for human designers, we introduce randomized level sizes and frozen “pinpoints” of pivotal game tiles as further ways of countering overfitting. To test the generalization ability of learned generators, we evaluate models on large, out-of-distribution map sizes, and find that partial observation sizes learn more robust design strategies.

This paper presents the second ChatGPT4PCG competition at the 2024 IEEE Conference on Games. In this edition of the competition, we follow the first edition, but make several improvements and changes. We introduce a new evaluation metric along with allowing a more flexible format for participants’ submissions and making several improvements to the evaluation pipeline. Continuing from the first edition, we aim to foster and explore the realm of prompt engineering (PE) for procedural content generation (PCG). While the first competition saw success, it was hindered by various limitations; we aim to mitigate these limitations in this edition. We introduce diversity as a new metric to discourage submissions aimed at producing repetitive structures. Furthermore, we allow submission of a Python program instead of a prompt text file for greater flexibility in implementing advanced PE approaches, which may require control flow, including conditions and iterations. We also make several improvements to the evaluation pipeline with a better classifier for similarity evaluation and better-performing function signatures. We thoroughly evaluate the effectiveness of the new metric and the improved classifier. Additionally, we perform an ablation study to select a function signature to instruct ChatGPT for level generation. Finally, we provide implementation examples of various PE techniques in Python and evaluate their preliminary performance. We hope this competition serves as a resource and platform for learning about PE and PCG in general1.1Source code and raw data: https://github.com/chatgpt4pcg/experiments2024

The Connections puzzle published each day by the New York Times tasks players with dividing a bank of sixteen words into four groups of four words that each relate to a common theme. Solving the puzzle requires both common linguistic knowledge (i.e. definitions and typical usage) as well as, in many cases, lateral or abstract thinking. This is because the four categories ascend in complexity, with the most challenging category often requiring thinking about words in uncommon ways or as parts of larger phrases. We investigate the capacity for automated AI systems to play Connections and explore the game’s potential as an automated benchmark for abstract reasoning and a way to measure the semantic information encoded by data-driven linguistic systems. In particular, we study both a sentence-embedding baseline and modern large language models (LLMs). We report their accuracy on the task, measure the impacts of chain-of-thought prompting, and discuss their failure modes. Overall, we find that the Connections task is challenging yet feasible, and a strong test-bed for future work.

This paper studies how large language models (LLMs) can act as effective, high-level creative collaborators and “muses” for game design. We model the design of this study after the exercises artists use by looking at amorphous ink splotches for creative inspiration. Our goal is to determine whether AI-assistance can improve, hinder, or provide an alternative quality to games when compared to the creative intents implemented by human designers. The capabilities of LLMs as game designers are stress tested by placing it at the forefront of the decision making process. Three prototype games are designed across 3 different genres: (1) a minimalist base game, (2) a game with features and game feel elements added by a human game designer, and (3) a game with features and feel elements directly implemented from prompted outputs of the LLM, ChatGPT. A user study was conducted and participants were asked to blindly evaluate the quality and their preference of these games. We discuss both the development process of communicating creative intent to an AI chatbot and the synthesized open feedback of the participants. We use this data to determine both the benefits and shortcomings of AI in a more design-centric role.

Procedural Content Generation (PCG) algorithms enable the automatic generation of complex and diverse artifacts. However, they don’t provide high-level control over the generated content and typically require domain expertise. In contrast, text-to-3D methods allow users to specify desired characteristics in natural language, offering a high amount of flexibility and expressivity. But unlike PCG, such approaches cannot guarantee functionality, which is crucial for certain applications like game design. In this paper, we present a method for generating functional 3D artifacts from free-form text prompts in the open-world game Minecraft. Our method, DreamCraft, trains quantized Neural Radiance Fields (NeRFs) to represent artifacts that, when viewed in-game, match given text descriptions. We find that DreamCraft produces more aligned in-game artifacts than a baseline that post-processes the output of an unconstrained NeRF. Thanks to the quantized representation of the environment, functional constraints can be integrated using specialized loss terms. We show how this can be leveraged to generate 3D structures that match a target distribution or obey certain adjacency rules over the block types. DreamCraft inherits a high degree of expressivity and controllability from the NeRF, while still being able to incorporate functional constraints through domain-specific objectives.

Large language models (LLMs) have emerged as powerful tools capable of accomplishing a broad spectrum of tasks. Their abilities span numerous areas, and one area where they have made a significant impact is in the domain of code generation. Here, we propose using the coding abilities of LLMs to introduce meaningful variations to code defining neural networks. Meanwhile, Quality-Diversity (QD) algorithms are known to discover diverse and robust solutions. By merging the code-generating abilities of LLMs with the diversity and robustness of QD solutions, we introduce LLMatic, a Neural Architecture Search (NAS) algorithm. While LLMs struggle to conduct NAS directly through prompts, LLMatic uses a procedural approach, leveraging QD for prompts and network architecture to create diverse and high-performing networks. We test LLMatic on the CIFAR-10 and NAS-bench-201 benchmarks, demonstrating that it can produce competitive networks while evaluating just 2, 000 candidates, even without prior knowledge of the benchmark domain or exposure to any previous top-performing models for the benchmark. The open-sourced code is available at https://github.com/umair-nasir14/LLMatic.

Large language models (LLMs) have recently demonstrated great success in generating and understanding natural language. While they have also shown potential beyond the domain of natural language, it remains an open question as to what extent and in which way these LLMs can plan. We investigate their planning capabilities by proposing \texttt{GameTraversalBenchmark (GTB)}, a benchmark consisting of diverse 2D grid-based game maps. An LLM succeeds if it can traverse through given objectives, with a minimum number of steps and a minimum number of generation errors. We evaluate a number of LLMs on \texttt{GTB} and found that GPT-4-Turbo achieved the highest score of $44.97\%$ on \texttt{GTB\_Score} (GTBS), a composite score that combines the three above criteria. Furthermore, we preliminarily test large reasoning models, namely o1, which scores $67.84\%$ on GTBS, indicating that the benchmark remains challenging for current models. Code, data, and documentation are available at \url{https://github.com/umair-nasir14/Game-Traversal-Benchmark}.

Automatically generating novel and interesting games is a complex task. Challenges include representing game rules in a computationally workable form, searching through the large space of potential games under most such representations, and accurately evaluating the originality and quality of previously unseen games. Prior work in automated game generation has largely focused on relatively restricted rule representations and relied on domain-specific heuristics. In this work, we explore the generation of novel games in the comparatively expansive Ludii game description language, which encodes the rules of over 1000 board games in a variety of styles and modes of play. We draw inspiration from recent advances in large language models and evolutionary computation in order to train a model that intelligently mutates and recombines games and mechanics expressed as code. We demonstrate both quantitatively and qualitatively that our approach is capable of generating new and interesting games, including in regions of the potential rules space not covered by existing games in the Ludii dataset.

As someone who does artificial intelligence (AI) research in a university, you develop a complicated relationship with the corporate AI research powerhouses, such as Google DeepMind, OpenAI, and Meta AI. Whenever you see one of these papers that train some kind of gigantic neural net model to do something you were not even sure a neural network could do, unquestionably pushing the state-of-the-art and reconfiguring your ideas of what is possible, you get conflicting emotions. On the one hand, it is very impressive. Good on you for pushing AI forward. On the other hand, how could we possibly keep up? As an AI academic, leading a laboratory with a few Ph.D. students and (if you are lucky) some postdoctoral fellows, perhaps with a few dozen graphics processing units (GPUs) in your laboratory, this kind of research is simply not possible to do.

Video games are one of the richest and most popular forms of human-computer interaction and, hence, their role is critical for our understanding of human behaviour and affect at a large scale. As artificial intelligence (AI) tools are gradually adopted by the game industry a series of ethical concerns arise. Such concerns, however, have so far not been extensively discussed in a video game context. Motivated by the lack of a comprehensive review on the ethics of AI as applied to games, we survey the current state of the art in this area and discuss ethical considerations of these systems from the holistic perspective of theaffective loop. Through the components of this loop, we study the ethical challenges that AI faces in video game development.Elicitationhighlights the ethical boundaries of artificially induced emotions;sensingshowcases the trade-off between privacy and safe gaming spaces; anddetection, as utilised during in-gameadaptation, poses challenges to transparency and ownership. This paper calls for an open dialogue and action for the games of today and the virtual spaces of the future. By setting an appropriate framework we aim to protect users and to guide developers towards safer and better experiences for their customers.

This study summarizes the first ChatGPT4PCG competition held at the 2023 IEEE Conference on Games. The goal of the competition is to explore emergent abilities of publicly available LLMs in performing complex tasks related to procedural content generation, specifically physics-based level generation for Angry Bird-like games. Participants are tasked with submitting their prompts for ChatGPT to generate Angry Birds-like game structures that resemble English uppercase characters. A structure is a collection of stacked game objects comprising a part of an entire Angry Birds-like level. A prompt is an input for large language models (LLMs) including ChatGPT. Two evaluation metrics, i.e., stability and similarity, are used to evaluate the submitted prompts. Stability measures the sturdiness of a structure to withstand in-game gravity, while similarity measures a structure's resemblance to the target character. With such evaluation, participants are challenged not only to produce character-like but also stable structures by utilizing prompt engineering techniques. Finally, the competition's results are discussed to provide valuable insights for future studies and competitions.

This article describes a new version of the mixed-initiative collaborative level-designing system, i.e.,Baba Is Y'all, as well as the results of a user study on the system.Baba is Y'allis a prototype for artificial intelligence (AI)-assisted game design in collaboration with others. The updated version includes a more user-friendly interface, a better level evolver and recommendation system, and extended site features. The system was evaluated via a user study where participants were required to play a previously submitted level from the site, and then create their own levels using the editor. They reported on their individual process creating the level and their overall experience interacting with the site. The results have shown both the benefits and limitations of this mixed-initiative system and how it can help with creating a diversity ofBaba is Youlevels that are both human and AI designed while maintaining their quality.

The Wave Function Collapse (WFC) algorithm is a widely used tile-based algorithm in procedural content generation, including textures, objects, and scenes. However, the current WFC algorithm and related optimized algorithms based on it lack the ability to generate commercial-scale or infinite content due to constraint conflicts and high time complexity. This paper proposes the Nested WFC (N-WFC) algorithm framework to reduce time complexity. To avoid conflict and backtracking problems, we offer a complete and sub-complete tileset preparation strategy, which requires only a small number of tiles to generate infinite, aperiodic, and deterministic content. We use Mario and Carcassonne as two game examples to describe their application and discuss potential research value. Our contribution addresses WFC's challenge in massive content generation and provides a theoretical basis for implementing concrete games.

Procedurally generating cities in Minecraft provides players more diverse scenarios and could help understand and improve the design of cities in other digital worlds and the real world. This paper presents a city generator that was submitted as an entry to the 2023 Edition of Minecraft Settlement Generation Competition for Minecraft. The generation procedure is composed of six main steps, namely vegetation clearing, terrain reshaping, building layout generation, route planning, streetlight placement, and wall construction. Three algorithms, including a heuristic-based algorithm, an evolving layout algorithm, and a random one are applied to generate the building layout, thus determining where to place different redstone style buildings, and tested by generating cities on random maps in limited time. Experimental results show that the heuristic-based algorithm is capable of finding an acceptable building layout faster for flat maps, while the evolving layout algorithm performs better in evolving layout for rugged maps. A user study is conducted to compare our generator with outstanding entries of the competition’s 2022 edition using the competition’s evaluation criteria and shows that our generator performs well in the adaptation and functionality criteria.

Large Language Models (LLMs) have proven to be useful tools in various domains outside of the field of their inception, which was natural language processing. In this study, we provide practical directions on how to use LLMs to generate 2D-game rooms for an under-development game, named Metavoidal. Our technique can harness the power of GPT-3 by Human-in-the-loop fine-tuning which allows our method to create 37% Playable-Novel levels from as scarce data as only 60 hand-designed rooms under a scenario of the non-trivial game, with respect to (Procedural Content Generation) PCG, that has a good amount of local and global constraints.

Path of Destruction (PoD) is a self-supervised method for learning iterative generators. The core idea is to produce a training set by destroying a set of artifacts, and for each destructive step create a training instance based on the corresponding repair action. A generator trained on this dataset can then generate new artifacts by "repairing" from arbitrary states. The PoD method is very data-efficient in terms of original training examples and well-suited to functional artifacts composed of categorical data, such as game levels and discrete 3D structures. In this paper, we extend the Path of Destruction method to allow designer control over aspects of the generated artifacts. Controllability is introduced by adding conditional inputs to the state-action pairs that make up the repair trajectories. We test the controllable PoD method in a 2D dungeon setting, as well as in the domain of small 3D Lego cars.

This paper presents the first ChatGPT4PCG Competition at the 2023 IEEE Conference on Games. The objective of this competition is for participants to create effective prompts for ChatGPT–enabling it to generate Science Birds levels with high stability and character-like qualities–fully using their creativity as well as prompt engineering skills. ChatGPT is a conversational agent developed by OpenAI. Science Birds is selected as the competition platform because designing an Angry Birds-like level is not a trivial task due to the in-game gravity; the quality of the levels is determined by their stability. To lower the entry barrier to the competition, we limit the task to the generation of capitalized English alphabetical characters. We also allow only a single prompt to be used for generating all the characters. Here, the quality of the generated levels is determined by their stability and similarity to the given characters. A sample prompt is provided to participants for their reference. An experiment is conducted to determine the effectiveness of several modified versions of this sample prompt on level stability and similarity by testing them on several characters. To the best of our knowledge, we believe that ChatGPT4PCG is the first competition of its kind and hope to inspire enthusiasm for prompt engineering in procedural content generation.

We explore AI-powered upscaling as a design assistance tool in the context of creating 2D game levels. Deep neural networks are used to upscale artificially downscaled patches of levels from the puzzle platformer game Lode Runner. The trained networks are incorporated into a web-based editor, where the user can create and edit levels at three different levels of resolution: 4x4, 8x8, and 16x16. An edit at any resolution instantly transfers to the other resolutions. As upscaling requires inventing features that might not be present at lower resolutions, we train neural networks to reproduce these features. We introduce a neural network architecture that is capable of not only learning upscaling but also giving higher priority to less frequent tiles. To investigate the potential of this tool and guide further development, we conduct a qualitative study with 3 designers to understand how they use it. Designers enjoyed co-designing with the tool, liked its underlying concept, and provided feedback for further improvement.

The open-world sandbox game Minecraft is well-known for applying a wide array of procedural content generation techniques to create unique and expansive game environments. However, procedurally generated buildings are absent in the Minecraft world, thus players must build their own structures to flesh out their worlds. This build process can be extremely time-consuming and appeals to more creatively-inclined players. To aid players in this process, we introduce a tool combining interactive evolution with latent variable evolution to evolve procedurally generated Minecraft structures to a player’s aesthetic choices. We employ two separate neural network models to generate structures: a 3D generative model for generating the structure design and an encoding model for applying Minecraft textures to the structure’s voxels. We evaluate this tool with a user study incorporating an online interface that allows participants to select, evolve, and guide a population of these generated 3D structures towards a specific design goal.

Large Language Models (LLMs) are powerful tools, capable of leveraging their training on natural language to write stories, generate code, and answer questions. But can they generate functional video game levels? Game levels, with their complex functional constraints and spatial relationships in more than one dimension, are very different from the kinds of data an LLM typically sees during training. Datasets of game levels are also hard to come by, potentially taxing the abilities of these data-hungry models. We investigate the use of LLMs to generate levels for the game Sokoban, finding that LLMs are indeed capable of doing so, and that their performance scales dramatically with dataset size. We also perform preliminary experiments on controlling LLM level generators and discuss promising areas for future work.

Facial recognition systems have made significant strides thanks to data-heavy deep learning models, but these models rely on large privacy-sensitive datasets. Further, many of these datasets lack diversity in terms of ethnicity and demographics, which can lead to biased models that can have serious societal and security implications. To address these issues, we propose a methodology that leverages the biased generative model StyleGAN2 to create demographically diverse images of synthetic individuals. The synthetic dataset is created using a novel evolutionary search algorithm that targets specific demographic groups. By training face recognition models with the resulting balanced dataset containing 50,000 identities per race (13.5 million images in total), we can improve their performance and minimize biases that might have been present in a model trained on a real dataset.

Hanabiis a cooperative game that brings the problem of modeling other players to the forefront. In this game, coordinated groups of players can leverage preestablished conventions to great effect. In this article, we focus onad hocsettings with no previous coordination between partners. We introduce a “Bayesian Meta-Agent” that maintains a belief distribution over hypotheses of partner policies. The policies that serve as initial hypotheses are generated using MAP-Elites, to ensure behavioral diversity. We evaluate an “Adaptive” version of the agent, which selects a response policy based on the updated belief distribution and a “Generalist” version, which selects a response based on the uniform prior. In short episodes of ten games with a consistent partner, the “Adaptive” version outperforms the “Generalist” when the training and evaluation populations are the same. This presents a first step toward an agent that can model its partner and adapt within a time frame that is compatible with human interaction.

POET-Inspired Neuroevolutionary System for KreativitY (PINSKY) is a system for open-ended learning through neuroevolution in game-based domains. It builds on the Paired Open-Ended Trailblazer (POET) system, which originally explored learning and environment generation for bipedal walkers, and adapts it to games in the General Video Game AI (GVGAI) system. Previous work showed that by coevolving levels and neural network policies, levels could be found for which successful policies could not be created via optimization alone. Studied in the realm of artificial life as a potentially open-ended alternative to gradient-based fitness, minimal criteria (MC)-based selection helps foster diversity in evolutionary populations. The main question addressed by this article is how the open-ended learning actually works, focusing in particular on the role of transfer of policies from one evolutionary branch (“species”) to another. We analyze the dynamics of the system through creating phylogenetic trees, analyzing evolutionary trajectories of policies, and temporally breaking down transfers according to species type. Furthermore, we analyze the impact of the minimal criterion on generated level diversity and interspecies transfer. The most insightful finding is that interspecies transfer, while rare, is crucial to the system's success.

Reinforcement learning algorithms have performed well in playing challenging board and video games. More and more studies focus on improving the generalisation ability of reinforcement learning algorithms. The GVGAI Learning Competition aims to develop agents capable of learning to play different game levels that were unseen during training. This paper summarises the five years' GVGAI Learning Competition editions. At each edition, three new games were designed. The training and test levels were designed separately in the first three editions. Since 2020, three test levels of each game were generated by perturbing or combining two training levels. Then, we present a novel reinforcement learning technique with dual-observation for general video game playing, assuming that it is more likely to observe similar local information in different levels rather than global information. Instead of directly inputting a single, raw pixel-based screenshot of the current game screen, our proposed general technique takes the encoded, transformed global and local observations of the game screen as two simultaneous inputs, aiming at learning local information for playing new levels. Our proposed technique is implemented with three state-of-the-art reinforcement learning algorithms and tested on the game set of the 2020 GVGAI Learning Competition. Ablation studies show the outstanding performance of using encoded, transformed dual observations as input.

Counterfactual regret minimization (CFR) has achieved many fascinating results in solving large-scale imperfect information games (IIGs). Neural network approximation CFR (neural CFR) is one of the promising techniques that can reduce computation and memory consumption by generalizing decision information between similar states. Current neural CFR algorithms have to approximate cumulative regrets. However, efficient and accurate approximation in a large-scale IIG is still a tough challenge. In this article, a new CFR variant, recursive CFR (ReCFR), is proposed. In ReCFR, recursive substitute values (RSVs) are learned and used to replace cumulative regrets. It is proven that ReCFR can converge to a Nash equilibrium at a rate of$O({1}/{\sqrt{T}})$. Based on ReCFR, a new model-free neural CFR with bootstrap learning, neural ReCFR-B, is proposed. Due to the recursive and noncumulative nature of RSVs, neural ReCFR-B has lower variance training targets than other neural CFRs. Experimental results show that neural ReCFR-B is competitive with the state-of-the-art neural CFR algorithms at a much lower training cost.

We investigate how to efficiently predict play personas based on playtraces. Play personas can be computed by calculating the action agreement ratio between a player and a generative model of playing behavior, a so-called procedural persona. But this is computationally expensive and assumes that appropriate procedural personas are readily available. We present two methods for estimating play personas, one using regular supervised learning and aggregate measures of game mechanics initiated, and another based on sequence learning on a trace of closely cropped gameplay observations. While both of these methods achieve high accuracy when predicting play personas defined by agreement with procedural personas, they utterly fail to predict play style as defined by the players themselves using a questionnaire. This interesting result highlights the value of using computational methods in defining play personas.

The Keke AI Competition introduces an artificial agent competition for the game Baba is You - a Sokoban-like puzzle game where players can create rules that influence the mechanics of the game. Altering a rule can cause temporary or permanent effects for the rest of the level that could be part of the solution space. The nature of these dynamic rules and the deterministic aspect of the game creates a challenge for AI to adapt to a variety of mechanic combinations in order to solve a level. This paper describes the framework and evaluation metrics used to rank submitted agents and baseline results from sample tree search agents.

Narratives are a predominant part of games, and their design poses challenges when identifying, encoding, interpreting, evaluating, and generating them. One way to address this would be to approach narrative design in a more abstract layer, such as narrative structures. This paper presents Story Designer, a mixed-initiative co-creative narrative structure tool built on top of the Evolutionary Dungeon Designer (EDD) that uses tropes, narrative conventions found across many media types, to design these structures. Story Designer uses tropes as building blocks for narrative designers to compose complete narrative structures by interconnecting them in graph structures called narrative graphs. Our mixed-initiative approach lets designers manually create their narrative graphs and feeds an underlying evolutionary algorithm with those, creating quality-diverse suggestions using MAP-Elites. Suggestions are visually represented for designers to compare and evaluate and can then be incorporated into the design for further manual editions. At the same time, we use the levels designed within EDD as constraints for the narrative structure, intertwining both level design and narrative. We evaluate the impact of these constraints and the system’s adaptability and expressiveness, resulting in a potential tool to create narrative structures combining level design aspects with narrative.

In this paper, we present a method for automated persona-driven video game tutorial level generation. Tutorial levels are scenarios in which the player can explore and discover different rules and game mechanics. Procedural personas can guide generators to create content which encourages or discourages certain playstyle behaviors. In this system, we use procedural personas to calculate the behavioral characteristics of levels which are evolved using the quality-diversity algorithm known as Constrained MAP-Elites. An evolved map’s quality is determined by its simplicity: the simpler it is, the better it is. Within this work, we show that the generated maps can strongly encourage or discourage different persona-like behaviors and range from simple solutions to complex puzzle-levels, making them perfect candidates for a tutorial generative system.

Procedural Content Generation via Reinforcement Learning (PCGRL) foregoes the need for large human-authored data-sets and allows agents to train explicitly on functional constraints, using computable, user-defined measures of quality instead of target output. We explore the application of PCGRL to 3D domains, in which content-generation tasks naturally have greater complexity and potential pertinence to real-world applications. Here, we introduce several PCGRL tasks for the 3D domain, Minecraft. These tasks will challenge RL-based generators using affordances often found in 3D environments, such as jumping, multiple dimensional movement, and gravity. We train agents to optimize each of these tasks to explore the capabilities of existing in PCGRL. The agents are able to generate relatively complex and diverse levels, and generalize to random initial states and control targets. Controllability tests in the presented tasks demonstrate their utility to analyze success and failure for 3D generators. We argue that these generators could serve both as co-creative tools for game designers, and as pre-trained environment generators in curriculum learning for player agents.

Search-based procedural content generation (PCG) is a well-known method for level generation in games. Its key advantage is that it is generic and able to satisfy functional constraints. However, due to the heavy computational costs to run these algorithms online, search-based PCG is rarely utilized for real-time generation. In this paper, we introduce mutation models, a new type of iterative level generator based on machine learning. We train a model to imitate the evolutionary process and use the trained model to generate levels. This trained model is able to modify noisy levels sequentially to create better levels without the need for a fitness function during inference. We evaluate our trained models on a 2D maze generation task. We compare several different versions of the method: training the models either at the end of evolution (normal evolution) or every 100 generations (assisted evolution) and using the model as a mutation function during evolution. Using the assisted evolution process, the final trained models are able to generate mazes with a success rate of and high diversity of . The trained model is many times faster than the evolutionary process it was trained on. This work opens the door to a new way of learning level generators guided by an evolutionary process, meaning automatic creation of generators with specifiable constraints and objectives that are fast enough for runtime deployment in games.

The GDMC AI settlement generation challenge is a procedural content generation (PCG) competition about producing an algorithm that can create a settlement in the game Minecraft. In contrast to the majority of AI competitions, the GDMC entries are evaluated by human experts on several criteria such as adaptability, functionality, evocative narrative, and visual aesthetics – all of which represent challenges to state-of-the-art PCG systems. This paper contains a collection of written experiences with this competition, by participants, judges, organizers and advisors. We asked people to reflect both on the artifacts themselves, and on the competition in general. The aim of this paper is to offer a shareable and edited collection of experiences and qualitative feedback which have the potential to push forward PCG and computational creativity, but would be lost once the individual assessments are compressed to scalar ratings. We reflect upon organizational issues for AI competitions, and discuss the future of the GDMC competition.

We present a method of generating diverse collections of neural cellular automata (NCA) to design video game levels. While NCAs have so far only been trained via supervised learning, we present a quality diversity (QD) approach to generating a collection of NCA level generators. By framing the problem as a QD problem, our approach can train diverse level generators, whose output levels vary based on aesthetic or functional criteria. To efficiently generate NCAs, we train generators via Covariance Matrix Adaptation MAP-Elites (CMA-ME), a quality diversity algorithm which specializes in continuous search spaces. We apply our new method to generate level generators for several 2D tile-based games: a maze game, Sokoban, and Zelda. Our results show that CMA-ME can generate small NCAs that are diverse yet capable, often satisfying complex solvability criteria for deterministic agents. We compare against a Compositional Pattern-Producing Network (CPPN) baseline trained to produce diverse collections of generators and show that the NCA representation yields a better exploration of level-space.

Consider the problem of training robustly capable agents. One approach is to generate a diverse collection of agent polices. Training can then be viewed as a quality diversity (QD) optimization problem, where we search for a collection of performant policies that are diverse with respect to quantified behavior. Recent work shows that differentiable quality diversity (DQD) algorithms greatly accelerate QD optimization when exact gradients are available. However, agent policies typically assume that the environment is not differentiable. To apply DQD algorithms to training agent policies, we must approximate gradients for performance and behavior. We propose two variants of the current state-of-the-art DQD algorithm that compute gradients via approximation methods common in reinforcement learning (RL). We evaluate our approach on four simulated locomotion tasks. One variant achieves results comparable to the current state-of-the-art in combining QD and RL, while the other performs comparably in two locomotion tasks. These results provide insight into the limitations of current DQD algorithms in domains where gradients must be approximated. Source code is available at https://github.com/icaros-usc/dqd-rl

Face swapping technology used to create “Deepfakes” has advanced significantly over the past few years and now enables us to create realistic facial manipulations. Current deep learning algorithms to detect deepfakes have shown promising results, however, they require large amounts of training data, and as we show they are biased towards a particular ethnicity. We propose a deepfake detection methodology that eliminates the need for any real data by making use of synthetically generated data using Style-GAN3. This not only performs at par with the traditional training methodology of using real data but it shows better generalization capabilities when finetuned with a small amount of real data. Furthermore, this also reduces biases created by facial image datasets that might have sparse data from particular ethnicities. To promote reproducibility the code base has been made publicly available11https://github.com/anubhav1997/youneednodataset

In this article, we propose the interactive constrained multidimensional archive of phenotypic elites (MAP-Elites), a quality-diversity solution for game content generation, implemented as a new feature of the evolutionary dungeon designer (EDD): a mixed-initiative co-creativity tool for designing dungeons. The feature uses the MAP-Elites algorithm, an illumination algorithm that segregates the population among several cells depending on their scores with respect to different behavioral dimensions. Users can flexibly and dynamically alternate between these dimensions anytime, thus guiding the evolutionary process in an intuitive way, and then incorporate suggestions produced by the algorithm in their room designs. At the same time, any modifications performed by the human user will feed back into MAP-Elites, closing a circular workflow of constant mutual inspiration. This article presents the algorithm followed by an in-depth evaluation of the expressive range of all possible dimension combinations in several scenarios and discusses their influence in the fitness landscape and in the overall performance of the procedural content generation in the EDD.

We propose modeling designer style in mixed-initiative game content creation tools as archetypical design traces. These design traces are formulated as transitions between design styles; these design styles are in turn found through clustering all intermediate designs along the way to making a complete design. This method is implemented in the Evolutionary Dungeon Designer, a research platform for mixed-initiative systems to create adventure and dungeon crawler games. We present results both in the form of design styles for rooms, which can be analyzed to better understand the kind of rooms designed by users, and in the form of archetypical sequences between these rooms, i.e., designer personas.

Generative adversarial networks (GANs) are quickly becoming a ubiquitous approach to procedurally generating video game levels. While GAN generated levels are stylistically similar to human-authored examples, human designers often want to explore the generative design space of GANs to extract interesting levels. However, human designers find latent vectors opaque and would rather explore along dimensions the designer specifies, such as number of enemies or obstacles. We propose using state-of-the-art quality diversity algorithms designed to optimize continuous spaces, i.e. MAP-Elites with a directional variation operator and Covariance Matrix Adaptation MAP-Elites, to efficiently explore the latent space of a GAN to extract levels that vary across a set of specified gameplay measures. In the benchmark domain of Super Mario Bros, we demonstrate how designers may specify gameplay measures to our system and extract high-quality (playable) levels with a diverse range of level mechanics, while still maintaining stylistic similarity to human authored examples. An online user study shows how the different mechanics of the automatically generated levels affect subjective ratings of their perceived difficulty and appearance.

We present Lode Encoder, a gamified mixed-initiative level creation system for the classic platform-puzzle game Lode Runner. The system is built around several autoen-coders which are trained on sets of Lode Runner levels. When fed with the user's design, each autoencoder produces a version of that design which is closer in style to the levels that it was trained on. The Lode Encoder interface allows the user to build and edit levels through “painting” from the suggestions provided by the autoencoders. Crucially, in order to encourage designers to explore new possibilities, the system does not include more traditional editing tools. We report on the system design and training procedure, as well as on the evolution of the system itself and user tests.

Machine learning for procedural content generation has recently become an active area of research. Levels vary in both form and function and are mostly unrelated to each other across games. This has made it difficult to assemble suitably large datasets to bring machine learning to level design in the same way as it's been used for image generation. Here we propose Generative Playing Networks which design levels for itself to play. The algorithm is built in two parts; an agent that learns to play game levels, and a generator that learns the distribution of playable levels. As the agent learns and improves its ability, the space of playable levels, as defined by the agent, grows. The generator targets the agents playability estimates to then update its understanding of what constitutes a playable level. We call this process of learning the distribution of data found through self-discovery with an environment, self-supervised inductive learning. Unlike previous approaches to procedural content generation, Generative Playing Networks are end-to-end differentiable and does not require human-designed examples or domain knowledge. We demonstrate the capability of this framework by training an agent and level generator for a 2D dungeon crawler game.

It has recently been shown that reinforcement learning can be used to train generators capable of producing high-quality game levels, with quality defined in terms of some user-specified heuristic. To ensure that these generators' output is sufficiently diverse (that is, not amounting to the reproduction of a single optimal level configuration), the generation process is constrained such that the initial seed results in some variance in the generator's output. However, this results in a loss of control over the generated content for the human user. We propose to train generators capable of producing controllably diverse output, by making them “goal-aware.” To this end, we add conditional inputs representing how close a generator is to some heuristic, and also modify the reward mechanism to incorporate that value. Testing on multiple domains, we show that the resulting level generators are capable of exploring the space of possible levels in a targeted, controllable manner, producing levels of comparable quality as their goal-unaware counterparts, that are diverse along designer-specified dimensions.

Understanding and engineering open-endedness, or the indefinite generation of novelty and complexity at arbitrary scales, has long been studied by implementing nature-inspired simulations specifically designed for artificial life studies. This paper argues that video games serve as a complementary domain for research on open-endedness. In support of this claim, experiments in this paper evaluate the effects of age-based and spatial destructive events in two game domains: an interactive Game of Life and the city-building game SimCity. These games are played by a neural-network-controlled gameplay agent trying to maximize reward. Results indicate that experiments with SimCity are more likely to identify statistically significant differences in complexity as a result of applied destructive events, highlighting the utility of this game domain for studying artificial life phenomena.

We present a new concept called Game Mechanic Alignment theory as a way to organize game mechanics through the lens of systemic rewards and agential motivations. By disentangling player and systemic influences, mechanics may be better identified for use in an automated tutorial generation system, which could tailor tutorials for a particular playstyle or player. Within, we apply this theory to several well-known games to demonstrate how designers can benefit from it, we describe a methodology for how to estimate “mechanic alignment”, and we apply this methodology on multiple games in the GVGAI framework. We discuss how effectively this estimation captures agential motivations and systemic rewards and how our theory could be used as an alternative way to find mechanics for tutorial generation.

Differential MAP-Elites is a novel algorithm that combines the illumination capacity of CVT-MAP-Elites with the continuous-space optimization capacity of Differential Evolution. The algorithm is motivated by observations that illumination algorithms, and quality-diversity algorithms in general, offer qualitatively new capabilities and applications for evolutionary computation yet are in their original versions relatively unsophisticated optimizers. The basic Differential MAP-Elites algorithm, introduced for the first time here, is relatively simple in that it simply combines the operators from Differential Evolution with the map structure of CVT-MAP-Elites. Experiments based on 25 numerical optimization problems suggest that Differential MAP-Elites clearly outperforms CVT-MAP-Elites, finding better-quality and more diverse solutions.

We propose a new method for learning compact state representations and policies separately but simultaneously for policy approximation in vision-based applications such as Atari games. Approaches based on deep reinforcement learning typically map pixels directly to actions to enable end-to-end training. Internally, however, the deep neural network bears the responsibility of both extracting useful information and making decisions based on it, two objectives which can be addressed independently. Separating the image processing from the action selection allows for a better understanding of either task individually, as well as potentially finding smaller policy representations which is inherently interesting. Our approach learns state representations using a compact encoder based on two novel algorithms: (i) Increasing Dictionary Vector Quantization builds a dictionary of state representations which grows in size over time, allowing our method to address new observations as they appear in an open-ended online-learning context; and (ii) Direct Residuals Sparse Coding encodes observations in function of the dictionary, aiming for highest information inclusion by disregarding reconstruction error and maximizing code sparsity. As the dictionary size increases, however, the encoder produces increasingly larger inputs for the neural network; this issue is addressed with a new variant of the Exponential Natural Evolution Strategies algorithm which adapts the dimensionality of its probability distribution along the run. We test our system on a selection of Atari games using tiny neural networks of only 6 to 18 neurons (depending on each game's controls). These are still capable of achieving results that are not much worse, and occasionally superior, to the state-of-the-art in direct policy search which uses two orders of magnitude more neurons.

Presents the editor's experiences with the first four years working on IEEE Transactions on Games.

What will the job market of the future look like? What jobs will be popular, and which skills will they require? Modeling the temporal progression of the job market, as represented by job ads, may help us answer this question. This paper represents a first step in this direction. In order to build a spatial representation of job market that allows to track changes in skills' demand, authors are training models to classify job tasks. Different natural language processing and classification approaches were compared, including term frequency - inverse document frequency, principal components analysis, word2vec, GloVe, fastText and BERT models, and feedforward neural networks, support vector machines, and bidirectional long short term memory recurrent neural networks. BERT obtained the best accuracy results with 52% for 94 classes and 65% for 22 classes.

This paper introduces an information-theoretic method for selecting a subset of problems which gives the most information about a group of problem-solving algorithms. This method was tested on the games in the General Video Game AI (GVGAI) framework, allowing us to identify a smaller set of games that still gives a large amount of information about the abilities of different game-playing agents. This approach can be used to make agent testing more efficient. We can achieve almost as good discriminatory accuracy when testing on only a handful of games as when testing on more than a hundred games, something which is often computationally infeasible. Furthermore, this method can be extended to study the dimensions of the effective variance in game design between these games, allowing us to identify which games differentiate between agents in the most complementary ways.

We present a collaborative mixed-initiative system for building levels for the puzzle game "Baba is You". Unlike previous mixed-initiative systems, Baba is Y'all is designed for collaborative asynchronous creation by multiple users over the internet. The system includes several AI-assisted features to help designers, including a level evolver and an automated player for playtesting. The level archives catalogues levels according to which mechanics are implemented and not implemented, allowing the system to ask users to design levels with specific combinations of mechanics. We describe the operation of the system and the results of small-scale informal user test, and discuss future development paths for this system as well as for collaborative mixed-initiative systems in general.

Video game tutorials allow players to gain mastery over game skills and mechanics. To hone players' skills, it is beneficial from practicing in environments that promote individual player skill sets. However, automatically generating environments which are mechanically similar to one-another is a non-trivial problem. This paper presents a level generation method for Super Mario by stitching together pre-generated "scenes" that contain specific mechanics, using mechanic-sequences from agent playthroughs as input specifications. Given a sequence of mechanics, the proposed system uses an FI-2Pop algorithm and a corpus of scenes to perform automated level authoring. The proposed system outputs levels that can be beaten using a similar mechanical sequence to the target mechanic sequence but with a different playthrough experience. We compare the proposed system to a greedy method that selects scenes that maximize the number of matched mechanics. Unlike the greedy approach, the proposed system is able to maximize the number of matched mechanics while reducing emergent mechanics using the stitching process.

Generative Adversarial Networks (GANs) have shown impressive results for image generation. However, GANs face challenges in generating contents with certain types of constraints, such as game levels. Specifically, it is difficult to generate levels that have aesthetic appeal and are playable at the same time. Additionally, because training data usually is limited, it is challenging to generate unique levels with current GANs. In this paper, we propose a new GAN architecture named Conditional Embedding Self-Attention Generative Adversarial Net-work (CESAGAN) and a new bootstrapping training procedure. The CESAGAN is a modification of the self-attention GAN that incorporates an embedding feature vector input to condition the training of the discriminator and generator. This allows the network to model non-local dependency between game objects, and to count objects. Additionally, to reduce the number of levels necessary to train the GAN, we propose a bootstrapping mechanism in which playable generated levels are added to the training set. The results demonstrate that the new approach does not only generate a larger number of levels that are playable but also generates fewer duplicate levels compared to a standard GAN.

Recent procedural content generation via machine learning (PCGML) methods allow learning from existing content to produce similar content automatically. While these approaches are able to generate content for different games (e.g. Super Mario Bros., DOOM, Zelda, and Kid Icarus), it is an open question how well these approaches can capture large-scale visual patterns such as symmetry. In this paper, we propose match-three games as a domain to test PCGML algorithms regarding their ability to generate suitable patterns. We demonstrate that popular algorithms such as Generative Adversarial Networks struggle in this domain and propose adaptations to improve their performance. In particular, we augment the neighbourhood of a Markov Random Fields approach to take into account not only local but also symmetric positional information. We conduct several empirical tests, including a user study that show the improvements achieved by the proposed modifications and obtain promising results.

Deep Reinforcement Learning (DRL) has shown impressive performance on domains with visual inputs, in particular various games. However, the agent is usually trained on a fixed environment, e.g. a fixed number of levels. A growing mass of evidence suggests that these trained models fail to generalize to even slight variations of the environments they were trained on. This paper advances the hypothesis that the lack of generalization is partly due to the input representation, and explores how rotation, cropping and translation could increase generality. We show that a cropped, translated and rotated observation can get better generalization on unseen levels of two-dimensional arcade games from the GVGAI framework. The generality of the agents is evaluated on both human-designed and procedurally generated levels.

In multi-stage processes, decisions happen in an ordered sequence of stages. Many of them have the structure of dual funnel problem: as the sample size decreases from one stage to the other, the information increases. A related example is a selection process, where applicants apply for a position, prize or grant. In each stage, more applicants are evaluated and filtered out and from the remaining ones, more information is collected. In the last stage, decision-makers use all available information to make their final decision. To train a classifier for each stage becomes impracticable as they can underfit due to the low dimensionality in early stages or overfit due to the small sample size in the latter stages. In this work, we proposed a Multi-StaGe Transfer Learning (MSGTL) approach that uses knowledge from simple classifiers trained in early stages to improve the performance of classifiers in the latter stages. By transferring weights from simpler neural networks trained in larger datasets, we able to fine-tune more complex neural networks in the latter stages without overfitting due to the small sample size. We show that is possible to control the trade-off between conserving knowledge and fine-tuning using a simple probabilistic map. Experiments using real-world data show the efficacy of our approach as it outperforms other state-of-the-art methods for transfer learning and regularization.

This paper introduces a fully automatic method of mechanic illumination for general video game level generation. Using the Constrained MAP-Elites algorithm and the GVG-AI framework, this system generates the simplest tile based levels that contain specific sets of game mechanics and also satisfy playability constraints. We apply this method to illuminate the mechanic space for four different games in GVG-AI: Zelda, Solarfox, Plants, and RealPortals. With this system, we can generate playable levels that contain different combinations of most of the possible mechanics. These levels can later be used to populate game tutorials that teach players how to use the mechanics of the game.

We present a new method of automatic critical mechanic discovery for video games using a combination of game description parsing and playtrace information. This method is applied to several games within the General Video Game Artificial Intelligence (GVG-AI) framework. In a user study, human-identified mechanics are compared against system-identified critical mechanics to verify alignment between humans and the system. The results of the study demonstrate that the new method is able to match humans with higher consistency than baseline. Our system is further validated by comparing MCTS agents augmented with critical mechanics and vanilla MCTS agents on 4 games from GVG-AI. Our new playtrace method shows a significant performance improvement over the baseline for all 4 tested games. The proposed method also shows either matched or improved performance over the old method, demonstrating that playtrace information is responsible for more complete critical mechanic discovery.

This paper introduces a new system to design constructive level generators by searching the space of constructive level generators defined by Marahel language. We use NSGA-II, a multi-objective optimization algorithm, to search for generators for three different problems (Binary, Zelda, and Sokoban). We restrict the representation to a subset of Marahel language to push the evolution to find more efficient generators. The results show that the generated generators were able to achieve good performance on most of the fitness functions over these three problems. However, on Zelda and Sokoban they tend to depend on the initial state than modifying the map.

We focus on the challenge of finding a diverse collection of quality solutions on complex continuous domains. While quality diversity (QD) algorithms like Novelty Search with Local Competition (NSLC) and MAP-Elites are designed to generate a diverse range of solutions, these algorithms require a large number of evaluations for exploration of continuous spaces. Meanwhile, variants of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) are among the best-performing derivative-free optimizers in single-objective continuous domains. This paper proposes a new QD algorithm called Covariance Matrix Adaptation MAP-Elites (CMA-ME). Our new algorithm combines the self-adaptation techniques of CMA-ES with archiving and mapping techniques for maintaining diversity in QD. Results from experiments based on standard continuous optimization benchmarks show that CMA-ME finds better-quality solutions than MAP-Elites; similarly, results on the strategic game Hearthstone show that CMA-ME finds both a higher overall quality and broader diversity of strategies than both CMA-ES and MAP-Elites. Overall, CMA-ME more than doubles the performance of MAP-Elites using standard QD performance metrics. These results suggest that QD algorithms augmented by operators from state-of-the-art optimization algorithms can yield high-performing methods for simultaneously exploring and optimizing continuous search spaces, with significant applications to design, testing, and reinforcement learning among other domains.

In multi-stage processes, decisions occur in an ordered sequence of stages. Early stages usually have more observations with general information (easier/cheaper to collect), while later stages have fewer observations but more specific data. This situation can be represented as a dual funnel structure, in which the sample size decreases from one stage to the other while the information available about each instance increases. Training classifiers in this scenario is challenging since information in the early stages may not contain distinct patterns to learn (underfitting). In contrast, the small sample size in later stages can cause overfitting. We address both cases by introducing a framework that combines adversarial autoencoders (AAE), multitask learning (MTL), and multi-label semi-supervised learning (MLSSL). We improve the decoder of the AAE with MTL so it can jointly reconstruct the original input and use feature nets to predict the features for the next stages. We also introduce a sequence constraint in the output of an MLSSL classifier to guarantee the sequential pattern in the predictions. Using different domains (selection process, medical diagnosis), we show that our approach outperforms other state-of-the-art methods.

Deep reinforcement learning applied to vision-based problems like Atari games maps pixels directly to actions; internally, the deep neural network bears the responsibility of both extracting useful information and making decisions based on it. By separating image processing from decision-making, one could better understand the complexity of each task, as well as potentially find smaller policy representations that are easier for humans to understand and may generalize better. To this end, we propose a new method for learning policies and compact state representations separately but simultaneously for policy approximation in reinforcement learning. State representations are generated by an encoder based on two novel algorithms: Increasing Dictionary Vector Quantization makes the encoder capable of growing its dictionary size over time, to address new observations; and Direct Residuals Sparse Coding encodes observations by aiming for highest information inclusion. We test our system on a selection of Atari games using tiny neural networks of only 6 to 18 neurons (depending on the game's controls). These are still capable of achieving results comparable---and occasionally superior---to state-of-the-art techniques which use two orders of magnitude more neurons.

We present a novel framework that can combine multi-domain learning (MDL), data imputation (DI) and multi-task learning (MTL) to improve performance for classification and regression tasks in different domains. The core of our method is an adversarial autoencoder that can: (1) learn to produce domain-invariant embeddings to reduce the difference between domains; (2) learn the data distribution for each domain and correctly perform data imputation on missing data. For MDL, we use the Maximum Mean Discrepancy (MMD) measure to align the domain distributions. For DI, we use an adversarial approach where a generator fill in information for missing data and a discriminator tries to distinguish between real and imputed values. Finally, using the universal feature representation in the embeddings, we train a classifier using MTL that given input from any domain, can predict labels for all domains. We demonstrate the superior performance of our approach compared to other state-of-art methods in three distinct settings, DG-DI in image recognition with unstructured data, MTL-DI in grade estimation with structured data and MDMTL-DI in a selection process using mixed data.

Facial expressions (FEs) communicate a rich variety of social, grammatical, and affective signals. However, the most generally accepted set of recognizable FEs remains limited to seven basic displays of emotion: happiness, sadness, fear, anger, disgust, surprise and contempt. To develop intelligent virtual agents capable of interpreting and synthesizing nuanced facial behavior, we need a more complete lexicon. One roadblock has been the limiting nature of forced-choice study designs, the most common paradigm for investigating observer judgements of FEs. However, there has been no consensus on an objective way to evaluate alternative free response designs.

In this paper, we review recent deep learning advances in the context of how they have been applied to play different types of video games such as first-person shooters, arcade games, and real-time strategy games. We analyze the unique requirements that different game genres pose to a deep learning system and highlight important open challenges in the context of applying these machine learning methods to video games, such as general game playing, dealing with extremely large decision spaces and sparse rewards.

We propose the use of quality-diversity algorithms for mixed-initiative game content generation. This idea is implemented as a new feature of the Evolutionary Dungeon Designer, a system for mixed-initiative design of the type of levels you typically find in computer role playing games. The feature uses the MAP-Elites algorithm, an illumination algorithm which divides the population into a number of cells depending on their values along several behavioral dimensions. Users can flexibly and dynamically choose relevant dimensions of variation, and incorporate suggestions produced by the algorithm in their map designs. At the same time, any modifications performed by the human feed back into MAP-Elites, and are used to generate further suggestions.

In complex scenarios where a model of other actors is necessary to predict and interpret their actions, it is often desirable that the model works well with a wide variety of previously unknown actors. Hanabi is a card game that brings the problem of modeling other players to the forefront, but there is no agreement on how to best generate a pool of agents to use as partners in ad-hoc cooperation evaluation. This paper proposes Quality Diversity algorithms as a promising class of algorithms to generate populations for this purpose and shows an initial implementation of an agent generator based on this idea. We also discuss what metrics can be used to compare such generators, and how the proposed generator could be leveraged to help build adaptive agents for the game.

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.

We propose the popular board game Blood Bowl as a new challenge for Artificial Intelligence (AI). Blood Bowl is a fully-observable, stochastic, turn-based, modern-style board game with a grid-based game board. At first sight, the game ought to be approachable by numerous game-playing algorithms. However, as all pieces on the board belonging to a player can be moved several times each turn, the turn-wise branching factor becomes overwhelming for traditional algorithms. Additionally, scoring points in the game is rare and difficult, which makes it hard to design heuristics for search algorithms or apply reinforcement learning. We present the Fantasy Football AI (FFAI) framework that implements the core rules of Blood Bowl and includes a forward model, several OpenAI Gym environments for reinforcement learning, competition functionalities, and a web application that allows for human play. We also present Bot Bowl I, the first AI competition that will use FFAI along with baseline agents and preliminary reinforcement learning results. Additionally, we present a wealth of opportunities for future AI competitions based on FFAI.

Elimination is a word puzzle game for browsers and mobile devices, where all levels are generated by a constrained evolutionary algorithm with no human intervention. This paper describes the design of the game and its level generation methods, and analysis of playtraces from almost a thousand players. The analysis corroborates that the level generator creates a sawtooth-shaped difficulty curve, as intended. The analysis also offers insights into player behavior in this game.

Videogame designers use tips and tricks and tools of the trade to design levels. Some of these tips are based on their gut feeling and others have been known in the game industry for the last 30 years. In this work, we discuss six of common level design patterns present in 2D videogames. The patterns under discussion are the product of an exploratory analysis of over thirty 2D games. We choose to focus on patterns that are both common and impactful for the overall player experience. We discuss in detail the rationale for and advantages of each pattern, showing examples of games that make use of such. We conclude with a discussion of the usage and understanding of these patterns from the perspective of level design and how other technical approaches can benefit from them.

Recommender Systems are widely and successfully applied in e-commerce. Could they be used for designƒ In this paper, we introduce Pitako1, a tool that applies the Recommender System concept to assist humans in creative tasks. More specifically, Pitako provides suggestions by taking games designed by humans as inputs, and recommends mechanics and dynamics as outputs. Pitako is implemented as a new system within the mixed-initiative AI-based Game Design Assistant, Cicero. This paper discusses the motivation behind the implementation of Pitako as well as its technical details and presents usage examples. We believe that Pitako can influence the use of recommender systems to help humans in their daily tasks.

Matching tile games are an extremely popular game genre. Arguably the most popular iteration, Match-3 games, are simple to understand puzzle games, making them great benchmarks for research. In this paper, we propose developing different procedural personas for Match-3 games in order to approximate different human playstyles to create an automated playtesting system. The procedural personas are realized through evolving the utility function for the Monte Carlo Tree Search agent. We compare the performance and results of the evolution agents with the standard Vanilla Monte Carlo Tree Search implementation as well as to a random move-selection agent. We then observe the impacts on both the game's design and the game design process. Lastly, a user study is performed to compare the agents to human play traces.

Balancing an ever growing strategic game of high complexity, such as Hearthstone is a complex task. The target of making strategies diverse and customizable results in a delicate intricate system. Tuning over 2000 cards to generate the desired outcome without disrupting the existing environment becomes a laborious challenge. In this paper, we discuss the impacts that changes to existing cards can have on strategy in Hearthstone. By analyzing the win rate on match-ups across different decks, being played by different strategies, we propose to compare their performance before and after changes are made to improve or worsen different cards. Then, using an evolutionary algorithm, we search for a combination of changes to the card attributes that cause the decks to approach equal, 50% win rates. We then expand our evolutionary algorithm to a multi-objective solution to search for this result, while making the minimum amount of changes, and as a consequence disruption, to the existing cards. Lastly, we propose and evaluate metrics to serve as heuristics with which to decide which cards to target with balance changes.

Procedural content generation can be used to create arbitrarily large amounts of game levels automatically, but traditionally the PCG algorithms needed to be developed or adapted for each game manually. Procedural Content Generation via Machine Learning (PCGML) harnesses the power of machine learning to semi-automate the development of PCG solutions, training on existing game content so as to create new content from the trained models. One of the machine learning techniques that have been suggested for this purpose is the autoencoder. However, very limited work has been done to explore the potential of autoencoders for PCGML. In this paper, we train autoencoders on levels for the platform game Lode Runner, and use them to generate levels. Compared to previous work, we use a multi-channel approach to represent content in full fidelity, and we compare standard and variational autoencoders. We also evolve the values of the hidden layer of trained autoencoders in order to find levels with desired properties.

From the beginning of the history of AI, there has been interest in games as a platform of research. As the field developed, human-level competence in complex games became a target researchers worked to reach. Only relatively recently has this target been finally met for traditional tabletop games such as Backgammon, Chess and Go. This prompted a shift in research focus towards electronic games, which provide unique new challenges. As is often the case with AI research, these results are liable to be exaggerated or mis-represented by either authors or third parties. The extent to which these game benchmarks constitute "fair" competition between human and AI is also a matter of debate. In this paper, we review statements made by reseachers and third parties in the general media and academic publications about these game benchmark results. We analyze what a fair competition would look like and suggest a taxonomy of dimensions to frame the debate of fairness in game contests between humans and machines. Eventually, we argue that there is no completely fair way to compare human and AI performance on a game.

This paper presents a two-step generative approach for creating dungeons in the rogue-like puzzle game MiniDungeons 2. Generation is split into two steps, initially producing the architectural layout of the level as its walls and floor tiles, and then furnishing it with game objects representing the player's start and goal position, challenges and rewards. Three layout creators and three furnishers are introduced in this paper, which can be combined in different ways in the two-step generative process for producing diverse dungeons levels. Layout creators generate the floors and walls of a level, while furnishers populate it with monsters, traps, and treasures. We test the generated levels on several expressivity measures, and in simulations with procedural persona agents.

This paper presents a method for generating floor plans for structures in Minecraft (Mojang 2009). Given a 3D space, it will auto-generate a building to fill that space using a combination of constrained growth and cellular automata. The result is a series of organic-looking buildings complete with rooms, windows, and doors connecting them. The method is applied to the Generative Design in Minecraft (GDMC) competition [24] to auto-generate buildings in Minecraft, and the results are discussed.

Quality diversity (QD) algorithms such as MAP-Elites have emerged as a powerful alternative to traditional single-objective optimization methods. They were initially applied to evolutionary robotics problems such as locomotion and maze navigation, but have yet to see widespread application. We argue that these algorithms are perfectly suited to the rich domain of video games, which contains many relevant problems with a multitude of successful strategies and often also multiple dimensions along which solutions can vary.

The procedural generation of levels and content in video games is a challenging AI problem. Often such generation relies on an intelligent way of evaluating the content being generated so that constraints are satisfied and/or objectives maximized. In this work, we address the problem of creating levels that are not only playable but also revolve around specific mechanics in the game. We use constrained evolutionary algorithms and quality-diversity algorithms to generate small sections of Super Mario Bros levels called scenes, using three different simulation approaches: Limited Agents, Punishing Model, and Mechanics Dimensions. All three approaches are able to create scenes that give opportunity for a player to encounter or use targeted mechanics with different properties. We conclude by discussing the advantages and disadvantages of each approach and compare them to each other.

The rapid pace of recent research in AI has been driven in part by the presence of fast and challenging simulation environments. These environments often take the form of games; with tasks ranging from simple board games, to competitive video games. We propose a new benchmark - Obstacle Tower: a high fidelity, 3D, 3rd person, procedurally generated environment. An agent in Obstacle Tower must learn to solve both low-level control and high-level planning problems in tandem while learning from pixels and a sparse reward signal. Unlike other benchmarks such as the Arcade Learning Environment, evaluation of agent performance in Obstacle Tower is based on an agent's ability to perform well on unseen instances of the environment. In this paper we outline the environment and provide a set of baseline results produced by current state-of-the-art Deep RL methods as well as human players. These algorithms fail to produce agents capable of performing near human level.

This paper presents a framework for generating adventure games from open data. Focusing on the murder mystery type of adventure games, the generator is able to transform open data from Wikipedia articles, OpenStreetMap, and images from Wikimedia Commons into WikiMysteries. Every WikiMystery game revolves around the murder of a person with a Wikipedia article, and populates the game with suspects who must be arrested by the player if guilty of the murder or absolved if innocent. Starting from only one person as the victim, an extensive generative pipeline finds suspects, their alibis, and paths connecting them from open data, transforms open data into cities, buildings, nonplayer characters, locks and keys, and dialog options. This paper describes in detail each generative step, provides a specific playthrough of one WikiMystery where Albert Einstein is murdered, and evaluates the outcomes of games generated for the 100 most influential people of the 20th century.

This paper describes a method for generative player modeling and its application to the automatic testing of game content using archetypal player models called procedural personas. Theoretically grounded in psychological decision theory, procedural personas are implemented using a variation of Monte Carlo tree search (MCTS) where the node selection criteria are developed using evolutionary computation, replacing the standard UCB1 criterion of MCTS. Using these personas, we demonstrate how generative player models can be applied to a varied corpus of game levels and demonstrate how different playstyles can be enacted in each level. In short, we use artificially intelligent personas to construct synthetic playtesters. The proposed approach could be used as a tool for automatic play testing when human feedback is not readily available or when quick visualization of potential interactions is necessary. Possible applications include interactive tools during game development or procedural content generation systems where many evaluations must be conducted within a short time span.

General video game playing aims at designing an agent that is capable of playing multiple video games with no human intervention. In 2014, the General Video Game Artificial Intelligence (GVGAI) competition framework was created and released with the purpose of providing researchers a common open-source and easy-to-use platform for testing their artificial intelligence (AI) methods with potentially infinity of games created using the video game description language (VGDL). The framework has been expanded into several tracks during the last few years to meet the demands of different research directions. The agents are required either to play multiple unknown games with or without access to game simulations, or to design new game levels or rules. This survey paper presents the VGDL, the GVGAI framework, existing tracks, and reviews the wide use of GVGAI framework in research, education, and competitions five years after its birth. A future plan of framework improvements is also described.

This paper presents an overview of the second AIBIRDS level generation competition, held jointly at the 2017 IEEE Conference on Computational Intelligence and Games and the 26th International Joint Conference on Artificial Intelligence. This competition tasked entrants with developing a level generator for the physics-based puzzle game Angry Birds. Submitted generators were required to deal with many physical reasoning constraints caused by the realistic nature of the game's environment, in addition to ensuring that the created levels were fun, challenging, and solvable. This year's competition was a significant improvement over the previous year, with a greater number of participants and more advanced generators. In this paper, we describe the framework, rules, submitted generators, and results for this competition. We also provide some background information on related research and other video game AI competitions and discuss what can be learned from this year's competition. There are several game and real-world applications for this type of research, and we provide some examples of the types of levels we would like future competition entries to generate.

We present Cicero, a mixed-initiative application for prototyping two-dimensional sprite-based games across different genres such as shooters, puzzles, and action games. Cicero provides a host of features which can offer assistance in different stages of the game development process. Noteworthy features include AI agents for gameplay simulation, a game mechanics recommender system, a playtrace aggregator, heatmap-based game analysis, a sequential replay mechanism, and a query system that allows searching for particular interaction patterns. In order to evaluate the efficacy and usefulness of the different features of Cicero, we conducted a user study in which we compared how users perform in game debugging tasks with different kinds of assistance.

A significant issue in game balancing is understanding the game itself. For simple games end-to-end optimization approaches can help explore the game's design space, but for more complex games it is necessary to isolate and explore its parts. Hearthstone, Blizzard's popular two-player turn-taking adversarial card game, has two distinct game-playing challenges: choosing when and how to play cards, and selecting which cards a player can access during the game (deckbuilding). Focusing on deckbuilding, four experiments are conducted to computationally explore the design of Hearthstone. They address the difficulty of constructing good decks, the specificity and generality of decks, and the transitivity of decks. Results suggest it is possible to find decks with an Evolution Strategy (ES) that convincingly beat other decks available in the game, but that they also exhibit some generality (i.e. they perform well against unknown decks). Interestingly, a second ES experiment is performed where decks are evolved against opponents playing the originally evolved decks. Since the originally evolved decks beat the starter decks, and the twice evolved decks beat the originally evolved decks, some degree of transitivity of the deck space is shown. While only a preliminary study with restrictive conditions, this paper paves the way for future work computationally identifying properties of cards important for different gameplay strategies and helping players build decks to fit their personal playstyles without the need for in-depth domain knowledge.

This paper introduces DATA Agent, a system which creates murder mystery adventures from open data. In the game, the player takes on the role of a detective tasked with finding the culprit of a murder. All characters, places, and items in DATA Agent games are generated using open data as source content. The paper discusses the general game design and user interface of DATA Agent, and provides details on the generative algorithms which transform linked data into different game objects. Findings from a user study with 30 participants playing through two games of DATA Agent show that the game is easy and fun to play, and that the mysteries it generates are straightforward to solve.

This paper introduces a fully automatic method for generating video game tutorials. The AtDELFI system (Automatically DEsigning Legible, Full Instructions for games) was created to investigate procedural generation of instructions that teach players how to play video games. We present a representation of game rules and mechanics using a graph system as well as a tutorial generation method that uses said graph representation. We demonstrate the concept by testing it on games within the General Video Game Artificial Intelligence (GVG-AI) framework; the paper discusses tutorials generated for eight different games. Our findings suggest that a graph representation scheme works well for simple arcade style games such as Space Invaders and Pacman, but it appears that tutorials for more complex games might require higher-level understanding of the game than just single mechanics.

The automatic generation of game tutorials is a challenging AI problem. While it is possible to generate annotations and instructions that explain to the player how the game is played, this paper focuses on generating a gameplay experience that introduces the player to a game mechanic. It evolves small levels for the Mario AI Framework that can only be beaten by an agent that knows how to perform specific actions in the game. It uses variations of a perfect A* agent that are limited in various ways, such as not being able to jump high or see enemies, to test how failing to do certain actions can stop the player from beating the level.

This paper introduces the settlement generation competition for Minecraft, the first part of the Generative Design in Minecraft challenge. The settlement generation competition is about creating Artificial Intelligence (AI) agents that can produce functional, aesthetically appealing and believable settlements adapted to a given Minecraft map---ideally at a level that can compete with human created designs. The aim of the competition is to advance procedural content generation for games, especially in overcoming the challenges of adaptive and holistic PCG. The paper introduces the technical details of the challenge, but mostly focuses on what challenges this competition provides and why they are scientifically relevant.

We present a search-based approach to generating boards and decks of cards for the game Ticket to Ride. Our evolutionary algorithm searches for boards that allow for a well-shaped game arc, and for decks that promote an equal distribution of desirability for cities. We show examples of two boards generated by our algorithm and compare our results to those of the actual components of the game. Our approach creates game content that is specifically designed towards metrics that can affect gameplay in an impactful way.

We introduce several deck of cards and dice models that can be used to represent stochastic outcomes in tabletop games. We analyze these using a toy game introduced as a Micro Combat game. By simulating the outcome of the game with these different models we can analyze them in terms of their salience, disparity, fairness and obfuscation. We expect this analysis to help designers choose the method that best suits their intended experience.

In this paper, we explore the possibility of search-based agents in games with resource-intensive forward models. We implemented a player agent in the Pommerman framework and put it against the baseline agent to measure its performance. We implemented a heuristic agent and improved it by enabling depth-limited tree search in specific gameplay moments. We also compared different node selection methods during depth-limited tree search. Our result shows that depth-limited tree search is still viable when presented with inefficient forward models and exploitation-driven selection method is the most efficient in this specific domain.

We describe a search-based approach to generating new levels for bullet hell games, which are action games characterized by and requiring avoidance of a very large amount of projectiles. Levels are represented using a domain-specific description language, and search in the space defined by this language is performed by a novel variant of the Map-Elites algorithm which incorporates a feasible-infeasible approach to constraint satisfaction. Simulation-based evaluation is used to gauge the fitness of levels, using an agent based on best-first search. The performance of the agent can be tuned according to the two dimensions of strategy and dexterity, making it possible to search for level configurations that require a specific combination of both. As far as we know, this paper describes the first generator for this game genre, and includes several algorithmic innovations.

Beginner heuristics for a game are simple rules that allow for effective playing. A chain of beginner heuristics of length N is the list of N rules that play the game best. Finding beginner heuristics is useful both for teaching a novice to play the game well and for understanding the dynamics of the game. We present and compare methods for finding beginner heuristics in a simple version of Poker: Pre-Flop Heads-Up Limit Texas Hold'em. We find that genetic programming outperforms greedy-exhaustive search and axis-aligned search in terms of finding well-playing heuristic chains of given length. We also find that there is a limited amount of non-transitivity when playing beginner heuristics of different lengths against each other, suggesting that while simpler heuristics are somewhat general, the more complex seem to overfit their training set.

Game designers can use computer-aided game design methods to model how players may experience the perceived difficulty of a game. We present methods to generate and analyze the difficulty of a wide variety of minimal action game variants throughout game space, where each point in this abstract design space represents a unique game variant. Focusing on a parameterized version of Flappy Bird, we predict hazard rates and difficulty curves using automatic playtesting, Monte Carlo simulation, a player model based on human motor skills (precision and actions per second), and survival analysis of score histograms. We demonstrate our techniques using simulated game play and actual game data from over 106 million play sessions of a popular online Flappy Bird variant, showing quantitative reasons why balancing a game for a wide range of player skill can be difficult. Some applications of our techniques include searching for a specific difficulty, game space visualization, computational creativity to find unique variants, and tuning game balance to adjust the difficulty curve even when game parameters are time varying, score dependent, or changing based on game progress.

We address the problem of playing turn-based multiaction adversarial games, which include many strategy games with extremely high branching factors as players take multiple actions each turn. This leads to the breakdown of standard tree search methods, including Monte Carlo tree search (MCTS), as they become unable to reach a sufficient depth in the game tree. In this paper, we introduce online evolutionary planning (OEP) to address this challenge, which searches for combinations of actions to perform during a single turn guided by a fitness function that evaluates the quality of a particular state. We compare OEP to different MCTS variations that constrain the exploration to deal with the high branching factor in the turn-based multiaction game Hero Academy. While the constrained MCTS variations outperform the vanilla MCTS implementation by a large margin, OEP is able to search the space of plans more efficiently than any of the tested tree search methods as it has a relative advantage when the number of actions per turn increases.

This survey explores procedural content generation via machine learning (PCGML), defined as the generation of game content using machine learning models trained on existing content. As the importance of PCG for game development increases, researchers explore new avenues for generating high-quality content with or without human involvement; this paper addresses the relatively new paradigm of using machine learning (in contrast with search-based, solver-based, and constructive methods). We focus on what is most often considered functional game content, such as platformer levels, game maps, interactive fiction stories, and cards in collectible card games, as opposed to cosmetic content, such as sprites and sound effects. In addition to using PCG for autonomous generation, cocreativity, mixed-initiative design, and compression, PCGML is suited for repair, critique, and content analysis because of its focus on modeling existing content. We discuss various data sources and representations that affect the generated content. Multiple PCGML methods are covered, including neural networks: long short-term memory networks, autoencoders, and deep convolutional networks; Markov models: $n$-grams and multi-dimensional Markov chains; clustering; and matrix factorization. Finally, we discuss open problems in PCGML, including learning from small data sets, lack of training data, multilayered learning, style-transfer, parameter tuning, and PCG as a game mechanic.

This study examined two metrics for measuring the distance between sequences (Euclid and OMSpell) and creating distance matrices combined with two types of clustering methods (AGNES and PAM) to analyze the career path clusters of knowledge workers. A regression tree of covariates and career path clusters was used to predict advancement rates. The results indicated that the metric which focused on subsequences (OMSpell) worked best for both clustering methods. Less time as a knowledge worker was associated with greater advancement. Implications for boundaryless careers and social capital formation are discussed.

Most games have, or can be generalised to have, a number of parameters that may be varied in order to provide instances of games that lead to very different player experiences. The space of possible parameter settings can be seen as a search space, and we can therefore use a Random Mutation Hill Climbing algorithm or other search methods to find the parameter settings that induce the best games. One of the hardest parts of this approach is defining a suitable fitness function. In this paper we explore the possibility of using one of a growing set of General Video Game AI agents to perform automatic play-testing. This enables a very general approach to game evaluation based on estimating the skill-depth of a game. Agent-based play-testing is computationally expensive, so we compare two simple but efficient optimisation algorithms: the Random Mutation Hill-Climber and the Multi-Armed Bandit Random Mutation Hill-Climber. For the test game we use a space-battle game in order to provide a suitable balance between simulation speed and potential skill-depth. Results show that both algorithms are able to rapidly evolve game versions with significant skill-depth, but that choosing a suitable resampling number is essential in order to combat the effects of noise.

This paper describes the design of SeekWhence, a retrospective analysis tool for gameplay session. SeekWhence is a new addition to the Cicero AI-assisted game design tool, which is built on top of the Video Game Description Language (VGDL) and the General Video Game Framework (GVG-AI). With SeekWhence, designers can prototype their games and record gameplay sessions simulated by agents or human players. They can go back and forth on every frame of the recorded session, analyzing it step by step and import it into their current project to edit it. This paper explains the technical details of SeekWhence and gives examples of its usage.

Ticket to Ride is a popular contemporary board game for two to four players, featuring a number of expansions with additional maps and tweaks to the core game mechanics. In this paper, four different game-playing agents that embody different playing styles are defined and used to analyze Ticket to Ride. Different playing styles are shown to be effective depending on the map and rule variation, and also depending on how many players play the game. The performance profiles of the different agents can be used to characterize maps and identify the most similar maps in the space of playstyles. Further analysis of the automatically played games reveal which cities on the map are most desirable, and that the relative attractiveness of cities is remarkably consistent across numbers of players. Finally, the automated analysis also reveals two classes of failures states, where the agents find states which are not covered by the game rules; this is akin to finding bugs in the rules. We see the analysis performed here as a possible template for AI-based playtesting of contemporary board games.

This paper describes an evaluation conducted on the MetaCompose music generator, which is based on evolutionary computation and uses a hybrid evolutionary technique that combines FI-2POP and multi-objective optimization. The main objective of MetaCompose is to create music in real-time that can express different mood-states. The experiment presented here aims to evaluate: (i) if the perceived mood experienced by the participants of a music score matches intended mood the system is trying to express and (ii) if participants can identify transitions in the mood expression that occur mid-piece. Music clips including transitions and with static affective states were produced by MetaCompose and a quantitative user study was performed. Participants were tasked with annotating the perceived mood and moreover were asked to annotate in real-time changes in valence. The data collected confirms the hypothesis that people can recognize changes in music mood and that MetaCompose can express perceptibly different levels of arousal. In regards to valence we observe that, while it is mainly perceived as expected, changes in arousal seems to also influence perceived valence, suggesting that one or more of the music features MetaCompose associates with arousal has some effect on valence as well.

Neuroevolution [i.e., evolving artificial neural networks (ANNs) through evolutionary algorithms] has shown promise in evolving agents and robot controllers, which display complex behaviors and can adapt to their environments. These properties are also relevant to video games, since they can increase their longevity and replayability. However, the design of most current games precludes the use of any techniques which might yield unpredictable or even open-ended results. This paper describes the game EvoCommander, with the goal to further demonstrate the potential of neuroevolution in games. In EvoCommander the player incrementally evolves an arsenal of ANN-controlled behaviors (e.g., ranged attack, flee, etc.) for a simple robot that has to battle other player and computer controlled robots. The game introduces the novel game mechanic of “brain switching,” selecting which evolved neural network is active at any point during battle. Results from playtests indicate that brain switching is a promising new game mechanic, leading to players employing interesting different strategies when training their robots and when controlling them in battle.

This paper surveys research on applying neuroevolution (NE) to games. In neuroevolution, artificial neural networks are trained through evolutionary algorithms, taking inspiration from the way biological brains evolved. We analyze the application of NE in games along five different axes, which are the role NE is chosen to play in a game, the different types of neural networks used, the way these networks are evolved, how the fitness is determined and what type of input the network receives. The paper also highlights important open research challenges in the field.

The General Video Game AI framework and competition pose the problem of creating artificial intelligence that can play a wide, and in principle unlimited, range of games. Concretely, it tackles the problem of devising an algorithm that is able to play any game it is given, even if the game is not known a priori. This area of study can be seen as an approximation of General Artificial Intelligence, with very little room for game-dependent heuristics. This short paper summarizes the motivation, infrastructure, results and future plans of General Video Game AI, stressing the findings and first conclusions drawn after two editions of our competition, and outlining our future plans.

This paper presents a framework and an initial study in general video game level generation, the problem of generating levels for not only a single game but for any game within a specified range. While existing level generators are tailored to a particular game, this new challenge requires generators to take into account the constraints and affordances of games that might not even have been designed when the generator was constructed. The framework presented here builds on the General Video Game AI framework (GVG-AI) and the Video Game Description Language (VGDL), in order to reap synergies from research activities connected to the General Video Game Playing Competition. The framework will also form the basis for a new track of this competition. In addition to the framework, the paper presents three general level generators and an empirical comparison of their qualities.

This paper presents the framework, rules, games, controllers, and results of the first General Video Game Playing Competition, held at the IEEE Conference on Computational Intelligence and Games in 2014. The competition proposes the challenge of creating controllers for general video game play, where a single agent must be able to play many different games, some of them unknown to the participants at the time of submitting their entries. This test can be seen as an approximation of general artificial intelligence, as the amount of game-dependent heuristics needs to be severely limited. The games employed are stochastic real-time scenarios (where the time budget to provide the next action is measured in milliseconds) with different winning conditions, scoring mechanisms, sprite types, and available actions for the player. It is a responsibility of the agents to discover the mechanics of each game, the requirements to obtain a high score and the requisites to finally achieve victory. This paper describes all controllers submitted to the competition, with an in-depth description of four of them by their authors, including the winner and the runner-up entries of the contest. The paper also analyzes the performance of the different approaches submitted, and finally proposes future tracks for the competition.

Game-based competitions are commonly used within the Computational Intelligence (CI) and Artificial Intelligence (AI) in games community to benchmark algorithms and to attract new researchers. While many competitions have been organized based on different games, the success of these competitions is highly varied. This short paper is a self-help paper for competition organizers and aspiring competition organizers. After analyzing the fate of a number of recent competitions, some factors likely to contribute to the success or failure of a competition are laid out, and a set of concrete recommendations is offered. There is also a discussion of how to write up game-based AI competitions and what we can ultimately learn from them.

Procedural content generation is an increasingly important area of technology within modern human-computer interaction with direct applications in digital games, the semantic web, and interface, media and software design. The personalization of experience via the modeling of the user, coupled with the appropriate adjustment of the content according to user needs and preferences are important steps towards effective and meaningful content generation. This paper introduces a framework for procedural content generation driven by computational models of user experience we name Experience-Driven Procedural Content Generation. While the framework is generic and applicable to various subareas of human computer interaction, we employ games as an indicative example of content-intensive software that enables rich forms of interaction.

This work investigates how to incorporate real-world data into game content so that the content is playable and enjoyable while not misrepresenting the data. We propose a method for generating balanced Civilization maps based on Open Data, describing how to acquire, transform and integrate information from different sources into a single content. Furthermore, we evolve players' initial positions in order to obtain balanced maps, while trying to minimize information accuracy loss. In addition, this paper describes a tool to assist users in this process. Maps generated using these method and tool are playable and balanced yet faithful to the original sources.

This paper presents the online application Brain-Crafter, in which users can manually build artificial neural networks (ANNs) to control a robot in a maze environment. Users can either start to construct networks from scratch or elaborate on networks created by other users. In particular, BrainCrafter was designed to study how good we as humans are at building ANNs for control problems and if collaborating with other users can facilitate this process. The results in this paper show that (1) some users were in fact able to successfully construct ANNs that solve the navigation tasks, (2) collaboration between users presented difficulties and (3) the human-developed ANNs that managed to solve the task had certain regularities, suggesting that humans can use some of their intuition and spatial understanding in the design of ANNs. Most importantly, the initial results in this paper can serve as a starting point for investigating how to best combine human and machine design capabilities to create more complex artificial brains.

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.

While games are a popular social media for children, there is a real risk that these children are exposed to potential sexual assault. A number of studies have already addressed this issue, however, the data used in previous research did not properly represent the real chats found in multiplayer online games. To address this issue, we obtained real chat data from MovieStarPlanet, a massively multiplayer online game for children. The research described in this paper aimed to detect predatory behaviors in the chats using machine learning methods. In order to achieve a high accuracy on this task, extensive preprocessing was necessary. We describe three different strategies for data selection and preprocessing, and extensively compare the performance of different learning algorithms on the different data sets and features.

This paper attempts to give a high-level overview of the field of artificial and computational intelligence (AI/CI) in games, with particular reference to how the different core research areas within this field inform and interact with each other, both actually and potentially. We identify ten main research areas within this field: NPC behavior learning, search and planning, player modeling, games as AI benchmarks, procedural content generation, computational narrative, believable agents, AI-assisted game design, general game artificial intelligence and AI in commercial games. We view and analyze the areas from three key perspectives: 1) the dominant AI method(s) used under each area; 2) the relation of each area with respect to the end (human) user; and 3) the placement of each area within a human-computer (player-game) interaction perspective. In addition, for each of these areas we consider how it could inform or interact with each of the other areas; in those cases where we find that meaningful interaction either exists or is possible, we describe the character of that interaction and provide references to published studies, if any. We believe that this paper improves understanding of the current nature of the game AI/CI research field and the interdependences between its core areas by providing a unifying overview. We also believe that the discussion of potential interactions between research areas provides a pointer to many interesting future research projects and unexplored subfields.

Monte Carlo Tree Search (MCTS) is applied to control the player character in a clone of the popular platform game Super Mario Bros. Standard MCTS is applied through search in state space with the goal of moving the furthest to the right as quickly as possible. Despite parameter tuning, only moderate success is reached. Several modifications to the algorithm are then introduced specifically to deal with the behavioural pathologies that were observed. Two of the modifications are to our best knowledge novel. A combination of these modifications is found to lead to almost perfect play on linear levels. Furthermore, when adding noise to the benchmark, MCTS outperforms the best known algorithm for these levels. The analysis and algorithmic innovations in this paper are likely to be useful when applying MCTS to other video games.

This paper presents a method for generating complex problems that allow multiple nonobvious solutions for the physical traveling salesman problem (PTSP). PTSP is a single-player game adaptation of the classical traveling salesman problem that makes use of a simple physics model: the player has to visit a number of waypoints as quickly as possible by navigating a ship in real time across an obstacle-filled 2-D map. The difficulty of this game depends on the distribution of waypoints and obstacles across the 2-D plane. Due to the physics of the game, the shortest route is not necessarily the fastest, as the ship's momentum makes it difficult to turn sharply at high speed. This paper proposes an evolutionary approach to obtaining maps where the optimal solution is not immediately obvious. In particular, any optimal route for these maps should differ distinctively from: 1) the optimal distance-based TSP route and 2) the route that corresponds to always approaching the nearest waypoint first. To achieve this, the evolutionary algorithm covariance matrix adaptation-evolutionary strategy (CMA-ES) is employed, where maps, indirectly represented as vectors of real numbers, are evolved to differentiate maximally between a game-playing agent that follows two or more different routes. The results presented in this paper show that CMA-ES is able to generate maps that fulfil the desired conditions.

In this paper we investigate the suitability of the arcade game Ms. Pac-Man, as implemented in the recent Pac-Man versus Ghost Teams Competition, as a testbed for competitive coevolution. To that end, we explore competitive co-evolution techniques to co-evolve Pac-Man and Ghosts team controllers. We analyze in some detail the dynamics of evolution between the two classes and compare them with single-objective evolution and static controllers. We note differences between evolutions of the two classes, having observed higher fitness transitivity in Pac-Man than in the Ghosts. The problem of finding a well-performing general purpose Pac-Man is far different than that of finding a good and general Ghosts controller.

We present a new evolutionary algorithm for community structure detection in both undirected and unweighted (sparse) graphs and fully connected weighted digraphs (complete networks). Previous investigations have found that, although evolutionary computation can identify community structure in complete networks, this approach seems to scale badly due to solutions with the wrong number of communities dominating the population. The new algorithm is based on a niching model, where separate compartments of the population contain candidate solutions with different numbers of communities. We experimentally compare the new algorithm to the well-known algorithms of Pizzuti and Tasgin, and find that we outperform those algorithms for sparse graphs under some conditions, and drastically outperform them on complete networks under all tested conditions.

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.

This paper aims at detecting the presence of group structures in complex artificial societies by solely observing and analysing the interactions occurring among the artificial agents. Our approach combines: (1) an unsupervised method for clustering interactions into two possible classes, namely in-group and out-group, (2) reinforcement learning for deriving the existing levels of collaboration within the society, and (3) an evolutionary algorithm for the detection of group structures and the assignment of group identities to the agents. Under a case study of static societies - i.e. the agents do not evolve their social preferences - where agents interact with each other by means of the Ultimatum Game, our approach proves to be successful for small-sized social networks independently on the underlying social structure of the society; promising results are also registered for mid-size societies.

Geometric differential evolution (GDE) is a recently introduced formal generalization of traditional differential evolution (DE) that can be used to derive specific differential evolution algorithms for both continuous and combinatorial spaces retaining the same geometric interpretation of the dynamics of the DE search across representations. In this article, we first review the theory behind the GDE algorithm, then, we use this framework to formally derive specific GDE for search spaces associated with binary strings, permutations, vectors of permutations and genetic programs. The resulting algorithms are representation-specific differential evolution algorithms searching the target spaces by acting directly on their underlying representations. We present experimental results for each of the new algorithms on a number of well-known problems comprising NK-landscapes, TSP, and Sudoku, for binary strings, permutations, and vectors of permutations. We also present results for the regression, artificial ant, parity, and multiplexer problems within the genetic programming domain. Experiments show that overall the new DE algorithms are competitive with well-tuned standard search algorithms.

What are the aesthetics of platform games and what makes a platform level engaging, challenging, and/or frustrating? We attempt to answer such questions through mining a large set of crowdsourced gameplay data of a clone of the classic platform game Super Mario Bros (SMB). The data consist of 40 short game levels that differ along six key level design parameters. Collectively, these levels are played 1560 times over the Internet, and the perceived experience is annotated by experiment participants via self-reported ranking (pairwise preferences). Given the wealth of this crowdsourced data, as all details about players' in-game behavior are logged, the problem becomes one of extracting meaningful numerical features at the appropriate level of abstraction for the construction of generic computational models of player experience and, thereby, game aesthetics. We explore dissimilar types of features, including direct measurements of event and item frequencies, and features constructed through frequent sequence mining, and go through an in-depth analysis of the interrelationship between level content, players' behavioral patterns, and reported experience. Furthermore, the fusion of the extracted features allows us to predict reported player experience with a high accuracy, even from short game segments. In addition to advancing our insight on the factors that contribute to platform game aesthetics, the results are useful for the personalization of game experience via automatic game adaptation.

In this paper we use the popular card game Dominion as a complex test-bed for the generation of interesting and balanced game rules. Dominion is a trading-card-like game where each card type represents a different game mechanic. Each playthrough only features ten different cards, the selection of which can form a new game each time. We compare and analyse three different agents that are capable of playing Dominion on different skill levels and use three different fitness functions to generate balanced card sets. Results reveal that there are particular cards of the game that lead to balanced games independently of player skill and behaviour. The approach taken could be used to balance other games with decomposable game mechanics.

We propose, discuss and exemplify data games. A data game is a game that allows the player(s) to explore data that is derived from outside the game, by transforming the data into something that can be played with. The transformation takes the form of procedural content generation based on real-world data. As an example of a data game, we briefly describe Open Data Monopoly.

We present an approach to learning to recognize concurrent activities based on multiple data streams. One example is recognition of concurrent activities in hospital operating rooms based on multiple wearable and embedded sensors. This problem differs from standard time series classification in that there is no natural single target dimension, as multiple activities are performed at the same time. Hence, most existing approaches fail. The key innovations that allow us to tackle this problem is (1) learning to recognize base activities from raw sensor data, (2) creating artificial joint activities from base activities using frequent pattern mining and (3) handling temporal dependency using virtual evidence boosting.

This paper presents a recommender system for teams of medical professionals working collaboratively in hospital operating rooms. The system recommends relevant virtual actions, such as retrieval of information resources and initiation of communication with professionals outside the operating rooms. Recommendations are based on the current state of the ongoing operation as recognised from sensor data using machine learning techniques. The selection and non-selection of virtual actions during operations are interpreted as implicit feedback and used to update the weight matrices that guide recommendations. A pilot user study involving medical professionals indicates that the adaptation mechanism is effective and that the system provides adequate recommendations.

This paper describes the Mario AI benchmark, a game-based benchmark for reinforcement learning algorithms and game AI techniques developed by the authors. The benchmark is based on a public domain clone of Nintendo's classic platform game Super Mario Bros, and completely open source. During the last two years, the benchmark has been used in a number of competitions associated with international conferences, and researchers and students from around the world have contributed diverse solutions to try to beat the benchmark. The paper summarizes these contributions, gives an overview of the state of the art in Mario-playing AIs, and chronicles the development of the benchmark. This paper is intended as the definitive point of reference for those using the benchmark for research or teaching.

This paper introduces a search-based approach to personalized content generation with respect to visual aesthetics. The approach is based on a two-step adaptation procedure where: 1) the evaluation function that characterizes the content is adjusted to match the visual aesthetics of users; and 2) the content itself is optimized based on the personalized evaluation function. To test the efficacy of the approach, we design fitness functions based on universal properties of visual perception, inspired by psychological and neurobiological research. Using these visual properties, we generate aesthetically pleasing 2-D game spaceships via neuroevolutionary constrained optimization and evaluate the impact of the designed visual properties on the generated spaceships. The offline generated spaceships are used as the initial population of an interactive evolution experiment in which players are asked to choose spaceships according to their visual taste: the impact of the various visual properties is adjusted based on player preferences and new content is generated online based on the updated computational model of visual aesthetics of the player. Results are presented that show the potential of the approach in generating content which is based on subjective criteria of visual aesthetics.

The aim of this paper is to introduce the use of Tower Defence (TD) games in Computational Intelligence (CI) research. We show how TD games can provide an important test-bed for the often under-represented casual games research area. Additionally, the use of CI in the TD games has the potential to create a more interesting, interactive and ongoing game experience for casual gamers. We present a definition of the current state and development of TD games, and include a classification of TD game components. We then describe some potential ways CI can be used to augment the TD experience. Finally, a prototype TD game based on experience driven procedural content generation is presented.

Procedural content generation (PCG) is an increasingly important area of technology within modern human-computer interaction (HCI) design. Personalization of user experience via affective and cognitive modeling, coupled with real-time adjustment of the content according to user needs and preferences are important steps toward effective and meaningful PCG. Games, Web 2.0, interface, and software design are among the most popular applications of automated content generation. The paper provides a taxonomy of PCG algorithms and introduces a framework for PCG driven by computational models of user experience. This approach, which we call Experience-Driven Procedural Content Generation (EDPCG), is generic and applicable to various subareas of HCI. We employ games as an example indicative of rich HCI and complex affect elicitation, and demonstrate the approach's effectiveness via dissimilar successful studies.

The Level Generation Competition, part of the IEEE Computational Intelligence Society (CIS)-sponsored 2010 Mario AI Championship, was to our knowledge the world's first procedural content generation competition. Competitors participated by submitting level generators - software that generates new levels for a version of Super Mario Bros tailored to individual players' playing style. This paper presents the rules of the competition, the software used, the scoring procedure, the submitted level generators, and the results of the competition. We also discuss what can be learned from this competition, both about organizing procedural content generation competitions and about automatically generating levels for platform games. The paper is coauthored by the organizers of the competition (the first three authors) and the competitors.

The eight papers in this special issue focus on procedural content generation in games. They present a good combination of surveys, conceptual frameworks, innovative methods, and applications.

The focus of this survey is on research in applying evolutionary and other metaheuristic search algorithms to automatically generating content for games, both digital and nondigital (such as board games). The term search-based procedural content generation is proposed as the name for this emerging field, which at present is growing quickly. A taxonomy for procedural content generation is devised, centering on what kind of content is generated, how the content is represented and how the quality/fitness of the content is evaluated; search-based procedural content generation in particular is situated within this taxonomy. This article also contains a survey of all published papers known to the authors in which game content is generated through search or optimisation, and ends with an overview of important open research problems.

The Nelder-Mead Algorithm (NMA) is an almost half-century old method for numerical optimization, and it is a close relative of Particle Swarm Optimization (PSO) and Differential Evolution (DE). In recent work, PSO, DE and NMA have been generalized using a formal geometric framework that treats solution representations in a uniform way. These formal algorithms can be used as templates to derive rigorously specific PSO, DE and NMA for both continuous and combinatorial spaces retaining the same geometric interpretation of the search dynamics of the original algorithms across representations. In previous work, a geometric NMA was derived for the binary string representation. In this paper, we advance this line of research and derive formally a specific NMA for the permutation representation. The result is a Nelder-Mead Algorithm searching the space of permutations by acting directly on this representation. We present initial experimental results for the new algorithm on the Traveling Salesman Problem. The peculiar geometry of the permutation space seems to affect the performance of the geometric NMA that does not perform as well as the NMA for the binary string representation. We present a discussion about the nature of permutation spaces that seeks to explain this phenomenon. Further study is required to understand if this is a fundamental limitation of the application of the geometric NMA to permutation spaces.

This paper describes the 2009 Mario AI Competition, which was run in association with the IEEE Games Innovation Conference and the IEEE Symposium on Computational Intelligence and Games. The focus of the competition was on developing controllers that could play a version of Super Mario Bros as well as possible. We describe the motivations for holding this competition, the challenges associated with developing artificial intelligence for platform games, the software and API developed for the competition, the competition rules and organization, the submitted controllers and the results. We conclude the paper by discussing what the outcomes of the competition can teach us both about developing platform game AI and about organizing game AI competitions. The first two authors are the organizers of the competition, while the third author is the winner of the competition.

In this paper, we overview the 2009 Simulated Car Racing Championship-an event comprising three competitions held in association with the 2009 IEEE Congress on Evolutionary Computation (CEC), the 2009 ACM Genetic and Evolutionary Computation Conference (GECCO), and the 2009 IEEE Symposium on Computational Intelligence and Games (CIG). First, we describe the competition regulations and the software framework. Then, the five best teams describe the methods of computational intelligence they used to develop their drivers and the lessons they learned from the participation in the championship. The organizers provide short summaries of the other competitors. Finally, we summarize the championship results, followed by a discussion about what the organizers learned about 1) the development of high-performing car racing controllers and 2) the organization of scientific competitions.

In this paper, we use computational intelligence techniques to built quantitative models of player experience for a platform game. The models accurately predict certain key affective states of the player based on both gameplay metrics that relate to the actions performed by the player in the game, and on parameters of the level that was played. For the experiments presented here, a version of the classicSuper Mario Brosgame is enhanced with parameterizable level generation and gameplay metrics collection. Player pairwise preference data is collected using forced choice questionnaires, and the models are trained using this data and neuroevolutionary preference learning of multilayer perceptrons (MLPs). The derived models will be used to optimize design parameters for particular types of player experience, allowing the designer to automatically generate unique levels that induce the desired experience for the player.

The problem of how to create NPC AI for videogames that believably imitates particular human players is addressed. Previous approaches to learning player behaviour is found to either not generalize well to new environments and noisy perceptions, or to not reproduce human behaviour in sufficient detail. It is proposed that better solutions to this problem can be built on multiobjective evolutionary algorithms, with objectives relating both to traditional progress-based fitness (playing the game well) and similarity to recorded human behaviour (behaving like the recorded player). This idea is explored in the context of a modern racing game.

Geometric particle swarm optimization (GPSO) is a recently introduced formal generalization of a simplified form of traditional particle swarm optimization (PSO) without the inertia term that applies naturally to both continuous and combinatorial spaces. In this paper, we propose an extension of GPSO, the inertial GPSO (IGPSO), that generalizes the traditional PSO endowed with the full equation of motion of particles to generic search spaces. We then formally derive the specific IGPSO for the Hamming space associated with binary strings and present experimental results for this new algorithm.

Geometric Particle Swarm Optimization (GPSO) is a recently introduced formal generalization of traditional Particle Swarm Optimization (PSO) that applies naturally to both continuous and combinatorial spaces. Differential Evolution (DE) is similar to PSO but it uses different equations governing the motion of the particles. This paper generalizes the DE algorithm to combinatorial search spaces extending its geometric interpretation to these spaces, analogously as what was done for the traditional PSO algorithm. Using this formal algorithm, Geometric Differential Evolution (GDE), we formally derive the specific GDE for the Hamming space associated with binary strings and present experimental results on a standard benchmark of problems.

We present the memetic climber, a simple search algorithm that learns topology and weights of neural networks on different time scales. When applied to the problem of learning control for a simulated racing task with carefully selected inputs to the neural network, the memetic climber outperforms a standard hill-climber. When inputs to the network are less carefully selected, the difference is drastic. We also present two variations of the memetic climber and discuss the generalization of the underlying principle to population-based neuroevolution algorithms.

Geometric particle swarm optimization (GPSO) is a recently introduced formal generalization of traditional particle swarm optimization (PSO) that applies naturally to both continuous and combinatorial spaces. In this paper we apply GPSO to the space of genetic programs represented as expression trees, uniting the paradigms of genetic programming and particle swarm optimization. The result is a particle swarm flying through the space of genetic programs. We present initial experimental results for our new algorithm.

Multi-objective optimisation is applied to encourage the effective use of state variables in car controlling programs evolved using Genetic Programming. Three different metrics for measuring the use of state within a program are introduced. Comparisons are performed among multi- and single-objective fitness functions with respect to learning speed and final fitness of evolved individuals, and attempts are made at understanding whether there is a trade-off between good performance and stateful controllers in this problem domain.

Multi-population competitive co-evolution is explored as a way of developing controllers for a simple (but definitely not trivial) car racing game. The three main uses we see for this method are to evolve more complex general intelligence than would be possible with other methods, to compare different evolvable architectures for controllers, and to develop behaviourally diverse populations of agents for computer games. Nine-population co-evolution is compared with single-population co-evolution and standard evolution strategies, steady-state and generational versions of the algorithm are compared, and a number of different controller architectures are compared with each other.

Several different controller representations are compared on anon-trivial problem in simulated car racing, with respect tolearning speed and final fitness. The controller representations arebased either on Neural Networks or Genetic Programming, and alsodiffer in regards to whether they allow for stateful controllers orjust reactive ones. Evolved GP trees are analysed, and attempts aremade at explaining the performance differences observed.

Over the last years, researchers have added neutrality in the evolutionary search in the hope that it can aid evolution. In this paper, we study the presence of neutrality that is already and to do so, we analised the fitness landscape of the Sudoku problem. How and why neutrality affects evolutionary search is a reasonably well-studied but still not clearly understood topic. Here, we use neutral walks, neutrality trajectories and fitness distance correlation to attempt to throw new light on this topic.

Geometric particle swarm optimization (GPSO) is a recentlyintroduced generalization of traditional particle swarm optimization(PSO) that applies to all combinatorial spaces. The aim of thispaper is to demonstrate the applicability of GPSO to non-trivialcombinatorial spaces. The Sudoku puzzle is a perfect candidate totest new algorithmic ideas because it is entertaining andinstructive as well as a non-trivial constrained combinatorialproblem. We apply GPSO to solve the sudoku puzzle.

The problem of how to acquire a model of a physical robot,which is fit for evolution of controllers that can subsequently be used to control that robot, is considered in the context of racing a radio-controlled toy car around a randomised track. Several modelling techniques are compared, and the specific properties of the acquired models that influence the quality of the evolved controller are discussed. As we aim tominimise the amount of domain knowledge used, we furtherinvestigate the relation between the assumptions about the modelled system made by particular modelling techniques and the suitability of the acquired models as bases for controller evolution. We find that none of the models acquired is good enough on its own, and that a key to evolving robustbehaviour is to evaluate controllers simultaneously on multiple models during evolution. Examples of successfully evolved racing control for the physical car are analysed.

In this paper we try to develop predictors in order to drive a simulated car around a track without the most recent sensor data. In order to test the predictive abilities of our car we developed two experiments: one where the sensor data was interrupted for a certain time and another where the sensor data is constantly delayed by a certain amount. The predictors are based on neural networks, and we compare backpropagation and evolutionary computation as methods of training these. In the end we found that predictors with good driving performance do not sample the set of predictors which minimize the prediction error in the sensors

Geometric crossover is a representation-independent definition of crossover based on the distance of the search space interpreted as a metric space. It generalizes the traditional crossover for binary strings and other important recombination operators for the most used representations. Using a distance tailored to the problem at hand, the abstract definition of crossover can be used to design new problem specific crossovers that embed problem knowledge in the search. In recent work, we have introduced the important notion of product geometric crossover that enables the construction of new geometric crossovers combining preexisting geometric crossovers in a simple way. In this paper, we use it to design an evolutionary algorithm to solve the Sudoku puzzle. The different types of constraints make Sudoku an interesting study case for crossover design. We conducted extensive experimental testing and found that, on medium and hard problems, the new geometric crossovers perform significantly better than hill-climbers and mutations alone.

The problem of the automatic development of controllers for vehicles for which the exact characteristics are not known is considered in the context of miniature helicopter flocking. A methodology is proposed in which neural network based controllers are evolved in a simulation using a dynamic model qualitatively similar to the physical helicopter. Several network architectures and evolutionary sequences are investigated, and two approaches are found that can evolve very competitive controllers. The division of the neural network into modules and of the task into incremental steps seems to be a precondition for success, and we analyse why this might be so.

Neural network-based controllers arc evolved for racing simulated R/C cars around several tracks of varying difficulty. The transferability of driving skills acquired when evolving for a single track is evaluated, and different ways of evolving controllers able to perform well on many different tracks are investigated, ft is further shown that such generally proficient controllers can reliably be developed into specialized controllers for individual tracks. Evolution of sensor parameters together with network weights is shown to lead to higher final fitness, but only if turned on after a general controller is developed, otherwise it hinders evolution, ft is argued that simulated car racing is a scalable and relevant testbed for evolutionary robotics research, and that the results of this research can be useful for commercial computer games.

This paper describes the evolution of controllers for racing a simulated radio-controlled car around a track, modelled on a real physical track. Five different controller architectures were compared, based on neural networks, force fields and action sequences. The controllers use egocentric (first person), Newtonian (third person) or no information about the state of the car (open-loop controller). The only controller that able to evolve good racing behaviour was based on neural network acting on egocentric inputs.