Andrew Gilpin

Algorithms for Abstracting and Solving Imperfect Information Games Degree Type: Ph.D. in Computer Science
Advisor(s): Tuomas Sandholm
Graduated: May 2009

Abstract:

Game theory is the mathematical study of rational behavior in strategic environments. In many settings, most notably two-person zero-sum games, game theory provides particularly strong and appealing solution concepts. Furthermore, these solutions are efficiently computable in the complexity-theory sense. However, in most interesting potential applications in artificial intelligence, the solutions are difficult to compute using current techniques due primarily to the extremely large state-spaces of the environments.

In this thesis, we propose new algorithms for tackling these computational difficulties. In one stream of research, we introduce automated abstraction algorithms for sequential games of imperfect information. These algorithms take as input a description of a game and produce a description of a strategically similar, but smaller, game as output. We present algorithms that are lossless (i.e., equilibrium-preserving), as well as algorithms that are lossy, but which can yield much smaller games while still retaining the most important features of the original game.

In a second stream of research, we develop specialized optimization algorithms for finding ε-equilibria in sequential games of imperfect information. The algorithms are based on recent advances in non-smooth convex optimization and provide significant improvements over previous algorithms for finding ε-equilibria.

Combining these two streams, we enable the application of game theory to games much larger than was previously possible. As an illustrative example, we find near-optimal solutions for four-round models of limit and no-limit Texas Hold’em poker, and report that the resulting players won the most chips overall at the 2008 AAAI Computer Poker Competition.

Thesis Committee:
Tuomas Sandholm (Chair)
Avrim Blum
Geoff Gordon
Javier Peña
Bernhard von Stengel (London School of Economics)

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Computational game theory, artificial intelligence, equilibrium computation, automated abstraction, nonsmooth convex optimization, sequential games, repeated games, imperfect information, poker AI