Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning
Abstract
Iterative algorithms such as Counterfactual Regret Minimization (CFR) are the most popular way to solve large zero-sum imperfect-information games. In this paper we introduce Best-Response Pruning (BRP), an improvement to iterative algorithms such as CFR that allows poorly-performing actions to be temporarily pruned. We prove that when using CFR in zero-sum games, adding BRP will asymptotically prune any action that is not part of a best response to some Nash equilibrium. This leads to provably faster convergence and lower space requirements. Experiments show that BRP results in a factor of 7 reduction in space, and the reduction factor increases with game size.
Cite
Text
Brown and Sandholm. "Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning." International Conference on Machine Learning, 2017.Markdown
[Brown and Sandholm. "Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning." International Conference on Machine Learning, 2017.](https://mlanthology.org/icml/2017/brown2017icml-reduced/)BibTeX
@inproceedings{brown2017icml-reduced,
title = {{Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning}},
author = {Brown, Noam and Sandholm, Tuomas},
booktitle = {International Conference on Machine Learning},
year = {2017},
pages = {596-604},
volume = {70},
url = {https://mlanthology.org/icml/2017/brown2017icml-reduced/}
}