The representation of combinatorial games and the algorithms used to play them.
Item
-
Title
-
The representation of combinatorial games and the algorithms used to play them.
-
Identifier
-
AAI9605616
-
identifier
-
9605616
-
Creator
-
Leff, Arthur Allan.
-
Contributor
-
Adviser: Michael Anshel
-
Date
-
1995
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
This dissertation is the results of a study of Wythoff's game based on the premise that different representations of the game would lead to new algorithms and new games. Representing the game as a queen on a three-dimensional chessboard led to a new algorithm for finding the P-positions and a new algorithm for finding the Grundy values of positions in the three-heap game. Representation of the game by string rewriting systems led to the development of a schema, Literary Wythoff, which, for n {dollar}\geq{dollar} 2 stones, includes Wythoff's game under both the Normal and Misere Ending Conditions. The results include four new variations of Wythoff's game, all of which were analyzed; and, four string rewriting games, one of which was analyzed. Also found in this dissertation is a chesspiece, Latin Rook, the Grundy values for which generate latin squares of size 2{dollar}\rm\sp{lcub}n{rcub},{dollar} n {dollar}\in{dollar} Z{dollar}\sp+;{dollar} and, a new variation of Nim, Antenim, in which coins are added to n {dollar}\geq{dollar} 2 bowls. To move, a player adds one or more coins to any one of the bowls until a specified multiset of values is reached.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
