A game decided before it starts

On a February afternoon in 1967, in the Cambridge mathematics department, John Conway and Michael Paterson invented a pencil game while trying to modify another game. It takes a pencil, a sheet of paper and a few dots. Conway reported that the next day the whole department seemed to be playing it, with people drawing strange diagrams on anything to hand. Martin Gardner wrote it up that July, and it has been a favourite ever since. Its appeal is that nothing about it looks like a mathematical structure, and yet the structure is exactly the one that makes every corner pay for itself on a polyhedron.

The rules of Sprouts take one sentence each. Start with $n$ spots. A move draws a curve between two spots, or from a spot back to itself, and adds a new spot on that curve. No curve may cross a curve or pass through a spot. No spot may have more than three curves coming out of it. The player who cannot move loses.

Conway also gave a variant which he called Brussels sprouts, offering it as a joke on the rules. Start with $n$ crosses, each having four free arms. A move draws a curve joining two free arms and places a new cross on it, which has the two free arms it did not use, one on each side of the curve. It looks like a richer game. It is in fact no game at all.

Why Sprouts must end #

Call the number of curves a spot can still take its lives. At the start each spot has three. A move uses two lives, one at each end of the curve, and adds a new spot with one life left, since it has two curves through it already. So each move decreases the total number of lives by exactly one. There are $3n$ to begin with, and so no game can last longer than $3n$ moves. It cannot even last that long. A move needs two lives, and one life alone cannot be used, so at most $3n - 1$ moves can occur.

There is a lower bound too, with a charming proof. When the game ends, there are some survivors: spots that still have a life. Each survivor had its neighbours used up, and it takes a small argument to see that each survivor has two spots to itself, of a kind called pharisees, each adjacent to it and to no other survivor. That ends up meaning a game must last at least $2n$ moves. So a game on $n$ spots lasts between $2n$ and $3n - 1$ moves, and the number of moves determines who wins.

The exact ranges here have been found by searching through every game. For one spot, every game lasts two moves. For two spots, between 4 and 5. For three, between 6 and 8. All of these match the limits exactly. Under random play, sampled out to twenty spots, the game lengths lie well inside these limits, about 2.45 moves per spot, with a modest spread. For twenty spots the range sampled runs from 47 to 51, within a theoretical range of 40 to 59. So a game’s length can vary, but only over a narrow band, and because the winner is just the parity of that length, the entire contest is over one bit, decided by who can steer it.

The figure’s histogram for eight spots has most games at 19 or 20 moves. Under random play, the first player wins 162 of 300, close to one half, and almost nothing in the shape of the histogram gives a hint of who actually wins under correct play. Theory says the second player does, at eight spots. Between good players, the game largely comes down to a fight over the small enclosed regions, each player trying to fix the number of remaining moves. A region with one live spot in it has a definite number of moves left, and so a player can make the parity favourable by sealing off regions of the right size.

Topology in place of geometry #

How can a game like that be analysed by computer at all, since curves can be drawn in infinitely many ways? The insight is that the exact shape of the curves does not matter. All that matters is which regions there are, which spots lie on the boundary of each, and how many lives each has. So a position is a list of regions, each with a list of boundary components, each of which is a cyclic list of spots.

A move is an operation on that structure. If the curve joins two spots on different boundaries of the same region, it merges the two boundaries into one, and the number of regions stays the same. If it joins two spots on the same boundary, it splits the region in two; and any other boundary components in that region must be assigned to one side or the other, which is a choice. A surprising amount of a game’s complexity is in this choice, since it can be made in $2^m$ ways.

The exhaustive search here covers one to five spots, with a table that stores each position up to a simple renaming. The results: second player, second, first, first, first. That took about ten seconds, on a table of 127,741 positions. David Applegate, Guy Jacobson and Daniel Sleator carried out a far more refined search in 1991, up to eleven spots, by separating positions into independent regions and using the Sprague–Grundy theory of sums of games. They noticed something remarkable. The first player wins exactly when $n$ leaves a remainder of 3, 4 or 5 modulo 6. Their results suggested a conjecture with no known reason behind it.

Julien Lemoine and Simon Viennot pushed this up to 44 spots and beyond, in the late 2000s, with a method that does not solve positions completely but only finds a proof-number strategy tree for a winner. All values agree with the pattern so far. There is no proof. The conjecture is a striking one, because it is a claim about a game with a rich and irregular structure, in which each outcome appears to need an enormous search. A period of six would not emerge from any obvious feature of the rules, and nobody has a theoretical explanation for it.

The smallest games by hand #

One spot is short enough to play out in full. The first player has only one possible move: a loop from the spot back to itself, with a new spot on the loop. The original spot has now used two of its three lives and has one left, and the new spot also has one left, and they lie on a single closed curve. The second player joins them, on one side of the loop or the other, adding a third spot in that region. Now the first two spots are used up. The third spot has one life, and no partner, so nothing can be done. That is two moves, the second player has made the last, and the first player loses. There are no alternatives that matter.

Two spots already have some genuine choice. A move can join the two spots, or a spot to itself, and from then on the regions start to differ. Every line of play lasts four or five moves, and at two spots the search above finds that the second player wins with correct play, which means steering the game to a length of four. At three spots the range of 6 to 8 includes both parities, and the first player has a way to force an odd length. It is hard to see why from the drawing, and this is what makes the game hard to play well. Most positions look the same to the eye, and they differ in a single bit that is carried by the arrangement of small enclosed regions.

A position that has broken up into several regions is a sum of independent games, as with the pieces in the game Euclid’s algorithm plays, where each turn is taken in just one part. The theory of Sprague and Grundy assigns each part a single number, and the parts combine by exclusive-or. That is what lets search programs reach dozens of spots, since the values of small regions can be stored once and reused. Most of the values in those tables are 0, 1, 2 or 3.

Brussels sprouts, or how not to design a game #

A cross has four arms. A move uses two free arms and creates a new cross with two free arms. So the number of free arms never changes. It starts at $4n$ and stays there. A game can only end when no two free arms can be joined: when every region of the paper has exactly one free arm in it. Two free arms in the same region can always be joined. So at the end, there are $4n$ regions, each with exactly one free arm.

That is already a remarkable invariant, and now Euler’s formula finishes the job.

Treat the final drawing as a planar graph. After $m$ moves, there are $n + m$ crosses, the vertices. Each move added a curve, split into two edges by the cross placed on it, so there are $2m$ edges. There are $F = 4n$ regions. And the drawing must be connected: if it were not, then some region would have two boundary components, each with its free arms, because each component of the graph has free arms on its outer boundary, and those two arms could still be joined. So Euler’s formula $V - E + F = 2$ gives

$$(n + m) - 2m + 4n = 2,$$

so $m = 5n - 2$, independent of anything the players do.

The simulation shows what it means to have no freedom. With random moves, at each size from one to twenty crosses, all 120 games last exactly $5n - 2$ moves. Twenty crosses gives 98 moves, every time. Each game ended with exactly $4n$ regions and exactly $4n$ free arms. So the winner is determined by the parity of $5n - 2$: the first player wins exactly when $n$ is odd. The game is entirely decided before it starts. Its beauty as a practical joke is that this cannot be seen from the board. A beginner, playing a few rounds, sees different drawings and different local decisions, and assumes that they matter.

The same counting applied to Sprouts shows why it remains a game. Let there be $m$ moves, with $s$ surviving lives. Then $3n - s = m$. Vertices are $n + m$ and edges are $2m$, but the number of regions at the end is not fixed: a region may contain one survivor with one life, or none. And the drawing may be disconnected. So Euler’s formula relates $F$ and the number of components to $m$, but there are two unknowns, and players can affect each of them. The freedom in Sprouts is that there’s a variable number of survivors and regions, and Euler’s formula is only one equation. Change the rule by one word, and a game with a theory becomes a theorem with no game in it.

The formula for crosses with more arms is also simple: with stars of $k$ arms, each move produces a new star with $k - 2$ free arms, and a similar count gives $(k + 1)n - 2$ moves for $k \ge 3$, with $k = 4$ giving $5n - 2$. For $k = 3$ it gives $4n - 2$, in which each new spot is a point with one arm on one side. That game is not quite Sprouts, since Sprouts spots are not committed to a side, and it is that one bit of freedom, on which side a new spot’s last curve will leave, that makes Sprouts a game.

Games on other surfaces #

Euler’s formula depends on the surface, and that suggests a question. On a torus, $V - E + F = 0$ rather than 2, as the solid where the answer is not two explains, provided each region is a disc. So Brussels sprouts on a torus would have $5n - 2$ replaced by something else. But a curve may run around the torus without separating anything, and the assumption that the final regions are all discs needs a separate check. The result, with some care, is that a game on a surface of genus $g$ lasts between $5n - 2$ and $5n + 2g - 2$ moves. So the moment the surface has a handle, the length is not fixed, and the same formula that kills the game on a sphere leaves it alive on a torus. Each handle gives two extra moves of play. The Sprouts bounds change in the same direction.

The twelve pentagons of every cage come from this same count of vertices, edges and faces, with a fixed answer that holds whatever else the shape does. Whichever way it is played, Sprouts is planar for a deep reason. Curves that cannot cross can be mapped onto two graphs that will not lie flat only in a limited way, and a game that tries to build a non-planar graph is stopped in advance by the rules. Compare the opposite game with edges required to meet, in which everything must cross and Euler’s formula is of much less use. There is a further resemblance with Hex, in that both are pencil games in which topology settles a question that seems to be about strategy. Hex has no draws because of a separation theorem. Brussels sprouts has only one length, because of Euler’s formula. In one the first player’s win is proved and the winning move is not known, and in the other there is no choice to make.

Another way to say this is in terms of a tree and its dual. In a connected plane graph, a spanning tree and the complementary dual tree together account for every edge, and that is where the formula comes from. The curves added during a game of Brussels sprouts form a growing plane graph, and at each moment each new curve either joins two pieces, adding an edge to the tree, or closes a loop, adding an edge to the dual tree. Each move makes one such decision, and Euler’s formula is the statement that the number of each kind is fixed in advance.

What was computed #

The position search for Sprouts is exhaustive up to five spots, with a sound but not fully canonical table of positions, so some equivalent positions are stored more than once. The results match the published values. The exact ranges of game length go up to three spots. Longer games were sampled at random, with a random choice among legal moves that is not uniform over all possible drawings, and so the lengths in that figure describe that particular random player, not a typical game between people.

The Brussels sprouts simulations are a test of the theorem, not a proof, on games represented by their regions and arms. A bad representation would have failed the test. Their agreement at all 1,200 games establishes that the bookkeeping is right, and the Euler count is what proves the result. Statements for larger boards in Sprouts, for other surfaces, and about the methods used by Applegate, Jacobson, Sleator, Lemoine and Viennot are quoted. The lower bound of $2n$ was described and not proved in full here, and the torus formula is only sketched.

Still open: the pattern of six #

Does the first player win Sprouts exactly when $n$ is congruent to 3, 4 or 5 modulo 6? No counterexample is known and there is no proof, and in fact no proof for all $n$ of any statement about who wins. It is not known that the outcome is eventually periodic. It would be remarkable if a proof could be found, given how little of the game’s structure is understood apart from enumeration. The misère version, where the player who cannot move wins, has a different and less regular pattern, with published values up to about $n = 20$. How hard the game is, in terms of complexity, is unsettled too. Nothing like a PSPACE-completeness proof is known for positions of the natural form.

A second question has a more elementary flavour. What can be said about the Sprague–Grundy values of positions with isolated regions? Each region is an independent game, and the whole position’s outcome is the nim-sum of its parts, so a theorem about the values for small regions could in principle deliver large parts of the pattern. Computed tables show they are mostly small numbers. Whether they remain bounded is not known.

One equation against two unknowns #

In Brussels sprouts the number of free arms is constant, so the end of the game has $4n$ regions, and Euler’s formula then allows exactly $5n - 2$ moves, however anyone plays. In Sprouts, a single change in the rules leaves survivors whose number can vary, so the same count leaves one unknown free. The length lies between $2n$ and $3n - 1$, the winner is the parity of the length, and an exhaustive search over the arrangements of regions gives second, second, first, first, first for one to five spots. Far larger searches keep finding a pattern modulo 6 that nobody can explain.

The two games share a sheet of paper and a rule about crossing, and they differ by one word. One is a theorem, and the other is a game that has held off proof for more than fifty years. Euler’s formula is the entire difference: one equation is enough to fix one unknown, and it is not enough to fix two.