Not Logged In

PapersDB

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

• Martin Zinkevich
• Michael Bowling, University of Alberta
• Neil Burch, Department of Computing Science, University of Alberta

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

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

• Home
• Search
  • Advanced Search
• Publications
  • View Publication Entries
• Authors
  • View Authors
• User
  • Login or Register