Hierarchical Abstraction, Distributed Equilibrium Computation, and Post-Processing, with Application to a Champion No-Limit Texas Hold'em Agent

By Noam Brown, Sam Ganzfried, Tuomas Sandholm. 2015

72 citations recorded by the source corpus.

The leading approach for solving large imperfect-information games is automated abstraction followed by running an equilibrium-finding algorithm. We introduce a distributed version of the most commonly used equilibrium-finding algorithm, counterfactual regret minimization (CFR), which enables CFR to scale to dramatically larger abstractions and numbers of cores. The new algorithm begets constraints on the abstraction so as to make the pieces running on different computers disjoint. We introduce an algorithm for generating such abstractions while capitalizing on state-of-the-art abstraction ideas such as imperfect recall and earth-mover's distance. Our techniques enabled an equilibrium computation of unprecedented size on a supercomputer with a high inter-blade memory latency. Prior approaches run slowly on this architecture. Our approach also leads to a significant improvement over using the prior best approach on a large shared-memory server with low memory latency. Finally, we introduce a family of post-processing techniques that outperform prior ones. We applied these techniques to generate an agent for two-player no-limit Texas Hold'em, called Tartanian7, that won the 2014 Annual Computer Poker Competition, beating each opponent with statistical significance.

Subfields: Artificial Intelligence, Economics and Econometrics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Economics and Econometrics

In Management Science and Operations Research

Citations in the corpus

A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, methodology): “When the model is fully known and the setting is strictly adversarial with two players, there are policy iteration methods based on regret minimization that scale very well when using domain-specific abstractions [27, 14, 46, 47], which was a major component of the expert no-limit poker AI Libratus ”
Maintaining cooperation in complex social dilemmas using deep reinforcement learning (2017, background): “Much of this literature focuses either on zerosum environments (Tesauro, 1995; Silver et al., 2016; 2017; Brown et al., 2015; Kempka et al., 2016; Wu & Tian, 2016; Usunier et al., 2016) or coordination games without an incentive to defect (Lowe et al.”
Time and Space: Why Imperfect Information Games are Hard (2018, background): “The quality of the strategy depends on the similarity of the grouped situations [57], and there has been a series of increasingly complicated algorithms for automatically generating abstract poker games [33, 29, 13].”