Abstraction for Solving Large Incomplete-Information Games

Abstract

Most real-world games and many recreational games are games of incomplete information. Over the last dozen years, abstraction has emerged as a key enabler for solving large incomplete-information games. First, the game is abstracted to generate a smaller, abstract game that is strategically similar to the original game. Second, an approximate equilibrium is computed in the abstract game. Third, the strategy from the abstract game is mapped back to the original game. In this paper, I will review key developments in the field. I present reasons for abstracting games, and point out the issue of abstraction pathology. I then review the practical algorithms for information abstraction and action abstraction. I then cover recent theoretical breakthroughs that beget bounds on the quality of the strategy from the abstract game, when measured in the original game. I then discuss how to reverse map the opponent's action into the abstraction if the opponent makes a move that is not in the abstraction. Finally, I discuss other topics of current and future research.