A Fast Bundle-Based Anytime Algorithm for Poker and Other Convex Games
Abstract
Convex games are a natural generalization of matrix (normal-form) games that can compactly model many strategic interactions with interesting structure. We present a new anytime algorithm for such games that leverages fast best-response oracles for both players to build a model of the overall game. This model is used to identify search directions; the algorithm then does an exact minimization in this direction via a specialized line search. We test the algorithm on a simplified version of Texas Hold’em poker represented as an extensive-form game. Our algorithm approximated the exact value of this game within \$0.20 (the maximum pot size is \$310.00) in a little over 2 hours, using less than 1.5GB of memory; finding a solution with comparable bounds using a state-of-the-art interior-point linear programming algorithm took over 4 days and 25GB of memory.
Cite
Text
McMahan and Gordon. "A Fast Bundle-Based Anytime Algorithm for Poker and Other Convex Games." Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, 2007.Markdown
[McMahan and Gordon. "A Fast Bundle-Based Anytime Algorithm for Poker and Other Convex Games." Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, 2007.](https://mlanthology.org/aistats/2007/mcmahan2007aistats-fast/)BibTeX
@inproceedings{mcmahan2007aistats-fast,
title = {{A Fast Bundle-Based Anytime Algorithm for Poker and Other Convex Games}},
author = {McMahan, H. Brendan and Gordon, Geoffrey J.},
booktitle = {Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics},
year = {2007},
pages = {323-330},
volume = {2},
url = {https://mlanthology.org/aistats/2007/mcmahan2007aistats-fast/}
}