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.
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.
@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" )