Abstract
Imperfect-information games, where players have private information, pose a unique challenge in artificial intelligence. In recent years, Heads-Up No-Limit Texas Hold'em poker, a popular version of poker, has emerged as the primary benchmark for evaluating game-solving algorithms for imperfect-information games. We demonstrate a winning agent from the 2016 Annual Computer Poker Competition, Baby Tartanian8.
Introduction
Unlike perfect-information games such as Chess or Go, poker involves hidden information (private cards), rendering traditional search algorithms inapplicable. Heads-Up No-Limit Texas Hold’em (HUNL) represents the "grand challenge" of this field due to its immense complexity; the game tree contains approximately $10^{165}$ nodes. To navigate this space, researchers must abstract the game into a tractable size, solve for a Nash equilibrium, and map the solution back to the full game. Baby Tartanian8 achieved success in this domain by combining massive-scale distributed computing with asymmetric abstraction and a novel pruning technique.
Methodology
Baby Tartanian8's architecture relies on three primary innovations designed to handle the scale of HUNL:
Asymmetric Action Abstraction
Rather than treating both players symmetrically, the authors employed asymmetric action abstraction. The agent's own choices were restricted to a small set of "expert-vetted" moves, while the opponent was modeled with a much broader range of possible actions. This approach leverages domain knowledge to simplify the agent's decision-making while ensuring it remains robust against diverse opponent behaviors.
Distributed Equilibrium Finding
The agent utilized a distributed version of Monte Carlo Counterfactual Regret Minimization (MCCFR). The game tree was decomposed at the "flop" (the first three community cards), with a "head" node managing the pre-flop strategy and separate "child" nodes handling post-flop scenarios. This allowed for massive parallelization across 3,408 cores on the Comet supercomputer, totaling approximately 2 million core hours.
Regret-Based Sampling (RBS)
A key algorithmic contribution is Regret-Based Sampling (RBS), a novel sampling algorithm based on Regret-Based Pruning (RBP). RBS allows the agent to skip exploring actions that have historically performed poorly, significantly accelerating the convergence toward a Nash equilibrium.
Experimental Results
Baby Tartanian8 demonstrated superior performance at the 2016 Annual Computer Poker Competition (ACPC), placing 1st in the Total Bankroll competition and 3rd in the Instant Runoff competition.
Preliminary experiments highlighted the efficiency of the RBS algorithm. As shown in the figure above, RBS significantly outperformed standard external sampling MCCFR, reaching higher performance levels (measured in mbb/hand) in a fraction of the core hours required by the baseline. While the full strategy required 16 TB of storage, it was "purified" (made deterministic) and compressed to under 200 GB to meet competition limits, resulting in the "Baby" version of the agent.
Discussion and Conclusion
The success of Baby Tartanian8 underscores the power of strategic pruning and asymmetric modeling in large-scale imperfect-information games. By limiting the agent's own action space to high-quality moves, computational resources can be redirected toward defending against a wider array of opponent strategies.
However, limitations remain. While RBS provides empirical speedups, it currently lacks a formal proof of convergence to a Nash equilibrium. Additionally, evidence suggests that RBS may slightly decrease performance when very close to convergence, leading the authors to disable the feature during the final stages of training. Future work will focus on refining these pruning techniques and exploring the robustness of uncompressed models.
Summary updated