Evaluating State-Space Abstractions in Extensive-Form Games

Michael Johanson, Neil Burch, Richard Valenzano, and Michael Bowling. Evaluating State-Space Abstractions in Extensive-Form Games. In Proceedings of the Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2013.



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 the derivation of a smaller, strategically similar and tractable abstract domain, and an optimal abstract strategy can be 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.


In this paper, we pursue two goals. First, we consider the standard methods of evaluating abstraction techniques in large games such as poker, and find them wanting. Abstractions are difficult to evaluate directly, and so the conventional approach is to use an abstraction to produce an abstract strategy, and evaluate it instead. However, both best response analysis and one-on-one performance of such strategies might be misleading, due to pathologies and the overfitting effect (as described in the RGBR paper), and possible intransitivities or ties in actual games against other similarly strong opponents. Instead, we use the recent CFR-BR technique to directly find the strategy in an abstraction that is as close as possible to an unabstracted Nash equilibrium. As proposed in the CFR-BR paper, this gives us a meaningful metric that more directly measures a property of an abstraction (its ability to represent a Nash equilibrium) than of a particular strategy in that abstraction. We then use this technique to evaluate a set of abstraction techniques, and in particular, investigate strength-based and potential-aware abstractions, reproducing an earlier experiment by Gilpin and Sandholm, and perfect recall and imperfect recall abstractions, as previously investigated by Waugh et al.

Second, in this paper, we unveil much of the the card abstraction technique used by the limit, 3-player, and no-limit Hyperborean agents since 2010. This abstraction technique is based on k-Means clustering and used two new features and distance metrics: hand strength distributions and earth mover's distance, for capturing more elements of a hand's potential than could be represented with earlier expected hand strength based techniques, and Opponent Cluster Hand Strength (OCHS) features, for capturing information about the public cards. We show that the combination of these features, along with an imperfect recall abstraction, produces stronger poker agents than equivalently sized abstract strategies created through other techniques. These new agents are stronger in terms of both one-on-one performance and worst-case exploitability.



@InProceedings{ 2013aamas-kmeans-abstraction,
  Title = "Evaluating State-Space Abstractions in Extensive-Form Games",
  Author = "Michael Johanson and Neil Burch and Richard Valenzano and Michael Bowling",
  Booktitle = "Proceedings of the Twelfth International Conference on Autonomous 
               Agents and Multi-Agent Systems (AAMAS)",
  Year = "2013"