Survey of results in impartial combinatorial games and an extension to three-player game
Master of Arts
There are several known methods to find winning strategies for two-player combinatorial games. This thesis surveys results known for two-player combinatorial games and elucidates a particular winning strategy for a three player game using graph theory. The motivation for work in this area is a belief on the ability of graph theoretic tools to handle multi-player combinatorial game analyses. A winning strategy for two-player undirected vertex Geography game has been formulated earlier and has been shown to be polynomial time. This thesis extends the result to three-player undirected vertex Geography, played on directed trees and answers the question "Does the first player have a winning strategy?". The extension serves as a platform for generalizing results to games involving more than three players.