An Exact Double-Oracle Algorithm for Zero-Sum
Extensive-Form Games with Imperfect Information
B Bosansky, C Kiekintveld, Viliam Lisy, and M Pechoucek
In Journal of Artificial Intelligence Research. 2014.
This is the author's version of the work.
Download
Abstract
Developing scalable solution algorithms is one of the central problems in computational
game theory. We present an iterative algorithm for computing an exact Nash equilibrium
for two-player zero-sum extensive-form games with imperfect information. Our approach
combines two key elements: (1) the compact sequence-form representation of extensiveform
games and (2) the algorithmic framework of double-oracle methods. The main idea of
our algorithm is to restrict the game by allowing the players to play only selected sequences
of available actions. After solving the restricted game, new sequences are added by finding
best responses to the current solution using fast algorithms.
We experimentally evaluate our algorithm on a set of games inspired by patrolling
scenarios, board, and card games. The results show significant runtime improvements in
games admitting an equilibrium with small support, and substantial improvement in memory
use even on games with large support. The improvement in memory use is particularly
important because it allows our algorithm to solve much larger game instances than existing
linear programming methods.
Our main contributions include (1) a generic sequence-form double-oracle algorithm for
solving zero-sum extensive-form games; (2) fast methods for maintaining a valid restricted
game model when adding new sequences; (3) a search algorithm and pruning methods for
computing best-response sequences; (4) theoretical guarantees about the convergence of
the algorithm to a Nash equilibrium; (5) experimental analysis of our algorithm on several
games, including an approximate version of the algorithm.
