Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/14023
Title: | Computing Winning Strategies for Poset Games |
Authors: | Wilson, Craig |
Advisor: | Soltys, Michael |
Department: | Computing and Software |
Keywords: | Computing and Software |
Publication Date: | 31-Mar-2008 |
Abstract: | <p>The problem of computing winning strategies in games has yielded many important results with applications in fields such as computer science, economics, and mathematics. For example, "Online" games, where the input is received on the fly are used to model process scheduling and paging algorithms. The concept of Nash Equilibrium has implications in economic theory, and Ehrenfeuct-Frass games are used to check whether two structures are isomorphic.</p> <p>In this thesis we are concerned with Partially-Ordered Set (Poset) games. We present two new methods for proving that computing winning strategies for the game of Chomp is in PSPACE. \Ne also present the idea of "Game Completeness", and give an overview of efforts to translate any poset game into an equivalent configuration of Chomp. Finally, we show how Skelley's bounded arithmetic theory W<sup>1</sup><sub>1</sub> can be applied to Chomp, and the consequences of expressing the existence of a winning strategy for the first player in Chomp in simpler arithmetic theories. In short, the contributions of this thesis are as follows:</p> <p>1. A new method for showing poset games in PSPACE, via a polynomial-time (logarithmic-space) reduction to the game of Geography.</p> <p>2. Attempts at a reduction from Geography to poset games, and implications to whether poset games are PSPACE-complete.</p> <p>3. A bounded-arithmetic formulation of the existence of a winning strategy for the first player in Chomp.</p> <p>4. A definition of the concept of Game Completeness, and a translation from treelike poset games to a modified version of Chomp.</p> |
URI: | http://hdl.handle.net/11375/14023 |
Identifier: | opendissertations/8853 9934 5352488 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
fulltext.pdf | 2.56 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.