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