GS3 and Tartanian: game theory-based heads-up limit and no-limit Texas Hold'em poker-playing programs

ABSTRACT

We demonstrate two game theory-based programs for heads-up limit and no-limit Texas Hold'em poker. The first player, GS3, is designed for playing limit Texas Hold'em, in which all bets are a fixed amount. The second player, Tartanian, is designed for the no-limit variant of the game, in which the amount bet can be any amount up to the number of chips the player has. Both GS3 and Tartanian are based on our potential-aware automated abstraction algorithm for identifying strategically similar situations in order to decrease the size of the game tree. Tartanian, in order to deal with the virtually infinite strategy space of no-limit poker, in addition uses a discretized betting model designed to capture the most important strategic choices in the game. The strategies for both players are computed using our improved version of Nesterov's excessive gap technique specialized for poker.

In this demonstration, participants will be invited to play against both of the players, and to experience first-hand the sophisticated strategies employed by our players.

REFERENCES

• 1: 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]
• 2: 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.
• 3: A. Gilpin and T. Sandholm. Optimal Rhode Island Hold'em poker. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 1684--1685, 2005. Intelligent Systems Demonstration.
• 4: 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.
• 5: Andrew Gilpin , Tuomas Sandholm, A Texas Hold'em poker player based on automated abstraction and real-time equilibrium computation, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160911]
• 6: 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]
• 7: 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]
• 8: 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.
• 9: 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
• 10: 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.

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, Texas Hold'em poker, automated abstraction, computational game theory, equilibrium finding, imperfect information games, sequential games