Similarity estimation is essential for many game AI applications, from the procedural generation of distinct assets to automated exploration with game-playing agents. While similarity metrics often substitute human evaluation, their alignment with our judgement is unclear. Consequently, the result of their application can fail human expectations, leading to e.g. unappreciated content or unbelievable agent behaviour. We alleviate this gap through a multi-factorial study of two tile-based games in two representations, where participants (N=456) judged the similarity of level triplets. Based on this data, we construct domain-specific perceptual spaces, encoding similarity-relevant attributes. We compare 12 metrics to these spaces and evaluate their approximation quality through several quantitative lenses. Moreover, we conduct a qualitative labelling study to identify the features underlying the human similarity judgement in this popular genre. Our findings inform the selection of existing metrics and highlight requirements for the design of new similarity metrics benefiting game development and research.

Generative adversarial networks (GANs) are a powerful indirect genotype-to-phenotype mapping for evolutionary search. Much previous work applying GANs to level generation focuses on fixed-size segments combined into a whole level, but individual segments may not fit together cohesively. In contrast, segments in human designed levels are often repeated, directly or with variation, and organized into patterns (the symmetric eagle in Level 1 ofThe Legend of Zelda, or repeated pipe motifs inSuper Mario Bros.). Such patterns can be produced with compositional pattern producing networks (CPPNs). CPPNs define latent vector GAN inputs as a function of geometry, organizing segments output by a GAN into complete levels. However, collections of latent vectors can also be evolved directly, producing more chaotic levels. We propose a hybrid approach that evolves CPPNs first, but allows latent vectors to evolve later, combining the benefits of both approaches. These approaches are evaluated inSuper Mario Bros. andThe Legend of Zelda. We previously demonstrated via a quality-diversity algorithm that CPPNs better cover the space of possible levels than directly evolved levels. Here, we show that the hybrid approach first, covers areas that neither of the other methods can, and second, achieves comparable or superior quality diversity (QD) scores.

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.

While games have been used extensively as mile-stones to evaluate game-playing AI, there exists no standardised framework for reporting the obtained observations. As a result, it remains difficult to draw general conclusions about the strengths and weaknesses of different game-playing AI algorithms. In this paper, we propose reporting guidelines for AI game-playing performance that, if followed, provide information suitable for unbiased comparisons between different AI approaches. The vision we describe is to build benchmarks and competitions based on such guidelines in order to be able to draw more general conclusions about the behaviour of different AI algorithms, as well as the types of challenges different games pose.

Generative Adversarial Networks (GANs) are an emerging form of indirect encoding. The GAN is trained to induce a latent space on training data, and a real-valued evolutionary algorithm can search that latent space. Such Latent Variable Evolution (LVE) has recently been applied to game levels. However, it is hard for objective scores to capture level features that are appealing to players. Therefore, this paper introduces a tool for interactive LVE of tile-based levels for games. The tool also allows for direct exploration of the latent dimensions, and allows users to play discovered levels. The tool works for a variety of GAN models trained for both Super Mario Bros. and The Legend of Zelda, and is easily generalizable to other games. A user study shows that both the evolution and latent space exploration features are appreciated, with a slight preference for direct exploration, but combining these features allows users to discover even better levels. User feedback also indicates how this system could eventually grow into a commercial design tool, with the addition of a few enhancements.

Generative Adversarial Networks (GANs) are proving to be a powerful indirect genotype-to-phenotype mapping for evolutionary search, but they have limitations. In particular, GAN output does not scale to arbitrary dimensions, and there is no obvious way of combining multiple GAN outputs into a cohesive whole, which would be useful in many areas, such as the generation of video game levels. Game levels often consist of several segments, sometimes repeated directly or with variation, organized into an engaging pattern. Such patterns can be produced with Compositional Pattern Producing Networks (CPPNs). Specifically, a CPPN can define latent vector GAN inputs as a function of geometry, which provides a way to organize level segments output by a GAN into a complete level. This new CPPN2GAN approach is validated in both Super Mario Bros. and The Legend of Zelda. Specifically, divergent search via MAP-Elites demonstrates that CPPN2GAN can better cover the space of possible levels. The layouts of the resulting levels are also more cohesive and aesthetically consistent.

This paper examines learning approaches for forward models based on local cell transition functions. We provide a formal definition of local forward models for which we propose two basic learning approaches. Our analysis is based on the game Sokoban, where a wrong action can lead to an unsolvable game state. Therefore, an accurate prediction of an action’s resulting state is necessary to avoid this scenario.In contrast to learning the complete state transition function, local forward models allow extracting multiple training examples from a single state transition. In this way, the Hash Set model, as well as the Decision Tree model, quickly learn to predict upcoming state transitions of both the training and the test set. Applying the model using a statistical forward planner showed that the best models can be used to satisfying degree even in cases in which the test levels have not yet been seen.Our evaluation includes an analysis of various local neighbourhood patterns and sizes to test the learners’ capabilities in case too few or too many attributes are extracted, of which the latter has shown do degrade the performance of the model learner.

This paper investigates the effect of learning a forward model on the performance of a statistical forward planning agent. We transform Conway's Game of Life simulation into a single-player game where the objective can be either to preserve as much life as possible or to extinguish all life as quickly as possible. In order to learn the forward model of the game, we formulate the problem in a novel way that learns the local cell transition function by creating a set of supervised training data and predicting the next state of each cell in the grid based on its current state and immediate neighbours. Using this method we are able to harvest sufficient data to learn perfect forward models by observing only a few complete state transitions, using either a look-up table, a decision tree, or a neural network. In contrast, learning the complete state transition function is a much harder task and our initial efforts to do this using deep convolutional auto-encoders were less successful.We also investigate the effects of imperfect learned models on prediction errors and game-playing performance, and show that even models with significant errors can provide good performance.

The analysis of games or game content, e.g. in the context of AI-assisted game design and search-based PCG, is often based on playthroughs that are generated by simulating human decisions using AI players. With this paper, we hope to encourage more systematic analyses of uncertainties and errors potentially introduced by simulating human decisions in this context. To this end, we conduct a case study on StarCraft II to demonstrate the potential effects of these uncertainties. We construct two usecases from an analysis of existing approaches in research that employ simulations of human decisions through game AI. We are able to demonstrate large impacts of the simulations and finally discuss how the resulting uncertainties can be controlled in future work.

This paper provides a detailed investigation of using the Kullback-Leibler (KL) Divergence as a way to compare and analyse game-levels, and hence to use the measure as the objective function of an evolutionary algorithm to evolve new levels. We describe the benefits of its asymmetry for level analysis and demonstrate how (not surprisingly) the quality of the results depends on the features used. Here we use tile-patterns of various sizes as features.

Despite a large interest in real-world problems from the research field of evolutionary optimisation, established benchmarks in the field are mostly artificial. We propose to use game optimisation problems in order to form a benchmark and implement function suites designed to work with the established COCO benchmarking framework. Game optimisation problems are real-world problems that are safe, reasonably complex and at the same time practical, as they are relatively fast to compute. We have created four function suites based on two optimisation problems previously published in the literature (TopTrumps and MarioGAN). For each of the applications, we implemented multiple instances of several scalable single- and multi-objective functions with different characteristics and fitness landscapes. Our results prove that game optimisation problems are interesting and challenging for evolutionary algorithms.

Generative Adversarial Networks (GANs) are a machine learning approach capable of generating novel example outputs across a space of provided training examples. Procedural Content Generation (PCG) of levels for video games could benefit from such models, especially for games where there is a pre-existing corpus of levels to emulate. This paper trains a GAN to generate levels for Super Mario Bros using a level from the Video Game Level Corpus. The approach successfully generates a variety of levels similar to one in the original corpus, but is further improved by application of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). Specifically, various fitness functions are used to discover levels within the latent space of the GAN that maximize desired properties. Simple static properties are optimized, such as a given distribution of tile types. Additionally, the champion A* agent from the 2009 Mario AI competition is used to assess whether a level is playable, and how many jumping actions are required to beat it. These fitness functions allow for the discovery of levels that exist within the space of examples designed by experts, and also guide the search towards levels that fulfill one or more specified objectives.

Uncertainty propagation is a technique to incorporate individuals with uncertain fitness estimates in evolutionary algorithms. The Surrogate-Assisted Partial Order-Based Evolutionary Optimisation Algorithm (SAPEO) uses uncertainty propagation of fitness predictions from a Kriging model to reduce the number of function evaluations. The fitness predictions are ranked with partial orders and the corresponding individuals are only evaluated if they are indistinguishable otherwise or the risk of uncertainty propagation exceeds a steadily decreasing error tolerance threshold. In this paper, we investigate the effects of using uncertainty propagation according to SAPEO on single-objective problems. To this end, we present and apply different ways of measuring the deviations of SAPEO from the underlying CMA-ES. We benchmark the algorithms on the BBOB testbed to assess the effects of uncertainty propagation on their performance throughout the runtime of the algorithm on a variety of problems. Additionally, we examine thoroughly the differences per iteration between the evolution paths of SAPEO and CMA-ES based on a model for the rank-one update. The BBOB results suggest that the success of SAPEO generally improves the performance but depends heavily on function and dimension, which is supported by the analysis of the evolution paths.

Game balancing is an important part of the (computer) game design process, in which designers adapt a game prototype so that the resulting gameplay is as entertaining as possible. In industry, the evaluation of a game is often based on costly playtests with human players. It suggests itself to automate this process using artificial players for the prediction of gameplay and outcome. In this paper, the feasibility of automatic balancing is investigated for the card game top trumps using simulation- and deck-based objectives. Additionally, the necessity of a multi-objective approach is asserted by assessing the only published (single-objective) method. We apply a multi-objective evolutionary algorithm to obtain decks that optimise objectives developed to express the fairness and the excitement of a game of top trumps, e.g. win rate and average number of tricks. The results are compared with decks from published top trumps games using the aforementioned objectives. The possibility to generate decks better or at least as good as decks from published top trumps decks in terms of these objectives is demonstrated. Our results indicate that automatic balancing with the presented approach is feasible even for more complex games such as real-time strategy games.