PaperlayerView exact revision on arXiv

Source-linked AI summary

Neuroevolution in Games: State of the Art and Open Challenges

Sebastian Risi, Julian Togelius

arXiv:1410.7326v3cs.NE

TL;DR

The paper addresses how neuroevolution is being applied across games and how the field can be organized and understood. It surveys applications by role, network, evolution, fitness, and input, finding broad applicability alongside open challenges and practical limitations.

  • Problem

    Researchers and practitioners need a guide to the growing range of neuroevolution applications in games and to games’ use as neuroevolution testbeds.

  • Method

    The paper surveys neuroevolution in games across five axes: role, neural-network type, evolution method, fitness evaluation, and input representation.

  • Results

    The survey finds that neuroevolution supports diverse game-related tasks, learning settings, strategies, controllers, models, and content, while presenting open research challenges.

  • Takeaways & Limitations

    Neuroevolution offers a general approach for games and enables applications and game designs that rely on exploration, diversity, or evolving content.

  • Takeaways & Limitations

    The paper is broad and representative rather than exhaustive, and surveyed work is often limited to single-game testbeds.

Abstract

from arXiv · show

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

I. INTRODUCTION

This paper surveys neuroevolution in games as an established but developing area, defining its scope and organizing applications across roles, networks, evolution, fitness, and input representations.

  • I. INTRODUCTION: Neuroevolution generates artificial neural networks, including their weights and/or topology, with evolutionary algorithms.The paper treats evolutionary computation and related bio-inspired stochastic search methods applied to neural networks as neuroevolution.
  • I. INTRODUCTION: The survey aims to provide a state-of-the-art guide for researchers applying neuroevolution to games and using games as testbeds.Its motivation includes the continued popularity of neuroevolution, numerous game applications, and games’ advantages over testbeds such as mobile robotics.
  • I. INTRODUCTION: The review analyzes neuroevolution in games by role, neural-network type, evolution method, fitness evaluation, and input representation.These axes structure the paper’s overview of the field.
  • I. INTRODUCTION: The paper covers broad and representative applications to commonly played digital and non-digital games, while excluding purely abstract games, robotics tasks, and non-game reinforcement-learning benchmarks.The authors acknowledge that the boundary between games and excluded problem types contains gray areas.

A. Basic Algorithm

The basic neuroevolution algorithm evolves neural-network encodings through fitness-based selection, mutation, and crossover, while its broad applicability supports diverse game and learning tasks.

  • A. Basic Algorithm: Neuroevolution evolves a population of ANN-encoding genotypes by evaluating networks, selecting fitter individuals, and generating offspring through mutation and crossover.Each genotype is decoded into a network, tested on a task, assigned a fitness, and replaced through evolutionary reproduction.
  • A. Basic Algorithm: The method is applicable across game strategies, player models, and game-content generation, although alternative methods can also address these tasks.The paper presents neuroevolution as a general method rather than the only available algorithmic choice.
  • A. Basic Algorithm: Neuroevolution can serve supervised, unsupervised, and reinforcement-learning tasks when candidate networks receive a numeric quality evaluation.With labeled target values, it can function similarly to backpropagation; in reinforcement learning it resembles other numeric-evaluation approaches.
  • A. Basic Algorithm: Selected game examples include high-performing racing controllers, applications in commercial games, and player-facing games built around evolving weapons or robot teams.The examples span TORCS, Creatures, GAR, and NERO.
  • A. Basic Algorithm: Neuroevolution can perform well on large action and state spaces, particularly when used for direct action selection.The comparison is made especially against temporal-difference reinforcement-learning algorithms.

4) Diversity:

Neuroevolution can generate diverse strategies, controllers, models, and content, and its exploratory and open-ended properties support game designs centered on evolving content, though learned behavior is difficult to predict and debug.

  • 4) Diversity:: Evolutionary diversity-preservation and multiobjective methods can produce meaningfully different strategies, controllers, models, and content.The paper identifies niching and related methods as mechanisms for maintaining diversity among results.
  • 4) Diversity:: Neuroevolution’s larger search space and topology evolution can in principle support open-ended learning and increasingly complex behavior.The paper contrasts this broader search with temporal-difference-based algorithms and frames the claim as a possibility.
  • 4) Diversity:: Games such as GAR, NERO, and Petalz use neuroevolution to let players evolve weapons, robot teams, or varied virtual flowers.The paper presents these designs as difficult to realize with traditional learning methods and notes their reliance on evolving content.
  • 4) Diversity:: Evolved networks often behave as black boxes, making learned behavior hard to debug and difficult to predict when neuroevolution runs online.This uncertainty can conflict with commercial game-design and quality-assurance practices.
  • 4) Diversity:: Across surveyed applications, neuroevolution is used mainly to learn gameplay or control NPCs, with additional roles in procedural content generation and player-experience or preference prediction.For gameplay and NPC control, networks either evaluate states or actions for another selector or directly choose actions.

A. State/action evaluation

Neuroevolution commonly supports game control by evaluating hypothetical future states or actions, which search procedures use to select high-valued moves. This approach spans board games and other games, but its effectiveness depends on searchability and game structure.

  • A. State/action evaluation: State evaluators assign values to hypothetical future states, enabling tree-search agents to choose actions leading toward higher-valued outcomes.The network is typically evolved using win rate against opponents, though other fitness functions, such as human playing style, are also used.
  • A. State/action evaluation: Chess and Checkers applications reached above-master or human-master play levels through self-play and evolved board evaluators.Fogel et al. evolved a Chess player above master level, while Blondie24 reached human master level in Checkers.
  • A. State/action evaluation: Othello research explored cooperative coevolution, convolutional networks, evolution strategies, and n-tuple networks for learning board evaluators.Later work found n-tuple networks could learn very good state evaluators.
  • A. State/action evaluation: Standard evolved evaluators can work on small Go boards but fail to scale, motivating architectures such as HyperNEAT and recurrent convolutional networks.The cited discussion links the difficulty to Go’s high branching factor and the challenge of estimating board value.
  • A. State/action evaluation: State-value search also applies beyond board games, including shallow-search control of single-player arcade games such as Ms. Pac-Man.The method evaluates resulting states and selects the action leading to the highest-valued state; limited action spaces can permit deeper search.
  • A. State/action evaluation: Action evaluators instead take the current state and a candidate future action as input, returning a value used to choose among enumerated actions.Comparisons in a simple car-racing game included evolving state evaluators and action evaluators.

B. Direct action selection

Direct action selection uses neural networks to map game observations directly to control outputs when enumerating future actions is impractical. Applications include racing, first-person shooters, platform games, board games, general game playing, and macro-action tasks.

  • B. Direct action selection: Direct action selection is useful when a game has too many possible actions for effective search, such as Civilization’s astronomical action space.The network receives a current-state description or observation and outputs an action through controller-like dimensions or action-specific outputs.
  • B. Direct action selection: Evolved racing controllers matched or exceeded human driving, generalized across tracks, and generated varied styles, although state evaluators performed better in one comparison.Competitive coevolution produced differently styled drivers, and neuroevolution also performed strongly in later simulated-racing competitions.
  • B. Direct action selection: In FPS games, evolved networks directly controlled movement, turning, shooting, path following, exploration, and layered behavioral components.Some controllers used separate networks whose outputs could override one another according to a fixed hierarchy.
  • B. Direct action selection: Platform-game agents face small discrete action spaces, making direct control through evolved neural networks a natural formulation.Related work also evolved networks to mimic human-player behavior rather than optimize only game performance.
  • B. Direct action selection: Neuroevolution has also been applied to direct action selection in board games and to networks intended to play many games described through a common language.These approaches include assigning outputs to board positions and evolving networks across collections of discrete 2D games.
  • B. Direct action selection: For macro-action tasks, NEAT selected among strategies lasting longer than one time step, while hybridizing with other reinforcement learning methods produced better results.Keepaway Soccer used three static macro-actions selected whenever an agent gained possession.

D. Modelling opponent strategy

Neuroevolution in games extends beyond action control to opponent prediction, player-experience modeling, modular architectures, and adaptive network designs. These applications show both specialized network roles and unresolved scope boundaries for existing network types.

  • D. Modelling opponent strategy: Evolved networks predicted opponent strategy in Texas Hold’em Poker, increasing the win rate of agents that used the model.Opponent prediction can be one component of a larger player whose other components may or may not use neuroevolution.
  • D. Modelling opponent strategy: Neuroevolution predicted player level preferences with up to 91% accuracy and supported searches for personalized levels maximizing selected experience properties.The preference models were trained from players’ choices between pairs of levels.
  • D. Modelling opponent strategy: Recurrent networks maintain internal state and memory of past events, unlike static feedforward networks, which can support temporal control behavior.Their directed cycles allow information to propagate from later layers back to earlier layers.
  • D. Modelling opponent strategy: Modular networks can outperform monolithic networks when behavior decomposes into sub-functions such as path following, shooting, and exploration.In Pac-Man, modular NEAT performed better than its standard version, while a hierarchical multi-module controller also outperformed a monolithic network.
  • D. Modelling opponent strategy: Plastic networks can change connection weights during operation, but the paper reports that they had not yet been applied to games to the authors’ knowledge.The paper identifies plastic networks as a possible avenue for controllers that learn across multiple games or game versions.

V. EVOLVING NEURAL NETWORKS

Neuroevolution evolves neural-network weights, topologies, or indirect encodings with evolutionary algorithms. The survey contrasts direct fixed-topology methods with topology-evolving and geometry-based approaches, including successful game applications.

  • V. EVOLVING NEURAL NETWORKS: Topology-evolving methods such as NEAT jointly evolve network structure and connection weights, often outperforming weight-only approaches and supporting recurrent networks.NEAT has been applied to car racing, robot teams, Ms. Pac-Man, and Unreal Tournament.
  • V. EVOLVING NEURAL NETWORKS: Fixed-topology networks require users to choose the topology and number of hidden nodes before evolution, while direct encodings represent connections separately.Direct encodings use a one-to-one mapping between network parameters and genetic representations.
  • V. EVOLVING NEURAL NETWORKS: Indirect encodings reuse regularities compactly; HyperNEAT exploits geometric properties to describe connectivity in large-scale artificial neural networks.CPPNs can generate patterns and indirectly encode neural networks, while HyperNEAT targets structured connectivity.
  • V. EVOLVING NEURAL NETWORKS: HyperNEAT learned Atari 2600 games directly from raw screen data and exceeded human high scores in three games.The result supports learning without a game-specific input representation.
  • V. EVOLVING NEURAL NETWORKS: Developmental encodings can evolve growth processes, exemplified by a developing neuron that played checkers and beat a Minimax-based program.The neuron grew new synaptic connections during play through an evolved genetic program.

VI. FITNESS EVALUATION

Fitness evaluation in neuroevolution ranges from task performance to cooperative, competitive, multiobjective, and human-guided objectives. Incremental evolution, transfer, and coevolution address increasingly complex or difficult-to-evaluate game tasks.

  • VI. FITNESS EVALUATION: Incremental evolution produced general driving skills when tracks were added progressively, whereas evaluating all tracks simultaneously produced no such skills.Fitness was averaged across increasingly challenging tracks after the population reached sufficient performance.
  • VI. FITNESS EVALUATION: Transfer learning accelerated adaptation: controllers transferred from TORCS to VDrift adapted faster than controllers evolved from scratch.NEAT transfer also significantly sped learning from 3 vs. 2 to 4 vs. 3 robot soccer Keepaway.
  • VI. FITNESS EVALUATION: Cooperative coevolution rewards individuals for collaborative performance, while competitive coevolution makes fitness depend negatively on opponents’ success.Fitness can be assigned at neuronal or network levels depending on the cooperative setup.
  • VI. FITNESS EVALUATION: Coevolution can speed search, but outcomes depend on domain and task structure: complex Keepaway tasks failed without the correct decomposition, and Pac-Man controllers were easier to evolve than ghost teams.Using multiple populations improved car-racing results notably.
  • VI. FITNESS EVALUATION: Multiobjective evolutionary algorithms handle multiple or conflicting fitness functions by mapping tradeoffs among objectives.The resulting solutions are those where no objective can improve without worsening another.
  • VI. FITNESS EVALUATION: Interactive evolution lets players shape objectives or training, including curricula in NERO, advice and environment shaping in OpenNERO, and player-selected breeding in Petalz.In GAR, weapon fitness is based on firing frequency, allowing player preferences to guide evolution implicitly.

VII. INPUT REPRESENTATION

Input representation is a major design axis because it influences autonomous learning and can bias the strategies that evolution discovers. The survey distinguishes sensor-based, third-person, and raw sensory representations while emphasizing scaling and relevance.

  • VII. INPUT REPRESENTATION: The chosen input representation can significantly influence autonomous learning and ultimately bias which strategies and behaviors evolution discovers.Its suitability depends partly on the network’s role and the game type.
  • VII. INPUT REPRESENTATION: The survey covers straight-line and pie-slice sensors, pathfinding sensors, third-person data, and raw sensory data as ways to convey game state.These representations differ in how information about the environment reaches the neural network.
  • VII. INPUT REPRESENTATION: Inputs should be scaled to a common range, preferably [−1, 1], because irrelevant inputs can actively harm learning.Input preprocessing and selection are therefore part of the evolutionary design problem.

A. Straight Line Sensors and Pie Slice Sensors

Egocentric sensors often provide evolution with more actionable spatial information than third-person state descriptions. Car-racing studies favored rangefinders, while related games used radar, angle, relative-position, and pathfinding sensors.

  • A. Straight Line Sensors and Pie Slice Sensors: Car-racing controllers performed best with egocentric rangefinder distances rather than third-person track-frame positions.The authors suggest that mapping third-person spatial information to first-person actions is highly non-linear.
  • A. Straight Line Sensors and Pie Slice Sensors: NEAT can automatically select useful straight-line sensors in car racing, eliminating redundant inputs.This extends neuroevolution beyond policy evolution to input-feature selection.
  • A. Straight Line Sensors and Pie Slice Sensors: Pie-slice sensors divide the agent’s surroundings into predetermined angular sectors, with activations reflecting enemy distance; NERO combines them with rangefinders.These radar-like inputs provide directional information about nearby enemies.
  • A. Straight Line Sensors and Pie Slice Sensors: Angle sensors report directions to relevant objects, while relative-position sensors encode distances along specified axes.Examples include waypoint sensing in racing, enemy and pickup sensing in Quake III, and ghost coordination in Pac-Man.
  • A. Straight Line Sensors and Pie Slice Sensors: Pathfinding sensors provide shortest-path distances to nearby entities and can support state evaluation when one-ply search performs action selection.Pac-Man examples used distances to ghosts, pills, and power pills.
  • A. Straight Line Sensors and Pie Slice Sensors: Separating edible from threat ghosts gives Ms. Pac-Man controllers distinct inputs for evolving different responses to those situations.The representation therefore encodes a behavioral distinction directly into the input features.

D. Third-person Input

Third-person inputs represent game state from an external perspective, with board-game controllers commonly encoding pieces and spatial geometry. Across raw or minimally processed visual inputs, NE can learn useful behavior, but performance depends strongly on representation and remains challenging in complex environments.

  • D. Third-person Input: Additional game-state inputs can provide frame-independent information, including remaining pills, ghost status, or a racing car’s damage.These inputs supplement first-person sensors rather than replacing them.
  • D. Third-person Input: Board-game ANNs typically receive third-person state descriptions such as piece differences and the piece occupying each board square.Representations can exploit board geometry through overlapping local regions or convolutional recurrent scans.
  • D. Third-person Input: Raw-data evolution can work, but early Pac-Man controllers performed worse than controllers using shortest-path distances.The experiment evolved directly encoded weights from a square centered on Pac-Man.
  • D. Third-person Input: In Super Mario, MLP controllers were compared with HyperNEAT-like controllers across 9, 25, and 49 grid sensors.The sensors separately detected obstacles and enemies through binary inputs.
  • D. Third-person Input: Bird’s-eye-view HyperNEAT held the ball longer than previously reported TD-based and NE methods in Keepaway.The representation also supported transfer from 3 vs. 2 to 4 vs. 3 players without retraining.
  • D. Third-person Input: Raw sensory control becomes harder in 3D because agents need depth estimation and perception changes nonlocally when viewing direction changes.A Quake II controller using a narrow 14×2 grayscale band learned to attack but often shot continuously and spun in circles.

VIII. OPEN CHALLENGES

The survey identifies broad open challenges in determining when NE is preferable, extending it to difficult raw-data settings, and combining it with alternative learning methods. It emphasizes that NE has many successes but also substantial unexplored or unsatisfactory domains.

  • VIII. OPEN CHALLENGES: The literature contains many NE successes, but some domains still lack satisfactory performance and other tasks remain unattempted.Several NE approaches have also received only superficial exploration.
  • VIII. OPEN CHALLENGES: The central unresolved question is when NE should be used instead of alternative evolvable, supervised-learning, or reinforcement-learning algorithms.Comparative studies suggest TD methods often learn faster but are more brittle, whereas NE can eventually reach higher performance.
  • VIII. OPEN CHALLENGES: Parameterizable benchmarks are needed to relate problem characteristics to the relative performance of NE and competing algorithms.Existing comparisons show that outcomes vary substantially across tasks and tuning conditions.
  • VIII. OPEN CHALLENGES: Hybrid methods combining NE with alternatives such as TD-learning and genetic programming are a promising follow-up once their relative strengths are mapped.Prior work combining NEAT and Q-learning has reported promising results in shooters and racing games.
  • VIII. OPEN CHALLENGES: Learning from raw images remains difficult because direct shallow approaches struggle with high-dimensional inputs and the signal transformations needed for high-level information.Convolutional and deep architectures, together with indirect encodings such as HyperNEAT, are identified as promising directions.

D. General video game playing

General video game playing remains understudied despite NE’s genericity, with most studies using only one game. The survey highlights lifelong adaptation, reliable control, and coevolution as routes toward broader and more capable game-playing systems.

  • D. General video game playing: Most NE studies use a single game, leaving controllers that learn across many games seriously understudied.Atari work is among the few exceptions, while VGDL-based benchmarks can provide generated and theoretically unbounded game sets.
  • D. General video game playing: A controller evolved to play any game from a large set would represent progress toward more generic AI capabilities.The General Video Game Playing Competition offers a complementary benchmark to Atari-based evaluation.
  • E. Combining NE with life-long learning: Evolving one network that adapts during its lifetime to multiple games is proposed as a larger step beyond ordinary general game playing.Evolving synaptic plasticity parameters could let network weights change during an agent’s lifetime.
  • E. Combining NE with life-long learning: Adaptive networks could adjust to opponent difficulty and acquire skills incrementally, but undesired behaviors, reliability, and controllability remain important concerns.Such networks have so far mostly been applied to relatively simple toy problems.
  • D. General video game playing: Competitive coevolution may enable open-ended arms races, while cooperative coevolution may decompose complex problems through partial-solution evaluation.Modern games may provide richer environments for open-ended evolution than earlier predator-prey scenarios.
  • D. General video game playing: The survey focuses on academic rather than commercial uses because published commercial examples of NE in games are scarce.The paper identifies understanding this limited uptake as a key research problem.
Loading 1410.7326v3…