DeepMind Proposes Graph-Theoretic Investigation of the Multiplayer Games Landscape

In the mid-1960s, computer science and AI researchers adopted the pet name “drosophila” for the game of Chess — a reference to the fruit flies commonly used in genetic research. American evolutionary biologist Thomas Morgan made critical contributions to the field by studying his famous “fly rooms,” and AI researchers today believe multiplayer games like Chess can provide similar accessible and relatively simple experimental environments for shaping useful knowledge about complex systems.

In recent years researchers have made multiplayer games a hot testbed for AI research, using reinforcement learning techniques to create superhuman agents in Chess, Go, StarCraft II and others.

“This progress, however, can be better informed by characterizing games and their topological landscape,” proposes the paper Navigating the Landscape of Multiplayer Games, recently published in Nature Communications. In the work, researchers from DeepMind and Universidade de Lisboa introduce a graph-based toolkit for analyzing and comparing games in this regard.

Understanding and decomposing the characterizing features of games can be leveraged for downstream training of agents via curriculum learning, which seeks to enable agents to learn increasingly-complex tasks. The researchers say it has become increasingly important to identify a framework that can taxonomize, characterize, and decompose complex AI tasks, and they turned to multiplayer games for references. They defined the core challenge as a Problem Problem: “the engineering problem of generating large numbers of interesting adaptive environments to support research.”

The researchers start with a fundamental question: What makes a game interesting enough for an AI agent to learn to play? They propose that answering this requires techniques that can characterize and enable discovery over the topological landscape of games, “whether they are interesting or not.”

The team combined graph and game theory to analyze the structure of general-sum, multiplayer games. They used the new toolkit to characterize games, looking at motivating examples and canonical games with well-defined structures first, then extending to larger-scale empirical games datasets. The games’ graph representations can offer researchers various insights, such as strong transitive relationships revealed in AlphaGo, the DeepMind program that defeated Go grandmaster Lee Sedol in 2016.

The study surveys the landscape of games and develops techniques to help with understanding the space of games, the downstream training of agents in game settings, and interest-improving algorithmic development. The team says the work opens paths for further exploration of the theoretical properties of graph-based games analysis and the Problem Problem and task theory, and can benefit related studies on the geometry and structure of games.

The paper Navigating the Landscape of Multiplayer Games is on Nature Communications.

---

Reporter: Fangyu Cai | Editor: Michael Sarazen

---

We know you don’t want to miss any news or research breakthroughs. Subscribe to our popular newsletter Synced Global AI Weekly to get weekly AI updates.

---

Thinking of contributing to Synced Review? Synced’s new column Share My Research welcomes scholars to share their own research breakthroughs with global AI enthusiasts.