A heads-up no-limit Texas Hold'em poker player: discretized betting models and automatically generated equilibrium-finding programs

ABSTRACT

We present Tartanian, a game theory-based player for heads-up no-limit Texas Hold'em poker. Tartanian is built from three components. First, to deal with the virtually infinite strategy space of no-limit poker, we develop a discretized betting model designed to capture the most important strategic choices in the game. Second, we employ potential-aware automated abstraction algorithms for identifying strategically similar situations in order to decrease the size of the game tree. Third, we develop a new technique for automatically generating the source code of an equilibrium-finding algorithm from an XML-based description of a game. This automatically generated program is more efficient than what would be possible with a general-purpose equilibrium-finding program. Finally, we present results from the AAAI-07 Computer Poker Competition, in which Tartanian placed second out of ten entries.

REFERENCES

• 1: R. Andersson. Pseudo-optimal strategies in no-limit poker. Master's thesis, Umeå University, May 2006.
• 2: D. Billings, M. Bowling, N. Burch, A. Davidson, R. Holte, J. Schaeffer, T. Schauenberg, and D. Szafron. Game tree search with adaptation in stochastic imperfect information games. In Proceedings of the 4th International Conference on Computers and Games (CG), pages 21--34, Ramat-Gan, Israel, July 2004. Springer-Verlag.
• 3: 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), pages 661--668, Acapulco, Mexico, 2003. Morgan Kaufmann.
• 4: Darse Billings , Aaron Davidson , Jonathan Schaeffer , Duane Szafron, The challenge of poker, Artificial Intelligence, v.134 n.1-2, p.201-240, January 2002 [doi>10.1016/S0004-3702(01)00130-8]
• 5: Sam Ganzfried , Tuomas Sandholm, Computing an approximate jam/fold equilibrium for 3-player no-limit Texas Hold'em tournaments, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 6: A. Gilpin, S. Hoda, J. Peña, and T. Sandholm. Gradient-based algorithms for finding Nash equilibria in extensive form games. In 3rd International Workshop on Internet and Network Economics (WINE), San Diego, CA, 2007.
• 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), Boston, MA, 2006. AAAI Press.
• 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), pages 50--57, Vancouver, Canada, 2007. AAAI Press.
• 11: D. Harrington and B. Robertie. Harrington on Hold'em Expert Strategy for No-Limit Tournaments, Vol. 1: Strategic Play. Two Plus Two, 2004.
• 12: S. Hoda, A. Gilpin, and J. Peña. A gradient-based approach for computing Nash equilibria of large sequential games. Available at http://www.optimization-online.org/, 2007.
• 13: M. Johanson, M. Zinkevich, and M. Bowling. Computing robust counter-strategies. In Proceedings of the 23rd Annual Conference on Uncertainty in Artificial Intelligence (UAI), Vancouver, BC, 2007.
• 14: D. Koller and N. Megiddo. The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior, 4(4):528--552, Oct. 1992.
• 15: Daphne Koller , Avi Pfeffer, Representations and solutions for game-theoretic problems, Artificial Intelligence, v.94 n.1-2, p.167-215, July 1997 [doi>10.1016/S0004-3702(97)00023-4]
• 16: K. Korb, A. Nicholson, and N. Jitnah. Bayesian poker. In Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence (UAI), pages 343--350, Stockholm, Sweden, 1999.
• 17: 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]
• 18: Yu. Nesterov, Excessive Gap Technique in Nonsmooth Convex Minimization, SIAM Journal on Optimization, v.16 n.1, p.235-249, 2005 [doi>10.1137/S1052623403422285]
• 19: I. Romanovskii. Reduction of a game with complete memory to a matrix game. Soviet Mathematics, 3:678--681, 1962.
• 20: Jiefu Shi , Michael L. Littman, Abstraction Methods for Game Theoretic Poker, Revised Papers from the Second International Conference on Computers and Games, p.333-345, October 26-28, 2000
• 21: K. Takusagawa. Nash equilibrium of Texas Hold'em poker, 2000. Undergraduate thesis, Stanford University.
• 22: B. von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220--246, 1996.
• 23: M. Zinkevich, M. Bowling, and N. Burch. A new algorithm for generating equilibria in massive zero-sum games. In Proceedings of the National Conference on Artificial Intelligence (AAAI), Vancouver, Canada, 2007.
• 24: M. Zinkevich, M. Bowling, M. Johanson, and C. Piccione. Regret minimization in games with incomplete information. In Proceedings of the 23rd Annual Conference on Uncertainty in Artificial Intelligence (UAI), Vancouver, BC, 2007.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics

Keywords:
Nash equilibrium, automated abstraction, computational game theory, equilibrium finding, heads-up no-limit poker, imperfect information games, sequential games