Paper Info
Title
Accelerating best response calculation in large extensive games
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.
Year
DOI
Venue
2011
10.5591/978-1-57735-516-8/IJCAI11-054
IJCAI
Keywords
Field
DocType
extensive game,general technique,large extensive game,texas hold,best response computation,best response calculation,large game,worst-case performance,fundamental evaluation criterion,ai technique,full game tree traversal,large imperfect information game
Tree traversal,Abstraction,Computer science,Best response,Theoretical computer science,Artificial intelligence,Perfect information,Game tree,Machine learning,Computation
Conference
Citations 
PageRank 
References 
34
1.55
5
Authors
4
Name
Order
Citations
PageRank
Michael Johanson136725.69
Kevin Waugh221715.18
Michael H. Bowling32460205.07
Martin Zinkevich41893160.99