Publications

15 conference papers, journal articles, and online preprints

Click on each title to display more information.

2020: 1 Papers

• Capturing Local and Global Patterns in Procedural Content Generation via Machine Learning

  Authors:

  • Vanessa Volz
  • Niels Justesen
  • Sam Snodgrass
  • Sahar Asadi
  • Sami Purmonen
  • Christoffer Holmgård
  • Julian Togelius
  • Sebastian Risi

  Abstract:

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

  Links:

  • Paper

  Bibtex:

  "@inproceedings{volz2020capturing,
    title={Capturing Local and Global Patterns in Procedural Content Generation via Machine Learning},
    author={Volz, Vanessa and Justesen, Niels and Snodgrass, Sam and Asadi, Sahar and Purmonen, Sami and Holmg{\aa}rd, Christoffer and Togelius, Julian and Risi, Sebastian},
    booktitle={2019 IEEE Conference on Games (CoG)},
    year={2020}
  }"
  

  ---

2019: 6 Papers

• Blood Bowl: A New Board Game Challenge and Competition for AI

  Authors:

  • Niels Justesen
  • Lasse Møller Uth
  • Christopher Jakobsen
  • Peter David Moore
  • Julian Togelius
  • Sebastian Risi

  Abstract:

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

  Links:

  • Paper
  • Source-code
  • Webpage

  Bibtex:

  "@inproceedings{justesen2019blood,
  title={Blood bowl: A new board game challenge and competition for AI},
  author={Justesen, Niels and Uth, Lasse M{\o}ller and Jakobsen, Christopher and Moore, Peter David and Togelius, Julian and Risi, Sebastian},
  booktitle={2019 IEEE Conference on Games (CoG)},
  pages={1--8},
  year={2019},
  organization={IEEE}}"
  

  ---

• Bootstrapping Conditional GANs for Video Game Level Generation

  Authors:

  • Ruben Rodriguez Torrado
  • Ahmed Khalifa
  • Michael Cerny Green
  • Niels Justesen
  • Sebastian Risi
  • Julian Togelius

  Abstract:

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

  Links:

  • Paper

  Bibtex:

  "@inproceedings{torrado2019bootstrapping,
    title={Bootstrapping Conditional GANs for Video Game Level Generation},
    author={Torrado, Ruben Rodriguez and Khalifa, Ahmed and Green, Michael Cerny and Justesen, Niels and Risi, Sebastian and Togelius, Julian},
    booktitle={2019 IEEE Conference on Games (CoG)},
    year={2019}
  }"
  

  ---

• Deep Learning for Video Game Playing

  Authors:

  • Niels Justesen
  • Philip Bontrager
  • Julian Togelius
  • Sebastian Risi

  Abstract:

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

  Links:

  • Paper

  Bibtex:

  "@article{justesen2019deep,
  title={Deep learning for video game playing},
  author={Justesen, Niels and Bontrager, Philip and Togelius, Julian and Risi, Sebastian},
  journal={IEEE Transactions on Games},
  year={2019},
  publisher={IEEE}}"
  

  ---

• Learning a Behavioral Repertoire from Demonstrations

  Authors:

  • Niels Justesen
  • Miguel Gonzalez Duque
  • Daniel Cabarcas Jaramillo
  • Jean-Baptiste Mouret
  • Sebastian Risi

  Abstract:

  Imitation Learning (IL) is a machine learning approach to learn a policy from a dataset of demonstrations. IL can be useful to kick-start learning before applying reinforcement learning (RL) but it can also be useful on its own, e.g. to learn to imitate human players in video games. However, a major limitation of current IL approaches is that they learn only a single “average” policy based on a dataset that possibly contains demonstrations of numerous different types of behaviors. In this paper, we propose a new approach called Behavioral Repertoire Imitation Learning (BRIL) that instead learns a repertoire of behaviors from a set of demonstrations by augmenting the state-action pairs with behavioral descriptions. The outcome of this approach is a single neural network policy conditioned on a behavior description that can be precisely modulated. We apply this approach to train a policy on 7,777 human replays to perform build-order planning in StarCraft II. Principal Component Analysis (PCA) is applied to construct a low-dimensional behavioral space from the high-dimensional army unit composition of each demonstration. The results demonstrate that the learned policy can be effectively manipulated to express distinct behaviors. Additionally, by applying the UCB1 algorithm, we are able to adapt the behavior of the policy – in-between games – to reach a performance beyond that of the traditional IL baseline approach.

  Links:

  • Paper

  Bibtex:

  "@inproceedings{justesen2019learning,
    title={Learning a Behavioral Repertoire from Demonstrations},
    author={Justesen, Niels and Duque, Miguel Gonzalez and Jaramillo, Daniel Cabarcas and Mouret, Jean-Baptiste and Risi, Sebastian},
    booktitle={2020 IEEE Conference on Games (CoG)},
    year={2019}
  }"
  

  ---

• MAP-Elites for Noisy Domains by Adaptive Sampling

  Authors:

  • Niels Justesen
  • Sebastian Risi
  • Jean-Baptiste Mouret

  Abstract:

  Quality Diversity algorithms (QD) evolve a set of high-performing phenotypes that each behaves as differently as possible. However, current algorithms are all elitist, which make them unable to cope with stochastic fitness functions and behavior evaluations. In fact, many of the promising applications of QD algorithms, for instance, games and robotics, are stochastic. Here we propose two new extensions to the QD-algorithm MAP-Elites — adaptive sampling and drifting-elites — and demonstrate empirically that these extensions increase the quality of solutions in a noisy artificial test function and the behavioral diversity in a 2D bipedal walker environment.

  Links:

  • Paper

  Bibtex:

  "@inproceedings{justesen2019we,
    title={When Are We Done with Games?},
    author={Justesen, Niels and Debus, Michael S and Risi, Sebastian},
    booktitle={2019 IEEE Conference on Games (CoG)},
    pages={1--8},
    year={2019},
    organization={IEEE}}"
  

  ---

• When Are We Done with Games?

  Authors:

  • Niels Justesen
  • Michael S. Debus
  • Sebastian Risi

  Abstract:

  From an early point, games have been promoted as important challenges within the research field of Artificial Intelligence (AI). Recent developments in machine learning have allowed a few AI systems to win against top professionals in even the most challenging video games, including Dota 2 and StarCraft. It thus may seem that AI has now achieved all of the long-standing goals that were set forth by the research community. In this paper, we introduce a black box approach that provides a pragmatic way of evaluating the fairness of AI vs. human competitions, by only considering motoric and perceptual fairness on the competitors’ side. Additionally, we introduce the notion of extrinsic and intrinsic factors of a game competition and apply these to discuss and compare the competitions in relation to human vs. human competitions. We conclude that Dota 2 and StarCraft II are not yet mastered by AI as they so far only have been able to win against top professionals in limited competition structures in restricted variants of the games.

  Links:

  • Paper

  Bibtex:

  "@inproceedings{justesen2019we,
    title={When Are We Done with Games?},
    author={Justesen, Niels and Debus, Michael S and Risi, Sebastian},
    booktitle={2019 IEEE Conference on Games (CoG)},
    pages={1--8},
    year={2019},
    organization={IEEE}}"
  

  ---

2018: 3 Papers

• Automated Curriculum Learning by Rewarding Temporally Rare Events

  Authors:

  • Niels Justesen
  • Sebastian Risi

  Abstract:

  Reward shaping allows reinforcement learning (RL) agents to accelerate learning by receiving additional reward signals. However, these signals can be difficult to design manually, especially for complex RL tasks. We propose a simple and general approach that determines the reward of pre-defined events by their rarity alone. Here events become less rewarding as they are experienced more often, which encourages the agent to continually explore new types of events as it learns. The adaptiveness of this reward function results in a form of automated curriculum learning that does not have to be specified by the experimenter. We demonstrate that this Rarity of Events (RoE) approach enables the agent to succeed in challenging VizDoom scenarios without access to the extrinsic reward from the environment. Furthermore, the results demonstrate that RoE learns a more versatile policy that adapts well to critical changes in the environment. Rewarding events based on their rarity could help in many unsolved RL environments that are characterized by sparse extrinsic rewards but a plethora of known event types.

  Links:

  • Paper
  • Source-code

  Bibtex:

  "@inproceedings{justesen2018automated,
    title={Automated curriculum learning by rewarding temporally rare events},
    author={Justesen, Niels and Risi, Sebastian},
    booktitle={2018 IEEE Conference on Computational Intelligence and Games (CIG)},
    pages={1--8},
    year={2018},
    organization={IEEE}}"
  

  ---

• Blood Bowl: The Next Board Game Challenge for AI

  Authors:

  • Niels Justesen
  • Sebastian Risi
  • Julian Togelius

  Abstract:

  We propose the popular board game Blood Bowl as a new challenge for Artificial Intelligence (AI). Blood Bowl is a fully-observable, stochastic, turn-based, modern-style board game with a grid-based playing board. At first sight, the game ought to be approachable by numerous game-playing algorithms. However, as all pieces on the board belonging to a player can be moved several times each turn, the turn-wise branching factor becomes overwhelming for traditional algorithms. Additionally, scoring points in the game is rare and difficult, which makes it hard to design heuristics for search algorithms or apply reinforcement learning. We present our work in progress on a game engine that implements the core rules of Blood Bowl with a forward model and a reinforcement learning interface. We plan to release the engine as open source and use it to facilitate future AI competitions.

  Links:

  • Paper
  • Source-code
  • Webpage

  Bibtex:

  "@article{justesen2018blood,
    title={Blood bowl: The next board game challenge for ai},
    author={Justesen, Niels and Risi, Sebastian and Togelius, Julian},
    journal={Foundations of Digital Games. Association for Computing Machinery},
    year={2018}}"
  

  ---

• Illuminating Generalization in Deep Reinforcement Learning through Procedural Level Generation

  Authors:

  • Niels Justesen
  • Ruben Rodriguez Torrado
  • Philip Bontrager
  • Ahmed Khalifa
  • Julian Togelius
  • Sebastian Risi

  Abstract:

  Deep reinforcement learning (RL) has shown impressive results in a variety of domains, learning directly from high-dimensional sensory streams. However, when neural networks are trained in a fixed environment, such as a single level in a video game, they will usually overfit and fail to generalize to new levels. When RL models overfit, even slight modifications to the environment can result in poor agent performance. This paper explores how procedurally generated levels during training can increase generality. We show that for some games procedural level generation enables generalization to new levels within the same distribution. Additionally, it is possible to achieve better performance with less data by manipulating the difficulty of the levels in response to the performance of the agent. The generality of the learned behaviors is also evaluated on a set of human-designed levels. The results suggest that the ability to generalize to human-designed levels highly depends on the design of the level generators. We apply dimensionality reduction and clustering techniques to visualize the generators’ distributions of levels and analyze to what degree they can produce levels similar to those designed by a human.

  Links:

  • Paper
  • Source-code

  Bibtex:

  "@article{justesen2018illuminating,
    title={Illuminating Generalization in Deep Reinforcement Learning through Procedural Level Generation},
    author={Justesen, Niels and Torrado, Ruben Rodriguez and Bontrager, Philip and Khalifa, Ahmed and Togelius, Julian and Risi, Sebastian},
    journal={NeurIPS 2018 Workshop on Deep Reinforcement Learning},
    year={2018}}"
  

  ---

2017: 3 Papers

• Continual Online Evolutionary Planning for In-Game Build Order Adaptation in StarCraft

  Authors:

  • Niels Justesen
  • Sebastian Risi

  Abstract:

  The real-time strategy game StarCraft has become an important benchmark for AI research as it poses a complex environment with numerous challenges. An important strategic aspect in this game is to decide what buildings and units to produce. StarCraft bots playing in AI competitions today are only able to switch between predefined strategies, which makes it hard to adapt to new situations. This paper introduces an evolutionary-based method to overcome this challenge, called Continual Online Evolutionary Planning (COEP), which is able to perform in-game adaptive build-order planning. COEP was added to an open source StarCraft bot called UAlbertaBot and is able to outperform the built-in bots in the game as well as being competitive against a number of scripted opening strategies. The COEP augmented bot can change its build order dynamically and quickly adapt to the opponent's strategy.

  Links:

  • Paper
  • Source-code

  Bibtex:

  "@inproceedings{justesen2017continual,
  title={Continual online evolutionary planning for in-game build order adaptation in StarCraft},
  author={Justesen, Niels and Risi, Sebastian},
  booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
  pages={187--194},
  year={2017}}"
  

  ---

• Learning Macromanagement in StarCraft from Replays using Deep Learning

  Authors:

  • Niels Justesen
  • Sebastian Risi

  Abstract:

  The real-time strategy game StarCraft has proven to be a challenging environment for artificial intelligence techniques, and as a result, current state-of-the-art solutions consist of numerous hand-crafted modules. In this paper, we show how macromanagement decisions in StarCraft can be learned directly from game replays using deep learning. Neural networks are trained on 789,571 state-action pairs extracted from 2,005 replays of highly skilled players, achieving top-1 and top-3 error rates of 54.6% and 22.9% in predicting the next build action. By integrating the trained network into UAlbertaBot, an open source StarCraft bot, the system can significantly outperform the game’s built-in Terran bot, and play competitively against UAlbertaBot with a fixed rush strategy. To our knowledge, this is the first time macromanagement tasks are learned directly from replays in StarCraft. While the best hand-crafted strategies are still the state-of-the-art, the deep network approach is able to express a wide range of different strategies and thus improving the network’s performance further with deep reinforcement learning is an immediately promising avenue for future research. Ultimately this approach could lead to strong StarCraft bots that are less reliant on hard-coded strategies.

  Links:

  • Paper

  Bibtex:

  "@inproceedings{justesen2017learning,
  title={Learning macromanagement in starcraft from replays using deep learning},
  author={Justesen, Niels and Risi, Sebastian},
  booktitle={2017 IEEE Conference on Computational Intelligence and Games (CIG)},
  pages={162--169},
  year={2017},
  organization={IEEE}}"
  

  ---

• Playing Multi-Action Adversarial Games; Online Evolution vs. Tree Search

  Authors:

  • Niels Justesen
  • Tobias Mahlmann
  • Sebastian Risi
  • Julian Togelius

  Abstract:

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

  Links:

  • Paper
  • Source-code

  Bibtex:

  "@article{justesen2017playing,
  title={Playing Multiaction Adversarial Games: Online Evolutionary Planning Versus Tree Search},
  author={Justesen, Niels and Mahlmann, Tobias and Risi, Sebastian and Togelius, Julian},
  journal={IEEE Transactions on Games},
  volume={10},
  number={3},
  pages={281--291},
  year={2017},
  publisher={IEEE}}"
  

  ---

2016: 1 Papers

• Online Evolution for Multi-Action Adversarial Games

  Authors:

  • Niels Justesen
  • Tobias Mahlmann
  • Sebastian Risi

  Abstract:

  We present Online Evolution, a novel method for playing turn-based multi-action adversarial games. Such games, which include most strategy games, have extremely high branching factors due to each turn having multiple actions. In Online Evolution, an evolutionary algorithm is used to evolve the combination of atomic actions that make up a single move, with a state evaluation function used for fitness. We implement Online Evolution for the turn-based multi-action game Hero Academy and compare it with a standard Monte Carlo Tree Search implementation as well as two types of greedy algorithms. Online Evolution is shown to outperform these methods by a large margin. This shows that evolutionary planning on the level of a single move can be very effective for this sort of problems.

  Links:

  • Paper

  Bibtex:

  "@inproceedings{justesen2016online,
    title={Online evolution for multi-action adversarial games},
    author={Justesen, Niels and Mahlmann, Tobias and Togelius, Julian},
    booktitle={European Conference on the Applications of Evolutionary Computation},
    pages={590--603},
    year={2016},
    organization={Springer}}"
  

  ---

2014: 1 Papers

• Script-and Cluster-Based UCT for StarCraft

  Authors:

  • Niels Justesen
  • Bálint Tillman
  • Julian Togelius
  • Sebastian Risi

  Abstract:

  Monte Carlo methods have recently shown promise in real-time strategy (RTS) games, which are challenging because of their fast pace with simultaneous moves and massive branching factors. This paper presents two extensions to the Monte Carlo method UCT Considering Durations (UCTCD) for finding optimal sequences of actions for units engaged in combat in the RTS game StarCraft. The first extension is a script-based approach inspired by Portfolio Greedy Search and searches for sequences of scripts instead of actions. The second extension is a clusterbased approach as it assigns scripts to clusters of units based on their type and position. The presented results demonstrate that both the script-based and cluster-based UCTCD extensions outperform the original UCTCD with a winning percentage of 100% for battles with 32 units or more. Additionally, unit clustering is shown to give some improvement in large scenarios while it is less effective in small combats. The algorithms were tested in our StarCraft combat simulator called JarCraft, a complete Java translation of the original C++ package SparCraft, made in hopes of making this research area more accessible

  Links:

  • Paper

  Bibtex:

  "@inproceedings{justesen2014script,
    title={Script-and cluster-based UCT for StarCraft},
    author={Justesen, Niels and Tillman, B{\'a}lint and Togelius, Julian and Risi, Sebastian},
    booktitle={2014 IEEE Conference on Computational Intelligence and Games},
    pages={1--8},
    year={2014},
    organization={IEEE}}"
  

  ---

PhD Dissertation

Algorithms for Adaptive Game-playing Agents

Abstract

Several games have been promoted by researchers as key challenges in the research field of Artificial Intelligence (AI) through the years, with the ultimate goal of defeating the best human players in these games. Recent developments in deep learning have enabled computers to learn strong policies for many games, where previous methods have fallen short. However, the most complex games, such as the Real-time Strategy (RTS) game StarCraft (Blizzard Entertainment, 1998), are still not mastered by AI. We identify three properties of adaptivity that we believe are required to fully master the most difficult games with AI. These properties are: (1) intra-game adaptivity: the ability to adapt to opponent strategies within a game, (2) inter-game adaptivity: the ability to intelligently switch strategy in-between games, and (3) generality: the ability to generalize to many different, and most likely unseen, variations (such as different levels). We analyze the shortcomings of state-of-the-art game-playing algorithms in regards to adaptation and present novel algorithmic approaches to each property. Several of the presented approaches also attempt to overcome the difficulty of learning adaptive policies in games with sparse rewards. The main contributions in this dissertation are: (a) a continual evolutionary planning algorithm that performs online adaptive build-order planning in StarCraft, (b) an imitation learning approach to intra-game adaptive build-order planning in StarCraft, resulting in the first (to the best of our knowledge) neural-network-based bot that plays the full game, (c) a novel imitation learning method for learning behavioral repertoires from demonstrations, which allows for inter-game adaptivity, (d) an automatic reward shaping technique for reinforcement learning that automatically assigns feedback values based on the temporal rarity of pre-defined events, that works as a form of curriculum learning and regularization technique to avoid overfitted behaviors in games with sparse rewards, (e) a new reinforcement learning framework that incorporates procedural content generation to generate new training levels each episode that get progressively harder as the agent improves, which is shown to overcome sparse rewards and increase the generality of the learned policy, (f) a pragmatic way of evaluating the fairness of game competitions between humans and AI that further highlights the importance of adaptation, and (g) a new challenge and competition for AI that is based on the board game Blood Bowl, which is orders of magnitude more complex than the game go and requires a high level of generality. These contributions bring a new perspective on the AI challenge of playing complex games that has a focus on adaptation. We believe this perspective is crucial to achieving strong and robust game-playing AI. Our contributions may potentially have an impact on many important real-world problems beyond games, such as robotic tasks in changing environments with complex interactions that require a high level of adaptivity.

Master Thesis

Artificial Intelligence for Hero Academy

Abstract

In many competitive video games it is possible for players to compete against a computer controlled opponent. It is important that such opponents are able to play at a worthy level to keep players engaged. A great deal of research has been done on Artificial Intelligence (AI) in games to create intelligent computer controlled players, more commonly referred to as AI agents, for a large collection of game genres. In this thesis we have focused on how to create an intelligent AI agent for the tactical turn-based game Hero Academy, using our own open source game engine Hero AIcademy. In this game, players can perform five sequential actions resulting in millions of possible outcomes each turn. We have implemented and compared several AI methods mainly based on Monte Carlo Tree Search (MCTS) and evolutionary algorithms. A novel progressive pruning strategy is introduced that significantly improves MCTS in Hero Academy. Another approach to MCTS is introduced, in which the exploration constant is set to zero and greedy rollouts are used, that also gives significant improvement. An online evolutionary algorithm that evolves plans during each turn achieved the best results. The fitness function of the evolution is based on depth-limited rollouts to determine the value of plans. It did, however, not increase the performance significantly. The online evolution agent was able to play Hero Academy competitively against human beginners but was easily beaten by intermediate and expert players. Aside from searching for possible plans it is critical to evaluate the outcome of these intelligently. We evolved a neural network, using NEAT, that outperforms our own manually designed evaluator for small game boards, while more work is needed to obtain similar results for larger game boards.