Accelerating Best Response Calculation in Large Extensive Games

Michael Johanson, Michael Bowling, Kevin Waugh, and Martin Zinkevich. Accelerating Best Response Calculation in Large Extensive Games. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI), pp. 258–265, 2011.

Download

[PDF] 

Abstract

One fundamental evaluation criteria of an AI technique is its performance in the worst-case. For static strategies in extensive games, this can be computed using a best response computation. Conventionally, this requires a full game tree traversal. For very large games, such as poker, that traversal is infeasible to perform on modern hardware. In this paper, we detail a general technique for best response computations that can often avoid a full game tree traversal. Additionally, our method is specifically well-suited for parallel environments. We apply this approach to computing the worst-case performance of a number of strategies in heads-up limit Texas hold'em, which, prior to this work, was not possible. We explore these results thoroughly as they provide insight into the effects of abstraction on worst-case performance in large imperfect information games. This is a topic that has received much attention, but could not previously be examined outside of toy domains.

BibTeX

@InProceedings(11ijcai-rgbr,
  Title = "Accelerating Best Response Calculation in Large Extensive Games",
  Author = "Michael Johanson and Michael Bowling and Kevin Waugh and Martin Zinkevich",
  Booktitle = "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI)",
  Year = "2011",
  Pages = "258--265",
  AcceptRate = "30\%",
  AcceptNumbers = "400 of 1325"
)

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