“What makes a game interesting enough for an AI agent to learn to play?”

For many years, efforts have been made to teach artificial intelligence to beat humans at almost every game that involves strategy. Games have been the testbed for the development of learning algorithms and the measurement of progress in artificial intelligence.

Even popular Russian mathematician Alexander Kronrod was quoted saying that “chess is the Drosophila of AI”. This parallel drawn to biology invites the question of whether shared structures linking various games can be identified. 

While the importance of games as a research platform for the development of AI agents is well-established, progress requires a proper taxonomy of games, an assessment of how interesting a game is, and how interesting games can be generated for training.

Multi-player interactions especially pose theoretical and practical challenges to AI techniques. The experimental results usually indicate that a carefully constructed AI algorithm can reach superhuman performance outside of two-player zero-sum games.

To survey the landscape of how agents within a game interact, the researchers at DeepMind developed a graph-theoretic toolkit that facilitates analysis of large-scale games, providing insights into their related topological structure in terms of their high-level strategic interactions.

Landscaping Games

The DeepMind researchers tried to demonstrate how network measures when applied to response graphs of large-scale games enable the landscaping of games, which in turn helps in quantifying relationships between games of varying sizes and characteristics. But how does one topologically analyse games? 

Usually, graph theory is considered as a framework for topological analysis of large systems involving interacting entities. Many AI breakthroughs in previous benchmark games, be it chess, Go or Dota 2, have been successful because they attempted to estimate a widely popular strategy– Nash equilibrium for mostly single or two-player games. Efficiently computing a Nash equilibrium for multiplayer games is more difficult.

In this work, the researchers combined graph and game theory for analysing the structure of multiplayer games.

This landscape that is illustrated above is generated by collecting the features associated with the response graph of games under consideration and by plotting the top two principal components. Games which are situated close to each other within that landscape indicate the presence of similar characteristics. For instance, the games that have similar or related rules are well-clustered together, indicating strong similarity despite their widely-varying raw sizes. 

The authors also observed that games with strong transitive components, for example, variations of Elo games, to be completely separated from strongly cyclical games like Rock–Paper–Scissors. 

This approach establishes a graph-theoretic approach for understanding the characteristics of defining games. The complexity of the game’s graph that is measured through information theory concepts is shown to provide a good assessment of the number of iterations required to solve it.

Finally, this information is then leveraged to generate new and interesting games, which allows for mixing the empirical games induced by Go and the AlphaStar League into a new game, contributing to the understanding of the topology of multiplayer games in AI.

Key Takeaways

• The main aim of this work is to provide a graph-based toolkit for analysis and comparison of games.

• This work can help generate games that are of interest in a richer context of domains.

• The proposed approach multiplayer games, enabling a richer understanding of the inherent relationships between strategies.

AI research has primarily emphasised the training of strong agents; the researchers call this as the Policy Problem, which entails the search for super human-level AI performance. Naturally, techniques for understanding the space of games are likely beneficial for the algorithmic development of future AI entities.

According to the authors, this work is a means of revealing topological structure, extending beyond related works and investigating this question for small classes of games. “Topological landscapes of games can help to generate related games of interest for AI agents to tackle, hopefully significantly extending the reach of AI system capabilities,” concluded the researchers.

Check the original paper here.