---
title: "Accelerating Best Response Calculation in Large Extensive Games"
authors:
  - "Michael Johanson"
  - "Kevin Waugh"
  - "Michael H. Bowling"
  - "Martin Zinkevich"
doi: "10.5591/978-1-57735-516-8/IJCAI11-054"
url: "https://ijcai.org/proceedings/2011/54"
pdf: "https://ijcai.org/proceedings/2011/0054.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "258-264"
track: ""
keywords:
---

# Accelerating Best Response Calculation in Large Extensive Games

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

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 258-264. DOI: [10.5591/978-1-57735-516-8/IJCAI11-054](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.