ERA

Download the full-sized PDF of Abstraction in Large Extensive GamesDownload the full-sized PDF

Analytics

Share

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

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

Abstraction in Large Extensive Games Open Access

Descriptions

Other title
Subject/Keyword
Extensive Form Games
Nash Equilibrium
Abstraction
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Waugh, Kevin
Supervisor and department
Bowling, Michael (Computing Science)
Schuurmans, Dale (Computing Science)
Examining committee member and department
Sturtevant, Nathan (Computing Science)
Hooper, Peter (Mathematics and Statistics)
Department
Department of Computing Science
Specialization

Date accepted
2009-09-11T14:40:22Z
Graduation date
2009-11
Degree
Master of Science
Degree level
Master's
Abstract
For zero-sum games, we have efficient solution techniques. Unfortunately, there are interesting games that are too large to solve. Here, a popular approach is to solve an abstract game that models the original game. We assume that more accurate the abstract games result in stronger strategies. There is substantial evidence to support this assumption. We begin by formalizing abstraction and refinement, a notion of expressive power for abstractions. We then show the assumption fails to hold under two criteria. The first is exploitability, which measures performance in the worst-case. The second is called the domination value, which measures how many mistakes a strategy makes. Despite these pathologies, we notice that larger strategies tend to make fewer mistakes and perform better in tournaments. Finally, we introduce strategy grafting, a technique that uses sub-game decomposition, which allow us to create good strategies in much larger spaces than previously possible.
Language
English
DOI
doi:10.7939/R3CM74
Rights
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication

File Details

Date Uploaded
Date Modified
2014-05-01T17:32:48.316+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 694280
Last modified: 2015:10:12 14:37:39-06:00
Filename: Waugh_Kevin_Fall_2009.pdf
Original checksum: f1cfbb467874945b9db325709b3bb5ee
Well formed: false
Valid: false
Status message: Lexical error offset=684504
Page count: 63
Activity of users you follow
User Activity Date