Iterative Algorithm for Solving Two-player Zero-sum Extensive-form Games with Imperfect Information
B Bosansky, C Kiekintveld, V Lisy, and M Pechoucek
In 20th European Conference on Artificial Intelligence (ECAI 2012).
This is the author's version of the work.
Download
Abstract
We develop and evaluate a new exact algorithm for finding
Nash equilibria of two-player zero-sum extensive-form games
with imperfect information. Our approach is based on the sequenceform
representation of the game, and uses an algorithmic framework
of double-oracle methods that have been used successfully in other
classes of games. The algorithm uses an iterative decomposition,
solving restricted games and exploiting fast best-response algorithms
to add additional sequences to the game over time. We demonstrate
our algorithm on a class of adversarial graph search games motivated
by real world border patrolling scenarios. The results indicate that
our framework is a promising way to scale up solutions for extensiveform
games, reducing both memory and computation time requirements.
