An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games
Abstract
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.
Cite
Text
Cermak et al. "An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/130Markdown
[Cermak et al. "An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/cermak2017ijcai-algorithm/) doi:10.24963/IJCAI.2017/130BibTeX
@inproceedings{cermak2017ijcai-algorithm,
title = {{An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games}},
author = {Cermak, Jiri and Bosanský, Branislav and Lisý, Viliam},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
pages = {936-942},
doi = {10.24963/IJCAI.2017/130},
url = {https://mlanthology.org/ijcai/2017/cermak2017ijcai-algorithm/}
}