New results in Loopy games
Aaron N. Siegel · 2009
A bstract . We strengthen the usual notion of simplest form for stoppers and show that under the stronger definition, equivalence coincides with graphisomorphism. We then show that the game graph of a canonical stopper contains no 2- or 3-cycles, but may contain n -cycles for all n ≥ 4. We also introduce several new methods for simplifying games γ whose graphs contain alternating cycles. These include a generalization of dominated and reversible moves. Introduction A loopy game is a combinatorial game in which repetition is permitted. The history and basic theory of loopy games are discussed in [Siegel 2009]. In this article we focus on two fundamental problems left unresolved by Winning Ways . Long irreducible cycles . The first problem concerns the cycles that appear in the game graph of a stopper. Conway showed that every stopper s admits a simplest form [Conway 1978], so one would expect that certain cycles are intrinsic to the play of s . All canonical stoppers discussed in Winning Ways are plumtrees : their graphs contain only 1-cycles. It is therefore natural to ask whether longer canonical cycles are possible, and to attempt to characterize the structure of such cycles. Conway defined the simplest form of s to be a representation with no dominated or reversible moves. This is not quite strong enough for our purposes, as illustrated by the example t shown in Figure 1. Certainly t has no dominated or reversible options, but it is easy to check that t = on .