research-article

A near-optimal strategy for a heads-up no-limit Texas Hold'em poker tournament

Authors:

Peter Bro Miltersen,

Troels Bjerre SørensenAuthors Info & Claims

AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems

Article No.: 191, Pages 1 - 8

https://doi.org/10.1145/1329125.1329357

Published: 14 May 2007 Publication History

Abstract

We analyze a heads-up no-limit Texas Hold'em poker tournament with a fixed small blind of 300 chips, a fixed big blind of 600 chips and a total amount of 8000 chips on the table (until recently, these parameters defined the heads-up endgame of sit-n-go tournaments on the popular Party-Poker.com online poker site). Due to the size of this game, a computation of an optimal (i.e. minimax) strategy for the game is completely infeasible. However, combining an algorithm due to Koller, Megiddo and von Stengel with concepts of Everett and suggestions of Sklansky, we compute an optimal jam/fold strategy, i.e. a strategy that would be optimal if any bet made by the player playing by the strategy (but not bets of his opponent) had to be his entire stack. Our computations establish that the computed strategy is near-optimal for the unrestricted tournament (i.e., with post-flop play being allowed) in the rigorous sense that a player playing by the computed strategy will win the tournament with a probability within 1.4 percentage points of the probability that an optimal strategy (allowing post-flop play) would give.

References

[1]

R. Andersson. Pseudo-optimal Strategies in No-Limit Poker. Master's thesis, Umeå University, May 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 IJCAI, 2003.

Digital Library

[3]

J. R. S. Blair, D. Mutchler, M. van Lent. Perfect Recall and Pruning in Games with Imperfect Information. Computational Intelligence, 12:131--154, 1996.

[4]

A. Condon. The Complexity of Stochastic Games. Information and Computation, pages 203--224, 1992.

Digital Library

[5]

A. Condon. On Algorithms for Simple Stochastic Games. Advances in Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 13:51--73, 1993.

[6]

J. Czyzyk, S. Mehrotra, M. Wagner, S. J. Wright. PCx: An Interior-Point Code for Linear Programming. Optimization Methods and Software, 12:397--430, 1999.

[7]

M. Dhiflaoui, S. Funke, C. Kwappik, K. Mehlhorn, M. Seel, E. Schmer, R. Schulte, and D. Weber. Certifying and Repairing Solutions to Large LPs, How Good are LP-Solvers? In SODA, pages 255--256, 2003.

Digital Library

[8]

H. Everett. Recursive games. In Contributions to the Theory of Games Vol. III, Vol 39 of Annals of Mathematical Studies, 1957.

[9]

A. Gilpin and T. Sandholm. Optimal Rhode Island Hold'em Poker. In AAAI, 2005.

Digital Library

[10]

A. Gilpin and T. Sandholm. Finding Equilibria in Large Sequential Games of Incomplete Information. In Electronic Commerce, pages 160--169, 2006.

Digital Library

[11]

A. Gilpin and T. Sandholm. A Texas Hold'em poker player based on automated abstraction and real-time equilibrium computation. In AAMAS, 2006.

Digital Library

[12]

D. Koller, N. Megiddo, and B. von Stengel. Fast Algorithms for Finding Randomized Strategies in Game Trees. In STOC, pages 750--759, 1994.

Digital Library

[13]

J. Shi and M. L. Littman. Abstraction Methods for Game Theoretic Poker. In Computers and Games, pages 333--345, 2001.

Digital Library

[14]

D. Sklansky. Tournament Poker for Advanced Players. Two Plus Two Publishing, 2002.

[15]

D. Sklansky. Card Player Magazine, 2003.

[16]

T. Streib. Blind versus Blind Play in Tournament Situations, Nov. 2005. Two Plus Two Internet Magazine (twoplustwo.com).

Cited By

Rubin JWatson I(2019)Computer pokerArtificial Intelligence10.1016/j.artint.2010.12.005175:5-6(958-987)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1016/j.artint.2010.12.005
Hilbe CŠimsa ŠChatterjee KNowak M(2018)Evolution of cooperation in stochastic gamesNature10.1038/s41586-018-0277-x559:7713(246-249)Online publication date: 4-Jul-2018
https://doi.org/10.1038/s41586-018-0277-x
Dalpasso MLancia G(2014)Estimating the strength of poker hands by integer linear programming techniquesCentral European Journal of Operations Research10.1007/s10100-014-0366-323:3(625-640)Online publication date: 30-Oct-2014
https://doi.org/10.1007/s10100-014-0366-3
Show More Cited By

Index Terms

A near-optimal strategy for a heads-up no-limit Texas Hold'em poker tournament
1. Information systems
  1. Information systems applications
    1. Decision support systems
      1. Expert systems

Recommendations

Heads-up limit hold'em poker is solved

Poker is a family of games that exhibit imperfect information, where players do not have full knowledge of past events. While many perfect information games have been solved (e.g., Connect-Four and checkers), no nontrivial imperfect information game ...
A Texas Hold'em poker player based on automated abstraction and real-time equilibrium computation
AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems

We demonstrate our game theory-based Texas Hold'em poker player. To overcome the computational difficulties stemming from Texas Hold'em's gigantic game tree, our player uses automated abstraction and real-time equilibrium approximation. Our player ...
Better automated abstraction techniques for imperfect information games, with application to Texas Hold'em poker
AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems

We present new approximation methods for computing game-theoretic strategies for sequential games of imperfect information. At a high level, we contribute two new ideas. First, we introduce a new state-space abstraction algorithm. In each round of the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems

May 2007

1585 pages

ISBN:9788190426275

DOI:10.1145/1329125

Conference Chairs:
Edmund Durfee
University of Michigan
,
Makoto Yokoo
Kyushu University
,
Program Chairs:
Michael Huhns
University of South Carolina
,
Onn Shehory
IBM Haifa Research Lab, Israel

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IFAAMAS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 May 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS07

Sponsor:

AAMAS07: International Conference on Autonomous Agents and Mulitagent Systems

May 14 - 18, 2007

Hawaii, Honolulu

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
944
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)25

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Rubin JWatson I(2019)Computer pokerArtificial Intelligence10.1016/j.artint.2010.12.005175:5-6(958-987)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1016/j.artint.2010.12.005
Hilbe CŠimsa ŠChatterjee KNowak M(2018)Evolution of cooperation in stochastic gamesNature10.1038/s41586-018-0277-x559:7713(246-249)Online publication date: 4-Jul-2018
https://doi.org/10.1038/s41586-018-0277-x
Dalpasso MLancia G(2014)Estimating the strength of poker hands by integer linear programming techniquesCentral European Journal of Operations Research10.1007/s10100-014-0366-323:3(625-640)Online publication date: 30-Oct-2014
https://doi.org/10.1007/s10100-014-0366-3
Sørensen T(2012)Repeated zero-sum games with budgetProceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 210.5555/2343776.2343815(829-836)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.5555/2343776.2343815
Teófilo LReis L(2011)Building a no limit texas hold'em poker agent based on game logs using supervised learningProceedings of the Second international conference on Autonomous and intelligent systems10.5555/2026956.2026965(73-82)Online publication date: 22-Jun-2011
https://dl.acm.org/doi/10.5555/2026956.2026965
Sandholm T(2010)The State of Solving Large Incomplete‐Information Games, and Application to PokerAI Magazine10.1609/aimag.v31i4.231131:4(13-32)Online publication date: Dec-2010
https://doi.org/10.1609/aimag.v31i4.2311
Ganzfried SSandholm T(2009)Computing equilibria in multiplayer stochastic games of imperfect informationProceedings of the 21st International Joint Conference on Artificial Intelligence10.5555/1661445.1661469(140-146)Online publication date: 11-Jul-2009
https://dl.acm.org/doi/10.5555/1661445.1661469
Halprin RNaor MCranor L(2009)Games for extracting randomnessProceedings of the 5th Symposium on Usable Privacy and Security10.1145/1572532.1572548(1-12)Online publication date: 15-Jul-2009
https://dl.acm.org/doi/10.1145/1572532.1572548
Mehrabi AHaghighat A(2009)Discovering the Rules in a Poker Player's Mind Based on the Association Rule MiningProceedings of the 2009 International Conference on Computer Technology and Development - Volume 0210.1109/ICCTD.2009.117(189-193)Online publication date: 13-Nov-2009
https://dl.acm.org/doi/10.1109/ICCTD.2009.117
Ganzfried SSandholm T(2008)Computing an approximate jam/fold equilibrium for 3-player no-limit Texas Hold'em tournamentsProceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 210.5555/1402298.1402351(919-925)Online publication date: 12-May-2008
https://dl.acm.org/doi/10.5555/1402298.1402351
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents