A Fast Bundle-based Anytime Algorithm for Poker and other Convex Games

H. Brendan McMahan, Geoffrey J. Gordon
Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, PMLR 2:323-330, 2007.

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-theart interior-point linear programming algorithm took over 4 days and 25GB of memory.

Cite this Paper

BibTeX
@InProceedings{pmlr-v2-mcmahan07a, 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}, pages = {323--330}, year = {2007}, editor = {Meila, Marina and Shen, Xiaotong}, volume = {2}, series = {Proceedings of Machine Learning Research}, address = {San Juan, Puerto Rico}, month = {21--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v2/mcmahan07a/mcmahan07a.pdf}, url = {https://proceedings.mlr.press/v2/mcmahan07a.html}, 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-theart interior-point linear programming algorithm took over 4 days and 25GB of memory.} }
Endnote
%0 Conference Paper %T A Fast Bundle-based Anytime Algorithm for Poker and other Convex Games %A H. Brendan McMahan %A Geoffrey J. Gordon %B Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2007 %E Marina Meila %E Xiaotong Shen %F pmlr-v2-mcmahan07a %I PMLR %P 323--330 %U https://proceedings.mlr.press/v2/mcmahan07a.html %V 2 %X 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-theart interior-point linear programming algorithm took over 4 days and 25GB of memory.
RIS
TY - CPAPER TI - A Fast Bundle-based Anytime Algorithm for Poker and other Convex Games AU - H. Brendan McMahan AU - Geoffrey J. Gordon BT - Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics DA - 2007/03/11 ED - Marina Meila ED - Xiaotong Shen ID - pmlr-v2-mcmahan07a PB - PMLR DP - Proceedings of Machine Learning Research VL - 2 SP - 323 EP - 330 L1 - http://proceedings.mlr.press/v2/mcmahan07a/mcmahan07a.pdf UR - https://proceedings.mlr.press/v2/mcmahan07a.html AB - 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-theart interior-point linear programming algorithm took over 4 days and 25GB of memory. ER -
APA
McMahan, H.B. & Gordon, G.J.. (2007). A Fast Bundle-based Anytime Algorithm for Poker and other Convex Games. Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 2:323-330 Available from https://proceedings.mlr.press/v2/mcmahan07a.html.

Related Material