Coping with cycles
Published online by Cambridge University Press: 28 February 2011
Summary
Abstract. Loopy games are combinatorial games in which repetition is permitted. The possibility of nonterminating play inevitably raises difficulties, and several theories have addressed these by imposing a variety of assumptions on the games under consideration. In this article we survey some significant results on partizan loopy games, focusing on the theory developed in the 1970s by Conway, Bach and Norton.
Introduction
A substantial portion of combinatorial games research focuses on games without repetition – those that are guaranteed to terminate after some finite number of moves. Such games are highly tractable, both theoretically and computationally, and the full force of the classical partizan theory can be brought to bear upon them. The great success of this theory has produced a vast body of splendid results, but it has also resulted in an unjust neglect of games with repetition.
In the late 1970s, John Conway and his students, Clive Bach and Simon Norton, introduced a disjunctive theory of partizan games with repetition – called loopy games because their game graphs may contain cycles. They showed that in many interesting cases, such games admit canonical forms. The past few years have witnessed some significant applications of this theory, to games as diverse as Fox and Geese, Hare and Hounds, Entrepreneurial Chess, and one-dimensional Phutball. In light of these advances, it is time for a reappraisal of the theory with an eye to the future.
- Type
- Chapter
- Information
- Games of No Chance 3 , pp. 91 - 124Publisher: Cambridge University PressPrint publication year: 2009