Survey of results in impartial combinatorial games and an extension to three-player game

[摘要] 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.

[发布机构] Rice University

[效力级别] Statistics