Double-oracle Algorithm for Computing an Exact Nash Equilibrium in Zero-sum Extensive-form Games
B Bosansky, C Kiekintveld, V Lisy, J Cermak, and M Pechoucek
In Proceedings of the Twelfth International Conference on
Autonomous Agents and Multiagent Systems (AAMAS 2013).
This is the author's version of the work.
Download
Abstract
We investigate an iterative algorithm for computing an exact Nash
equilibrium in two-player zero-sum extensive-form games with imperfect
information. The approach uses the sequence-form representation
of extensive-form games and the double-oracle algorithmic
framework. The main idea is to restrict the game by allowing
the players to play only some of the sequences of available
actions, then iteratively solve this restricted game, and exploit
fast best-response algorithms to add additional sequences to
the restricted game for the next iteration. In this paper we (1) extend
the sequence-form double-oracle method to be applicable on
non-deterministic extensive-form games, (2) present more ecient
methods for maintaining valid restricted game and computing bestresponse
sequences, and finally we (3) provide theoretical guarantees
of the convergence of the algorithm to a Nash equilibrium.
We experimentally evaluate our algorithm on two types of games:
a search game on a graph and simplified variants of Poker. The results
show significant running-time improvements compared to the
previous variant of the double-oracle algorithm, and demonstrate
the ability to find an exact solution of much larger games compared
to solving full linear program for the complete game.
