In Social Deduction Games (SDGs) such as Avalon, Mafia, and Werewolf, players conceal their identities and deliberately mislead others, making hidden-role inference a central and demanding task. Accurate role identification, which forms the basis of an agent's belief state, is therefore the keystone for both human and AI performance. We introduce CSP4SDG, a probabilistic, constraint–satisfaction framework that analyses gameplay objectively. Game events and dialogue are mapped to four linguistically agnostic constraint classes—evidence, phenomena, assertions, and hypotheses. Hard constraints prune impossible role assignments, while weighted soft constraints score the remainder; information-gain weighting links each hypothesis to its expected value under entropy reduction, and a simple closed-form scoring rule guarantees that truthful assertions converge to classical hard logic with minimum error. The resulting posterior over roles is fully interpretable and updates in real time. Experiments on three public datasets show that CSP4SDG (i) outperforms LLM-based baselines in every inference scenario, and (ii) boosts LLMs when supplied as an auxiliary "reasoning tool." Our study validates that principled probabilistic reasoning with information theory is a scalable alternative—or complement—to heavy-weight neural models for SDGs.

This study introduces Adapter-RL, a novel architecture aimed at improving the performance of existing agents in reinforcement learning tasks. The approach integrates human-knowledge-based systems with deep reinforcement learning, combining the interpretability and rule-based logic of the former with the adaptive learning capabilities of the latter. A crucial aspect of this method is the use of “adapters”—concise modules integrated with a base-agent, designed to adjust the policy for specific tasks. The Adapter-RL framework comprises a base-agent responsible for initial decision-making and an adapter module that refines these decisions to meet task-specific requirements. The adapter facilitates efficient training, reduces parameter requirements, and mitigates catastrophic forgetting, enhancing overall performance and adaptability. This architecture enables agents to be fine-tuned effectively, allowing them to adapt to complex tasks with rapidly changing or uncertain conditions. The research demonstrates the efficacy of Adapter-RL through experiments in microRTS, a challenging real-time strategy game. The results demonstrate that Adapter-RL significantly accelerates the training process and outperforms base-agents across various tasks, highlighting its efficiency and robustness. In addition, the study investigates the temperature coefficient tradeoff in adapter training, finding that optimal performance is achievable within a broad range of coefficients. This underscores the stability of the method. The Adapter-RL method enables the specialization of base AI for specific characters or scenarios.

Single-player deduction games are a canonical form of hidden-information reasoning. Agents iteratively issue actions (queries) and receive deterministic feedback, thereby shrinking the information set of feasible secret codes. Classical search techniques-such as Information-Set Monte-Carlo Tree Search (ISMCTS) or the entropy-driven Information-Set Entropy Search (ISES)-handle these games by sampling or by fully enumerating states, but both methods encounter difficulties when the combinatorial space explodes. This paper introduces a constraintpropagation variant of ISES that models the information set as a constraint-satisfaction problem (CSP) and applies the AC-3 arcconsistency algorithm after every observation. By aggressively pruning unsupported variable values before entropy evaluation, the method eliminates a large number of impossible states and accelerates inference without sacrificing optimality. Using several single-player deduction games from the Deduction Game Framework as case studies, we show that constraint propagation significantly enhances the efficiency of ISES.

We introduce JSON Bag-of-Tokens model (JSONBag) as a method to generically represent game trajectories by tokenizing their JSON descriptions and apply Jensen-Shannon distance (JSD) as distance metric for them. Using a prototypebased nearest-neighbor search (P-NNS), we evaluate the validity of JSON-Bag with JSD on six tabletop games—7 Wonders, Dominion, Sea Salt and Paper, Can't Stop, Connect4, Dots and boxes—each over three game trajectory classification tasks: classifying the playing agents, game parameters, or game seeds that were used to generate the trajectories. Our approach outperforms a baseline using hand-crafted features in the majority of tasks. Evaluating on N -shot classification suggests using JSON-Bag prototype to represent game trajectory classes is also sample efficient. Additionally, we demonstrate JSON-Bag ability for automatic feature extraction by treating tokens as individual features to be used in Random Forest to solve the tasks above, which significantly improves accuracy on underperforming tasks. Finally, we show that, across all six games, the JSD between JSON-Bag prototypes of agent classes highly correlates with the distances between agents' policies.

Play style identification can provide valuable game design insights and enable adaptive experiences, with the potential to improve game playing agents. Previous work relies on domain knowledge to construct play trace representations using handcrafted features. More recent approaches incorporate the sequential structure of play traces but still require some level of domain abstraction. In this study, we explore the use of unsupervised CNN-LSTM autoencoder models to obtain latent representations directly from low-level play trace data in MicroRTS. We demonstrate that this approach yields a meaningful separation of different game playing agents in the latent space, reducing reliance on domain expertise and its associated biases. This latent space is then used to guide the exploration of diverse play styles within studied AI players.

This study investigates efficient AI agents for the multi-player deduction game Cluedo.We propose a knowledge representation method based on constraint satisfaction problems (CSPs) and formalize the deductive reasoning process into two key modules: knowledge updating and action selection, enabling the creation of multiple distinct AI agents.Experimental results demonstrate that constraint-solving methods can be effectively applied to build powerful Cluedo AI agents.

Games often incorporate random elements in the form of dice or shuffled card decks. This randomness is a key contributor to the player experience and the variety of game situations encountered. There is a tension between a level of randomness that makes the game interesting and contributes to the player's enjoyment of a game, and a level at which the outcome itself is effectively random and the game becomes dull. The optimal level for a game will depend on the design goals and target audience. We introduce a new technique to quantify the level of randomness in game outcome and use it to compare 15 tabletop games and disentangle the different contributions to the overall randomness from specific parts of some games. We further explore the interaction between game randomness and player skill, and how this innate randomness can affect error analysis in common game experiments.

This paper proposes an innovative approach to the Generalized Advantage Estimator (GAE) to address the bias-variance trade-off in truncated roll-outs during reinforcement learning. In typical GAE implementations, the k-step advantage is estimated using a lambda-weighted average, until the terminal state. While this method provides constant bias-variance properties at any time step, it often necessitates truncated roll-outs with shorter horizons for faster learning and policy updates within a single episode. This study highlights an unexplored issue: the bias-variance properties differ for small versus considerable time steps within truncated roll-outs. Specifically, smaller time steps may have a significant bias, prompting a need for their increase. The proposed solution involves a partial GAE update, calculating the advantage estimates for all time steps but updating the policy only for a specified range. To prevent data wastage, the data from this range is retained for further processing and policy parameter updates. This partial GAE approach, despite the increased memory requirements, promises enhanced computation speed and optimal data utilization. Empirical validation was conducted on four MuJoCo tasks and microRTS. The results show a performance improvement trend with the partial GAE estimator, outperforming regular GAE in task completion speed in microRTS. These findings offer a promising direction for improving policy update efficiency in reinforcement learning.

There are well-established methods for rating the relative skill of players such as Elo or TrueSkill ratings. This is not the case for rating games by their relative difficulty, or the level of ‘skill’ required to play them well. Previous work has proposed skill-traces as an answer to this question, which use data from games played between agents with progressively higher computational budgets to estimate the difficulty of the game (or skill-depth). We try to improve on previous work by expanding the algorithmic space considered and that this can radically change the ratings of some games. We then propose a new parameterised model for the level of skill a game requires and test this on a suite of multiplayer tabletop board games, concluding that the parameters can be usefully interpreted and provide a slightly better fit to human-estimates.

Tabletop games often incorporate random elements in the form of dice or shuffled card decks. This randomness is a key contributor to the player experience and the variety of game situations encountered. There is often a tension between a level of randomness that makes the game interesting, and a level at which the outcome itself is effectively random and the game becomes dull. The sweet-spot for any given game will depend on the design goals and target audience. We introduce a new technique to quantify the level of randomness in game outcome due to these elements. We use this to compare 15 different tabletop games, and then to disentangle the different contributions to the overall randomness from specific parts of the game. We show the utility of this approach by using it with a game publisher as a tool in the development phase of a new commercial board game.

We present a game framework tailored for deduction games, enabling structured analysis from the perspective of Shannon entropy variations. Additionally, we introduce a new forward search algorithm, Information Set Entropy Search (ISES), which effectively solves many single-player deduction games. The ISES algorithm, augmented with sampling techniques, allows agents to make decisions within controlled computational resources and time constraints. Experimental results on eight games within our framework demonstrate the significant superiority of our method over the Single Observer Information Set Monte Carlo Tree Search(SO-ISMCTS) algorithm under limited decision time constraints. The entropy variation of game states in our framework enables explainable decision-making, which can also be used to analyze the appeal of deduction games and provide insights for game designers.

We use AI agents to play successive design iterations of an analogue board game to understand the sorts of question a designer asks of a game, and how AI play-testing approaches can help answer these questions and reduce the need for time-consuming human play-testing. Our case study supports the view that AI play-testing can complement human testing, but can certainly not replace it. A core issue to be addressed is the extent to which the designer trusts the results of AI play-testing as sufficiently human-like. The majority of design changes are inspired from human play-testing, but AI play-testing helpfully complements these and often gave the designer the confidence to make changes faster where AI and humans ‘agreed’.

In a two-player zero-sum game, players classically want to maximise their chance of winning. When a game has more than two players, using the binary win rate as an objective is no longer such an obvious choice. A player might instead have the objective of doing as well as possible in terms of ranked order, or in maximising their score. We investigate the impact of different game-agnostic objectives in several popular tabletop games, and whether it can be better to use the game score as a proxy for winning. We find that the games considered largely fall into two groups. In one it is helpful to focus just on one’s own score during the game, and then shift to beating opponents only in the end-game. In the other, larger, group it is better to ‘Follow the Leader’ and constantly track one’s relative position to the opponents throughout the game.

In the realm of games research, artificial general intelligence algorithms often use score as the main reward signal for learning or playing actions. However, this has shown its limitations in scenarios where the rewards are very rare or absent until the end of the game. The problem is even more severe when the computational budget available is limited. This article proposes a new approach based on event logging: the game state triggers an event every time one of its features changes. These events are processed by an event-value function (EF) that assigns a value to a single action or a sequence. Experiments show that this approach can mitigate the problem of scarce rewards and improve the artificial intelligence performance compared with both the point-based heuristics and state-value functions. Furthermore, this represents a step forward in a finer control of the strategy adopted by the artificial agent, by describing a much richer and controllable behavioral space through EFs. Tuned EFs are able to neatly synthesize the relevance of the events in the game. Agents using an EF are also more robust when playing games with several opponents.

In this article, we present an approach to generate ateamof general video game playing agents with differentiated behaviors that can ultimately assist in the game development process. We consider the agent behavior as the corresponding outcomes of playing the game: rate of wins, score, exploration, enemies killed, items collected, etc. We create and identify agents that are expected to achieve particular goals but do not necessarily simulate human behavior during gameplay. We present a solution that, byheuristic diversification, provides a controller with different heuristics and a corresponding set ofweights, driving its actions. Given the simplicity of thisbehavior-encodingand its easiness to evolve, we use Multidimensional Archive of Phenotypic Elites to generate different solutions that elicit particular behaviors and assemble ateam. The resulting agents are allocated in a feature space, used to identify the expectations of each of them. We generate ateamfor four games of the General Video Game Artificial Intelligence framework and find six differentbehavior-typeagents in each. We include an experiment to check the portability of these agents when playing alternative levels and an exploratory work aiming to use them to detect design flaws in game levels.

The Fighting Game AI Competition (FTGAIC) provides a challenging benchmark for two-player video game artificial intelligence. The challenge arises from the large action space, diverse styles of characters and abilities, and the real-time nature of the game. In this article, we propose a novel algorithm that combines the rolling horizon evolution algorithm (RHEA) with opponent model learning. The approach is readily applicable to any two-player video game. In contrast to conventional RHEA, an opponent model is proposed and is optimized by supervised learning with cross-entropy and reinforcement learning with policy gradient and Q-learning respectively, based on history observations from opponent. The model is learned during the live gameplay. With the learned opponent model, the extended RHEA is able to make more realistic plans based on what the opponent is likely to do. This tends to lead to better results. We compared our approach directly with the bots from the FTGAIC 2018 competition and found our method to significantly outperform all of them for all three characters. Furthermore, our proposed bot with the policy gradient based opponent model is the only one without using Monte Carlo tree search among the top five bots in the 2019 competition in which it achieved second place, while using much less domain knowledge than the winner.

We introduce MultiTree Monte Carlo Tree Search (MT-MCTS), in which a tree is constructed independently for each player. This permits deeper search for the acting agent’s own move, at the cost of a poorer opponent model and the loss of conditioning a move on the specific action of another player.We test MT-MCTS in eleven different tabletop board and card games, with varying numbers of players. The main benefit occurs in simultaneous-move games, where independent trees better model the information structure. We find that in other games MT-MCTS can outperform vanilla MCTS, which incorporates all players in a single tree, but that this advantage usually decreases as the computational budget increases, and the cost of poor opponent modelling outweighs the gain from deeper search.

Game-playing evolutionary algorithms, specifically rolling horizon evolutionary algorithms (RHEA), have recently managed to beat the state of the art in win rate across many video games. However, the best results in a game are highly dependent on the specific configuration of modifications introduced over several papers, each adding additional parameters to the core algorithm. Furthermore, the best previously published parameters have been found from only a few human-picked combinations, as the possibility space has grown beyond exhaustive search. This article presents the state of the art in RHEA, combining all modifications described in the literature, as well as new ones. We then use a parameter optimizer, the$N$-tuple bandit evolutionary algorithm, to find the best combination of parameters in 20 games from the general video game Artificial Intelligence (AI) framework. Furthermore, we analyze the algorithm’s parameters and some interesting combinations revealed through the optimization process. Finally, we find new state of the art solutions on several games by automatically exploring the large parameter space of RHEA.

In this article, we compare four different “game spaces” in terms of their usefulness in characterizing multiplayer tabletop games, with a particular interest in any underlying change to a game’s characteristics as the number of players changes. In each case, we take a 16-D feature space and reduce it to a 2-D visualizable landscape. We find that a space obtained from optimization of parameters in Monte Carlo tree search is most directly interpretable to characterize our set of games in terms of the relative importance of imperfect information, adversarial opponents, and reward sparsity. These results do not correlate with a space defined using attributes of the game tree. This dimensionality reduction does not show any general effect as the number of players changes. Therefore, we consider the question using the original features to classify the games into two sets: 1) those for which the characteristics of the game change significantly as the number of players changes and 2) those for which there is no such effect.

We present some initial work on characterizing games using a visual ‘fingerprint’ generated from several independent optimisation runs over the parameters used in Monte Carlo Tree Search (MCTS). This ‘fingerprint’ provides a useful tool to compare games, as well as highlighting the relative sensitivity of a specific game to algorithmic variants of MCTS. The exploratory work presented here shows that in some games there is a major change in the optimal MCTS parameters when we move from 2-players to 3 or 4-players.

Opponent Modelling tries to predict the future actions of opponents, and is required to perform well in multiplayer games. There is a deep literature on learning an opponent model, but much less on how accurate such models must be to be useful. We investigate the sensitivity of Monte Carlo Tree Search (MCTS) and a Rolling Horizon Evolutionary Algorithm (RHEA) to the accuracy of their modelling of the opponent in a simple Real-Time Strategy game. We find that in this domain RHEA is much more sensitive to the accuracy of an opponent model than MCTS. MCTS generally does better even with an inaccurate model, while this will degrade RHEA's performance. We show that faced with an unknown opponent and a low computational budget it is better not to use any explicit model with RHEA, and to model the opponent's actions within the tree as part of the MCTS algorithm.

The General Video Game Artificial Intelligence (GVGAI) competition has been running for several years with various tracks. This paper focuses on the challenge of the GVGAI learning track in which 3 games are selected and 2 levels are given for training, while 3 hidden levels are left for evaluation. This setup poses a difficult challenge for current Reinforcement Learning (RL) algorithms, as they typically require much more data. This work investigates 3 versions of the Advantage Actor-Critic (A2C) algorithm trained on a maximum of 2 levels from the available 5 from the GVGAI framework and compares their performance on all levels. The selected sub-set of games have different characteristics, like stochasticity, reward distribution and objectives. We found that stochasticity improves the generalisation, but too much can cause the algorithms to fail to learn the training levels. The quality of the training levels also matters, different sets of training levels can boost generalisation over all levels. In the GVGAI competition agents are scored based on their win rates and then their scores achieved in the games. We found that solely using the rewards provided by the game might not encourage winning.

Access to a fast and easily copied forward model of a game is essential for model-based reinforcement learning and for algorithms such as Monte Carlo tree search, and is also beneficial as a source of unlimited experience data for model-free algorithms. Learning forward models is an interesting and important challenge in order to address problems where a model is not available. Building upon previous work on the Neural GPU, this paper introduces the Neural Game Engine, as a way to learn models directly from pixels. The learned models are able to generalize to different size game levels to the ones they were trained on without loss of accuracy. Results on 10 deterministic General Video Game AI games demonstrate competitive performance, with many of the games' models being learned perfectly both in terms of pixel predictions and reward predictions. The pre-trained models are available through the OpenAI Gym interface and are available publicly for future research here: https://github.com/Bam4d/Neural-Game-Engine.

In the realm of games research, Artificial General Intelligence algorithms often use score as main reward signal for learning or playing actions. However this has shown its severe limitations when the point rewards are very rare or absent until the end of the game. This paper proposes a new approach based on event logging: the game state triggers an event every time one of its features changes. These events are processed by an Event-value Function (EF) that assigns a value to a single action or a sequence. The experiments have shown that such approach can mitigate the problem of scarce point rewards and improve the AI performance. Furthermore this represents a step forward in controlling the strategy adopted by the artificial agent, by describing a much richer and controllable behavioural space through the EF. Tuned EF are able to neatly synthesise the relevance of the events in the game. Agents using an EF show more robust when playing games with several opponents.

In this paper, we are going to explain the design process for our GVGAI game-learning agent, which is going to be submitted to the GVGAI competition's learning track 2020. The agent relies on a local forward modeling approach, which uses predictions of future game-states to allow the application of simulation-based search algorithms. We first explain our process in identifying repeating tiles throughout a pixel-based state observation. Using the tile information, a local forward model is trained to predict the future state of each tile based on its current state and its surrounding tiles. We accompany this approach with a simple reward model, which determines the expected reward of a predicted state transition. The proposed approach has been tested using multiple games of the GVGAI framework. Results show that the approach seems to be especially feasible for learning how to play deterministic games. Except for one non-deterministic game, the agent performance is very similar to agents using the true forward model. Nevertheless, the prediction accuracy needs to be further improved to facilitate a better game-playing performance.

For general video game playing agents, the biggest challenge is adapting to the wide variety of situations they encounter and responding appropriately. Some success was recently achieved by modifying search-control parameters in agents on-line, during one play-through of a game. We propose adapting such methods for Rolling Horizon Evolutionary Algorithms, which have shown high performance in many different environments, and test the effect of on-line adaptation on the agent's win rate. On-line tuned agents are able to achieve results comparable to the state of the art, including first win rates in hard problems, while employing a more general and highly adaptive approach. We additionally include further insight into the algorithm itself, given by statistics gathered during the tuning process and highlight key parameter choices.

This demo paper describes a simple and practical approach to writing cross-platform casual games using the Kotlin programming language. A key aim is to make it much easier for researchers to demonstrate their AI playing a range of games. Pure Kotlin code (which excludes using any Java graphics libraries) can be transpiled to JavaScript and run in a web browser. However, writing Kotlin code that will run without modification both in a web browser and on the JVM is not trivial; it requires strict adherence to an appropriate methodology. The contribution of this paper is to provide such a method including a software design and to demonstrate this working for Tetris, played either by AI or human.

Having access to a forward model enables the use of planning algorithms such as Monte Carlo Tree Search and Rolling Horizon Evolution. Where a model is unavailable, a natural aim is to learn a model that reflects accurately the dynamics of the environment. In many situations it might not be possible and minimal glitches in the model may lead to poor performance and failure. This paper explores the problem of model misspecification through uncertainty-aware reinforcement learning agents. We propose a bootstrapped multi-headed neural network that learns the distribution of future states and rewards. We experiment with a number of schemes to extract the most likely predictions. Moreover, we also introduce a global error correction filter that applies high-level constraints guided by the context provided through the predictive distribution. We illustrate our approach on Minipacman. The evaluation demonstrates that when dealing with imperfect models, our methods exhibit increased performance and stability, both in terms of model accuracy and in its use within a planning algorithm.

This paper introduces a computer-game design tool which enables game designers to explore and develop game mechanics for arbitrary game systems. The tool is implemented as a plugin for the Godot game engine. It allows the designer to view an abstraction of a game's states while in active development and to quickly view and explore which states are navigable from which other states. This information is used to rapidly explore, validate and improve the design of the game. The tool is most practical for game systems which are computer-explorable within roughly 2000 states. The tool is demonstrated by presenting how it was used to create a small, yet complete, commercial game.

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.

One of the issues general AI game players are required to deal with is the different reward systems in the variety of games they are expected to be able to play at a high level. Some games may present plentiful rewards which the agents can use to guide their search for the best solution, whereas others feature sparse reward landscapes that provide little information to the agents. The work presented in this paper focuses on the latter case, which most agents struggle with. Thus, modifications are proposed for two algorithms, Monte Carlo Tree Search and Rolling Horizon Evolutionary Algorithms, aiming at improving performance in this type of games while maintaining overall win rate across those where rewards are plentiful. Results show that longer rollouts and individual lengths, either fixed or responsive to changes in fitness landscape features, lead to a boost of performance in the games during testing without being detrimental to non-sparse reward scenarios.

Game-based benchmarks have been playing an essential role in the development of Artificial Intelligence (AI) techniques. Providing diverse challenges is crucial to push research toward innovation and understanding in modern techniques. Rinascimento provides a parameterised partially-observable multiplayer card-based board game, these parameters can easily modify the rules, objectives and items in the game. We describe the framework in all its features and the game-playing challenge providing baseline game-playing AIs and analysis of their skills. We reserve to agents' hyper-parameter tuning a central role in the experiments highlighting how it can heavily influence the performance. The base-line agents contain several additional contribution to Statistical Forward Planning algorithms.

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.

The space of Artificial Intelligence entities is dominated by conversational bots. Some of them fit in our pockets and we take them everywhere we go, or allow them to be a part of human homes. Siri, Alexa, they are recognised as present in our world. But a lot of games research is restricted to existing in the separate realm of software. We enter different worlds when playing games, but those worlds cease to exist once we quit. Similarly, AI game-players are run once on a game (or maybe for longer periods of time, in the case of learning algorithms which need some, still limited, period for training), and they cease to exist once the game ends. But what if they didn't? What if there existed artificial game-players that continuously played games, learned from their experiences and kept getting better? What if they interacted with the real world and us, humans: live-streaming games, chatting with viewers, accepting suggestions for strategies or games to play, forming opinions on popular game titles? In this paper, we introduce the vision behind a new project called Thyia, which focuses around creating a present, continuous, `always-on', interactive game-player.

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 Games Fusion Project was an experimental learning experience that mirrored commercial realities and processes in order to wrap the core game-making skills in a fusion of wider industry-relevant competencies. This provided both contextual knowledge and exposed participants to failure and reflection, foregrounding the importance of iterative learning loops, foundational in creative digital industry design processes as well as (experiential) learning paradigms. This project has explored how the relevance of game design for education lies not only in the creative, communication and project management competencies exposed in the game design process but also how this can be abstracted to inform project curriculum development more widely.

There are few digital tools to help designers create game mechanics. A general language to express game mechanics is necessary for rapid game design iteration. The first iteration of a mechanics-focused language, together with its interfacing tool, are introduced in this paper. The language is restricted to two-dimensional, turn-based, tile-based, deterministic, complete-information games. The tool is compared to the existing alternatives for game mechanics prototyping and shown to be capable of succinctly implementing a range of well-known game mechanics.

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.

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.

Modern genetic programming (GP) operates within the statistical machine learning (SML) framework. In this framework, evolution needs to balance between approximation of an unknown target function on the training data and generalization, which is the ability to predict well on new data. This paper provides a survey and critical discussion of SML methods that enable GP to generalize.

This paper describes the N-Tuple Bandit Evolutionary Algorithm (NTBEA), an optimisation algorithm developed for noisy and expensive discrete (combinatorial) optimisation problems. The algorithm is applied to two game-based hyperparameter optimisation problems. The N-Tuple system directly models the statistics, approximating the fitness and number of evaluations of each modelled combination of parameters. The model is simple, efficient and informative. Results show that the NTBEA significantly outperforms grid search and an estimation of distribution algorithm.

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.

This paper showcases the setting and results of the first Two-Player General Video Game AI Competition, which ran in 2016 at the IEEE World Congress on Computational Intelligence and the IEEE Conference on Computational Intelligence and Games. The challenges for the general game AI agents are expanded in this track from the single-player version, looking at direct player interaction in both competitive and cooperative environments of various types and degrees of difficulty. The focus is on the agents not only handling multiple problems, but also having to account for another intelligent entity in the game, who is expected to work toward their own goals (winning the game). This other player will possibly interact with first agent in a more engaging way than the environment or any nonplaying character may do. The top competition entries are analyzed in detail and the performance of all agents is compared across the four sets of games. The results validate the competition system in assessing generality, as well as showing Monte Carlo tree search continuing to dominate by winning the overall championship. However, this approach is closely followed by rolling horizon evolutionary algorithms, employed by the winner of the second leg of the contest.

Pac-Man and its equally popular successor Ms.Pac-Man are often attributed to being the frontrunners of the golden age of arcade video games. Their impact goes well beyond the commercial world of video games and both games have featured in numerous academic research projects over the last two decades. In fact, scientific interest is on the rise and many avenues of research have been pursued, including studies in robotics, biology, sociology, and psychology. The most active field of research is computational intelligence, not least because of popular academic gaming competitions that feature Ms. Pac-Man. This paper summarizes the peer-reviewed research that focuses on either game (or close variants thereof) with particular emphasis on the field of computational intelligence. The potential usefulness of games like Pac-Man for higher education is also discussed and the paper concludes with a discussion of prospects for future work.

While Monte Carlo Tree Search and closely related methods have dominated General Video Game Playing, recent research has demonstrated the promise of Rolling Horizon Evolutionary Algorithms as an interesting alternative. However, there is little attention paid to population initialization techniques in the setting of general real-time video games. Therefore, this paper proposes the use of population seeding to improve the performance of Rolling Horizon Evolution and presents the results of two methods, One Step Look Ahead and Monte Carlo Tree Search, tested on 20 games of the General Video Game AI corpus with multiple evolution parameter values (population size and individual length). An in-depth analysis is carried out between the results of the seeding methods and the vanilla Rolling Horizon Evolution. In addition, the paper presents a comparison to a Monte Carlo Tree Search algorithm. The results are promising, with seeding able to boost performance significantly over baseline evolution and even match the high level of play obtained by the Monte Carlo Tree Search.

This paper describes a new evolutionary algorithm that is especially well suited to AI-Assisted Game Design. The approach adopted in this paper is to use observations of AI agents playing the game to estimate the game's quality. Some of best agents for this purpose are General Video Game AI agents, since they can be deployed directly on a new game without game-specific tuning; these agents tend to be based on stochastic algorithms which give robust but noisy results and tend to be expensive to run. This motivates the main contribution of the paper: the development of the novel N-Tuple Bandit Evolutionary Algorithm, where a model is used to estimate the fitness of unsampled points and a bandit approach is used to balance exploration and exploitation of the search space. Initial results on optimising a Space Battle game variant suggest that the algorithm offers far more robust results than the Random Mutation Hill Climber and a Biased Mutation variant, which are themselves known to offer competitive performance across a range of problems. Subjective observations are also given by human players on the nature of the evolved games, which indicate a preference towards games generated by the N-Tuple algorithm.

General Video Game Artificial Intelligence is a general game playing framework for Artificial General Intelligence research in the video-games domain. In this paper, we propose for the first time a screen capture learning agent for General Video Game AI framework. A Deep Q-Network algorithm was applied and improved to develop an agent capable of learning to play different games in the framework. After testing this algorithm using various games of different categories and difficulty levels, the results suggest that our proposed screen capture learning agent has the potential to learn many different games using only a single learning algorithm.

The Random Mutation Hill-Climbing algorithm is a direct search technique mostly used in discrete domains. It repeats the process of randomly selecting a neighbour of a best-so-far solution and accepts the neighbour if it is better than or equal to it. In this work, we propose to use a novel method to select the neighbour solution using a set of independent multi-armed bandit-style selection units which results in a bandit-based Random Mutation Hill-Climbing algorithm. The new algorithm significantly outperforms Random Mutation Hill-Climbing in both OneMax (in noise-free and noisy cases) and Royal Road problems (in the noise-free case). The algorithm shows particular promise for discrete optimisation problems where each fitness evaluation is expensive.

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.

Agent modelling involves considering how other agents will behave, in order to influence your own actions. In this paper, we explore the use of agent modelling in the hidden-information, collaborative card game Hanabi. We implement a number of rule-based agents, both from the literature and of our own devising, in addition to an Information Set-Monte Carlo Tree Search (IS-MCTS) agent. We observe poor results from IS-MCTS, so construct a new, predictor version that uses a model of the agents with which it is paired. We observe a significant improvement in game-playing strength from this agent in comparison to IS-MCTS, resulting from its consideration of what the other agents in a game would do. In addition, we create a flawed rule-based agent to highlight the predictor's capabilities with such an agent.

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.

The design of algorithms for Game AI agents usually focuses on the single objective of winning, or maximizing a given score. Even if the heuristic that guides the search (for reinforcement learning or evolutionary approaches) is composed of several factors, these typically provide a single numeric value (reward or fitness, respectively) to be optimized. Multi-Objective approaches are an alternative concept to face these problems, as they try to optimize several objectives, often contradictory, at the same time. This paper proposes for the first time a study of Multi-Objective approaches for General Video Game playing, where the game to be played is not known a priori by the agent. The experimental study described here compares several algorithms in this setting, and the results suggest that Multi-Objective approaches can perform even better than their single-objective counterparts.

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 competitions may involve different player roles and be score-based rather than win/loss based. This raises the issue of how best to draw opponents for matches in ongoing competitions, and how best to rank the players in each role. An example is the Ms Pac-Man versus Ghosts Competition which requires competitors to develop software controllers to take charge of the game's protagonists: participants may develop software controllers for either or both Ms Pac-Man and the team of four ghosts. In this paper, we compare two ranking schemes for win-loss games, Bayes Elo and Glicko. We convert the game into one of win-loss (“dominance”) by matching controllers of identical type against the same opponent in a series of pair-wise comparisons. This implicitly creates a “solution concept” as to what a constitutes a good player. We analyze how many games are needed under two popular ranking algorithms, Glicko and Bayes Elo, before one can infer the strength of the players, according to our proposed solution concept, without performing an exhaustive evaluation. We show that Glicko should be the method of choice for online score-based game competitions.

General Video Game Playing is a sub-field of Game Artificial Intelligence, where the goal is to find algorithms capable of playing many different real-time games, some of them unknown a priori. In this scenario, the presence of domain knowledge must be severely limited, or the algorithm will overfit to the training games and perform poorly on the unknown games of the test set. Research in this area has been of special interest in the last years, with emerging contests like the General Video Game AI (GVG-AI) Competition. This paper introduces three different open loop techniques for dealing with this problem. First, a simple directed depth first search algorithm is employed as a baseline. Then, a tree search algorithm with a multi-armed bandit based tree policy is presented, followed by a Rolling Horizon Evolutionary Algorithm (RHEA) approach. In order to test these techniques, the games from the GVG-AI Competition framework are used as a benchmark, evaluation on a training set of 29 games, and submitting to the 10 unknown games at the competition website. Results show how the general game-independent heuristic proposed works well across all algorithms and games, and how the RHEA becomes the best evolutionary technique in the rankings of the test set.

Multiobjective optimization has been traditionally a matter of study in domains like engineering or finance, with little impact on games research. However, action-decision based on multiobjective evaluation may be beneficial in order to obtain a high quality level of play. This paper presents a multiobjective Monte Carlo tree search algorithm for planning and control in real-time game domains, those where the time budget to decide the next move to make is close to 40 ms. A comparison is made between the proposed algorithm, a single-objective version of Monte Carlo tree search and a rolling horizon implementation of nondominated sorting evolutionary algorithm II (NSGA-II). Two different benchmarks are employed, deep sea treasure (DST) and the multiobjective physical traveling salesman problem (MO-PTSP). Using the same heuristics on each game, the analysis is focused on how well the algorithms explore the search space. Results show that the algorithm proposed outperforms NSGA-II. Additionally, it is also shown that the algorithm is able to converge to different optimal solutions or the optimal Pareto front (if achieved during search).

This paper presents the game, framework, rules and results of the Multi-objective Physical Travelling Salesman Problem (MO-PTSP) Competition, that was held at the 2013 IEEE Conference on Computational Intelligence in Games (CIG). The MO-PTSP is a real-time game that can be seen as a modification of the Travelling Salesman Problem, where the player controls a ship that must visit a series of waypoints in a maze while minimizing three opposing goals: time spent, fuel consumed and damage taken. The rankings of the competition are computed using multi-objective concepts, a novel approach in the field of game artificial intelligence competitions. The winning entry of the contest is also explained in detail. This controller is based on the Monte Carlo Tree Search algorithm, and employed Covariance Matrix Adaptation Evolution Strategy (CMA-ES) for parameter tuning.

This paper presents a number of approaches for solving a real-time game consisting of a ship that must visit a number of waypoints scattered around a 2-D maze full of obstacles. The game, the Physical Traveling Salesman Problem (PTSP), which featured in two IEEE conference competitions during 2012, provides a good balance between long-term planning (finding the optimal sequence of waypoints to visit), and short-term planning (driving the ship in the maze). This paper focuses on the algorithm that won both PTSP competitions: it takes advantage of the physics of the game to calculate the optimal order of waypoints, and it employs Monte Carlo tree search (MCTS) to drive the ship. The algorithm uses repetitions of actions (macro actions) to reduce the search space for navigation. Variations of this algorithm are presented and analyzed, in order to understand the strength of each one of its constituents and to comprehend what makes such an approach the best controller found so far for the PTSP.

This paper investigates the use of preference learning as an approach to move prediction and evaluation function approximation, using the game of Othello as a test domain. Using the same sets of features, we compare our approach with least squares temporal difference learning, direct classification, and with the Bradley-Terry model, fitted using minorization-maximization (MM). The results show that the exact way in which preference learning is applied is critical to achieving high performance. Best results were obtained using a combination of board inversion and pair-wise preference learning. This combination significantly outperformed the others under test, both in terms of move prediction accuracy, and in the level of play achieved when using the learned evaluation function as a move selector during game play.

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 real-time games, agents have limited time to respond to environmental cues. This requires either a policy defined up-front or, if one has access to a generative model, a very efficient rolling horizon search. In this paper, different search techniques are compared in a simple, yet interesting, real-time game known as the Physical Travelling Salesman Problem (PTSP).We introduce a rolling horizon version of a simple evolutionary algorithm that handles macro-actions and compare it against Monte Carlo Tree Search (MCTS), an approach known to perform well in practice, as well as random search. The experimental setup employs a variety of settings for both the action space of the agent as well as the algorithms used. We show that MCTS is able to handle very fine-grained searches whereas evolution performs better as we move to coarser-grained actions; the choice of algorithm becomes irrelevant if the actions are even more coarse-grained. We conclude that evolutionary algorithms can be a viable and competitive alternative to MCTS.

Coevolution is a natural choice for learning in problem domains where one agent's behavior is directly related to the behavior of other agents. However, there is a known tendency for coevolution to produce mediocre solutions. One of the main reasons for this is cycling, caused by intransitivities among a set of players. In this paper, we explore the link between coevolution and games, and revisit some of the coevolutionary literature in a games and measurement context. We propose a set of measurements to identify cycling in a population and a new algorithm that tries to minimize cycling in strictly competitive (zero sum) games. We experimentally verify our approach by evolving weighted piece counter value functions to play othello, a classic two-player perfect information board game. Our method is able to find extremely strong value functions of this type.

Numerous competitions have emerged in recent years that allow researchers to evaluate their algorithms on a variety of real-time video games with different degrees of complexity. These competitions, which vary from classical arcade games like Ms Pac-Man to racing simulations (Torcs) and realtime strategy games (StarCraft), are essential to establish a uniform testbed that allows practitioners to refine their algorithms over time. In this paper we propose a new competition to be held for the first time at WCCI 2012: the Physical Travelling Salesman Problem is an open-ended single-player real-time game that removes some of the complexities evident in other video games while preserving some of the most fundamental challenges. This paper motivates and outlines the PTSP and discusses in detail the framework of the competition, including software interfaces, parameter settings, rules and details of submission.

Monte Carlo tree search (MCTS) is a recently proposed search method that combines the precision of tree search with the generality of random sampling. It has received considerable interest due to its spectacular success in the difficult problem of computer Go, but has also proved beneficial in a range of other domains. This paper is a survey of the literature to date, intended to provide a snapshot of the state of the art after the first five years of MCTS research. We outline the core algorithm's derivation, impart some structure on the many variations and enhancements that have been proposed, and summarize the results from the key game and nongame domains to which MCTS methods have been applied. A number of open research questions indicate that the field is ripe for future work.

Games provide an ideal test bed for computational intelligence and significant progress has been made in recent years, most notably in games such as Go, where the level of play is now competitive with expert human play on smaller boards. Recently, a significantly more complex class of games has received increasing attention: real-time video games. These games pose many new challenges, including strict time constraints, simultaneous moves and open-endedness. Unlike in traditional board games, computational play is generally unable to compete with human players. One driving force in improving the overall performance of artificial intelligence players are game competitions where practitioners may evaluate and compare their methods against those submitted by others and possibly human players as well. In this pa per we introduce a new competition based on the popular arcade video game Ms Pac-Man: Ms Pac-Man versus Ghost Team. The competition, to be held at the Congress on Evolutionary Computation 2011 for the first time, allows participants to develop controllers for either the Ms Pac-Man agent or for the Ghost Team and unlike previous Ms Pac-Man competitions that relied on screen capture, the players now interface directly with the game engine. In this paper we introduce the competition, including a review of previous work as well as a discussion of several aspects regarding the setting up of the game competition itself.

Coevolutionary algorithms are plagued with a set of problems related to intransitivity that make it questionable what the end product of a coevolutionary run can achieve. With the introduction of solution concepts into coevolution, part of the issue was alleviated, however efficiently representing and achieving game theoretic solution concepts is still not a trivial task. In this paper we propose a coevolutionary algorithm that approximates behavioural strategy Nash equilibria in n-player zero sum games, by exploiting the min-max solution concept. In order to support our case we provide a set of experiments in both games of known and unknown equilibria. In the case of known equilibria, we can confirm our algorithm converges to the known solution, while in the case of unknown equilibria we can see a steady progress towards Nash.

We present an application of Monte Carlo tree search (MCTS) for the game of Ms Pac-Man. Contrary to most applications of MCTS to date, Ms Pac-Man requires almost real-time decision making and does not have a natural end state. We approached the problem by performing Monte Carlo tree searches on a five player maxntree representation of the game with limited tree search depth. We performed a number of experiments using both the MCTS game agents (for pacman and ghosts) and agents used in previous work (for ghosts). Performance-wise, our approach gets excellent scores, outperforming previous non-MCTS opponent approaches to the game by up to two orders of magnitude.

The Scanning N-Tuple Grid (SNT-Grid) has been demonstrated to be a fast classifier for 2-dimensional images. The high speed is accomplished by scanning separately along rows and columns to extract features and can process thousands of pre-segmented characters per second in training and recognition. This paper proposes the use of orientational features within the SNT-Grid and makes a comparison in performance with features previously reported in literature. In terms of training the classifier, it explores cross entropy training and concludes that it outperforms more conventional maximum likelihood training. Finally, zoned orientational features offer a better implementation with an additional cost in computational time for training and recognition. The best accuracy reported has reduced the error rate of the system by 70% on the same dataset.

The author first provides an overview of computational intelligence and AI in games. Then he describes the new IEEE Transactions, which will publish archival quality original papers in all aspects of computational intelligence and AI related to all types of games. To name some examples, these include computer and video games, board games, card games, mathematical games, games that model economies or societies, serious games with educational and training applications, and games involving physical objects such as robot football and robotic car racing. Emphasis will also be placed on the use of these methods to improve performance in, and understanding of, the dynamics of games, as well as gaining insight into the properties of the methods as applied to games. It will also include using games as a platform for building intelligent embedded agents for real-world applications. The journal builds on a scientific community that has already been active in recent years with the development of new conference series such as the IEEE Symposium on Computational Intelligence in Games (CIG) and Artificial Intelligence and Interactive Digital Entertainment (AIIDE), as well as special issues on games in journals such as the IEEE Transactions on Evolutionary Computation. When setting up the journal, a decision was made to include both artificial intelligence (AI) and computational intelligence (CI) in the title. AI seeks to simulate intelligent behavior in any way that can be programmed effectively. Some see the field of AI as being all-inclusive, while others argue that there is nothing artificial about real intelligence as exhibited by higher mammals.

Single and multi-step time-series predictors were evolved for forecasting minimum bidding prices in a simulated supply chain management scenario. Evolved programs were allowed to use primitives that facilitate the statistical analysis of historical data. An investigation of the relationships between the use of such primitives and the induction of both accurate and predictive solutions was made, with the statistics calculated based on three input data transformation methods: integral, differential, and rational. Results are presented showing which features work best for both single-step and multi-step predictions. Copyright 2008 ACM.

Two families (stateful and stateless) of genetically programmed classifiers were tested on a five class brain-computer interface (BCI) data set of raw EEG signals. The ability of evolved classifiers to discriminate mental tasks from each other were analysed in terms of accuracy, precision and recall. A model describing the dynamics of state usage in stateful programs is introduced. An investigation of relationships between the model attributes and associated classification results was made. The results show that both stateful and stateless programs can be successfully evolved for this task, though stateful programs start from lower fitness and take longer to evolve.

Two different classifier representations based on dynamic Artificial Neural Networks (ANNs) and Genetic Programming (GP) are being compared on a human action recognition task by an ubiquitous mobile robot. The classification methodologies used, process time series generated by an indoor ubiquitous 3D tracker which generates spatial points based on 23 reflectable markers attached on a human body. This investigation focuses mainly on class discrimination of normal and aggressive action recognition performed by an architecture which implements an interconnection between an ubiquitous 3D sensory tracker system and a mobile robot to perceive, process, and classify physical human actions. The 3D tracker and the robot are used as a perception-to-action architecture to process physical activities generated by human subjects. Both classifiers process the activity time series to eventually generate surveillance assessment reports by generating evaluation statistics indicating the classification accuracy of the actions recognized.

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.

This paper describes an evolutionary music composition system that combines trainable music critics with a bag of notes constraint. Unlike many evolutionary composition systems, there is no human interaction involved in the loop. The role of the human within our system is to select the set of melodies to train the critics on, and choose the bag of notes. The trainable critics are N-gram model. The system then evolves pleasant sounding melodies by permuting the order of the notes selected from the bag. The bag of notes constraint prevents a previously observed problem. We solve a prior problem where the Maximum Likelihood Sequence (MLS) generated by our N-gram model is repetitive using the bag of notes constraint. In this paper, two experiments are constructed. Both experiments are identical except for the melody representations, which are Absolute Pitch (AP) and Pitch Difference (PD) representations. In each case, the bag of notes constraint results in more pleasing melodies, and the melody shape of the melodies are more controllable and predictable with appropriate operators. We suggest that using absolute pitch representation leads to better sounding melodies than the pitch difference representation, especially if the user enjoys arpeggio effects.

Learning finite state machines from samples of data has been extensively studied within machine learning and since the dawn of evolutionary computation. Conventional crossover or recombination operators used for finite state machines suffer from the competing conventions problem, caused by the combinatorial number of isomorphisms of each distinct machine. This paper introduces an efficient alignment operator to counteract this phenomenon. Results show that when in the neighbourhood of the target machine, the aligned crossover operator reaches the optimum in far few steps (on average) than either a naive crossover operator or a standard flip-style mutation operator.

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.

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

Finite-state transducers (FSTs) are finite-state machines (FSMs) that map strings in a source domain into strings in a target domain. While there are many reports in the literature of evolving FSMs, there has been much less work on evolving FSTs. In particular, the fitness functions required for evolving FSTs are generally different from those used for FSMs. In this paper, three string distance-based fitness functions are evaluated, in order of increasing computational complexity: string equality, Hamming distance, and edit distance. The fitness-distance correlation (FDC) and evolutionary performance of each fitness function is analyzed when used within a random mutation hill-climber (RMHC). Edit distance has the strongest FDC and also provides the best evolutionary performance, in that it is more likely to find the target FST within a given number of fitness function evaluations. Edit distance is also the most expensive to compute, but in most cases this extra computation is more than justified by its performance. The RMHC was compared with the best known heuristic method for learning FSTs, the onward subsequential transducer inference algorithm (OSTIA). On noise-free data, the RMHC performs best on problems with sparse training sets and small target machines. The RMHC and OSTIA offer similar performance for large target machines and denser data sets. When noise-corrupted data is used for training, the RMHC still performs well, while OSTIA performs poorly given even small amounts of noise. The RMHC is also shown to outperform a genetic algorithm. Hence, for certain classes of FST induction problem, the RMHC presented in this paper offers the best performance of any known algorithm

Object Oriented Genetic Programming (OOGP) is applied to the task of evolving general recursive sorting algorithms. We studied the effects of language primitives and fitness functions on the success of the evolutionary process. For language primitives, these were the methods of a simple list processing package. Five different fitness functions based on sequence disorder were evaluated. The time complexity of the successfully evolved algorithms was measured experimentally in terms of the number of method invocations made, and for the best evolved individuals this was best approximated as O(n times log(n)). This is the first time that sorting algorithms of this complexity have been evolved.

Conventionally, automatic music composition is done by evolving music sequences whose fitness is evaluated by a human listener. This interactive approach has led to interesting results but is very time consuming. Here we propose a system that is capable of automatically generating music using an evolutionary algorithm (EA), replacing the human evaluation process with a trainable music evaluation algorithm. This algorithm can be trained on existing music samples, such as Mozart compositions for example. This kind of system could provide a fast and cheap music composition tool. The current evaluation system is implemented with an N-gram language model. This paper discusses the system in two parts. Firstly, it describes the performance of the proposed music evaluation algorithm. Secondly, it discusses the impacts of different sequence-oriented genetic operators in the evolutionary algorithm. Part one of the experimental results show that the N-Gram model is able to distinguish the composer of piano compositions by Mozart, Beethoven and Chopin with up to 81.9% accuracy. Part two of the results show that some of the sequence-oriented operators increased the fitness of the generated melodies, but some operators did not. The impacts of these operators are discussed in the experimental results section. Significantly, the results also show that better classification accuracy does not necessarily lead to better evolved music, suggesting that perceptual relevance is also an important factor.

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.

This paper describes the results of the ICDAR 2005 competition for locating text in camera captured scenes. For this we used the same data as the ICDAR 2003 competition, which has been kept private until now. This allows a direct comparison with the 2003 entries. The main result is that the leading 2005 entry has improved significantly on the leading 2003 entry, with an increase in average f-score from 0.5 to 0.62, where the f-score is the same adapted information retrieval measure used for the 2003 competition. The paper also discusses the Web-based deployment and evaluation of text locating systems, and one of the leading entries has now been deployed in this way. This mode of usage could lead to more complete and more immediate knowledge of the strengths and weaknesses of each newly developed system.

This paper introduces a novel high speed convolutional character recognition system. Convolutional mode operation means that no prior localization or segmentation of characters is required, making this mode extremely robust. The method uses a 2-d n-tuple grid to sample the image, but decomposes the address calculations into two one-dimensional scans. This simple innovation leads to a very fast system, and speeds in excess of 100,000 recognitions per second have been achieved for a 10-class character recognition problem, when operated in convolutional mode. Quantitative performance results show an error rate of 4.3% on the MNist dataset of isolated hand-written characters. Qualitative results are presented on museum archive card images, indicating that the method has great potential for the character recognition component in a document image analysis system for images of this type.

Learning a Deterministic Finite Automaton (DFA) from a training set of labeled strings is a hard task that has been much studied within the machine learning community. It is equivalent to learning a regular language by example and has applications in language modeling. In this paper, we describe a novel evolutionary method for learning DFA that evolves only the transition matrix and uses a simple deterministic procedure to optimally assign state labels. We compare its performance with the Evidence Driven State Merging (EDSM) algorithm, one of the most powerful known DFA learning algorithms. We present results on random DFA induction problems of varying target size and training set density. We also studythe effects of noisy training data on the evolutionary approach and on EDSM. On noise-free data, we find that our evolutionary method outperforms EDSM on small sparse data sets. In the case of noisy training data, we find that our evolutionary method consistently outperforms EDSM, as well as other significant methods submitted to two recent competitions.

Two learning methods for acquiring position evaluation for small Go boards are studied and compared. In each case the function to be learned is a position-weighted piece counter and only the learning method differs. The methods studied are temporal difference learning (TDL) using the self-play gradient-descent method and coevolutionary learning, using an evolution strategy. The two approaches are compared with the hope of gaining a greater insight into the problem of searching for "optimal" zero-sum game strategies. Using tuned standard setups for each algorithm, it was found that the temporal-difference method learned faster, and in most cases also achieved a higher level of play than coevolution, providing that the gradient descent step size was chosen suitably. The performance of the coevolution method was found to be sensitive to the design of the evolutionary algorithm in several respects. Given the right configuration, however, coevolution achieved a higher level of play than TDL. Self-play results in optimal play against a copy of itself. A self-play player will prefer moves from which it is unlikely to lose even when it occasionally makes random exploratory moves. An evolutionary player forced to perform exploratory moves in the same way can achieve superior strategies to those acquired through self-play alone. The reason for this is that the evolutionary player is exposed to more varied game-play, because it plays against a diverse population of players.

The game of Cellz has been designed as a test bed for evolutionary algorithms. The game has a minimal set of rules that nonetheless offer the possibility for complex behaviour to emerge. Computationally, the game is cheap to simulate, which leads to rapid runs of evolutionary algorithms. A key feature of the game is the cell division process, which can lead to evolution in situ without reference to any externally defined fitness function. This paper describes the rationale behind the development of Cellz, the rules of the game and the software interfaces for the cell controllers. The randomness in the game initialisation leads to extremely noisy fitness functions, which adds to the challenge of evolving high-performance controllers. Initial results demonstrate that an evolved perceptron-type controller can achieve mediocre performance on the single species game.

Learning deterministic finite automata (DFA) is a hard task that has been much studied within machine learning and evolutionary computation research. This paper presents a new method for evolving DFAs, where only the transition matrix is evolved, and the state labels are chosen to optimize the fit between final states and training set labels. This new procedure reduces the size and in particular, the complexity, of the search space. We present results on the Tomita languages, and also on a set of random DFA induction problems of varying target size and training set density. The Tomita set results show that we can learn the languages with far fewer fitness evaluations than previous evolutionary methods. On the random DFA task we compare our methods with the evidence driven state merging (EDSM) algorithms, which is one of the most powerful known DFA learning algorithms. We show that our method outperforms EDSM when the target DFA is small (less than 32 states) and the training set is sparse.

This paper summarises the achievements of a multidisciplinary Bioinformatics project which has the objective of providing a general mechanism for efficient computerisation of typewritten/hand-annotated archive card indexes, of the type found in most museums, archives and libraries. In addition to efficiently scanning, recognising and databasing the content of the cards, the original card images must be maintained as the ultimate source record, and a flexible database structure is required to allow taxonomists to reorganise and update the resulting online archive. Implementation mechanisms for each part of the overall system are described, and conversion performance for a demonstrator database of 27,578 Pyralid moth archive cards is reported. The system is currently being used to convert the full NHM archive of Lepidoptera totalling 290,886 cards.

This paper describes a complete system for reading type-written lexicon words in noisy images - in this case museum index cards. The system is conceptually simple, and straightforward to implement. It involves three stages of processing. The first stage extracts row-regions from the image, where each row is a hypothesized line of text. The next stage scans an OCR classifier over each row image, creating a character hypothesis graph in the process. This graph is then searched using a priority-queue based algorithm for the best matches with a set of words (lexicon). Performance evaluation on a set of museum archive cards indicates competitive accuracy and also reasonable throughput. The priority queue algorithm is over two hundred times faster than using flat dynamic programming on these graphs.

This paper describes the robust reading competitions for ICDAR 2003. With the rapid growth in research over the last few years on recognizing text in natural scenes, there is an urgent need to establish some common benchmark datasets, and gain a clear understanding of the current state of the art. We use the term robust reading to refer to text images that are beyond the capabilities of current commercial OCR packages. We chose to break down the robust reading problem into three sub-problems, and run competitions for each stage, and also a competition for the best overall system. The sub-problems we chose were text locating, character recognition and word recognition. By breaking down the problem in this way, we hope to gain a better understanding of the state of the art in each of the sub-problems. Furthermore, our methodology involves storing detailed results of applying each algorithm to each image in the data sets, allowing researchers to study in depth the strengths and weaknesses of each algorithm. The text locating contest was the only one to have any entries. We report the results of this contest, and show cases where the leading algorithms succeed and fail. 1.

For many interesting design problems the solution is most naturally represented as a type of graph. This paper proposes that the problem of evolving spring-mass models for a set of design challenges makes an excellent test-bed for evaluating the performance of various graph encoding schemes. We describe how the problem is set up, and introduce a planar graph coding scheme. Results demonstrate that the planar graph encoding scheme significantly outperforms a simple direct encoding scheme on a height-challenge design problem.

Presents a progress report (after 1 year of a 3 year project) on the overall design for a flexible archive conversion system, intended eventually for widespread use as a tool to convert legacy typescript and handwritten archive card indexes into Internet-accessible and searchable databases. The VIADOCS system is being developed and evaluated on a demonstrator archive of 30,000 pyraloid moth cards at the UK Natural History Museum, and has already demonstrated a successful and efficient mechanism for image acquisition using a modified bank cheque scanner. Document image processing and analysis techniques, defined by an XML validating document type definition (DTD), are being used to correct defects in the acquired images and parse card sequences to match the hierarchical taxonomy of pyraloid moth species. Parsed data is processed by offline OCR engines augmented by field-specific subject dictionaries to produce a 'draft' online archive. This archive will then be validated interactively via a Web browser as it is used. It is hoped eventually to provide an efficient and configurable legacy archive document conversion system not only for the Natural History Museum, but also for all museums, libraries and archives where there is a need to interrogate legacy documents via computer.

We describe a novel robust approach to enable efficient searching of the type-written text on museum archive cards. Depending on such factors as the state of the typewriter and its ribbon, these text images may be faint with parts of the character missing, or be in heavy type with adjacent characters merging together. Both these problems can make this kind of text hard to read with conventional OCR methods that rely on the use of a limited number of segmentation hypotheses prior to recognition. Our method involves sliding a classifier over the entire word or card image, such that we get a set of recognition hypotheses for each possible window position which gives rise to a large character hypothesis graph. We then apply a graph reduction followed by an efficient graph search method to search for words in the reduced graph. Results so far are promising, with our system achieving 45% word recognition accuracy compared to the 25% achieved by a leading commercial package. However, searching the original larger graphs is much slower but yields 85% accuracy; so further work is needed either in improving the graph reduction method, or in improving the efficiency with which we can search the larger graph.

This paper describes a novel method for applying dictionary knowledge to optimally interpret the confidence-rated hypothesis sets produced by lower-level pattern classifiers. The problem is cast as enumerating the paths in a graph in best-first order given the constraint that each complete path is a word in some specified dictionary. The solution described here is of particular interest due to its generality, flexibility and because the time to retrieve each path is independent of the size of the dictionary. Results are presented for searching dictionaries of up to 1 million UK postcodes given graphs that correspond to insertion, deletion and substitution errors.

This paper describes a system for the automatic evaluation of algorithms (especially pattern recognition algorithms) over the Internet. We present the case for such a system, discuss the system requirements and potential users, and present an initial prototype. We illustrate usage of the system with an evaluation of image distance measures used for face recognition.

Lazy evaluation is a best-first state space search method for contextual handwriting recognition which searches an ordered space and applies constraints at the earliest possible opportunity to maximise computational efficiency. Lazy evaluation is well-suited to multi-level hypothesis verification because it operates recursively on a hierarchical semantic tree of context constraints. This paper describes the lazy evaluation algorithm in detail, and proves that, if ordered hypotheses for the lowest-level sub-patterns are provided as inputs, and the combined belief function is monotonic, then overall interpretations are guaranteed to be generated in best-first order. Applications of lazy evaluation to postcode dictionary and address recognition problems are outlined as illustrations of the algorithm.

Describes a new general-purpose contextual architecture which provides a unified framework for efficiently combining all types and levels of context in hand-print recognition applications. The architecture has been designed and built as a C++ class library and utilised within an initial demonstrator which implements full contextual constraints for a combination of postcode and corresponding postal address. Preliminary evaluation of the demonstrator suggests the system has the potential to achieve genuinely remarkable performance compared with previous context systems: its memory requirements are an order of magnitude less than an equivalent trie-based dictionary; its search speed is at least an order of magnitude faster than the trie, and actually gets faster as the dictionary size increases(!); and its error rate is virtually zero if suitable contextual constraints can be applied. Using this architecture, it appears to be possible to build real-time solutions to large-scale heterogeneous contextual problems.

It is shown how syntactic neural networks can be applied to the problem of translating orthographic strings to phonetics strings, and vice versa, due to the symmetry of the model. This is unusual in text-phonetics translation systems; most systems have to be trained to operate in a single direction. Another novel feature is the lack of supervision required during training. The only requirement is that one have whole-word orthographic/phonetic symbol-string pairs. To test the system the authors have formed a lexicon of (6000, single-syllable) such pairs in English by extracting the relevant information from the machine-readable Oxford Advanced Learner's Dictionary. Results are presented for cases where the training set varies between 10 and 2000 words. In each case, the trained nets are tested on the training set and an equal-size (disjoint) test set. Present results are poor compared to conventional translation systems, but most of the errors may be due to the system's immaturity.>

A syntactic neural network is equivalent to a parser for a certain type of grammar-in this case, strictly hierarchical context-free. This allows an efficient method for pattern description and has the added advantage of being a generative model. The authors show how the network itself can infer the grammar. Syntactic neural nets can model stochastic or nonstochastic grammars. The stochastic nets are properly probabilistic and are powerful discriminators; the nonstochastic nets are less powerful, but have straightforward silicon implementations with existing technology. Learning in syntactic nets may proceed supervised or unsupervised. In each case, the algorithm is the same; the difference lies in the data presented to the net. In prior publications, the authors applied syntactic neural nets to character recognition and cursive script recognition. The authors presently show that nonstochastic nets can perform signature verification with high reliability. This raises the possibility of signature verification on a robust smart card