Game of cycles on trees reveals hidden nim heap strategy flaws
Nim heaps in the Game of Cycles: the parity conjecture fails on trees
Discrete Mathematics
Summary
The Game of Cycles is a two-player game played on graphs where players draw arrows without creating certain patterns. Many thought that on tree-shaped graphs, the second player would win if the number of valid edges was even. The authors show this idea is wrong because parts of the tree act like a Nim game, a well-known strategy game, making the outcome more complex. They describe when the original idea fails, how to calculate outcomes for various trees, and identify structures where the old rule holds or breaks.
What this means in practice
- •For game designers: Design new strategy games that incorporate complex Nim-like interactions on tree graphs for richer gameplay.
- •For algorithm developers: Develop algorithms for analyzing combinatorial games on graphs by modeling substructures as Nim heaps to predict game outcomes efficiently.
A theory result. No direct application yet.
Authors
Muchen Xu
Abstract
The Game of Cycles, invented by Francis Su, is a two-player game in which the players take turns drawing arrows on the edges of a plane graph, never creating a sink or a source. On a tree only the sink-source rule matters, and the player who makes the last move wins. Several authors conjectured that on a tree the second player wins exactly when the number of markable edges is even. We show that this parity conjecture is false, and we explain why. The explanation is a hidden game of Nim: a path segment that is blocked by an arrow at one end and free at the other behaves exactly like a nim heap whose size is its length. Combined with a calculus for cutting and gluing trees at vertices next to leaves, this shows that the conjecture fails as soon as a single tree has Grundy value at least 2. The smallest counterexamples have 15 vertices. Trees with Grundy values 2 and 4 first appear at 17 vertices, and every value up to 63 occurs, which answers a question of Fokkink and Zandee. We also refute a related conjecture of Zandee. We then look closely at spiders. The spiders S(2,3,z) violate the conjecture for every z >= 14. The Grundy values of S(1,2j,z) are given by an exact formula governed by binary carries. For 99 pairs (x,y), the value of S(x,y,z) is eventually the parity of z. On the positive side, the conjecture holds for all trees in which every thread has at most two edges, and this bound is sharp. Along the way we prove a twin-branch reduction, give an algorithm that is polynomial for spiders with a fixed number of legs, and collect the questions that we could not answer. The boldest asks whether every non-negative integer is the Grundy value of some tree.