Deep Learning for Video Game Playing
Niels Justesen Philip Bontrager Julian Togelius Sebastian Risi










Deep Learning for Video Game Playing
    Niels Justesen^1, Philip Bontrager^2, Julian Togelius^2, Sebastian Risi^1

^1IT University of Copenhagen, Copenhagen

^2New York University, New York


    Received: December 30, 2023/ Accepted: December 30, 2023
===========================================================================================================================================================





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. 







§ INTRODUCTION

Applying AI techniques to games is now an established research field with multiple conferences and dedicated journals. In this article, we review recent advances in deep learning for video game playing and employed game research platforms while highlighting important open challenges. Our motivation for writing this article is to review the field from the perspective of different types of games, the challenges they pose for deep learning, and how deep learning can be used to play these games. A variety of review articles on deep learning exists <cit.>, as well as surveys on reinforcement learning <cit.> and deep reinforcement learning <cit.>, here we focus on these techniques applied to video game playing.




In particular, in this article, we focus on game problems and environments that have been used extensively for DL-based Game AI, such as Atari/ALE, Doom, Minecraft, StarCraft, and car racing. Additionally, we review existing work and point out important challenges that remain to be solved. We are interested in  approaches that aim to play a particular video game well (in contrast to board games such as Go, etc.), from pixels or feature vectors, without an existing forward model. Several game genres are analyzed to point out the many and diverse challenges they pose to human and machine players.

It is important to note that there are many uses of AI in and for games that are not covered in this article; Game AI is a large and diverse field <cit.>. 
This article is focused on deep learning methods for playing video games well, while there is plenty of research on playing games in a believable, entertaining or human-like manner <cit.>. AI is also used for modeling players' behavior, experience or preferences <cit.>, or generating game content such as levels, textures or rules <cit.>. Deep learning is far from the only AI method used in games. Other prominent methods include Monte Carlo Tree Search <cit.> and evolutionary computation <cit.>. In what follows, it is important to be aware of the limitations of the scope of this article.

The paper is structured as follows: The next section gives an overview of different deep learning methods applied to games, followed by the different research platforms that are currently in use. Section <ref> reviews the use of DL methods in different video game types and Section <ref> gives a historical overview of the field. We conclude the paper by pointing out important open challenges in Section <ref> and a conclusion in Section <ref>.


















§ DEEP LEARNING IN GAMES OVERVIEW

This section gives a brief overview of neural networks and machine learning in the context of games. First, we describe common neural network architectures followed by an overview of the three main categories of machine learning tasks: supervised learning, unsupervised learning, and reinforcement learning. Approaches in these categories are typically based on gradient-descent optimization. We also highlight evolutionary approaches as well as a few examples of hybrid approaches that combine several optimization techniques.




 §.§ Neural Network Models


Artificial neural networks (ANNs) are general purpose functions that are defined by their network structure and the weight of each graph edge. Because of their generality and ability to approximate any continuous real-valued function (given enough parameters), they have been applied to a variety of tasks, including video game playing. 


The architectures of these ANNs can roughly be divided into two major categories: feedforward and recurrent neural networks (RNN). Feedforward networks take a single input, for example, a representation of the game state, and outputs probabilities or values for each possible action. 

Convolutional neural networks (CNN) consists of trainable filters and is suitable for processing image data such as pixels from a video game screen.



RNNs are typically applied to time series data, in which the output of the network can depend on the network's activation from previous time-steps <cit.>. The training process is similar to feedforward networks, except that the network's previous hidden state is fed back into the network together with the next input. This allows the network to become context-aware by memorizing the previous activations, which is useful when a single observation from a game does not represent the complete game state. For video game playing, it is common to use a stack of convolutional layers followed by recurrent layers and fully-connected feed-forward layers.

The following sections will give a brief overview of different optimization methods which are commonly used for learning game-playing behaviors with deep neural networks. These methods search for the optimal set of parameters to solve some problem. Optimization can also be used to find hyper-parameters, such as network architecture and learning parameters, and is well studied within deep learning <cit.>.



 §.§ Optimizing Neural Networks




  §.§.§ Supervised Learning


In supervised learning a model is trained from examples. During training, the model is asked to make a decision for which the correct answer is known. The error, i.e. difference between the provided answer and the ground truth, is used as a loss to update the model. The goal is to achieve a model that can generalize beyond the training data and thus perform well on examples it has never seen before. Large data sets usually improve the model's ability to generalize. 


In games, this data can come from play traces  <cit.> (i.e. humans playing through the game while being recorded), allowing the agent to learn the mapping from the input state to output actions based on what actions the human performed in a given state. If the game is already solved by another algorithm, it can be used to generate training data, which is useful if the first algorithm is too slow to run in real-time. 
While learning to play from existing data allows agents to quickly learn best practices, it is often brittle; the data available can be expensive to produce and may be missing key scenarios the agent should be able to deal with. For gameplay, the algorithm is limited to the strategies available in the data and cannot explore new ones itself. Therefore, in games, supervised algorithms are often combined with additional training through reinforcement learning algorithms <cit.>.



Another application of supervised learning in games is to learn the state transitions of a game. Instead of providing the action for a given state, the neural network can learn to predict the next state for an action-state pair. Thus, the network is essentially learning a model of the game, which can then be used to play the game better or to perform planning <cit.>.







  §.§.§ Unsupervised Learning


Instead of learning a mapping between data and its labels, the objective in unsupervised learning is to discover patterns in the data. 

These algorithms can learn the distribution of features for a dataset, which can be used to cluster similar data, compress data into its essential features, or create new synthetic data that is characteristic of the original data. For games with sparse rewards (such as Montezuma's Revenge), learning from data in an unsupervised fashion is a potential solution and an important open deep learning challenge.


A prominent unsupervised learning technique in deep learning is the autoencoder, which is a neural network that attempts to learn the identity function such that the output is identical to the input <cit.>. The network consists of two parts: an encoder that maps the input x to a low-dimensional hidden vector h, and a decoder that attempts to re-construct x from h. 

The main idea is that by keeping h small, the network has to learn to compress the data and therefore learn a good representation. Researchers are beginning to apply such unsupervised algorithms to games to help distill high dimensional data to more meaningful lower dimensional data, but this research direction is still in its early stages <cit.>. For a more detailed overview of supervised and unsupervised learning see <cit.>.





  §.§.§ Reinforcement Learning Approaches



	

	
	
	

	
	

	
	




In reinforcement learning (RL) an agent learns a behavior by interacting with an environment that provides a reward signal back to the agent. A video game can easily be modeled as an environment in an RL setting, wherein players are modeled as agents with a finite set of actions that can be taken at each step and the reward signal can be determined by the game score.



In RL, the agent relies on the reward signal. These signals can occur frequently, such as the change in score within a game, or it can occur infrequently, such as whether an agent has won or lost a game. Video games and RL go well together since most games give rewards for successful strategies.  
Open world games do not always have a clear reward model and are thus challenging for RL algorithms.

A key challenge in applying RL to games with sparse rewards is to determine how to assign credit to the many previous actions when a reward signal is obtained. The reward R(s) for state s, needs to be propagated back to the actions that lead to the reward. Historically, there are several different ways this problem is approached which are described below. If an environment can be described as a Markov Decision Process (MDP), then the agent can build a probability tree of future states and their rewards. The probability tree can then be used to calculate the utility of the current state. For an RL agent this

means learning the model P(s' | s, a), where P is the probability of state s' given state s and action a. With a model P, utilities can be calculated by 

    U(s) = R(s) + γmax_a ∑_s' P(s' | s, a)U(s'),

where γ is the discount factor for the utility of future states. This algorithm, known as Adaptive Dynamic Programming, can converge rather quickly as it directly handles the credit assignment problem <cit.>. The issue is that it has to build a probability tree over the whole problem space and is therefore intractable for large problems. As the games covered in this work are considered "large problems", we will not go into further detail on this algorithm.

Another approach to this problem is temporal difference (TD) learning. In TD learning, the agent learns the utilities U directly based off of the observation that the current utility is equal to the current reward plus the utility value of the next state <cit.>. Instead of learning the state transition model P, it learns to model the utility U, for every state. The update equation for U is:

    U(s) = U(s) + α(R(s) + γ U(s') - U(s)),
 
where α is the learning rate of the algorithm. The equation above does not take into account how s' was chosen. If a reward is found at s_t, it will only affect U(s_t). The next time the agent is at s_t-1, then U(s_t-1) will be aware of the future reward. This will propagate backward over time. Likewise, less common transitions will have less of an impact on utility values. Therefore, U will converge to the same values as are obtained from ADP, albeit slower.

There are alternative implementations of TD that learn rewards for state-action pairs. This allows an agent to choose an action, given the state, with no model of how to transition to future states. For this reason, these approaches are referred to as model-free methods. A popular model-free RL method is Q-learning <cit.> where the utility of a state is equal to the maximum Q-value for a state. The update equation for Q-learning is: 

    Q(s, a) = Q(s, a) + α(R(s) + γmax_a' Q(s',a') - Q(s, a)).

In Q-learning, the future reward is accounted for by selecting the best-known future state-action pair. In a similar algorithm called SARSA (State-Action-Reward-State-Action), Q(s,a) is updated only when the next a has been selected and the next s is known <cit.>. This action pair is used instead of the maximum Q-value. This makes SARSA an on-policy method in contrast to Q-learning which is off-policy because SARSA's Q-value accounts  for the agent's own policy. 

Q-learning and SARSA can use a neural network as a function approximator for the Q-function. The given Q update equation can be used to provide the new "expected" Q value for a state-action pair. The network can then be updated as it is in supervised learning.

An agent's policy π(s) determines which action to take given a state s. For Q-learning, a simple policy would be to always take the action with the highest Q-value. Yet, early on in training, Q-values are not very accurate and an agent could get stuck always exploiting a small reward. A learning agent should prioritize exploration of new actions as well as the exploitation of what it has learned. This problem is known as a multi-armed bandit problem and has been well explored. The ϵ-greedy strategy is a simple approach that selects the (estimated) optimal action with ϵ probability and otherwise selects a random action. 

One approach to RL is to perform gradient descent in the policy's parameter space. Let π_θ(s, a) be the probability that action a is taken at state s given parameters θ. 

The basic policy gradient algorithm from the REINFORCE family of algorithms <cit.> updates θ using the gradient ∇_θ∑_a π_θ(s, a)R(s) where R(s) is the discounted cumulative reward obtained from s and forward. In practice, a sample of possible actions from the  policy is taken and it is updated to increase the likelihood that the more successful actions are returned in the future. This lends itself well to neural networks as π can be a neural network and θ the network weights.


Actor-Critic methods combine the policy gradient approach with TD learning, where an actor learns a policy π_θ(s,a) using the policy gradient algorithm, and the critic learns to approximate R using TD-learning <cit.>. Together, they are an effective approach to iteratively learning a policy. In actor-critic methods there can either be a single network to predict both π and R, or two separate networks. For an overview of reinforcement learning applied to deep neural networks we suggest the article by Arulkumaran et al. <cit.>.




  §.§.§ Evolutionary Approaches

The optimization techniques discussed so far rely on gradient descent, based on differentiation of a defined error. However, derivative-free optimization methods such as evolutionary algorithms have also been widely used to train neural networks, including, but not limited to, reinforcement learning tasks. This approach, often referred to as neuroevolution (NE), can optimize a network's weights as well as their topology/architecture. Because of their generality, NE approaches have been applied extensively to different types of video games. For a complete overview of this field, we refer the interested reader to our NE survey paper <cit.>.

Compared to gradient-descent based training methods, NE approaches have the benefit of not requiring the network to be differentiable and can be applied to both supervised, unsupervised and reinforcement learning problems. 
The ability to evolve the topology, as well as the weights, potentially offers a way of automating the development of neural network architecture, which currently requires considerable domain knowledge. The 
promise of these techniques is that evolution could find a neural network topology that is better at playing a certain game than existing human-designed architectures.
While NE has been traditionally applied to problems with lower input dimensionality than typical deep learning approaches, recently Salimans et al. <cit.> showed that evolution strategies, which rely on parameter-exploration through stochastic noise instead of calculating gradients, can achieve results competitive to current deep RL approaches for Atari video game playing, given enough computational resources. 




  §.§.§ Hybrid Learning Approaches

More recently researchers have started to investigate hybrid approaches for video game playing, which combine deep learning methods with other machine learning approaches. 


Both Alvernaz and Togelius <cit.> and Poulsen et al. <cit.> experimented with combining a deep network trained through gradient descent feeding a condensed feature representation into a network trained through artificial evolution. These hybrids aim to combine the best of both approaches as deep learning methods are able to learn directly from high-dimensional input, while evolutionary methods do not rely on differentiable architectures and work well in games with sparse rewards. Some results suggest that gradient-free methods seem to be better in the early stages of training to avoid premature convergence while gradient-based methods may be better in the end when less exploration is needed <cit.>.

Another hybrid method for board game playing was AlphaGo <cit.> that relied on deep neural networks and tree search methods to defeat the world champion in Go, and <cit.> that applies planning on top of a predictive model. 

In general, the hybridization of ontogenetic RL (such as Q-learning) with phylogenetic methods (such as evolutionary algorithms) has the potential to be very impactful as it could enable concurrent learning on different timescales <cit.>.



§ GAME GENRES AND RESEARCH PLATFORMS


The fast progression of deep learning methods is undoubtedly due to the convention of comparing results on publicly available datasets. A similar convention in game AI is to use game environments to compare game playing algorithms, in which methods are ranked based on their ability to score points or win in games. Conferences like the IEEE Conference on Computational Intelligence and Games run popular competitions in a variety of game environments. 



This section describes popular game genres and research platforms, used in the literature, that are relevant to deep learning; some examples are shown in Figure <ref>. For each genre, we briefly outline what characterizes that genre and describe the challenges faced by algorithms playing games of the genre. The video games that are discussed in this paper have to a large extent supplanted an earlier generation of simpler control problems that long served as the main reinforcement learning benchmarks but are generally too simple for modern RL methods.
In such classic control problems, the input is a simple feature vector, describing the position, velocity, and angles etc. Popular platforms for such problems are rllab <cit.>, which includes classic problems such as pole balancing and the mountain car problem, and MuJoCo (Multi-Joint dynamics with Contact), a physics engine for complex control tasks such as the humanoid walking task <cit.>. 



 §.§ Arcade Games


Classic arcade games, of the type found in the late seventies' and early eighties' arcade cabinets, home video game consoles and home computers, have been commonly used as AI benchmarks within the last decade. Representative platforms for this game type are the Atari 2600, Nintendo NES, Commodore 64 and ZX Spectrum. Most classic arcade games are characterized by movement in a two-dimensional space (sometimes represented isometrically to provide the illusion of three-dimensional movement), heavy use of graphical logics (where game rules are triggered by the intersection of sprites or images), continuous-time progression, and either continuous-space or discrete-space movement. The challenges of playing such games vary by game. Most games require fast reactions and precise timing, and a few games, in particular, early sports games such as Track & Field (Konami, 1983) rely almost exclusively on speed and reactions. Many games require prioritization of several co-occurring events, which requires some ability to predict the behavior or trajectory of other entities in the game. This challenge is explicit in e.g. Tapper (Bally Midway, 1983) but also in different ways part of platform games such as Super Mario Bros (Nintendo, 1985) and shooters such as Missile Command (Atari Inc., 1980). Another common requirement is navigating mazes or other complex environments, as exemplified clearly by games such as Pac-Man (Namco, 1980) and Boulder Dash (First Star Software, 1984). Some games, such as Montezuma's Revenge (Parker Brothers, 1984), require long-term planning involving the memorization of temporarily unobservable game states. Some games feature incomplete information and stochasticity, others are completely deterministic and fully observable.


The most notable game platform used for deep learning methods is the Arcade Learning Environment (ALE) <cit.>. ALE is built on top of the Atari 2600 emulator Stella and contains more than 50 original Atari 2600 games. The framework extracts the game score, 160×210 screen pixels and the RAM content that can be used as input for game playing agents. ALE was the main environment explored in the first deep RL papers that used raw pixels as input. By enabling agents to learn from visual input, ALE thus differs from classic control problems in the reinforcement learning literature, such as the Cart Pole and Mountain Car problems. An overview and discussion of the ALE environment can be found in <cit.>.  
 

Another platform for classic arcade games is the Retro Learning Environment (RLE) that currently contains seven games released for the Super Nintendo Entertainment System (SNES) <cit.>. Many of these games have 3D graphics and the controller allows for over 720 action combinations. SNES games are thus more complex and realistic than Atari 2600 games but RLE has not been as popular as ALE. 



The General Video Game AI (GVG-AI) framework <cit.> allows for easy creation and modification of games and levels using the Video Game Description Language (VGDL) <cit.>. This is ideal for testing the generality of agents on multiple games or levels. GVG-AI includes over 100 classic arcade games each with five different levels.





 §.§ Racing Games


Racing games are games where the player is tasked with controlling some kind of vehicle or character so as to reach a goal in the shortest possible time, or as to traverse as far as possible along a track in a given time. Usually, the game employs a first-person perspective or a vantage point from just behind the player-controlled vehicle. The vast majority of racing games take a continuous input signal as steering input, similar to a steering wheel. Some games, such as those in the Forza Motorsport (Microsoft Studios, 2005–2016) or Real Racing (Firemint and EA Games, 2009–2013) series, allow for complex input including gear stick, clutch and handbrake, whereas more arcade-focused games such as those in the Need for Speed (Electronic Arts, 1994–2015) series typically have a simpler set of inputs and thus lower branching factor.

A challenge that is common in all racing games is that the agent needs to control the position of the vehicle and adjust the acceleration or braking, using fine-tuned continuous input, so as to traverse the track as fast as possible. Doing this optimally requires at least short-term planning, one or two turns forward. If there are resources to be managed in the game, such as fuel, damage or speed boosts, this requires longer-term planning. When other vehicles are present on the track, there is an adversarial planning aspect added, in trying to manage or block overtaking; this planning is often done in the presence of hidden information (position and resources of other vehicles on different parts of the track).

A popular environment for visual reinforcement learning with realistic 3D graphics is the open racing car simulator TORCS <cit.>.



 §.§ First-Person Shooters (FPS)


More advanced game environments have recently emerged for visual reinforcement learning agents in a First-Person Shooters (FPS). In contrast to classic arcade games such as those in the ALE benchmark, FPSes have 3D graphics with partially observable states and are thus a more realistic environment to study. Usually, the viewpoint is that of the player-controlled character, though some games that are broadly in the FPS categories adopt an over-the-shoulder viewpoint. The design of FPS games is such that part of the challenge is simply fast perception and reaction, in particular, spotting enemies and quickly aiming at them. But there are other cognitive challenges as well, including orientation and movement in a complex three-dimensional environment, predicting actions and locations of multiple adversaries, and in some game modes also team-based collaboration. If visual inputs are used, there is the challenge of extracting relevant information from pixels.

Among FPS platforms are ViZDoom, a framework that allows agents to play the classic first-person shooter Doom (id Software, 1993–2017) using the screen buffer as input <cit.>. DeepMind Lab is a platform for 3D navigation and puzzle-solving tasks based on the Quake III Arena (id Software, 1999) engine <cit.>.



 §.§ Open-World Games

Open-world games such as Minecraft (Mojang, 2011) or the Grand Theft Auto (Rockstar Games, 1997–2013) series are characterized by very non-linear gameplay, with a large game world to explore, either no set goals or many goals with unclear internal ordering, and large freedom of action at any given time. Key challenges for agents are exploring the world and setting goals which are realistic and meaningful. As this is a very complex challenge, most research use these open environments to explore reinforcement learning methods that can reuse and transfer learned knowledge to new tasks. Project Malmo is a platform built on top of the open-world game Minecraft, which can be used to define many diverse and complex problems <cit.>.



 §.§ Real-time Strategy Games


Strategy games are games where the player controls multiple characters or units, and the objective of the game is to prevail in some sort of conquest or conflict. Usually, but not always, the narrative and graphics reflect a military conflict, where units may be e.g. knights, tanks or battleships. The key challenge in strategy games is to lay out and execute complex plans involving multiple units. This challenge is in general significantly harder than the planning challenge in classic board games such as Chess mainly because multiple units must be moved at any time and the effective branching factor is typically enormous. The planning horizon can be extremely long, where actions that are taken at the beginning of a game impact the overall strategy. In addition, there is the challenge of predicting the moves of one or several adversaries, who have multiple units themselves. Real-time Strategy Games (RTS) are strategy games which do not progress in discrete turns, but where actions can be taken at any point in time. RTS games add the challenge of time prioritization to the already substantial challenges of playing strategy games.

The StarCraft (Blizzard Entertainment, 1998–2017) series is without a doubt the most studied game in the Real-Time Strategy (RTS) genre. The Brood War API (BWAPI)[http://bwapi.github.io/] enables software to communicate with StarCraft while the game runs, e.g. to extract state features and perform actions. BWAPI has been used extensively in game AI research, but currently, only a few examples exist where deep learning has been applied. TorchCraft is a library built on top of BWAPI that connects the scientific computing framework Torch to StarCraft to enable machine learning research for this game <cit.>. Additionally, DeepMind and Blizzard (the developers of StarCraft) have developed a machine learning API to support research in StarCraft II with features such as simplified visuals designed for convolutional networks <cit.>. This API contains several mini-challenges while it also supports the full 1v1 game setting. μRTS <cit.> and ELF <cit.> are two minimalistic RTS game engines that implement some of the features that are present in RTS games.



 §.§ Team Sports Games

Popular sports games are typically based on team-based sports such as soccer, basketball, and football. These games aim to be as realistic as possible with life-like animations and 3D graphics.   Several soccer-like environments have been used extensively as research platforms, both with physical robots and 2D/3D simulations, in the annual Robot World Cup Soccer Games (RoboCup) <cit.>. 
Keepaway Soccer is a simplistic soccer-like environment where one team of agents try to maintain control of the ball while another team tries to gain control of it <cit.>. A similar environment for multi-agent learning is RoboCup 2D Half-Field-Offense (HFO) where teams of 2-3 players either take the role as offense or defense on one half of a soccer field <cit.>.



 §.§ Text Adventure Games

A classic text adventure game is a form of interactive fiction where players are given descriptions and instructions in text, rather than graphics, and interact with the storyline through text-based commands <cit.>. These commands are usually used to query the system about the state, interact with characters in the story, collect and use items, or navigate the space in the fictional world.

These games typically implement one of three text-based interfaces: parser-based, choice-Based, and hyperlink-based <cit.>. Choice-based and hyperlink-based interfaces provide the possible actions to the player at a given state as a list, out of context, or as links in the state description. Parser-Based interfaces are, on the other hand, open to any input and the player has to learn what words the game understands. This is interesting for computers as it is much more akin to natural language, where you have to know what actions should exist based on your understanding of language and the given state.

Unlike some other game genres, like arcade games, text adventure games have not had a standard benchmark of games that everyone can compare against. 
This makes a lot of results hard to directly compare. A lot of research has focused on games that run on Infocom's Z-Machine game engine, an engine that can play a lot of the early, classic games. Recently, Microsoft has introduced the environment TextWorld to help create a standardized text adventure environment <cit.>.



 §.§ OpenAI Gym & Universe

OpenAI Gym is a large platform for comparing reinforcement learning algorithms with a single interface to a suite of different environments including ALE, GVG-AI, MuJoCo, Malmo, ViZDoom and more <cit.>. OpenAI Universe is an extension to OpenAI Gym that currently interfaces with more than a thousand Flash games and aims to add many modern video games in the future[https://universe.openai.com/].



§ DEEP LEARNING METHODS FOR GAME PLAYING



This section gives an overview of deep learning techniques used to play video games, divided by game genre. Table <ref> lists deep learning methods for each game genre and highlights which input features, network architecture, and training methods they rely upon. A typical neural network architecture used in deep RL is shown in Figure <ref>. 






 §.§ Arcade Games


The Arcade Learning Environment (ALE) consists of more than 50 Atari games and has been the main testbed for deep reinforcement learning algorithms that learn control policies directly from raw pixels. This section reviews the main advancements that have been demonstrated in ALE. An overview of these advancements is shown in Table <ref>. 


Deep Q-Network (DQN) was the first learning algorithm that showed human expert-level control in ALE <cit.>. DQN was tested in seven Atari 2600 games and outperformed previous approaches, such as SARSA with feature construction <cit.> and neuroevolution <cit.>, as well as a human expert on three of the games. DQN is based on Q-learning, where a neural network model learns to approximate Q^π(s,a) that estimates the expected return of taking action a in state s while following a behavior policy μ. A simple network architecture consisting of two convolutional layers followed by a single fully-connected layer was used as a function approximator. 

A key mechanism in DQN is experience replay <cit.>, where experiences in the form {s_t, a_t, r_t+1, s_t+1} are stored in a replay memory and randomly sampled in batches when the network is updated. This enables the algorithm to reuse and learn from past and uncorrelated experiences, which reduces the variance of the updates. DQN was later extended with a separate target Q-network which parameters are held fixed between individual updates and was shown to achieve above human expert scores in 29 out of 49 tested games <cit.>. 

Deep Recurrent Q-Learning (DRQN) extends the DQN architecture with a recurrent layer before the output and works well for games with partially observable states <cit.>.

A distributed version of DQN was shown to outperform a non-distributed version in 41 of the 49 games using the Gorila architecture (General Reinforcement Learning Architecture) <cit.>. Gorila parallelizes actors that collect experiences into a distributed replay memory as well as parallelizing learners that train on samples from the same replay memory. 



One problem with the Q-learning algorithm is that it often overestimates action values because it uses the same value function for action-selection and action-evaluation. Double DQN, based on double Q-learning <cit.>, reduces the observed overestimation by learning two value networks with parameters θ and θ^' that both use the other network for value-estimation, such that the target Y_t = R_t+1 + γ Q(S_t+1, max_a Q(S_t+1,a;θ_t);θ^'_t) <cit.>. 

Another improvement is prioritized experience replay from which important experiences are sampled more frequently based on the TD-error, which was shown to significantly improve both DQN and Double DQN <cit.>.

Dueling DQN uses a network that is split into two streams after the convolutional layers to separately estimate state-value V^π(s) and the action-advantage A^π(s,a), such that Q^π(s,a) = V^π(s) + A^π(s,a) <cit.>. Dueling DQN improves Double DQN and can also be combined with prioritized experience replay. 

Double DQN and Dueling DQN were also tested in the five more complex games in the RLE and achieved a mean score of around 50% of a human expert <cit.>. The best result in these experiments was by Dueling DQN in the game Mortal Kombat (Midway, 1992) with 128%. 

Bootstrapped DQN improves exploration by training multiple Q-networks. A randomly sampled network is used during each training episode and bootstrap masks modulate the gradients to train the networks differently <cit.>. 

Robust policies can be learned with DQN for competitive or cooperative multi-player games by training one network for each player and play them against each other in the training process <cit.>. Agents trained in multiplayer mode perform very well against novel opponents, whereas agents trained against a stationary algorithm fail to generalize their strategies to novel adversaries.

Multi-threaded asynchronous variants of DQN, SARSA and Actor-Critic methods can utilize multiple CPU threads on a single machine, reducing  training roughly linear to the number of parallel threads <cit.>. These variants do not rely on a replay memory because the network is updated on uncorrelated experiences from parallel actors which also helps to stabilize on-policy methods. The Asynchronous Advantage Actor-Critic (A3C) algorithm is an actor-critic method that uses several parallel agents to collect experiences that all asynchronously update a global actor-critic network. A3C outperformed Prioritized Dueling DQN, which was trained for 8 days on a GPU, with just half the training time on a CPU <cit.>.

An actor-critic method with experience replay (ACER) implements an efficient trust region policy method that forces updates to not deviate far from a running average of past policies <cit.>. The performance of ACER in ALE matches Dueling DQN with prioritized experience replay and A3C without experience replay, while it is much more data efficient. 

A3C with progressive neural networks <cit.> can effectively transfer learning from one game to another. The training is done by instantiating a network for every new task with connections to all the previous learned networks. This gives the new network access to knowledge already learned. 

The Advantage Actor-Critic (A2C), a synchronous variant of A3C <cit.>, updates the parameters synchronously in batches and has comparable performance while only maintaining one neural network <cit.>. Actor-Critic using Kronecker-Factored Trust Region (ACKTR) extends A2C by approximating the natural policy gradient updates for both the actor and the critic <cit.>. In Atari, ACKTR has slower updates compared to A2C (at most 25% per time step) but is more sample efficient (e.g. by a factor of 10 in Atlantis) <cit.>. Trust Region Policy Optimization (TRPO) uses a surrogate objective with theoretical guarantees for monotonic policy improvement, while it practically implements an approximation called trust region <cit.>. This is done by constraining network updates with a bound on the KL divergence between the current and the updated policy. TRPO has robust and data efficient performance in Atari games while it has high memory requirements and several restrictions. Proximal Policy Optimization (PPO) is an improvement on TRPO that uses a similar surrogate objective <cit.>, but instead uses a soft constraint (originally suggested in <cit.>) by adding the KL-divergence as a penalty. Instead of having a fixed penalty coefficient, it uses a clipped surrogate objective that penalizes policy updates outside some specified interval. PPO was shown to be more sample efficient than A2C and on par with ACER in Atari, while PPO does not rely on replay memory. PPO was also shown to have comparable or better performance than TRPO in continuous control tasks while being simpler and easier to parallelize.

IMPALA (Importance Weighted Actor-Learner Architecture) is an actor-critic method where multiple learners with GPU access share gradients between each other while being synchronously updated from a set of actors <cit.>. This method can scale to a large number of machines and outperforms A3C. Additionally, IMPALA was trained, with one set of parameters, to play all 57 Atari games in ALE with a mean human-normalized score of  176.9% (median of 59.7%) <cit.>. Experiences collected by the actors in the IMPALA setup can lack behind the learners' policy and thus result in off-policy learning. This discrepancy is mitigated through a V-trace algorithm that weighs the importance of experiences based on the difference between the actor's and learner's policies <cit.>.

UNREAL (UNsupervised REinforcement and Auxiliary Learning) algorithm is based on A3C but uses a replay memory from which it learns auxiliary tasks and pseudo-reward functions concurrently <cit.>. UNREAL only shows a small improvement over vanilla A3C in ALE, but larger improvements in other domains (see Section <ref>). 

Distributional DQN takes a distributional perspective on reinforcement learning by treating Q(s,a) as an approximate distribution of returns instead of a single approximate expectation for each action <cit.>. The distribution is divided into a so-called set of atoms, which determines the granularity of the distribution. Their results show that the more fine-grained the distributions are, the better are the results, and with 51 atoms (this variant was called C51) it achieved mean scores in ALE almost comparable to UNREAL.

In NoisyNets, noise is added to the network parameters and a unique noise level for each parameter is learned using gradient descent <cit.>. In contrast to ϵ-greedy exploration, where an agent either samples actions from the policy or from a uniform random distribution, NoisyNets use a noisy version of the policy to ensure exploration, and this was shown to improve DQN (NoisyNet-DQN) and A3C (NoisyNet-A3C).

Rainbow combines several DQN enhancements: Double DQN, Prioritized Replay, Dueling DQN, Distributional DQN, and NoisyNets, and achieved a mean score higher than any of the enhancements individually <cit.>.

Evolution Strategies (ES) are black-box optimization algorithms that rely on parameter-exploration through stochastic noise instead of calculating gradients and were found to be highly parallelizable with a linear speedup in training time when more CPUs are used <cit.>. 720 CPUs were used for one hour whereafter ES managed to outperform A3C (which ran for 4 days) in 23 out of 51 games, while ES used 3 to 10 times as much data due to its high parallelization. ES only ran a single day and thus their full potential is currently unknown. Novelty search is a popular algorithm that can overcome environments with deceptive and/or sparse rewards by guiding the search towards novel behaviors <cit.>. ES has been extended to use Novelty Search (NS-ES) which outperforms ES on several challenging Atari games by defining novel behaviors based on the RAM states <cit.>. A quality-diversity variant called NSR-ES that uses both novelty and the reward signal reach an even higher performance <cit.>. NS-ES and NSR-ES reached worse results on a few games, possibly where the reward function is not sparse or deceptive. 

A simple genetic algorithm with a Gaussian noise mutation operator evolves the parameters of a deep neural network (Deep GA) and can achieve surprisingly good scores across several Atari games <cit.>. Deep GA shows comparable results to DQN, A3C, and ES on 13 Atari games using up to thousands of CPUs in parallel. Additionally, random search, given roughly the same amount of computation, was shown to outperform DQN on 4 out of 13 games and A3C on 5 games <cit.>. While there has been concern that evolutionary methods do not scale as well as gradient descent-based methods, one possibility is separating the feature construction from the policy network; evolutionary algorithms can then create extremely small networks that still play well <cit.>.





A few supervised learning approaches have been applied to arcade games. In Guo et al. <cit.> a slow planning agent was applied offline, using Monte-Carlo Tree Search, to generate data for training a CNN via multinomial classification. This approach, called UCTtoClassification, was shown to outperform DQN. Policy distillation <cit.> or actor-mimic <cit.> methods can be used to train one network to mimic a set of policies (e.g. for different games). These methods can reduce the size of the network and sometimes also improve the performance. A frame prediction model can be learned from a dataset generated by a DQN agent using the encoding-transformation-decoding network architecture; the model can then be used to improve exploration in a retraining phase <cit.>. Self-supervised tasks, such as reward prediction, validation of state-successor pairs, and mapping states and successor states to actions can define auxiliary losses used in pre-training of a policy network, which ultimately can improve learning <cit.>.





The training objective provides feedback to the agent while the performance objective specifies the target behavior. Often, a single reward function takes both roles, but for some games, the performance objective does not guide the training sufficiently. The Hybrid Reward Architecture (HRA) splits the reward function into n different reward functions, where each of them are assigned a separate learning agent <cit.>. HRA does this by having n output streams in the network, and thus n Q-values, which are combined when actions are selected. HRA was able to achieve the maximum possible score in less than 3,000 episodes.



 §.§ Montezuma's Revenge


Environments with sparse feedback remain an open challenge for reinforcement learning. The game Montezuma's Revenge is a good example of such an environment in ALE and has thus been studied in more detail and used for benchmarking learning methods based on intrinsic motivation and curiosity. The main idea of applying intrinsic motivation is to improve the exploration of the environment based on some self-rewarding system, which eventually will help the agent to obtain an extrinsic reward. DQN fails to obtain any reward in this game (receiving a score of 0) and Gorila achieves an average score of just 4.2. A human expert can achieve 4,367 points and it is clear that the methods presented so far are unable to deal with environments with such sparse rewards. A few promising methods aim to overcome these challenges.

Hierarchical-DQN (h-DQN) <cit.>  operates on two temporal scales, where one Q-value function Q_1(s,a;g), the controller, learns a policy over actions that satisfy goals chosen by a higher-level Q-value function Q_2(s, g), the meta-controller, which learns a policy over intrinsic goals (i.e. which goals to select). This method was able to reach an average score of around 400 in Montezuma's Revenge where goals were defined as states in which the agent reaches (collides with) a certain type of object. This method, therefore, must rely on some object detection mechanism. 

Pseudo-counts have been used to provide intrinsic motivation in the form of exploration bonuses when unexpected pixel configurations are observed and can be derived from CTS density models <cit.> or neural density models <cit.>. Density models assign probabilities to images, and a model's pseudo count of an observed image is the model's change in prediction compared to being trained one  additional time on the same image.
Impressive results were achieved in Montezuma's Revenge and other hard Atari games by combining DQN with the CTS density model (DQN-CTS) or the PixelCNN density model (DQN-PixelCNN) <cit.>. Interestingly, the results were less impressive when the CTS density model was combined with A3C (A3C-CTS) <cit.>. 



\end






Ape-X DQN is a distributed DQN architecture similar to Gorila, as in actors are separated from the learner. Ape-X DQN was able to reach state-of-art results across the 57 Atari games using 376 cores and 1 GPU, running at ∼50K FPS <cit.>. Deep Q-learning from Demonstrations (DQfD) draw samples from an experience replay buffer that is initialized with demonstration data from a human expert and is superior to previous methods on 11 Atari games with sparse rewards <cit.>. Ape-X DQfD combines the distributed architecture from Ape-X and the learning algorithm from DQfD using expert data and was shown to outperform all previous methods in ALE as well as beating level 1 in Montezuma's Revenge <cit.>.


To improve the performance, Kaplan et. al. augmented the agent training with text instructions. An instruction-based reinforcement learning approach that uses both a CNN for visual input and RNN for text-based instruction, inputs managed to achieve a score of 3,500 points. Instructions were linked to positions in rooms and agents were rewarded when they reached those locations <cit.>, demonstrating a fruitful collaboration between a human and a learning algorithm. Experiments in Montezuma's Revenge also showed that the network learned to generalize to unseen instructions that were similar to previous instructions.

Similar work demonstrates how an agent can execute text-based commands in a 2D maze-like environment called XWORLD, such as walking to and picking up objects, after having learned a teacher's language <cit.>. An RNN-based language module is connected to a CNN-based perception module. These two modules were then connected to an action-selection module and a recognition module that learns the teacher's language in a question answering process.




 §.§ Racing Games

There are generally two paradigms for vision-based autonomous driving highlighted in Chen at al. <cit.>; (1) end-to-end systems that learn to map images to actions directly (behavior reflex), and (2) systems that parse the sensor data to make informed decisions (mediated perception). An approach that falls in between these paradigms is direct perception where a CNN learns to map from images to meaningful affordance indicators, such as the car angle and distance to lane markings, from which a simple controller can make decisions <cit.>. Direct perception was trained on recordings of 12 hours of human driving in TORCS and the trained system was able to drive in very diverse environments. Amazingly, the network was also able to generalize to real images. 

End-to-end reinforcement learning algorithms such as DQN cannot be directly applied to continuous environments such as racing games because the action space must be discrete and with relatively low dimensionality. Instead, policy gradient methods, such as actor-critic <cit.> and Deterministic Policy Gradient (DPG) <cit.> can learn policies in high-dimensional and continuous action spaces. Deep DPG (DDPG) is a policy gradient method that implements both experience replay and a separate target network and was used to train a CNN end-to-end in TORCS from images <cit.>.

The aforementioned A3C methods have also been applied to the racing game TORCS using only pixels as input <cit.>. In those experiments, rewards were shaped as the agent's velocity on the track, and after 12 hours of training, A3C reached a score between roughly 75% and 90% of a human tester in tracks with and without opponent bots, respectively. 


While most approaches to training deep networks from high-dimensional input in video games are based on gradient descent, a notable exception is an approach by Koutník et al. <cit.>, where Fourier-type coefficients were evolved that encoded a recurrent network with over 1 million weights. Here, evolution was able to find a high-performing controller for TORCS that only relied on high-dimensional visual input. 



 §.§ First-Person Shooters



Kempka et al. <cit.> demonstrated that a CNN with max-pooling and fully connected layers trained with DQN can achieve human-like behaviors in basic scenarios. In the Visual Doom AI Competition 2016[http://vizdoom.cs.put.edu.pl/competition-cig-2016], a number of participants submitted pre-trained neural network-based agents that competed in a multi-player deathmatch setting. Both a limited competition was held, in which bots competed in known levels, and a full competition that included bots competing in unseen levels. 
The winner of the limited track used a CNN trained with A3C using reward shaping and curriculum learning <cit.>. Reward shaping tackled the problem of sparse and delayed rewards, giving artificial positive rewards for picking up items and negative rewards for using ammunition and losing health. Curriculum learning attempts to speed up learning by training on a set of progressively harder environments <cit.>. The second-place entry in the limited track used a modified DRQN network architecture with an additional stream of fully connected layers to learn supervised auxiliary tasks such as enemy detection, with the purpose of speeding up the training of the convolutional layers <cit.>. Position inference and object mapping from pixels and depth-buffers using Simultaneous Localization and Mapping (SLAM) also improve DQN in Doom <cit.>.



The winner of the full deathmatch competition implemented a Direct Future Prediction (DFP) approach that was shown to outperform DQN and A3C

<cit.>. The architecture used in DFP has three streams: one for the screen pixels, one for lower-dimensional measurements describing the agent's current state, and one for describing the agent's goal, which is a linear combination of prioritized measurements. DFP collects experiences in a memory and is trained with supervised learning techniques to predict the future measurements based on the current state, goal and selected action. During training, actions are selected that yield the best-predicted outcome, based on the current goal. This method can be trained on various goals and generalizes to unseen goals at test time.  


Navigation in 3D environments is one of the important skills required for FPS games and has been studied extensively. A CNN+LSTM network was trained with A3C extended with additional outputs predicting the pixel depths and loop closure, showing significant improvements <cit.>. 

The UNREAL algorithm, based on A3C, implements an auxiliary task that trains the network to predict the immediate subsequent future reward from a sequence of consecutive observations. UNREAL was tested on fruit gathering and exploration tasks in OpenArena

and achieved a mean human-normalized score of 87%, where A3C only achieved 53% <cit.>.

The ability to transfer knowledge to new environments can reduce the learning time and can in some cases be crucial for some challenging tasks. Transfer learning can be achieved by pre-training a network in similar environments with simpler tasks or by using random textures during training <cit.>. The Distill and Transfer Learning (Distral) method trains several worker policies (one for each task) concurrently and shares a distilled policy  <cit.>. The worker policies are regularized to stay close to the shared policy which will be the centroid of the worker policies. Distral was applied to DeepMind Lab.



The Intrinsic Curiosity Module (ICM), consisting of several neural networks, computes an intrinsic reward each time step based on the agent's inability to predict the outcome of taking actions. It was shown to learn to navigate in complex Doom and Super Mario levels only relying on intrinsic rewards <cit.>.









 §.§ Open-World Games

The Hierarchical Deep Reinforcement Learning Network (H-DRLN) architecture implements a lifelong learning framework, which is shown  to be able to transfer knowledge between simple tasks in Minecraft such as navigation, item collection, and placement tasks <cit.>. H-DRLN uses a variation of policy distillation <cit.> to retain and encapsulate learned knowledge into a single network. 

Neural Turing Machines (NTMs) are fully differentiable neural networks coupled with an external memory resource, which can learn to solve simple algorithmic problems such as copying and sorting <cit.>. Two memory-based variations, inspired by NTM, called Recurrent Memory Q-Network (RMQN) and Feedback Recurrent Memory Q-Network (FRMQN) were able to solve complex navigation tasks that require memory and active perception <cit.>. 

The Teacher-Student Curriculum Learning (TSCL) framework incorporates a teacher that prioritizes tasks wherein the student's performance is either increasing (learning) or decreasing (forgetting) <cit.>. TSCL enabled a policy gradient learning method to solve mazes that were otherwise not possible with a uniform sampling of subtasks. 



 §.§ Real-Time Strategy Games


The previous sections described methods that learn to play games end-to-end, i.e. a neural network is trained to map states directly to actions. Real-Time Strategy (RTS) games, however, offer much more complex environments, in which players have to control multiple agents simultaneously in real-time on a partially observable map. Additionally, RTS games have no in-game scoring and thus the reward is determined by who wins the game. For these reasons, learning to play RTS games end-to-end may be infeasible for the foreseeable future and instead, sub-problems have been studied so far. 

For the simplistic RTS platform μRTS a CNN was trained as a state evaluator using supervised learning on a generated data set and used in combination with Monte Carlo Tree Search <cit.>. This approach performed significantly better than previous evaluation methods. 

StarCraft has been a popular game platform for AI research, but so far only with a few deep learning approaches. Deep learning methods for StarCraft have focused on micromanagement (unit control) or build-order planning and has ignored other aspects of the game. The problem of delayed rewards in StarCraft can be circumvented in combat scenarios; here rewards can be shaped as the difference between damage inflicted and damage incurred <cit.>. States and actions are often described locally relative to units, which is extracted from the game engine. If agents are trained individually it is difficult to know which agents contributed to the global reward <cit.>, a problem known as the multi-agent credit assignment problem. One approach is to train a generic network, which controls each unit separately and search in policy space using Zero-Order optimization based on the reward accrued in each episode <cit.>. This strategy was able to learn successful policies for armies of up to 15 units. 

Independent Q-learning (IQL) simplifies the multi-agent RL problem by controlling units individually while treating other agents as if they were part of the environment <cit.>. This enables Q-learning to scale well to a large number of agents. However, when combining IQL with recent techniques such as experience replay, agents tend to optimize their policies based on experiences with obsolete policies. This problem is overcome by applying fingerprints to experiences and by applying an importance-weighted loss function that naturally decays obsolete data, which has shown improvements for some small combat scenarios <cit.>.


The Multiagent Bidirectionally-Coordinated Network (BiCNet) implements a vectorized actor-critic framework based on a bi-directional RNN, with one dimension for every agent, and outputs a sequence of actions <cit.>. This network architecture is unique to the other approaches as it can handle an arbitrary number of units of different types.

Counterfactual multi-agent (COMA) policy gradients is an actor-critic method with a centralized critic and decentralized actors that address the multi-agent credit assignment problem with a counterfactual baseline computed by the critic network <cit.>. COMA achieves state-of-the-art results, for decentralized methods, in small combat scenarios with up to ten units on each side.

Deep learning has also been applied to build-order planning in StarCraft using macro-based supervised learning approach to imitate human strategies <cit.>. The trained network was integrated as a module used in an existing bot capable of playing the full game with an other-wise hand-crafted behavior. Another macro-based approach, here using RL instead of SL, called Convolutional Neural Network Fitted Q-Learning (CNNFQ), was trained with Double DQN for build-order planning in StarCraft II and was able to win against medium-level scripted bots on small maps <cit.>. A macro action-based reinforcement learning method that uses Proximal Policy Optimization (PPO) for build order planning and high-level attack planning was able to outperform the built-in bot in StarCraft II at level 10 <cit.>. This is particularly impressive as the level 10 bot cheats by having full vision of the map and faster resource harvesting. The results were obtained using 1920 parallel actors on 3840 CPUs across 80 machines and only for one matchup on one map. This system won a few games against Platinum-level human players but lost all games against Diamond-level players. The authors report that the learned policy "lacks strategy diversity in order to consistently beat human players" <cit.>.





 §.§ Team Sports Games


Deep Deterministic Policy Gradients (DDPG) was applied to RoboCup 2D Half-Field-Offense (HFO) <cit.>. The actor network used two output streams, one for the selection of discrete action types (dash, turn, tackle, and kick) and one for each action type's 1-2 continuously-valued parameters (power and direction). The Inverting Gradients bounding approach downscales the gradients as the output approaches its boundaries and inverts the gradients if the parameter exceeds them. This approach outperformed both SARSA and the best agent in the 2012 RoboCup. DDPG was also applied to HFO by mixing on-policy updates with 1-step Q-Learning updates <cit.> and outperformed a hand-coded agent with expert knowledge with one player on each team.





 §.§ Physics Games

As video games are usually a reflection or simplification of the real world, it can be fruitful to learn an intuition about the physical laws in an environment. A predictive neural network using an object-centered approach (also called fixations) learned to run simulations of a billiards game after being trained on random interactions <cit.>. This predictive model could then be used for planning actions in the game. 

A similar predictive approach was tested in a 3D game-like environment, using the Unreal Engine, where ResNet-34 <cit.> (a deep residual network used for image classification) was extended and trained to predict the visual outcome of blocks that were stacked such that they would usually fall <cit.>. Residual networks implement shortcut connections that skip layers, which can improve learning in very deep networks.



 §.§ Text Adventure Games



Text adventure games, in which both states and actions are presented as text only, are a special video game genre. A network architecture called LSTM-DQN <cit.> was designed specifically to play these games and is implemented using LSTM networks that convert text from the world state into a vector representation, which estimates Q-values for all possible state-action pairs. LSTM-DQN was able to complete between 96% and 100% of the quests on average in two different text adventure games.

To be able to improve on these results, researchers have moved toward learning language models and word embeddings to augment the neural network. An approach that combines reinforcement learning with explicit language understanding is Deep Reinforcement Relevance Net (DRRN) <cit.>. This approach has two networks that learn word embeddings. One embeds the state description, the other embeds the action description. Relevance between the two embedding vectors is calculated with an interaction function such as the inner product of the vectors or a bilinear operation. The Relevance is then used as the Q-Value and the whole process is trained end-to-end with Deep Q-Learning. This approach allows the network to generalize to phrases not seen during training which is an improvement for very large text games. The approach was tested on the text games Saving John and Machine of Death, both choice-based games.

Taking language modeling further, Fulda et. al. explicitly modeled language affordances to assist in action selection <cit.>. A word embedding is first learned from a Wikipedia Corpus via unsupervised learning <cit.> and this embedding is then used to calculate analogies such as song is to sing as bike is to x, where x can then be calculated in the embedding space <cit.>. The authors build a dictionary of verbs, noun pairs, and another one of object manipulation pairs. Using the learned affordances, the model can suggest a small set of actions for a state description. Policies were learned with Q-Learning and tested on 50 Z-Machine games.

The Golovin Agent focuses exclusively on language models <cit.> that are pre-trained from a corpus of books in the fantasy genre. Using word embeddings, the agent can replace synonyms with known words. Golovin is built of five command generators: General, Movement, Battle, Gather, and Inventory. These are generated by analyzing the state description, using the language models to calculate and sample from a number of features for each command. Golovin uses no reinforcement learning and scores comparable to the affordance method.

Most recently, Zahavy et. al. proposed another DQN method <cit.>. This method uses a type of attention mechanism called Action Elimination Network (AEN). In parser-based games, the actions space is very large. The AEN learns, while playing, to predict which actions that will have no effect for a given state description. The AEN is then used to eliminate most of the available actions for a given state and after which the remaining actions are evaluated with the Q-network. The whole process is trained end-to-end and achieves similar performance to DQN with a manually constrained actions space. Despite the progress made for text adventure games, current techniques are still far from matching human performance.

Outside of text adventure games, natural language processing has been used for other text-based games as well. To facilitate communication, a deep distributed recurrent Q-network (DDRQN) architecture was used to train several agents to learn a communication protocol to solve the multi-agent Hats and Switch riddles <cit.>. One of the novel modifications in DDRQN is that agents use shared network weights that are conditioned on their unique ID, which enables faster learning while retaining diversity between agents.














§ HISTORICAL OVERVIEW OF DEEP LEARNING IN GAMES


The previous section discussed deep learning methods in games according to the game type. This section instead looks at the development of these methods in terms of how they influenced each other, giving a historical overview of the deep learning methods that are reviewed in the previous section. Many of these methods are inspired from or directly build upon previous methods, while some are applied to different game genres and others are tailored to specific types of games.

Figure <ref> shows an influence diagram with the reviewed methods and their relations to earlier methods (the current section can be read as a long caption to that figure). Each method in the diagram is colored to show the game benchmark. DQN <cit.> was very influential as an algorithm that uses gradient-based deep learning for pixel-based video game playing and was originally applied to the Atari benchmark. Note that earlier approaches exist but with less success such as <cit.>, and successful gradient-free methods <cit.>. Double DQN <cit.> and Dueling DQN <cit.> are early extensions that use multiple networks to improve estimations. DRQN <cit.> uses a recurrent neural network as the Q network. Prioritized DQN <cit.> is another early extension and it adds improved experience replay sampling. Bootstrapped DQN <cit.> builds off of Double DQN with a different improved sampling strategy. Further DQN enhancements used for Atari include: the C51 algorithm <cit.>, which is based on DQN but changes the Q function; Noisy-Nets which make the networks stochastic to aid with exploration <cit.>; DQfD which also learns from examples <cit.>; and Rainbow, which combines many of these state-of-the-art techniques together <cit.>.

Gorila was the first asynchronous method based on DQN <cit.> and was followed by A3C <cit.> which uses multiple asynchronous agents for an actor-critic approach. This was further extended at the end of 2016 with UNREAL <cit.>, which incorporates work done with auxiliary learning to handle sparse feedback environments. Since then there has been a lot of additional extensions on A3C <cit.>, <cit.>, <cit.>, <cit.>. IMPALA has taken it further with focusing on a single trained agent that can play all of the Atari games <cit.>. In 2018, the move toward large scale distributed learning has continued and advanced with Ape-X <cit.>.


Evolutionary techniques are also seeing a Renaissance for video games. First Salimans et. al. showed that Evolution Strategies could compete with deep RL <cit.>. Then two more papers came out of Uber AI: one showing that derivative-free evolutionary algorithms can compete with deep RL <cit.>, and an extension to ES <cit.>. These benefit from easy parallelization and possibly have some advantage in exploration.


Another approach used on Atari around the time that DQN was introduced is Trust Region Policy Optimization <cit.>. This updates a surrogate objective that is updated from the environment. Later in 2017, Proximal Policy Optimization was introduced as a more robust, simpler surrogate optimization scheme that also draws from innovations in A3C <cit.>. Some extensions are specifically for Montezuma's revenge, which is a game within the ALE benchmark, but it is particularly difficult due to sparse rewards and hidden information. The algorithms that do best on Montezuma do so by extending DQN with intrinsic motivation <cit.> and hierarchical learning <cit.>. Ms. Pack-Man was also singled out from Atari, where the reward function was learned in separate parts to make the agent more robust to new environments <cit.>. 

Doom is another benchmark that is new as of 2016. Most of the work for this game has been extending methods designed for Atari to handle richer data. A3C + Curriculum Learning <cit.> proposes using curriculum learning with A3C. DRQN + Auxiliary Learning <cit.> extends DRQN by adding additional rewards during training. DQN + SLAM <cit.> combines techniques for mapping unknown environments with DQN. 

DFP <cit.> is the only approach that is not extending an Atari technique. Like UCT To Classification <cit.> for Atari, Object-centric Prediction <cit.> for Billiard, and Direct Perception <cit.> for Racing, DFP uses supervised learning to learn about the game. All of these, except UCT To Classification, learn to directly predict some future state of the game and make a prediction from this information. None of these works, all from different years, refer to each other. Besides Direct Perception, the only unique work for racing is Deep DPG <cit.>, which extends DQN for continuous controls. This technique has been extended for RoboCup Soccer <cit.> <cit.>.

Work on StarCraft micro-management (unit control) is based on Q-learning started in late 2016. IQL <cit.> extends DQN Prioritized DQN by treating all other agents as part of the environment. COMA <cit.> extends IQL by calculating counterfactual rewards, the marginal contribution each agent added. biCNet <cit.> and Zero Order Optimization <cit.>, are reinforcement learning based but are not derived from DQN. Another popular approach is hierarchical learning. In 2017 it was tried with replay data <cit.> and in 2018 state of the art results were achieved by using it with two different RL methods <cit.>.

Some work published in 2016 extends DQN to play Minecraft <cit.>. At around the same time, techniques were developed to make DQN context-aware and modular to handle the large state space <cit.>. Recently, curriculum learning has been applied to Minecraft as well <cit.>.

DQN was applied to text adventure games in 2015 <cit.>. Soon after, it was modified to have a language-specific architecture and use the state-action pair relevance as the Q value <cit.>. Most of the work on these games has been focused on explicit language modeling. Golovin Agent and Affordance Based Action Selection both use neural networks to learn language models which provide the actions for the agents to play <cit.>. Recently, in 2018, DQN was used again paired with an Action Elimination Network <cit.>.

Combining extensions from previous algorithms have proven to be a promising direction for deep learning applied to video games, with Atari being the most popular benchmark for RL. Another clear trend, which is apparent in Table <ref>, is the focus on parallelization: distributing the work among multiple CPUs and GPUs. Parallelization is most common with actor-critic methods, such as A2C and A3C, and evolutionary approaches, such as Deep GA <cit.> and Evolution Strategies <cit.>. Hierarchical reinforcement learning, intrinsic motivation, and transfer learning are promising new directions to explore to master currently unsolved problems in video game playing.





§ OPEN CHALLENGES


While deep learning has shown remarkable results in video game playing, a multitude of important open challenges remain, which we review here. Indeed, looking back at the current state of research from a decade or two in the future, it is likely that we will see the current research as early steps in a broad and important research field. This section is divided into four broad categories (agent model properties, game industry, learning models of games, and computational resources) with different game-playing challenges that remain open for deep learning techniques. We mention a few potential approaches for some of the challenges while the best way forward for others is currently not clear.




 §.§ Agent Model Properties



  §.§.§ General Video Game Playing


Being able to solve a single problem does not make you intelligent; nobody would say that Deep Blue or AlphaGo <cit.> possess general intelligence, as they cannot even play Checkers (without re-training), much less make coffee or tie their shoelaces. To learn generally intelligent behavior, you need to train on not just a single task, but many different tasks <cit.>. Video games have been suggested as ideal environments for learning general intelligence, partly because there are so many video games that share common interface and reward conventions <cit.>. Yet, the vast majority of work on deep learning in video games focuses on learning to play a single game or even performing a single task in a single game.

While deep RL-based approaches can learn to play a variety of different Atari games, it is still a significant challenge  to develop algorithms that can learn to play any kind of game (e.g. Atari games, DOOM, and StarCraft). Current approaches still require significant effort to design the network architecture and reward function to a specific type of game. 



Progress on the problem of playing multiple games includes progressive neural networks <cit.>, which allow new games to be learned (without forgetting previously learned ones) and solved quicker by exploiting previously learned features through lateral connections. However, they require a separate network for each task. Elastic weight consolidation <cit.> can learn multiple Atari games sequentially and avoids catastrophic forgetting by protecting weights from being modified that are important for previously learned games. In PathNet an evolutionary algorithm is used to select which parts of a neural network are used for learning new tasks, demonstrating some transfer learning performance on ALE games <cit.>.

In the future it will be important to extend these methods to learn to play multiple games, even if those games are very different — most current approaches focus on different (known) games in the ALE framework. One suitable avenue for this kind of research is the new Learning Track of the GVGAI competition <cit.>. GVGAI has a potentially unlimited set of games, unlike ALE. Recent work in GVGAI showed that model-free deep RL overfitted not just to the individual game, but even to the individual level; this was countered by continuously generating new levels during training <cit.>. 

It is possible that significant advances on the multi-game problem will come from outside deep learning. In particular, the recent Tangled Graph representation, a form of genetic programming, has shown promise in this task <cit.>. The recent IMPALA algorithm tries to tackle multi-game learning through massive scaling, with somewhat promising results <cit.>.





  §.§.§ Overcoming sparse, delayed, or deceptive Rewards

Games such as Montezuma's Revenge that are characterized by sparse rewards still pose a challenge for most Deep RL approaches. While recent advances that combine DQN with intrinsic motivation <cit.> or expert demonstrations <cit.> can help, games with sparse rewards are still a challenge for current deep RL methods. There is a long history of research in intrinsically motivated reinforcement learning <cit.> as well as hierarchical reinforcement learning which might be useful here <cit.>. The Project Malmo environment, based on Minecraft, provides an excellent venue for creating tasks with very sparse rewards where agents need to set their own goals. Derivative-free and gradient-free methods, such as  evolution strategies and genetic algorithms, explore the parameter space by sampling locally and are promising for these games, especially when combined with novelty search as in <cit.>.



  §.§.§ Learning with multiple agents

Current deep RL approaches are mostly concerned with training a single agent. A few exceptions exist where multiple agents have to cooperate <cit.>, but it remains an open challenge how these can scale to more agents in various situations. In many current video games such as StarCraft or GTA V, many agents interact with each other and the player. To scale multi-agent learning in video games to the same level of performance as current single agent approaches will likely require new methods that can effectively train multiple agents at the same time.



  §.§.§ Lifetime adaptation

While NPCs can be trained to play a variety of games well (see Section <ref>), current machine learning techniques still struggle when it comes to agents that should be able to adapt during their lifetime, i.e. while the game is being played. For example, a human player can quickly change its behavior when realizing that the player is always ambushed at the same position in an FPS map. However, most current DL techniques would require expensive re-training to adapt to these situations and other unforeseen situations that they have not encountered during training. The amount of data provided by the real-time behavior of a single human is nowhere near that required by common deep learning methods. This challenge is related to the wider problem of few-shot learning, transfer learning and general video game playing. Solving it will be important to create more believable and human-like NPCs.



  §.§.§ Human-like game playing

Lifetime learning is just one of the differences that current NPCs lack in comparison to human players. Most approaches are concerned with creating agents that play a particular game as well as possible, often only taking into account the score reached. However, if humans are expected to play against or cooperate with AI-based bots in video games, other factors come into play. Instead of creating a bot that plays perfectly, in this context it becomes more important that the bot is believable and is fun to play against, with similar idiosyncrasies we expect from a human player. 

Human-like game playing is an active area of research with two different competitions focused on human-like behavior namely the 2k BotPrize <cit.> and the Turing Test track of the Mario AI Championship <cit.>. Most entries in these competitions are based on various non-neural network techniques while some used evolutionary training of deep neural networks to generate human-like behavior <cit.>.







  §.§.§ Adjustable performance levels


Almost all current research on DL for game playing aims at creating agents that can play the game as well as possible, maybe even “beating” it. However, for purposes of both game testing, creating tutorials, and demonstrating games—in all those places where it would be important to have human-like game `play—it could be important to be able to create agents with a particular skill level. If your agent plays better than any human player, then it is not a good model of what a human would do in the game. At its most basic, this could entail training an agent that plays the game very well, and then find a way of decreasing the performance of that agent. However, it would be more useful to be able to adjust the performance level in a more fine-grained way, so as to for example separately control the reaction speed or long-term planning ability of an agent. Even more useful would be to be able to ban certain capacities of playstyles of a trained agent, so a to test whether for example a given level could be solved without certain actions or tactics.

One path to realizing this is the concept of procedural personas, where the preferences of an agent are encoded as a set of utility weights <cit.>. However, this concept has not been implemented using deep learning, and it is still unclear how to realize the planning depth control in this context.



  §.§.§ Dealing with extremely large decision spaces

Whereas the average branching factor hovers around 30 for Chess and 300 for Go, a game like StarCraft has a branching factor that is orders of magnitudes larger. While recent advances in evolutionary planning have allowed real-time and long-term planning in games with larger branching factors to <cit.>, how we can scale Deep RL to such levels of complexity is an important open challenge. Learning heuristics with deep learning in these games to enhance search algorithms is also a promising direction.





 §.§ Game Industry



  §.§.§ Adoption in the game industry

Many of the recent advances in DL have been accelerated because of the increased interest by a variety of different companies such as Facebook, Google/Alphabet, Microsoft and Amazon, which heavily invest in its development. However, the game industry has not embraced these advances to the same extent. This sometimes surprises commentators outside of the game industry, as games are seen as making heavy use of AI techniques. However, the type of AI that is  most commonly used in the games industry focuses more on hand-authoring of expressive non-player character (NPC) behaviors rather than machine learning. An often-cited reason for the lack of adoption of neural networks (and similar methods) within this industry is that such methods are inherently difficult to control, which could result in unwanted NPC behaviors (e.g. an NPC could decide to kill a key actor that is relevant to the story). Additionally, training deep network models require a certain level of expertise and the pool of experts in this area is still limited. It is important to address these challenges to encourage a wide adoption in the game industry. 

Additionally, while most DL approaches focus exclusively on playing games as well as possible, this goal might not be the most important for the game industry <cit.>. Here  the level of fun or engagement the player experiences while playing is a crucial component. One use of DL for game playing in the game production process is for game testing, where artificial agents test that levels are solvable or that the difficulty is appropriate. DL might see its most prominent use in the games industry not for playing games, but for generating game content <cit.> based on training on existing content  <cit.>, or for modeling player experience <cit.>. 





Within the game industry, several of the large development and technology companies, including Electronic Arts, Ubisoft and Unity have recently started in-house research arms focusing partly on deep learning. It remains to be seen whether these techniques will also be embraced by the development arms of these companies or their customers. 



  §.§.§ Interactive tools for game development

Related to the previous challenge, there is currently a lack of tools for designers to easily train NPC behaviors. While many open-source tools to training deep networks exist now, most of them require a significant level of expertise. A tool that allows designers to easily specify desired NPC behaviors (and undesired ones) while assuring a certain level of control over the final trained outcomes would greatly accelerate the uptake of these new methods in the game industry. 

Learning from human preferences is one promising direction in this area. This approach has been extensively studied in the context of neuroevolution <cit.>, and also in the context of video games,  allowing non-expert users to breed behaviors for Super Mario <cit.>. Recently a similar preference-based approach was applied to deep RL method <cit.>, allowing agents to learn Atari games based on a combination of human preference learning and deep RL. Recently, the game company King published results using imitation learning to learn policies for play-testing of Candy Crush levels, showing a promising direction for new design-tools <cit.>.



  §.§.§ Creating new types of video games

DL could potentially offer a way to create completely new games. Most of today's game designs stem from a time when no advanced AI methods were available or the hardware too limited to utilize them, meaning that games have been designed to not need AI. Designing new games around AI can help to break out of these limitations. While evolutionary algorithms and neuroevolution in particular <cit.> have allowed the creation of completely new types of games, DL based on gradient descent has not been explored in this context. Neuroevolution is a core mechanic in games such as NERO <cit.>, Galactic Arms Race <cit.>, Petalz <cit.> and EvoCommander <cit.>. One challenge with gradient-based optimization is that the structures are often limited to having mathematical smoothness (i.e. differentiability), making it challenging to create interesting and unexpected outputs.



 §.§ Learning models of games


Much work on deep learning for game-playing takes a model-free end-to-end learning approach, where a neural network is trained to produce actions given state observations as input. However, it is well known that a good and fast forward model makes game-playing much easier, as it makes it possible to use planning methods based on tree search or evolution <cit.>. Therefore, an important open challenge in this field is to develop methods that can learn a forward model of the game, making it possible to reason about its dynamics.

The hope is that approaches that learn the rules of the game can generalize better to different game variations and show more robust learning. Promising work in this area  includes the approach by Guzdial et al. <cit.> that learns a simple game engine of Super Mario Bros. from gameplay data. Kansky et al. <cit.> introduce the idea of Schema Networks that follow an object-oriented approach and are trained to predict future object attributes and rewards based on the current attributes and actions. A trained schema network thus provides a probabilistic
model that can be used for planning and is able to perform zero-shot transfer to variations of Breakout similar to those used in training. 



 §.§ Computational Resources



With more advanced computational models and a larger number of agents in  open-worlds, computational speed becomes a concern. Methods that aim to make the networks computationally more efficient by either compressing networks <cit.> or pruning networks after training <cit.> could be useful. Of course, improvements in processing power in general or for neural networks specifically will also be important. Currently, it is not feasible to train networks in real-time to adapt to changes in the game or to fit players' playing styles, something which could be useful in the design process.




















§ CONCLUSION


This paper reviewed deep learning methods applied to game playing in video games of various genres including; arcade, racing, first-person shooters, open-world, real-time strategy, team sports, physics, and text adventure games. Most of the reviewed work is within end-to-end model-free deep reinforcement learning, where a convolutional neural network learns to play directly from raw pixels by interacting with the game. Recent work demonstrates that derivative-free evolution strategies and genetic algorithms are competitive alternatives. Some of the reviewed work apply supervised learning to imitate behaviors from game logs, while others are based on methods that learn a model of the environment. For simple games, such as most arcade games, the reviewed methods can achieve above human-level performance, while there are many open challenges in more complex games.




§ ACKNOWLEDGEMENTS

We thank the numerous colleagues who took the time to comment on drafts of this article, including Chen Tessler,
Diego Pérez-Liébana,
Ethan Caballero,
Hal Daumé III,
Jonas Busk,
Kai Arulkumaran,
Malcolm Heywood,
Marc G. Bellemare,
Marc-Philippe Huget,
Mike Preuss,
Nando de Freitas,
Nicolas A. Barriga,
Olivier Delalleau,
Peter Stone,
Santiago Ontañón,
Tambet Matiisen,
Yong Fu, and
Yuqing Hou.





§ USES




 §.§ Playing games
 
(games as AI testbeds), 



 §.§ Content generation

Review article: Procedural Content Generation via Machine Learning (PCGML)




 §.§ Player modeling

https://wiseodd.github.io/techblog/2017/01/29/infogan/


§ TRAINING METHODS





 §.§ Supervised

Scott Lee, Aaron Isaksen, Christoffer Holmgård and Julian Togelius (2016): Predicting Resource Locations in Game Maps Using Deep Convolutional Neural Networks. EXAG Workshop at AIIDE. 

Deep Learning for Classifying Battlefield 4 Players

The Game Imitation: Deep Supervised Convolutional Networks for Quick Video Game AI

Deep Apprenticeship Learning for Playing Video Games



 §.§ Deep Reinforcement Learning




 §.§ Unsupervised

Content generation?



 §.§ Combinations with Search


- Mastering the game of Go with deep neural networks and tree search

DQN

Models with and without memory 



§ GAME TYPES


Overview table



 §.§ Board games
 



 §.§ Atari games




 §.§ Racing Games




 §.§ 3D Games

Labyrinth, VizDoom, Quake, ...



 §.§ Strategy Games

Starcraft (also a very open challenge)



 §.§ Game Research Platforms

GVGAI, DeepMind Labs, OpenAI Universe, ...



§ CHALLENGES



 §.§ Continual Learning in Games

- Learning to play more than one game (progressive networks, elastic weight consolidation)


 §.§ Making Games More fun?



abbrv




l25mm 
    
    < g r a p h i c s >

  Niels Justesen is a PhD fellow at the IT University of Copenhagen where he is part of the Center for Computer Games Research and the Robotics, Evolution and Art Lab (REAL). His research is focussed on game-playing algorithms for strategy games, including tree search, evolutionary algorithms and deep learning. 
Justesen holds a BSc in software development and MSc in games technology, both from the IT University of Copenhagen. He has previously worked at IT Minds.





l25mm 
  
  
    < g r a p h i c s >

  Philip Bontrager is a PhD Candidate at New York University school of engineering. There he is a member of the Game Innovation Lab. Philip’s research consists of using deep learning and evolution strategies to further procedural generation techniques. Philip has a B.A. in Informatics and Mathematics from Goshen College and a MSc from New York University in Computer Science.




l25mm 



    < g r a p h i c s >

  Julian Togelius is an Associate Professor in the Department of Computer Science and Engineering, New York University, USA. He works on all aspects of computational intelligence and games and on selected topics in evolutionary computation and evolutionary reinforcement learning. His current main research directions involve search-based procedural content generation in games, general video game playing, player modeling, and fair and relevant benchmarking of AI through game-based competitions. He is a past chair of the IEEE CIS Technical Committee on Games, and an associate editor of IEEE Transactions on Computational Intelligence and Games. Togelius holds a BA from Lund University, an MSc from the University of Sussex, and a PhD from the University of Essex. He has previously worked at IDSIA in Lugano and
at the IT University of Copenhagen.

  


l25mm 



    < g r a p h i c s >

  Sebastian Risi is an Associate Professor at the IT University of Copenhagen where he is part of the Center for Computer Games Research and the Robotics, Evolution and Art Lab (REAL). His interests include neuroevolution, evolutionary robotics and human computation. Risi completed his PhD in computer science from the University of Central Florida. He has won several best paper awards at GECCO, EvoMusArt, IJCNN, and the Continual Learning Workshop at NIPS for his work on adaptive systems, the HyperNEAT algorithm for evolving complex artificial neural networks, and music generation. He is a consultant for the recently formed Uber AI labs and was a co-founder of FinchBeak, a company that focused on casual and educational social games enabled by AI technology.


