Computing an approximate jam/fold equilibrium for 3-player no-limit Texas Hold'em tournaments

ABSTRACT

A recent paper computes near-optimal strategies for two-player no-limit Texas hold'em tournaments; however, the techniques used are unable to compute equilibrium strategies for tournaments with more than two players. Motivated by the widespread popularity of multiplayer tournaments and the observation that jam/fold strategies are nearoptimal in the two player case, we develop an algorithm that computes approximate jam/fold equilibrium strategies in tournaments with three --- and potentially even more --- players. Our algorithm combines an extension of fictitious play to imperfect information games, an algorithm similar to value iteration for solving stochastic games, and a heuristic from the poker community known as the Independent Chip Model which we use as an initialization. Several ways of exploiting suit symmetries and the use of custom indexing schemes made the approach computationally feasible. Aside from the initialization and the restriction to jam/fold strategies, our high level algorithm makes no poker-specific assumptions and thus also applies to other multiplayer stochastic games of imperfect information.

REFERENCES

• 1: J. Ankenman and B. Chen. The Mathematics of Poker. ConJelCo LLC, 2006.
• 2: D. Billings, N. Burch, A. Davidson, R. Holte, J. Schaeffer, T. Schauenberg, and D. Szafron. Approximating game-theoretic optimal strategies for full-scale poker. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), 2003.
• 3: B. Bollobás. Combinatorics. Cambridge University Press, Cambridge, 1986.
• 4: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 5: D. Fudenberg and D. Levine. The Theory of Learning in Games. MIT Press, 1998.
• 6: S. Ganzfried and T. Sandholm. Algorithms for multiplayer stochastic games of imperfect information with application to three-player no-limit Texas hold'em tournaments. Draft.
• 7: A. Gilpin and T. Sandholm. A competitive Texas Hold'em poker player via automated abstraction and real-time equilibrium computation. In Proceedings of the National Conference on Artificial Intelligence (AAAI), 2006.
• 8: Andrew Gilpin , Tuomas Sandholm, Better automated abstraction techniques for imperfect information games, with application to Texas Hold'em poker, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329358]
• 9: Andrew Gilpin , Tuomas Sandholm, Lossless abstraction of imperfect information games, Journal of the ACM (JACM), v.54 n.5, p.25-es, October 2007 [doi>10.1145/1284320.1284324]
• 10: A. Gilpin, T. Sandholm, and T. B. Sørensen. Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of Texas Hold'em poker. In Proceedings of the National Conference on Artificial Intelligence (AAAI), 2007.
• 11: Andrew Gilpin , Tuomas Sandholm , Troels Bjerre Sørensen, A heads-up no-limit Texas Hold'em poker player: discretized betting models and automatically generated equilibrium-finding programs, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 12: Hold'emResources.net. www.holdemresources.net/hr/sngs/icmcalculator.html.
• 13: Peter Bro Miltersen , Troels Bjerre Sørensen, A near-optimal strategy for a heads-up no-limit Texas Hold'em poker tournament, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329357]
• 14: Sit-n-Go Power Tools, 2005. http://www.sitngo-analyzer.com/.
• 15: Two Plus Two Forums. Single table tournament forum FAQ, 2007. http://forumserver.twoplustwo.com/.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Economics

Keywords:
Texas Hold'em, equilibrium finding, game theory, imperfect information, poker, stochastic games