The Computational Complexity of Some Games and Puzzles With Theoretical Applications

<p>The subject of this thesis is the algorithmic properties of one- and two-player </p> <p>games people enjoy playing, such as Sudoku or Chess. Questions asked about puzzles </p> <p>and games in this context are of the following type: can we design efficient computer </p> <p>programs that play optimally given any opponent (for a two-player game), or solve </p> <p>any instance of the puzzle in question? </p> <p>We examine four games and puzzles and show algorithmic as well as intractability </p> <p>results. First, we study the wolf-goat-cabbage puzzle, where a man wants to transport </p> <p>a wolf, a goat, and a cabbage across a river by using a boat that can carry only one </p> <p>item at a time, making sure that no incompatible items are left alone together. We </p> <p>study generalizations of this puzzle, showing a close connection with the Vertex </p> <p>Cover problem that implies NP-hardness as well as inapproximability results. </p> <p>Second, we study the SET game, a card game where the objective is to form </p> <p>sets of cards that match in a certain sense using cards from a special deck. We </p> <p>study single- and multi-round variations of this game and establish interesting con- </p> <p>nections with other classical computational problems, such as Perfect Multi- </p> <p>Dimensional Matching, Set Packing, Independent Edge Dominating Set, </p> <p>and Arc Kayles. We prove algorithmic and hardness results in the classical and </p> <p>the parameterized sense. </p> <p>Third, we study the UNO game, a game of colored numbered cards where players </p> <p>take turns discarding cards that match either in color or in number. We extend results </p> <p>by Demaine et. al. (2010 and 2014) that connected one- and two-player generaliza- </p> <p>tions of the game to Edge Hamiltonian Path and Generalized Geography, </p> <p>proving that a solitaire version parameterized by the number of colors is fixed param- </p> <p>eter tractable and that a k-player generalization for k greater or equal to 3 is PSPACE-hard. </p> <p>Finally, we study the Scrabble game, a word game where players are trying to </p> <p>form words in a crossword fashion by placing letter tiles on a grid board. We prove </p> <p>that a generalized version of Scrabble is PSPACE-hard, answering a question posed </p> <p>by Demaine and Hearn in 2008. </p>

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor

The Graduate School and University Center of The City University of New York

Year dc:date.available

2014

Author dc:creator

• Mitsou, Vasiliki Despoina

Advisor dc:contributor.advisor

• Amotz Bar-Noy

• Computer Sciences
• Algorithms
• Combinatorial Game Theory
• Computational Complexity
• Graph Theory

Repository record dc:identifier

https://academicworks.cuny.edu/gc_etds/326

OAI identifier oai:identifier

oai:academicworks.cuny.edu:gc_etds-1325