Accelerating Best Response Calculation in Large Extensive Games

Johanson, Michael; Waugh, Kevin; Bowling, Michael H.; Zinkevich, Martin

doi:10.5591/978-1-57735-516-8/IJCAI11-054

Accelerating Best Response Calculation in Large Extensive Games

Michael Johanson, Kevin Waugh, Michael H. Bowling, Martin Zinkevich

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 258-264.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-054

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.

Michael Johanson, Kevin Waugh, Michael H. Bowling, and Martin Zinkevich. 2011. Accelerating Best Response Calculation in Large Extensive Games. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 258–264. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-054

@inproceedings{ijcai2011p54,
  title     = {Accelerating Best Response Calculation in Large Extensive Games},
  author    = {Johanson, Michael and Waugh, Kevin and Bowling, Michael H. and Zinkevich, Martin},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {258--264},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-054},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-054},
}

TY  - CPAPER
TI  - Accelerating Best Response Calculation in Large Extensive Games
AU  - Johanson, Michael
AU  - Waugh, Kevin
AU  - Bowling, Michael H.
AU  - Zinkevich, Martin
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 258
EP  - 264
DO  - 10.5591/978-1-57735-516-8/IJCAI11-054
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-054
ER  -