Not Logged In

A New Algorithm for Generating Equilibria in Massive Zero-Sum Games

In normal scenarios, computer scientists often consider the number of states in a game to capture the difficulty of learning an equilibrium. However, players do not see games in the same light: most consider Go or Chess to be more complex than Monopoly. In this paper, we discuss a new measure of game complexity that links existing state-of-the-art algorithms for computing approximate equilibria to a more human measure. In particular, we consider the range of skill in a game, i.e. how many different skill levels exist. We then modify existing techniques to design a new algorithm to compute approximate equilibria whose performance can be captured by this new measure. We use it to develop the first near Nash equilibrium for a four round abstraction of poker, and show that it would have been able to win handily the bankroll competition from last year's AAAI poker competition.

Citation

M. Zinkevich, M. Bowling, N. Burch. "A New Algorithm for Generating Equilibria in Massive Zero-Sum Games". National Conference on Artificial Intelligence (AAAI), July 2007.

Keywords: 1.8 Game Playing, 7.1 Multi-Agent Systems, machine learning
Category: In Conference

BibTeX

@incollection{Zinkevich+al:AAAI07,
  author = {Martin Zinkevich and Michael Bowling and Neil Burch},
  title = {A New Algorithm for Generating Equilibria in Massive Zero-Sum Games},
  booktitle = {National Conference on Artificial Intelligence (AAAI)},
  year = 2007,
}

Last Updated: February 01, 2008
Submitted by Nelson Loyola

University of Alberta Logo AICML Logo