HyperNEAT-GGP: a hyperNEAT-based atari general game player

Matthew J. Hausknecht, Piyush Khandelwal, Risto Miikkulainen, Peter StoneGECCO 2012 · DOI

TL;DR

This paper introduces HyperNEAT-GGP, a novel approach to general game playing in Atari 2600 games. By leveraging the geometric regularities of the game screen and a neuroevolutionary technique called HyperNEAT, the agent learns to play games like Asterix and Freeway effectively, outperforming existing benchmarks with minimal domain-specific knowledge.

What Problem Does This Paper Address?

The grand challenge in artificial intelligence is to create agents that can learn and perform a wide variety of tasks with minimal pre-programmed knowledge. While impressive AI systems have been developed for specific games like chess and Jeopardy, they are often highly specialized. This paper tackles the problem of developing a general game-playing agent that can learn to play different games without being explicitly programmed for each one. The Atari 2600 platform is chosen as a research ground because it offers a diverse set of games with a consistent visual interface, bridging the gap between simple board games and complex modern video games.

Methods

The core of HyperNEAT-GGP is the HyperNEAT algorithm, an extension of Neuro Evolution of Augmenting Topologies (NEAT). Unlike standard NEAT which evolves the structure and weights of a neural network directly, HyperNEAT evolves an indirect encoding called a Compositional Pattern Producing Network (CPPN). This CPPN is then used to generate the weights of a standard neural network (ANN) that solves the task. The key advantage of HyperNEAT is its ability to exploit geometric regularities present in the input domain.

For Atari games, this translates to:

  • Visual Processing Stack: A game-independent pipeline that takes raw pixel data from the Atari screen and extracts meaningful information. This involves:
  • Image Segmentation: Grouping pixels of similar colors into "blobs."
    • Blob Merging: Identifying objects by tracking blobs with consistent velocity across frames.
  • Object Clustering: Grouping similar-shaped objects into "object classes" (e.g., cars facing left, cars facing right, the player's character).
  • Self-Identification: A crucial step to identify which on-screen entity is controlled by the agent. This is achieved by analyzing the velocity history of blobs and calculating "information gain" to determine which blob's movement is most consistently influenced by the agent's actions.
  • HyperNEAT-GGP Interface: The identified object classes and the agent's "self" are mapped to real-valued inputs for the ANN. The ANN's output is then interpreted to select an action. The paper uses a discretized grid overlay of the game screen, feeding object class information into the ANN's input nodes.

Datasets

The paper evaluates HyperNEAT-GGP on two Atari 2600 games: Freeway and Asterix. These games were chosen for their differing dynamics. The Atari 2600 platform itself, with its large collection of games and readily available emulators (like the Atari Learning Environment - ALE), serves as the broader benchmark environment.

Key Insights and Ideas

  • Geometric Regularity is Key: HyperNEAT's ability to exploit geometric patterns in the 2D game screen is a significant advantage for learning game-playing policies. This is particularly relevant for visual domains like Atari.
  • Indirect Encoding for Generality: Evolving a CPPN that generates the ANN's weights, rather than evolving the ANN directly, allows for more flexible and generalizable solutions. The CPPN's inherent geometric awareness is implicitly transferred to the ANN.
  • Game-Independent Visual Processing: Developing a visual processing pipeline that works across different Atari games reduces the need for game-specific feature engineering, a crucial step towards general game playing.
  • Self-Identification is Crucial: Knowing which entity on screen is controlled by the agent is fundamental for making informed decisions, and the information gain approach provides a robust method for this.
  • Atari as a Research Platform: The Atari 2600 is highlighted as an excellent platform for AI research due to its diverse game library, simple yet rich interface, and the availability of fast emulators.

Key Results

HyperNEAT-GGP demonstrated strong performance on both Freeway and Asterix, significantly outperforming previous reinforcement learning benchmarks, including various Sarsa(λ) agents and random action agents.

  • Freeway: HyperNEAT-GGP achieved champion scores of 29 (average 27.4) at generation 250, while Sarsa(λ) agents scored 0. This is attributed to the sparse rewards in Freeway, where HyperNEAT's initial random policies often stumbled upon successful strategies early on.
  • Asterix: HyperNEAT-GGP achieved champion scores of 1000 (average 870) at generation 250, significantly outperforming Sarsa(λ) agents (best 545). While random exploration yields some reward in Asterix, HyperNEAT-GGP showed steady improvement throughout training, reaching human-comparable scores.

Limitations and Future Work

The authors acknowledge several limitations and outline promising future directions:

  • Limited Object Classes and Actions: The current approach struggles with games that have a very large number of distinct object classes or complex action spaces (e.g., button presses in addition to joystick movements). Mapping many object classes to a limited set of input values becomes challenging.
  • Robustness of Visual Processing: The visual processing stack can be improved. Objects can be lost if they change shape or rotate, and static objects (like walls in Pac-Man) are not currently detected. Self-identification can also be made more robust by considering object persistence and velocity history more comprehensively.
  • Extending to More Games: The primary future work is to extend HyperNEAT-GGP to a wider variety of Atari games, addressing the challenges of more complex action spaces, numerous object classes, and more robust visual processing.
  • Generalization: The ultimate goal is to create an agent that can learn and seamlessly transition between many different tasks, and this work represents a significant step towards that ambitious objective.

Summary updated

BibTeX
@inproceedings{hausknecht2012hyperneat,
  author = {Matthew J. Hausknecht and Piyush Khandelwal and Risto Miikkulainen and Peter Stone},
  title = {{HyperNEAT-GGP: a hyperNEAT-based atari general game player}},
  booktitle = {GECCO},
  year = {2012},
  doi = {10.1145/2330163.2330195},
}
Figure