Adversarial Coevolutionary Illumination with Generational Adversarial MAP-Elites

Timothée Anne, Noah Syrkis, Sebastian Risi

TL;DR

This paper introduces Generational Adversarial MAP-Elites (GAME), a novel Quality-Diversity (QD) algorithm that tackles adversarial problems by coevolving both competing sides simultaneously. By integrating a vision embedding model (VEM), GAME can learn from raw video data, eliminating the need for manual behavior descriptors and enabling broader applicability across diverse domains.

What Problem Does This Paper Address?

Traditional optimization algorithms aim to find a single "best" solution. In contrast, Quality-Diversity (QD) algorithms seek to discover a range of high-performing solutions that explore a "behavior space." This is crucial for complex problems where multiple strategies might be effective, or where the definition of "best" is subjective. However, applying QD to adversarial problems (like games where two sides compete) is tricky. The behavior of one side directly influences the other, creating a dynamic "arms race." Existing QD methods often simplify this by only evolving one side, which limits the exploration of the full adversarial landscape. This paper addresses this limitation by proposing a method to coevolve both sides of an adversarial problem, aiming for a more comprehensive illumination of the strategy space.

Methods

The core innovation is Generational Adversarial MAP-Elites (GAME). It's a coevolutionary QD algorithm that works by alternating which side (e.g., Blue or Red) is evolved at each generation. This means that in one generation, Blue agents are trained to be good against a fixed set of Red agents, and in the next, Red agents are trained against the newly evolved Blue agents. This iterative process encourages an "arms race" dynamic.

A key technical contribution is the use of a Vision Embedding Model (VEM), specifically CLIP. Instead of requiring researchers to manually define what constitutes a "behavior" (e.g., "aggressive attack" or "defensive stance"), GAME takes raw video footage of the agents' interactions and uses the VEM to extract a high-dimensional behavior descriptor. This makes the algorithm much more generalizable, as it doesn't need domain-specific feature engineering. To handle the high dimensionality of these VEM-derived behaviors, GAME employs an unstructured archive, which is a flexible way to store and organize diverse solutions without a rigid grid.

Datasets

The paper evaluates GAME on three distinct adversarial domains:

  • Parabellum: A multi-agent battle game where agents control units with behavior trees. This is the primary domain for ablation studies and demonstrating core GAME mechanics.
  • Wrestling: A 2D soft-robot simulation environment where robots evolve their morphology and control to compete. This showcases GAME's applicability to physical simulation and morphology evolution.
  • Hearthbreaker: A deck-building card game (a simulator of Hearthstone) where agents evolve decks of cards to compete. This demonstrates GAME's ability to handle strategic, combinatorial problems.

No new datasets were introduced; rather, existing simulation environments were adapted for adversarial QD tasks.

Key Insights and Ideas

  • Coevolutionary Arms Races: GAME naturally fosters "arms race" dynamics, where each side continuously adapts to the other's evolving strategies, leading to more sophisticated behaviors.
  • Neutral Mutations as Stepping Stones: The paper suggests that "neutral mutations" (changes that don't immediately improve fitness but don't hurt it either) are crucial. These seemingly insignificant changes can act as stepping stones, enabling future, more significant performance leaps.
  • VEM for Domain Agnosticism: Using a VEM like CLIP to extract behavior descriptors from video is a powerful way to make QD algorithms applicable to a wider range of problems without requiring manual feature engineering.
  • Bootstrap's Role: Bootstrapping (using evaluations from previous generations to seed new ones) appears to accelerate search, but surprisingly, the variant without bootstrapping showed more consistent novelty generation, hinting at a trade-off between speed and sustained open-endedness.

Key Results

  • Parabellum: GAME successfully illuminated the strategy space, outperforming one-sided QD baselines and demonstrating the necessity of its components (VEM, coevolution, unstructured archive) through ablation studies.
  • Wrestling: GAME evolved diverse and high-performing soft-robot morphologies, showing higher velocities and better quality (measured by ELO score) compared to baselines. The VEM was shown to be robust to variations in the number of frames used.
  • Hearthbreaker: GAME demonstrated its ability to evolve competitive decks, showing comparable or better quality than a one-sided MAP-Elites approach, even though it explored a much wider range of strategies.
  • Robustness: GAME proved robust to fixed random seeds in stochastic environments.

Limitations and Future Work

  • Search Space Limitations: The authors acknowledge that the current search spaces (behavior trees, soft-robot morphologies, card decks) are not inherently "open-ended." This limits the algorithm's ability to generate truly unbounded novelty.
  • VEM Behavior Space: While powerful, the VEM-derived behavior space might not perfectly capture all aspects of an agent's strategy, especially in domains where subtle tactical nuances are critical.
  • Future Directions: The paper suggests applying GAME to more inherently open-ended search spaces (e.g., using end-to-end neural networks for controllers, or more complex agents with reactive behaviors). Exploring the role of extinction events in driving novelty and investigating body-brain coevolution for artificial creatures are also highlighted.

Summary updated

Abstract

Unlike traditional optimization algorithms focusing on finding a single optimal solution, Quality-Diversity (QD) algorithms illuminate a search space by finding high-performing solutions that cover a specified behavior space. However, tackling adversarial problems is more challenging due to the behavioral interdependence between opposing sides. Most applications of QD algorithms to these problems evolve only one side, thus reducing illumination coverage. In this paper, we propose a new QD algorithm, Generational Adversarial MAP-Elites (GAME), which coevolves solutions by alternating sides through a sequence of generations. Combining GAME with vision embedding models enables the algorithm to directly work from videos of behaviors instead of handcrafted descriptors. Some key findings are that (1) emerging evolutionary dynamics sometimes resemble an arms race, (2) starting each generation from scratch increases openendedness, and (3) keeping neutral mutations preserves stepping stones that seem necessary to reach the highest performance. In conclusion, the results demonstrate that GAME can successfully illuminate an adversarial multi-agent game, opening up interesting future directions in understanding the emergence of open-ended coevolution.
BibTeX
@misc{anne2025adversarial,
  author = {Timothée Anne and Noah Syrkis and Sebastian Risi},
  title = {{Adversarial Coevolutionary Illumination with Generational Adversarial MAP-Elites}},
  year = {2025},
  eprint = {2505.06617},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.06617},
}
Figure