A conjecture from hand play

Sprouts was invented in 1967 by John Conway and Michael Paterson, in a Cambridge common room, with a pencil.

The rules take a sentence. Start with some spots. A move joins two spots — or a spot to itself — with a curve that crosses nothing, and places a new spot on that curve. No spot may have more than three lines meeting it. Whoever cannot move loses.

They played it, noticed a pattern in who wins, and conjectured that the pattern continues. Fifty-eight years later the pattern has been checked far beyond where anybody could play, and it is still a conjecture.

The game ends, and the proof is a count #

Before anything about who wins, there is a question that is not obvious from the rules: does the game stop?

It does, and the argument is a piece of bookkeeping that Conway and Paterson had immediately.

Each spot starts with three lives — three line-ends it can still accept. A move uses two lives, one at each end of the new curve, and creates a new spot with three lives, of which the curve immediately consumes one. So each move costs two lives and creates one: every move reduces the total number of lives by exactly one.

Starting with $n$ spots there are $3n$ lives, so there are at most $3n - 1$ moves. The game cannot last longer, and cannot go on for ever.

There is a matching lower bound — a game lasts at least $2n$ moves — so the length is pinned to a narrow band, which is unusual and pleasant.

The lower bound, and why the band is narrow #

The upper bound of $3n - 1$ moves is the lives count. There is a matching lower bound, and it is the more interesting of the two.

At the end of a game every surviving spot has either no lives left, or one life that cannot be used — because the only spots it could reach are in a different region, walled off by the curves already drawn. Counting the ways a game can end gives at least $2n$ moves.

So a game from $n$ spots lasts between $2n$ and $3n - 1$ moves, and the band is one third wide and does not grow. That is unusual: most games in this subject have lengths varying by a factor rather than by a third.

And that is the trap. The band being narrow makes it look as though a parity argument should settle the game, and the band being not a point is exactly why one does not. Brussels Sprouts, below, is the case where the band collapses to a point and the parity argument works.

What the conjecture says #

The observed pattern is about the starting number of spots. The first player wins for some values of $n$ and loses for others, and the pattern appeared to depend on $n$ modulo 6: a first-player win unless $n$ leaves remainder 0, 1 or 2.

That guess was made from games played by hand, which means from very small $n$. It has held everywhere it has been checked since.

Why this site’s solver stops at three #

This is where the essay has to be careful, because the temptation is to quote the published frontier and the site’s own rule forbids it.

The search here does not canonicalise positions at all, and that is the honest description of why it gives out on Sprouts from three spots: it walks the move tree, passes a million positions and stops. Every position reachable by two different orders of play is searched twice, and the number of such orders is what the budget is being spent on.

That is a limitation of this machinery rather than a fact about the game, and the two are worth keeping apart. Two Sprouts positions are the same when their maps are the same up to relabelling and up to which region counts as the outside, and a search that could decide that would collapse most of the tree into a much smaller graph. Deciding it means canonicalising a planar map, which is a piece of work in its own right and one this site has not done.

So the honest statement is a frontier rather than an answer, and it is stated that way deliberately: what “solved” means distinguishes three claims that one word is used for, and “somebody has computed this” is not a claim this site can make on its own behalf.

The published frontier is far beyond this. Computations have settled Sprouts for starting positions well into the dozens, and the pattern has held. What this site can say honestly is: the bookkeeping argument is exact and checked, the small cases are computed here, and the frontier belongs to machinery this site does not have.

The surprise: the easier-looking variant is completely solved #

Conway and Paterson also invented Brussels Sprouts, which looks like the same game and is not.

It starts with crosses rather than spots — four arms each — and a move joins two free arm-ends with a curve and puts a new cross on it, consuming two of the new cross’s arms and leaving two. So each move costs two arms and creates two: the total is invariant, and the game’s length is fixed entirely by the starting position.

That makes Brussels Sprouts a game with no strategy at all. The winner is determined by the parity of the number of moves, which is determined by $n$. Playing it is theatre.

That last identity is where the fixed length comes from, and it is worth having in full because the usual one-line version of it is wrong. The arms are conserved at $4n$. The game stops when every face holds exactly one arm, so it stops at $4n$ faces. All $n$ crosses have been joined into one piece by then, so $n-1$ of the moves were joins. Add the two: $4n - 1 + n - 1 = 5n - 2$.

The pair is instructive. Two games with almost identical rules; one has a fixed length and a trivial answer, the other has a variable length and an open problem. The difference is one arm.

What a search has to do, and why it is expensive #

The termination bound says a game from $n$ spots lasts at most $3n - 1$ moves, which sounds small. From three spots that is eight moves, and eight moves of a game with a handful of options each should be nothing.

It is not nothing, and the reason is the state.

A position is a planar map: a set of spots, a set of curves, and — crucially — the arrangement of regions those curves cut the plane into. Two positions are the same when their maps are the same after relabelling the spots and after choosing which region counts as the outside. So a search cannot compare positions by comparing drawings, and it cannot compare them by comparing lists of edges either.

Which is exactly what the search on this page is paying for. Without canonicalisation it re-explores the same position along every route that reaches it — the difference between a recursion tree and a position graph — and here the ratio is severe, because a Sprouts position is reachable by a great many orders of play and the tree counts every one of them.

What the players are actually fighting over #

The lives count is presented above as a termination argument, and it says something much stronger than that, which the essay can extract without any new machinery.

Every move reduces the total number of lives by exactly one. So a game that starts with $3n$ lives and lasts $m$ moves ends with $3n - m$ lives on the board, and those survivors are lives that exist and cannot be used — spots with a free end and nowhere to reach, walled off from every other free end by the curves already drawn.

Call that number $L$. Then

$$m \;=\; 3n - L,$$

and since whoever makes the last move wins, the winner is decided by the parity of $L$. Not by the shape of the final map, not by who is ahead in any sense — by whether an odd or an even number of lives ends up stranded.

That is the whole strategic content of Sprouts, and it is a much more concrete thing to be playing for than “who cannot move”. Each player is trying to steer the game towards an end position whose count of unusable lives has the parity they want, and every curve drawn is a move in that argument: a curve that seals a region strands whatever is inside it, and sealing regions is the only mechanism the game has.

Which is why the band matters, and why Brussels Sprouts has no game #

The two bounds now say something they did not say as bounds.

The upper bound of $3n - 1$ moves is $L \geq 1$: at least one life is always stranded, so a game never uses everything. The lower bound of $2n$ moves is $L \leq n$: at most $n$ lives are ever stranded. So $L$ runs between 1 and $n$, and for every $n$ beyond the smallest that range contains both parities.

A range containing both parities is exactly a game. Each player has something to aim at, neither aim is unreachable a priori, and the question of which one optimal play achieves is a real question with no arithmetic answer. Had the bounds pinned $L$ to a single value, or to one parity, the winner would follow from $n$ and there would be nothing to compute.

Brussels Sprouts is the case where they do. Its move costs two arms and returns two, so the arm count is invariant, the length is fixed by the starting position alone, and $L$ has no room to vary. There is no parity to fight over, so there is no fight — which is the essay’s own observation, now with a mechanism rather than an analogy behind it.

And it says what the conjecture is a conjecture about #

Read this way, the modulus stops being a pattern in a list of outcomes and becomes a claim about a quantity.

The conjecture says the first player wins unless $n$ leaves remainder 0, 1 or 2 on division by six. Since the first player wins exactly when $3n - L$ is odd, the conjecture is equivalent to a statement about the parity of $L$ under optimal play — that the number of stranded lives comes out with one parity for three residues and the other for three.

That does not make it easier. But it does say what a proof would have to be about, and it is not about who wins: it is about how many lives a game can be forced to strand, which is a question about the geometry of planar maps rather than about game trees. Somebody looking for the mechanism the next section says nobody has found would be looking for an invariant of a partly-drawn map that controls the parity of its eventual stranded count.

That is a narrower target than “explain the period six”, and it is available from the bookkeeping Conway and Paterson had on the first afternoon.

Why the pattern has period six, as far as anybody knows #

The observed pattern depends on $n$ modulo 6, which is a strange modulus to appear in a game with a three-lives rule.

Nobody has an explanation. That is worth saying plainly, because the temptation with an observed periodicity is to assume a mechanism exists and has merely not been found. Here there is not even a candidate: no invariant of a Sprouts position is known that behaves with period 6 in the starting size, and the pattern is an empirical regularity in a list of computed outcomes.

That situation is the same one as the octal periodicity conjecture, and the resemblance is not superficial. Both are patterns in a sequence of outcomes, both have held everywhere checked, both have resisted every attempt at a mechanism, and both would follow immediately from a finite summary of the position that nobody has found.

What termination buys, which is more than it looks #

The lives argument is worth one more paragraph, because it does something the rest of the analysis depends on and gets no credit for.

It makes Sprouts a finite game, which puts it inside Zermelo’s hypothesis and therefore makes “who wins from $n$ spots” a well-posed question with an answer. Without it there would be nothing to conjecture.

More than that: it bounds the depth of the search tree at $3n - 1$, which is tiny. The difficulty is entirely in the breadth — how many distinct positions there are at each depth — and that is the reverse of the usual situation, where depth is what kills a search.

Where the model stops #

A move here is a curve, and a curve is a topological object. Everything about Sprouts depends on planarity — which curves cross which, which regions are separated — and none of it depends on where anything is drawn. A figure of a Sprouts position is one drawing of an equivalence class of drawings.

And the modelling has bitten before. This site’s earlier work on Sprouts recorded a case where treating a spot’s unused lives as drawn stubs made one-spot Sprouts finish in one move instead of two — because a Brussels cross’s arms point somewhere definite on the paper and a Sprouts spot’s lives do not. The two games need two representations, and using one for both is wrong in a way a pencil catches immediately.

The one thing that is proved #

Amid the open questions there is a genuine theorem and it should not be lost: Sprouts terminates, and its length is bounded above and below by explicit linear functions of the starting size.

That is a complete, elementary, checkable result of exactly the kind Bouton’s was, and it was available immediately from the rules. It is also, as it happens, the only thing about Sprouts anybody has proved in fifty-eight years.

The contrast with Nim is instructive and slightly deflating. Bouton’s elementary argument settled his game completely; the equally elementary argument here settles that the game ends, and everything past that has resisted.

What the picture cannot show #

Not one figure here draws a position, and that is deliberate rather than an omission. A Sprouts position is a planar map — which spots share a boundary with which region, and in what cyclic order — and it says nothing whatever about where anything sits on the paper. Two drawings that look identical can be different positions, and two that look nothing alike can be the same one, since a redrawing that moves a curve across the page changes nothing while a redrawing that moves it across a spot changes everything.

So a picture of a Sprouts position would be a picture of coordinates the program invented, and a reader studying it would be studying the invention. What the figures report instead is what the machinery counted: lives, faces, pieces, moves, and how large the search had to be.

That gap between a drawing and the object it stands for is unusually wide in this game, and it is the reason the search is hard rather than merely slow. No figure closes it, and the tables above are what taking that seriously looks like.

The second thing they do not show is the frontier. Every count here comes from one, two or three spots; the conjecture is about every $n$, and the published searches that reach into the dozens are somebody else’s machinery, quoted as such and drawn nowhere on this page.

What kind of claim the conjecture is #

It is worth classifying it, because “conjecture” covers several quite different situations and this one is a specific kind.

It is not a claim that a computation will terminate. Every instance is decidable: given $n$, the outcome is determined and computable in principle. The conjecture is about the pattern across instances.

It is not supported by a partial theorem. There is no proof for $n$ in some class of cases, no reduction of the general case to a smaller one, and no bound on how large a counterexample would have to be.

And it cannot be confirmed by computation, only failed to be refuted. Every extension of the frontier removes some possible counterexamples and leaves infinitely many.

So what supports it is: a pattern that has held over every case anybody has settled, and nothing else. That is a weaker evidential position than most open problems occupy — the octal conjecture at least has a proof for the subtraction sub-case to suggest the shape of a general argument — and it is worth being clear about, because “conjectured in 1967 and still open” sounds like a well-studied claim and understates how little is known.

Who found it, and when #

Conway and Paterson invented it in 1967. Martin Gardner’s column brought it to a wide audience in 1967, which is how most people met it, and the conjecture has been folklore ever since.

The machine computations are a long chain of people extending the frontier by better canonicalisation rather than by faster machines — which is the correct place to spend effort, and is the same lesson as the difference between walking a recursion tree and walking a position graph.

Why it was invented, which is not why it is studied #

Conway and Paterson were not looking for a hard problem. They were looking for a game that could be played on the back of an envelope, ended reliably, and was not obviously trivial — the ordinary requirements of an afternoon.

That it turned out to be hard is an accident, and the specific accident is worth naming: the state is a topological object rather than a combinatorial one. Almost every other game in this subject has a state that is a list of numbers or a pattern on a grid, both of which canonicalise cheaply. A planar map does not, and nobody choosing a game for fun would notice that they had just chosen the one property that makes a search expensive.

Where the ladder goes next #

The first rung is the game and its bookkeeping. This rung is the conjecture and the honest frontier. Onward from here is the pattern of what a search can and cannot settle — the same territory as the octal sequences nobody has settled, where computing further has never turned into understanding.