ERA

Download the full-sized PDF of Robust Strategies and Counter-Strategies: From Superhuman to Optimal PlayDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R37W67H0W

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Robust Strategies and Counter-Strategies: From Superhuman to Optimal Play Open Access

Descriptions

Other title
Subject/Keyword
Game Theory
Computer Poker
Artificial Intelligence
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Johanson, Michael Bradley
Supervisor and department
Bowling, Michael (Computing Science)
Examining committee member and department
Schaeffer, Jonathan (Computing Science)
Schuurmans, Dale (Computing Science)
Littman, Michael (Computer Science, Brown University)
Carbonaro, Michael (Educational Psychology)
Department
Department of Computing Science
Specialization

Date accepted
2016-03-01T14:58:37Z
Graduation date
2016-06
Degree
Doctor of Philosophy
Degree level
Doctoral
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.
Language
English
DOI
doi:10.7939/R37W67H0W
Rights
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
Citation for previous publication
Michael Johanson, Kevin Waugh, Michael Bowling, and Martin Zinkevich. Accelerating best response calculation in large extensive games. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI-11), pages 258–265, 2011.Michael Johanson, Nolan Bard, Marc Lanctot, Richard Gibson, and Michael Bowling. Efficient Nash equilibrium approximation through Monte Carlo counterfactual regret minimization. In Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS- 12), pages 837 – 844, 2012.Michael Johanson, Nolan Bard, Neil Burch, and Michael Bowling. Finding optimal abstract strategies in extensive-form games. In Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI-12), 2012.Michael Johanson, Neil Burch, Richard Valenzano, and Michael Bowling. Evaluating state-space abstractions in extensive-form games. In Proceedings of the Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-13), 2013.Michael Johanson and Michael Bowling. Data biased robust counter strategies. In Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS-09), 2009.Michael Bowling, Michael Johanson, Neil Burch, and Duane Szafron. Strategy evaluation in extensive games with importance sampling. In Proceedings of the 25th Annual International Conference on Machine Learning (ICML-08), 2008.Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold’em poker is solved. Science, 347(6218):145– 149, January 2015.

File Details

Date Uploaded
Date Modified
2016-03-01T22:20:57.756+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 1972550
Last modified: 2016:06:16 17:02:27-06:00
Filename: Johanson_Michael_B_201601_PhD.pdf
Original checksum: d05756ee092f3b7862bd265ab942c673
Activity of users you follow
User Activity Date