Evaluating state-space abstractions in extensive-form games

By Michael Bradley Johanson, Neil Burch, Richard Anthony Valenzano, Michael H. Bowling. 2013

81 citations recorded by the source corpus.

Efficient algorithms exist for finding optimal policies in extensive-form games. However, human-scale problems are typically so large that this computation remains infeasible with modern computing resources. State-space abstraction techniques allow for the derivation of a smaller and strategically similar abstract domain, in which an optimal strategy can be computed and then used as a suboptimal strategy in the real domain. In this paper, we consider the task of evaluating the quality of an abstraction, independent of a specific abstract strategy. In particular, we use a recent metric for abstraction quality and examine imperfect recall abstractions, in which agents "forget" previously observed information to focus the abstraction effort on more recent and relevant state information. We present experimental results in the domain of Texas hold'em poker that validate the use of distribution-aware abstractions over expectation-based approaches, demonstrate that the new metric better predicts tournament performance, and show that abstractions built using imperfect recall outperform those built using perfect recall in terms of both exploitability and one-on-one play.

How researchers see this paper

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

Citations in the corpus

Deep Reinforcement Learning from Self-Play in Imperfect-Information Games (2016, background): “In this domain, current game-theoretic approaches use heuristics of card strength to abstract the game to a tractable size (Johanson et al., 2013).”
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 ”
Solving Imperfect Information Games Using Decomposition (2013, background): “agents in the Annual Computer Poker Competition are optimal strategies for simpler “abstract” poker games, which are smaller and simpler versions of the original problem which ignore some information [9]. The quality of the solution is strongly correlated with the size of the abstraction, so there i”
Time and Space: Why Imperfect Information Games are Hard (2018, background): “We have observed that, as we use finer-grained abstraction and better mapping functions, one on one performance increases and exploitability decreases [46].”
Hierarchical Abstraction, Distributed Equilibrium Computation, and Post-Processing, with Application to a Champion No-Limit Texas Hold'em Agent (2015, methodology): “For our poker agent, we used an abstraction algorithm that had previously been demonstrated to perform well as the Ar’s [18].”
Endgame Solving in Large Imperfect-Information Games (2015, background): “Recent work has also considered an approach where the opponent’s preflop hands are first grouped into several buckets, then hands for the later rounds are grouped together if they perform similarly against each of the preflop buckets [13].”
Deep Counterfactual Regret Minimization (2018, methodology): “In both games, we compare performance to NFSP, which is the previous leading algorithm for imperfect-information game solving using domain-independent function approximation, as well as state-of-the-art abstraction techniques designed for the domain of poker (Johanson et al., 2013; Ganzfried & Sandh”
Self-play Monte-Carlo tree search in computer poker (2014, methodology): “A more sophisticated abstraction technique, e.g. discretisation through clustering or distribution-aware methods (Johanson et al. 2013), should improve the performance in Texas Hold’em.”
Extensive-form game abstraction with bounds (2014, background): “Prior game abstraction algorithms typically proceed level by level in the game tree—possibly moving both up and down—e.g. [Gilpin and Sandholm 2006, 2007a,b; Gilpin et al. 2007, 2008; Zinkevich et al. 2007; Sandholm and Singh 2012; Johanson et al. 2013; Ganzfried and Sandholm 2014].”
Depth-Limited Solving for Imperfect-Information Games (2018, methodology): “On the remaining betting rounds, the hands are grouped into 30,000 buckets [2, 12, 20].”