A Competitive Texas Hold'em Poker Player via Automated Abstraction and Real-Time Equilibrium Computation

Andrew Gilpin, Tuomas SandholmAAAI 2006 · OpenReview

Abstract

We present a game theory-based heads-up Texas Hold'em poker player, GS1. To overcome the computational obstacles stemming from Texas Hold'em's gigantic game tree, the player employs our automated abstraction techniques to reduce the complexity of the strategy computations. Texas Hold'em consists of four betting rounds. Our player solves a large linear program (offline) to compute strategies for the abstracted first and second rounds. After the second betting round, our player updates the probability of each possible hand based on the observed betting actions in the first two rounds as well as the revealed cards. Using these updated probabilities, our player computes in real-time an equilibrium approximation for the last two abstracted rounds. We demonstrate that our player, which incorporates very little poker-specific knowledge, is competitive with leading poker-playing programs which incorporate extensive domain knowledge, as well as with advanced human players.

Introduction

Texas Hold’em is a game of imperfect information with a staggering state space of approximately $10^{18}$ nodes. While small games can be solved using the "sequence form" and linear programming (LP) to find a Nash equilibrium, Texas Hold’em is far too large for direct computation. Previous state-of-the-art bots relied heavily on manual abstraction—expert poker players grouping "similar" hands together to simplify the game tree. This approach is inherently flawed as it relies on human intuition, which can be biased or imprecise.

The GS1 system addresses these challenges by automatically discovering abstractions and computing strategies robust against any opponent, aiming for a minimax equilibrium rather than trying to exploit specific human weaknesses.

Methods

The researchers developed a two-pronged approach to handle the four betting rounds of poker:

Automated Abstraction (GameShrink)

Instead of human-defined rules, the GameShrink algorithm was used to group hands into "equivalence classes" based on their win/loss probability distributions. For the first two rounds (pre-flop and flop), the game was reduced to a size manageable by a massive offline LP solver.

Hybrid Computation

  1. Offline (Rounds 1 & 2): A massive LP (244k columns, 101M non-zeros) was solved over seven days to determine the optimal strategy for the start of the game.
  2. Real-time (Rounds 3 & 4): Because the game tree expands significantly in later rounds, GS1 uses Bayesian inference once the "turn" card is revealed to estimate the opponent's likely hands. It then solves a smaller, localized equilibrium for the remainder of the game in real-time.

Anytime Solving with Simplex

To ensure the bot always has a move ready within a 15-60 second time limit, the system utilizes the Simplex algorithm. By choosing dual simplex when playing as Player 1 and primal simplex for Player 2, the researchers ensured that the "interim" solution was always a feasible strategy, even if the solver was interrupted.

Results

GS1 was evaluated against both computer programs and human players to assess its competitiveness.

Performance Against Computer Opponents

GS1 was tested against Sparbot, a game-theory bot using manual abstractions, and Vexbot, an opponent-modeling bot. After 10,000 hands against Sparbot, GS1 was essentially tied, winning 0.007 small bets per hand. Against Vexbot, GS1 initially saw significant gains, though Vexbot’s learning algorithm eventually narrowed the gap to a tie after 5,000 hands.

GS1 performance against Sparbot (left) and Vexbot (right) over thousands of hands.

Performance Against Human Players

In a trial of 1,576 hands against a pool of human players, GS1 proved highly competitive. While it lost a negligible 0.02 small bets per hand overall, it achieved a positive win rate of 0.01 small bets per hand against the "expert" subgroup.

Performance of GS1 against intermediate and expert human players.

The results indicate that GS1 is effectively on par with the best players and programs of its era, with observed differences falling within the standard deviation of the high-variance game.

Conclusion

GS1 demonstrates that a competitive poker AI can be built with minimal domain-specific knowledge. By leveraging automated abstraction and real-time equilibrium computation, the system achieves robustness through minimax strategies. Future work will focus on addressing "off-path" scenarios where the real-time solver may not have a prepared move and extending these techniques to multi-player (3+) poker, which remains a significant challenge in game theory.

Summary updated

Abstract

We present a game theory-based heads-up Texas Hold'em poker player, GS1. To overcome the computational obstacles stemming from Texas Hold'em's gigantic game tree, the player employs our automated abstraction techniques to reduce the complexity of the strategy computations. Texas Hold'em consists of four betting rounds. Our player solves a large linear program (offline) to compute strategies for the abstracted first and second rounds. After the second betting round, our player updates the probability of each possible hand based on the observed betting actions in the first two rounds as well as the revealed cards. Using these updated probabilities, our player computes in real-time an equilibrium approximation for the last two abstracted rounds. We demonstrate that our player, which incorporates very little poker-specific knowledge, is competitive with leading poker-playing programs which incorporate extensive domain knowledge, as well as with advanced human players.
BibTeX
@inproceedings{gilpin2006competitive,
  author = {Andrew Gilpin and Tuomas Sandholm},
  title = {{A Competitive Texas Hold'em Poker Player via Automated Abstraction and Real-Time Equilibrium Computation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=rkVsi6l_bS},
}
Figure