Robust Strategies and Counter-Strategies: From Superhuman to Optimal Play Open Access
- Other title
- Type of item
- 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 of Computing Science
- Date accepted
- Graduation date
Doctor of Philosophy
- Degree level
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.
- 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.
- Date Uploaded
- Date Modified
- Audit Status
- Audits have not yet been run on this file.
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 1972550
Last modified: 2016:06:16 17:02:27-06:00
Original checksum: d05756ee092f3b7862bd265ab942c673
Activity of users you follow