Automated Construction of Abstractions in Games

An important part of our game theory research at AIC deals with sequential decision making, that is selecting a set of actions to play in a game environment. This task amounts to a difficult research problem mainly due to its size. In games like go, chess or poker which serve as benchmarks for AI research, there are more possible situations than atoms in the universe. That is why solving these games is so challenging. Our paper proposes a novel method using an iterative algorithm to create and solve imperfect recall abstractions of games. This approach allows us to carefully detect problems caused by missing information and refine the abstraction. We evaluated two possible domain-independent algorithms and were more than happy with the results. Watch the video to see the outcome of our research and read the full paper to dig deeper into the topic.

Abstract

Information abstraction is one of the methods for tackling large extensive-form games (EFGs). Removing some information available to players reduces the memory required for computing and storing strategies. We present novel domain-independent abstraction methods for creating very coarse abstractions of EFGs that still compute strategies that are (near) optimal in the original game. First, the methods start with an arbitrary abstraction of the original game (domain-specific or the coarsest possible). Next, they iteratively detect which information is required in the abstract game so that a (near) optimal strategy in the original game can be found and include this information into the abstract game. Moreover, the methods are able to exploit imperfect-recall abstractions where players can even forget the history of their own actions. We present two algorithms that follow these steps -- FPIRA, based on fictitious play, and CFR+IRA, based on counterfactual regret minimization. The experimental evaluation confirms that our methods can closely approximate Nash equilibrium of large games using abstraction with only 0.9% of information sets of the original game.