PhD Thesis
Robust Strategies and Counter Strategies: From Superhuman to Optimal Play


Michael Bradley Johanson. Robust Strategies and Counter-Strategies: From Superhuman to Optimal Play. PhD thesis, University of Alberta, Department of Computing Science. January 2016.

Download

  • Paper: [PDF]
    • Paper-based format, spanning 7 core publications from my PhD.
    • Covers the arc from our 2008 victory over human poker pros in heads-up limit Texas hold'em, to essentially solving the game in 2015.
    • Includes a thorough analysis of the 2007 and 2008 Man-vs-Machine poker matches, showing that Polaris earned its 2008 victory.
  • Presentation: [PDF]
    • Given as a Grad Seminar: an hour long high level talk, spanning my research.
    • This talk focuses on our 10-year effort to solve heads-up limit Texas hold'em.

Abstract

Games have been used as a testbed for artificial intelligence research since the earliest conceptions of computing itself. The twin goals of defeating human professional players at games, and of solving games outright by creating an optimal computer agent, have helped to drive practical research in this field. Deep Blue defeating Kasparov at chess and Chinook solving the game of checkers serve as milestone events in the popular understanding of artificial intelligence. However, imperfect information games present new challenges and require new research. The Abstraction-Solving-Translation procedure for approaching such games involves abstracting a game down to a tractable size, solving the abstract game to produce a strong abstract strategy, and translating its decisions into the real game as needed. Related challenges include principled evaluation of the resulting computer agents, and using opponent models to improve in-game performance against imperfect adversaries. The papers presented in this thesis encompass the complete end-to-end task of creating strong agents for extremely large games by using the Abstraction-Solving-Translation procedure, and we present a body of research that has made contributions to each step of this task. We use the game of poker as a testbed domain to validate our research, and present two milestone accomplishments reached as a result: the first victory of a computer agent over human professionals in a meaningful poker match, and the first solution to any imperfect information game played competitively by humans.



BibTeX


% Michael Johanson's PhD thesis, 2016
% End-to-End description of creating computer agents for large
% imperfect information games.  Details on Hyperborean 2008-2014,
% and essentially solving heads-up limit Texas hold'em.
@phdthesis{2016-johanson-phd-thesis,
author = {Michael Bradley Johanson},
title = {Robust Strategies and Counter-Strategies: From Superhuman to Optimal Play},
school = {University of Alberta},
year = {2016},
note = {\url{http://johanson.ca/publications/theses/2016-johanson-phd-thesis/2016-johanson-phd-thesis.pdf}}
}