MSc Thesis:
Robust Strategies and Counter-Strategies: Building a Champion Level Computer Poker Player


Michael Johanson. Robust Strategies and Counter-Strategies: Building a Champion Level Computer Poker Player. Masters thesis, University of Alberta, Department of Computing Science. October 2007.

Download

  • Thesis: [PDF]
    • One of three finalists for the Department of Computing Science's Best MSc Thesis award
  • Presentation: [PDF]
    • Presented as a Grad Seminar: a summary of my degree, given to a general CS audience.
    • Designed to fill one hour, but with questions and more depth, can fill 1.5 or 2.

Abstract

Poker is a challenging game with strong human and computer players. In this thesis, we will explore four approaches towards creating a computer program capable of challenging these poker experts. The first approach is to approximate a Nash equilibrium strategy which is robust against any opponent. The second approach is to find an exploitive counter-strategy to an opponent. We will show that these counter-strategies are brittle: they can lose to arbitrary other opponents. The third approach is a compromise of the first two, to find robust counter-strategies. The fourth approach is to combine several of these agents into a team, and learn during a game which to use. As proof of the value of these techniques, we have used the resulting poker programs to win an event in the 2007 AAAI Computer Poker Competition and play competitively against two human poker professionals in the First Man-Machine Poker Championship.


Notes

My Masters thesis is a good end-to-end summary of the work that went into making Hyperborean 2007 and Polaris 2007. It describes the background problems that I didn't work on, like state-space abstraction and evaluation, and then summarizes the two NIPS papers on CFR and Restricted Nash Response. The last chapter talks about the 2007 Annual Computer Poker Competition and First Man-vs-Machine matches. If you're looking for a starting point where you can see the big picture, try this one.


Links


BibTeX

% Michael Johanson's MSc thesis, 2007
% End-to-End description of Hyperborean2007 and Polaris2007,
% including CFR, Restricted Nash Response, and using UCB to switch between strategies.
% Also describes early abstraction techniques (E[HS^2], nested abstractions)
% Includes First Man-vs-Machine match analysis and description of the agents used.
@mastersthesis{2007-johanson-msc,
 author={Michael Johanson},
 title={Robust Strategies and Counter-Strategies: 
        Building a Champion Level Computer Poker Player},
 school={University of Alberta},
 year={2007},
}