An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games

An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games

Jiri Cermak, Branislav Bošanský, Viliam Lisý

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 936-942. https://doi.org/10.24963/ijcai.2017/130

We solve large two-player zero-sum extensive-form games with perfect recall. We propose a new algorithm based on fictitious play that significantly reduces memory requirements for storing average strategies. The key feature is exploiting imperfect recall abstractions while preserving the convergence rate and guarantees of fictitious play applied directly to the perfect recall game. The algorithm creates a coarse imperfect recall abstraction of the perfect recall game and automatically refines its information set structure only where the imperfect recall might cause problems. Experimental evaluation shows that our novel algorithm is able to solve a simplified poker game with 7.10^5 information sets using an abstracted game with only 1.8% of information sets of the original game. Additional experiments on poker and randomly generated games suggest that the relative size of the abstraction decreases as the size of the solved games increases.
Keywords:
Knowledge Representation, Reasoning, and Logic: Game Theory
Agent-based and Multi-agent Systems: Noncooperative Games