Finding Optimal Abstract Strategies in Extensive Form Games

Michael Johanson, Nolan Bard, Neil Burch, and Michael Bowling. Finding Optimal Abstract Strategies in Extensive Form Games. In Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI), pp. 1371–1379, 2012.

Download

[PDF] 

Abstract

Extensive-form games are a powerful model for representing interactions between agents. Nash equilibrium strategies are a common solution concept for extensive-form games and, in two-player zero-sum games, there are efficient algorithms for calculating such strategies. In large games, this computation may require too much memory and time to be tractable. A standard approach in such cases is to apply a lossy state-space abstraction technique to produce a smaller abstract game that can be tractably solved, while hoping that the resulting abstract game equilibrium is close to an equilibrium strategy in the unabstracted game. Recent work has shown that this assumption is unreliable, and an arbitrary Nash equilibrium in the abstract game is unlikely to be even near the least suboptimal strategy that can be represented in that space. In this work, we present for the first time an algorithm which efficiently finds optimal abstract strategies --- strategies with minimal exploitability in the unabstracted game. We use this technique to find the least exploitable strategy ever reported for two-player limit Texas hold'em.

BibTeX

@InProceedings(12aaai-cfrbr,
  Title = "Finding Optimal Abstract Strategies in Extensive Form Games",
  Author = "Michael Johanson and Nolan Bard and Neil Burch and Michael Bowling",
  Booktitle = "Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI)",
  Pages = "1371--1379",
  Year = "2012",
  AcceptRate = "26\%",
  AcceptNumbers = "294 of 1129"
)

Generated by bib2html.pl (written by Patrick Riley) on Fri Feb 13, 2015 15:54:27