2011/07/25 by Will Johnson, Johnson, Will · 1 citation
Computer Science · Mathematics · #Artificial Intelligence in Games #cs.GT #math.CO #msc:91A46
paper · pdf · doi:10.48550/arxiv.1107.5092
too many pages, undergrad honors senior thesis for the University of Washington, preliminary version
arxiv created 2011/07/25 · arxiv updated 2011/07/27
We begin by reviewing and proving the basic facts of combinatorial game theory. We then consider scoring games (also known as Milnor games or positional games), focusing on the "fixed-length" games for which all sequences of play terminate after the same number of moves. The theory of fixed-length scoring games is shown to have properties similar to the theory of loopy combinatorial games, with operations similar to onsides and offsides. We give a complete description of the structure of fixed-length scoring games in terms of the class of short partizan games. We also consider fixed-length scoring games taking values in the two-element boolean algebra, and classify these games up to indistinguishability. We then apply these results to analyze some positions in the knotting-unknotting game of Pechenik, Townsend, Henrich, MacNaughton, and Silversmith.