Generational Adversarial MAP-Elites for Multi-Agent Game Illumination

Timothée Anne, Noah Syrkis, Meriem Elhosni, Florian Turati, Franck Legendre, Alain Jaquier, Sebastian RisiALIFE 2025 · DOI

Abstract

Unlike traditional optimization algorithms, which focus 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 operate directly on videos of behaviors, rather than relying on handcrafted descriptors. Some key findings are that (1) emerging evolutionary dynamics sometimes resemble an arms race, (2) starting each generation from scratch increases open-endedness, 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
@inproceedings{anne2025generational,
  author = {Timothée Anne and Noah Syrkis and Meriem Elhosni and Florian Turati and Franck Legendre and Alain Jaquier and Sebastian Risi},
  title = {{Generational Adversarial MAP-Elites for Multi-Agent Game Illumination}},
  booktitle = {ALIFE},
  year = {2025},
  doi = {10.1162/isal.a.859},
}
Figure