Sprouts, and the game that is not one

Sprouts is played with a pencil. Put some dots on paper. A move joins two dots with a curve that crosses nothing, and places a new dot on the curve just drawn. No dot may have more than three curve-ends at it, and the player who cannot move loses.

Brussels Sprouts is the same, with two changes. The starting dots are crosses, with four arms already drawn; a move joins two free arm-ends and puts a crossbar on the new curve, contributing two new free ends. No limit on anything else.

The two games look so alike that they are usually introduced together as variations. They are not variations. One of them is unsolved and the other has nothing to solve.

The move, in both games #

Two bookkeeping facts fall out of that picture and they are the whole difference.

In Brussels Sprouts the count of free ends is conserved: a move consumes two and produces two. Nothing runs out. The game ends for a purely topological reason — eventually no two free ends are on the same face, so no legal curve exists, even though there are ends everywhere.

In Sprouts the lives run down: a move spends two and returns one, so each move reduces the total by one. From $n$ spots there are $3n$ lives and each move costs one net, which is why the game lasts between $2n$ and $3n-1$ moves. It also has the topological ending condition, and which of the two bites first depends on how the game was played.

Brussels Sprouts is not a game #

From $n$ crosses, every Brussels Sprouts game lasts exactly $5n-2$ moves.

Not on average, not usually — exactly, every time, whatever either player does. So the player who makes the last move is determined by the parity of $5n-2$ before anybody has drawn anything, and the two players’ choices are decorative.

That is startling enough to be worth demonstrating rather than asserting. Forty random games were played from each of one, two, three and four crosses, and the figure at the top of this page reports every length that occurred. There is one length per starting position.

The reason is Euler’s relation, and this site does not re-derive it — the theorem and its proof belong elsewhere, and it is used here rather than established. What has to be got right is which quantities it is being applied to, and the obvious account is wrong.

It is not true that each move adds a face. A curve drawn between two points of one connected piece cuts its face in two; a curve joining two separate pieces sitting in the same face merges their boundaries and cuts nothing. A Brussels game from two crosses starts as two pieces in one face, so its first move adds no face at all, and its face count opens 1, 1, 2, 3 rather than 1, 2, 3, 4.

The statement that survives carries the piece count with it: every move either cuts a face in two or joins two pieces, and never both. So after $m$ moves,

$$m \;=\; (\text{faces} - 1) \;+\; (\text{pieces at the start} - \text{pieces now}),$$

which is Euler’s relation for a map with several components. That finishes the derivation the loose version could not. The arms are conserved at $4n$; a Brussels game stops when every face holds exactly one arm, so it stops at $4n$ faces; all $n$ pieces have joined by then, so $n-1$ of its moves were joins. Add them: $4n - 1 + n - 1 = 5n - 2$.

The important thing is not the formula but its consequence. Brussels Sprouts has a rule, a board, two players and legal moves, and no decisions. Whatever a player does, they arrive at the same place. It is a game in the sense that chess is a game and a coin toss is not, and it is a coin toss.

Sprouts is a game nobody has solved #

Sprouts has decisions, and they are hard.

One spot: the game lasts exactly two moves, so the second player makes the last one and wins. Three positions in the search.

Two spots: the game lasts four or five moves, so the first player would like five and the second would like four, and the second player can force four. Second player wins, in a few hundred positions.

Three spots: the search on this page gives up. It is known that the first player wins, from published machine searches, and the pattern those searches found is that the first player wins exactly when the number of spots leaves a remainder of three, four or five on division by six. That has been confirmed well past forty spots, and it has not been proved.

The figure reports the first two and refuses the third, which is the honest shape of the situation. The site’s rule is that nothing is claimed to have been solved that the code did not solve, and the outcome for three spots is not something this page computed.

The two cases that were computed do provide one small check on the published pattern, and it is worth taking for what it is. One and two leave remainders of one and two on division by six, so the pattern predicts a second-player win for both — and the exhaustive searches here return a second-player win for both. Two agreements out of a pattern with period six is not evidence of much, and it is not nothing: a search returning the wrong answer on the easiest cases in the family would have discredited itself immediately.

What the solver computed, and how #

Neither game can be played from a drawing, and that is the substantial part of the work here.

A curve is legal exactly when its two ends lie on the same face of what is already drawn. A face is not something a picture can be asked about — a program looking at coordinates would have to do computational geometry, and the game is not about geometry at all. So the position is carried as a planar map: a set of darts, a pairing that says which darts are two ends of the same edge, and a cyclic order of darts at each vertex, which is the embedding. Faces are traced from that after every move, by the standard rule of taking the other end of an edge and then the next dart around that vertex.

The two games then need different models of an unused end, and getting that wrong is what the first version of this machinery did.

A Brussels arm is drawn on the paper. It points in a definite direction, it sits in a definite sector at its cross, and a curve leaving it starts in that sector. So an arm is modelled as a real edge to a stub vertex, and faces trace through it uniformly.

A Sprouts life is not drawn. It is a dot with unused capacity, pointing nowhere, and a spot that sits on a closed curve can send its last life to either side of that curve. So a life is a count, and spending one requires choosing a corner — a sector between two consecutive edges at that spot — at the moment it is used.

Modelling Sprouts the first way makes one-spot Sprouts finish in one move instead of two, because it fixes the surviving life on one side of the loop when the player should have been free to choose. That is how the difference was found: the search returned an answer that contradicted a fact anybody can check with a pencil.

One further subtlety is a genuine choice in the game rather than a modelling artefact. When a curve is drawn inside a face containing several disconnected islands, the player also decides which islands end up inside the new loop and which outside. Those are different positions and both are legal, so the move generator offers them all.

Four claims about this machinery are checked by the figures that draw it, which refuse rather than report. Every Brussels game played out here must last exactly $5n-2$ moves. Every Sprouts game must land inside the band $2n$ to $3n-1$, and the moves and the stranded lives must add to $3n$ when the lives left are counted off the finished map. Every move of either game must either cut a face in two or join two pieces, and never both. And — the one that could fail in the opposite direction — Sprouts from two spots must not have a fixed length, since a bug that made both games deterministic would satisfy all three of the others, each of which says a count came out where it was supposed to.

Why Sprouts has no values #

The rest of this site evaluates positions. Sprouts is a game about which nothing in the value theory has anything to say, and it is worth being precise about why, because the reason is structural rather than a matter of difficulty.

Sprouts is impartial — both players have exactly the same moves from any position — so the Sprague–Grundy theorem applies and every position is worth some Nim heap. That is true, and it is useless, because computing the Grundy value requires the same exhaustive search as computing the outcome, and there is no structure in the positions to shortcut it.

The shortcut that works elsewhere is decomposition. A position that splits into independent parts has a value that is the nim-sum of the parts, and that turns an exponential search into arithmetic. A Sprouts position does split — the drawing falls into connected components — but the components are not independent, because a curve may be drawn from one component to another as long as they share a face. Two components in the same face interact; two in different faces do not.

That is worth setting against what decomposition buys where it is available. Two independent Nim heaps have a value each; the nim-sum of the two settles the pair in one step; and the work is a lookup rather than a search. A Sprouts drawing falls into pieces that look exactly like that and are not, because a move may join two pieces that share a face — which is the same joining move the face count above had to be corrected for, seen from the other side. In the bookkeeping it is the move that adds no face; in the theory it is the move that destroys independence.

So the face structure is doing two jobs at once: it decides which moves are legal, and it decides which parts of the position are independent. A theory of Sprouts would have to track it, and tracking it is exactly the expensive thing.

That is a fair general diagnosis of why some games resist the machinery. It is not that their positions are large. It is that their notion of independence is dynamic — parts that were separate can be joined — and every technique on this site assumes independence is a property of the position rather than something a move can undo.

Where the model stops #

The map is combinatorial and the game is drawn. Every claim here is about faces and rotations. A real player draws a curve, and two drawings with the same combinatorial map are the same position however different they look. That equivalence is the right one and it is worth stating, because it is doing a great deal of quiet work.

The search budget is a stated limit, not a result. Three spots exceeded a million positions here. That is a fact about this computation. A search with position canonicalisation — recognising that two maps are the same up to relabelling — would go considerably further, and building one is a piece of work this site has not done. The distinction between a game being hard and a particular program being slow matters, and this page is on the second side of it.

Normal play. Under misère play the Sprouts pattern is different and, as usual, worse understood. Brussels Sprouts under misère play is still not a game; only the winner changes, and it changes by parity.

“Not a game” is a claim about decisions, not about interest. Brussels Sprouts is a perfectly good way of demonstrating Euler’s relation to somebody with a pencil. What it is not is a contest. It has a determined outcome in the same sense that a position of value zero has one, except that here the whole game is determined rather than one position.

The distinction worth taking away #

The two games differ in one bookkeeping fact — whether the count of available ends is conserved or runs down — and that fact decides whether there is anything to think about.

A conserved quantity means the game ends for a structural reason at a structurally determined time. A depleting quantity means the players’ choices affect when it ends, and once they affect that, they affect who makes the last move.

And since whoever makes the last move wins, the winner is the parity of that stranded count and nothing else. That is what the two players are fighting over — not the drawing, not the number of spots, but whether an odd or an even number of lives ends up walled off with nowhere to reach. Brussels has no such argument available, because its arms are conserved and there is nothing to strand.

That is a general test worth carrying: given an unfamiliar game, ask what is conserved. A game with a conserved move budget and a determined stopping condition has no decisions in it, however elaborate its rules look.

The test also has a partial converse worth stating. A depleting quantity is necessary for decisions and is not sufficient: Cutcake depletes steadily and its values are all whole numbers, because although the players choose where to cut, nothing they choose changes the count. Conservation kills the game outright; depletion only makes decisions possible.

One thing the test does not tell anybody is how much room the depletion leaves, and that is worth a second measurement at a larger start.

What the figures cannot show #

Every figure on this page is a table or a strip, and none of them is a picture of a position. That is deliberate and worth explaining, because a Sprouts essay without a drawing of a Sprouts game looks like an omission.

A rotation system says which curves meet which, in what cyclic order, and on which face — and says nothing whatever about where anything is. Two drawings with the same map are the same position; two drawings that look identical may be different positions. To draw one of these positions a program would have to invent coordinates, and the coordinates would carry no information: a reader would be looking at a picture of a choice the program made rather than at the position.

So the figures report what the simulation produced. How long each game lasted. What the counts did after each move. How large the search had to be. Those are the quantities the argument is about, and each of them is a number the machinery computed rather than a shape somebody laid out.

The one exception is the move diagram, which is drawn from fixed geometry and is a picture of the rule rather than of a position. Its caption says so, and it is the only figure here where the coordinates were chosen by hand.

That answers a question the two bounds leave open and is worth stating plainly, because the essay above has been treating the two conditions as alternatives whose order depends on play. It does not: it depends on size. The lives argument is what makes the game finite, and it stops being the reason any particular game ended almost immediately.

The general situation this page is one instance of is the wall every exact evaluation runs into: a few dozen moves and then nothing. Sprouts is unusual only in that its wall arrives at three spots rather than at three hundred squares.

A game with no decomposition and no values #

Sprouts sits oddly in this collection and it is worth saying why, because the reason is a property of the game rather than a limit of the analysis.

A Sprouts position does not decompose. The graph grows; a new spot appears with each move; and a curve drawn anywhere can cut off a region and change what is reachable elsewhere. There is no moment where the position becomes a sum of independent parts, so the one exponential saving this subject has is unavailable from beginning to end.

And there is no useful value. Values are worth computing because they compose, and a game whose positions never form sums has nothing for a value to be used in. A Sprouts position has a Grundy value — it is impartial and finite — and knowing it settles that position and nothing else, because the position will never appear beside another.

So what is left is exhaustive search on positions that grow, which is why the known results are a list of small cases rather than a theory. That is not a gap waiting to be filled by cleverness; it is the shape of a game whose whole difficulty is that its parts do not separate.

Which makes Sprouts a useful control for everything else here. Nearly every technique on this site assumes a position that is a sum or becomes one, and Sprouts is the specimen that never does — so the amount known about it is a fair measure of what the subject can do with no decomposition at all.

Who found it, and when #

Sprouts was invented by John Conway and Michael Paterson in Cambridge in 1967, some years before the value theory that runs the rest of this site existed, on an afternoon that both later described as a diversion. The name is Conway’s; Paterson contributed the rule that a new spot goes on the curve, which is what makes the game finite.

Brussels Sprouts was invented immediately afterwards as a joke on people who had just learned the first game — offered as a harder variant, and in fact not a variant at all. The joke has a point in it, which is that a game’s apparent depth is not visible from its rules.

The computational history is a good illustration of what search buys. Denis Mollison analysed up to six spots by hand for a bet. Applegate, Jacobson and Sleator reached eleven by machine in 1991 and conjectured the period-six pattern. Lemoine and Viennot pushed it past forty in the 2000s. The pattern has held every time it has been tested, and there is still no proof.

The ladder from here #

This is the base rung of the Sprouts anchor.

Later rungs: the derivation of $5n-2$ from Euler’s relation, done properly. Position canonicalisation for planar maps, which is what a serious Sprouts search needs and is an interesting problem in its own right. The misère version, and what the period-six pattern becomes. The upper and lower bounds on Sprouts game length and which of the two ending conditions binds. And the general question this game poses well — how to tell a game with decisions in it from one without, which is not answered by looking at the rules.

The thing established here is a method rather than a result. Both games were played by a program that carries the embedding explicitly, because the legality of a move is a question about faces, and a program that guessed at faces from coordinates would be answering a different question.