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


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


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.

Related Material