CMU-CS-09-127Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-09-127
Andrew Gilpin May 2009 Ph.D. Thesis
Keywords: Computational game theory, artificial intelligence,
equilibrium computation, automated abstraction, nonsmooth convex optimization,
sequential games, repeated games, imperfect information, poker AI
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
In a second stream of research, we develop 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. 208 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |