What computing further has bought

A conjecture from hand play leaves Sprouts in a particular state. The outcome pattern — the first player wins from n spots exactly when n leaves 3, 4 or 5 on division by six — was guessed from games played with a pencil, and it has been confirmed by computer for every number of spots anybody has reached. Forty-four confirmations and no proof.

The obvious response is that the computing will eventually turn into understanding. It usually does: a hard case gets solved, the solution suggests a lemma, the lemma covers the rest. That is exactly what happened to the octal games, where a period is a proof describes the moment a finite computation becomes an infinite claim. So it is fair to ask what fifty years of computing Sprouts further has actually bought.

The answer is best approached from the other end, by measuring what the computing costs.

Three spots. Thirteen and a half million positions to establish that the first player wins a game that a child can play in a minute with a pencil.

That is not an embarrassing result and it is not a badly written search. It is the honest cost of walking the tree of a game with no memoisation across the whole state space, no symmetry reduction, and no theory. It is what “computing the answer” means before anybody has had an idea.

What the search is actually walking #

A word about the thirteen million, because the number is not the number of positions in the ordinary sense.

The search here walks the game tree rather than the position graph. Two different sequences of moves that arrive at the same drawing are counted twice, three times, however many times they are reached, and on a game whose moves largely commute that is most of the cost. A solver that recognised repeated positions would collapse a great deal of it — that is exactly the memoisation knowing who wins and knowing what it is worth is about — and the reason it is not done here is that recognising two Sprouts drawings as the same drawing is itself a hard problem. The positions are planar maps up to homeomorphism, and deciding whether two of them are the same is the piece of work the published solvers spend most of their ingenuity on.

So the first honest qualification of the number is that thirteen million is a tree count and the state count is smaller — possibly much smaller. The second is that it does not matter for the argument. Even a solver that collapsed the tree perfectly would face a state count growing at some multiple per spot, and the projection below uses the measured growth of this search rather than a theoretical one precisely so that it is an arithmetic claim about this method rather than a claim about all methods. The claim it makes is narrow and it is enough: this method does not reach forty-seven, and it does not fail to by a factor anybody can close.

The distance to forty-seven #

The interesting number is not three. It is the ratio between three and forty-seven.

One spot to two multiplied the search by 479. Two to three multiplied it by 7,075. Take the gentler of those and carry it to forty-seven spots and the answer is about 10¹²⁵ positions.

There is no computer. There will not be a computer. The number is forty-five orders of magnitude past the count of atoms in the observable universe, and that comparison is not rhetorical decoration — it is the reason the sentence “they computed further” is misleading about what happened.

What happened is that people had ideas. Positions were represented canonically so that the same shape drawn differently counted once. Independent components were separated and combined, which is the sum is the object applied to a game where the components are regions of a plane. Positions were normalised so that vast families collapsed to a single record. Each of those is a piece of mathematics, and each bought several spots. Forty-four more confirmations of the conjecture is what the mathematics produced; it is not what the computing produced, and the difference matters because only one of the two can be scaled by waiting.

Three confirmations. That is the site’s entire independent contribution to a conjecture with forty-four of them, and stating it that plainly is the point: a confirmation is one bit, the bits do not compose, and forty-four of them is forty-four bits.

The check is worth having anyway, for a reason that is about the site rather than about Sprouts. The pattern is quoted here from the literature and the search is written here; if the two disagreed at any row, one of them would be wrong and it would almost certainly be the search. So the figure asserts the agreement rather than printing both columns and leaving the reader to compare — and it does the same for the move range, requiring it to sit inside the band the lives argument allows. Neither assertion has fired, which is the only evidence available that the machinery producing every other number on this page is doing what it says.

That is a small instance of a general habit and it is the reason it is worth naming. A search that reproduces a known result is not adding to knowledge; it is testing itself against knowledge. The three confirmations buy nothing about Sprouts and a great deal about whether the thirteen-million-position figure means anything.

The game next door, which computing did explain #

All of that would be a complaint about hard problems if there were not a control sitting beside it, invented in the same room on the same afternoon.

Brussels Sprouts from n crosses runs exactly 5n − 2 moves. Not on average, not usually: exactly, every time, whatever either player does. Sprouts sets out the argument — the arms are conserved at 4n, every move either splits a face or joins two pieces, and Euler’s relation closes the account. The winner is decided by the parity of 5n − 2 before anybody draws anything.

Sprouts has no such number. A game from n spots runs somewhere between 2n and 3n − 1 moves, and the measurement above establishes something the bound alone does not: every length in that band actually happens. One spot runs 2 moves and only 2. Two spots run 4 or 5. Three spots run 6, 7 or 8. The band is not a conservative estimate with slack in it; it is achieved at both ends and everywhere between, and the figure refuses to draw if a row ever comes in narrower than the theory allows.

So the parity that decides the winner is a thing to be fought over rather than counted. That is the whole difference between the two games, and it can be made sharper still.

The band’s width is n − 1, so it widens by exactly one move for every spot added. At three spots there are three possible lengths; at forty-seven there would be forty-seven. That growth is arithmetic rather than exponential and it is worth setting against the exponential growth of the search, because the two together say something specific about where the difficulty is. The number of outcomes the game can have stays two. The number of lengths grows linearly. The number of positions grows by three orders of magnitude a spot. So the difficulty is not in the answer, and not in the range of answers; it is entirely in the number of ways to get to one.

Five million choices, none of which matter #

A position holds a decision when some of its moves lead to a win and some to a loss. Count those and the two games separate completely.

Brussels Sprouts from two crosses: 23,541,801 positions searched, 5,109,801 of them offering more than one legal move, some offering as many as forty — and not one in which the choice affects who wins. Every branch of that five-million-way tree ends the same way. A player choosing at random and a player playing perfectly are indistinguishable, because there is nothing to play well.

Sprouts from three spots: 3,074,566 positions with a choice, and 553,417 of them — eighteen per cent — where the choice decides the game.

Nought against half a million. Note also which of the two has the wider choices: Brussels Sprouts reaches forty legal moves at its widest and Sprouts thirty, so the game with nothing to decide is the one offering more to decide between. A count of legal moves is not a count of anything that matters, and the two columns beside each other are the demonstration.

That is not a difference of degree between a hard game and an easy one; it is the difference between a game and a ritual. And it is what “computing explained this game” looks like when it has actually happened: not a table of confirmed outcomes, but a number that turns out to be forced, a reason it is forced, and a count of decisions that comes out at zero because the reason is airtight.

Why the two came out differently #

The two games are almost the same object. Both are played by drawing curves in the plane and adding a spot; both terminate for reasons about arms running out; both are decided by the parity of the length. Everything in the previous paragraph is true of Sprouts too, except the last clause of it — Sprouts’ length is not a number.

The single structural difference is what a move does to the arm count. In Brussels Sprouts a cross has four arms, a curve consumes two and the new cross adds four minus the two it uses, so the total is conserved exactly. In Sprouts a spot has three lives, a curve consumes two and the new spot has one left, so every move destroys exactly one life — but the game does not end when the lives run out, it ends when no two remaining lives share a face, and that is the quantity nobody can count in advance.

So the whole of the difference is one conserved quantity against one that is merely decreasing. Euler’s relation settles the first and has nothing to say about the second. That is a genuinely small hinge for two games of such different difficulty to turn on, and it is worth noticing that no amount of computing either game would have located it — the argument is a page of topology and the search is thirteen million positions, and only one of them says why.

Two people four years apart is about the same phenomenon in the history: the thing that unlocks a subject is rarely the thing that had been getting steadily better.

There is a temptation, having seen the hinge, to expect it to be turnable — to look for the extra condition that would make Sprouts’ length conserved too, or the weighting under which it is. It is worth resisting for a measured reason rather than an aesthetic one. If some quantity were conserved in Sprouts, the game would have a fixed length, and the measurement above says the lengths at three spots are 6, 7 and 8. Whatever is being sought would have to be conserved and yet compatible with three different lengths, which is to say it would not be the length. That does not prove nothing of the kind exists; it does establish that the obvious form of it is already ruled out by three numbers.

What a confirmation is worth #

The remaining question is what forty-four confirmations of the period-six pattern actually establish, and the honest answer is: a great deal about the first forty-seven spots and nothing about the forty-eighth.

That is not scepticism about the conjecture. It is a statement about the shape of the evidence, and the contrast that makes it precise is available in this collection. In an octal game, a computation that finds the Grundy sequence periodic for long enough triggers a lemma, and the lemma converts the finite check into a theorem about every heap size there will ever be. The computation stops being evidence and becomes a proof. A period is a proof is that moment, and it is worth reading beside this essay precisely because it is the thing that has not happened here.

Sprouts has no periodicity lemma. There is no theorem saying that if the pattern holds to n it holds beyond, and nobody has proposed a mechanism that would produce a period of six. So each new value is a fresh computation producing a fresh bit, and forty-four bits of a pattern that could stop at any point is exactly forty-four bits.

That places the game precisely. It is not where the impartial theory stops — the theory applies fine, the positions have values, the recursion works. It is not PSPACE-completeness either, which is a statement about a family of games rather than about one number. It is the narrower and more frustrating situation of a game where every individual question is decidable, every answer so far has fitted a simple pattern, and there is no lever anywhere to turn the pattern into a claim about all of them.

What would count as progress #

It is easy to say what has not happened and harder to say what would, so it is worth being specific, because the specification is the useful part of the diagnosis.

Three things would each be progress, and they are of very different sizes.

The smallest is another confirmation — forty-eight spots. It costs whatever the current best solver costs times its growth factor, it produces one bit, and it would be worth having only in the sense that a counterexample would be enormous news. Nobody expects one. The value of the next confirmation is almost entirely the small probability that it fails.

The middle one is a reduction: some theorem saying the outcome at n is determined by the outcome at n − 6, or at n − 1 together with something computable. That is the shape a period is a proof has, and it is what turns a table into a theorem. Nothing of the sort is known for Sprouts and nothing about the game’s structure obviously suggests where to look — the six is not a count of anything anybody has identified, which is precisely why the conjecture is a conjecture rather than a lemma with a gap in the proof.

The largest is the Brussels Sprouts answer: a conserved quantity, an argument from it, and a closed form. That is ruled out in its obvious form by the three lengths above, and it is the outcome everybody would want.

What is instructive is that only the first of the three is bought by computing, and the first is the one worth least. That inverts the usual relationship between effort and result in a computational subject, and it is the reason this rung is a history essay rather than a complexity one. A golden ratio thirty years early records a case where somebody found the closed form before anybody had a machine to check it against; here there are machines, there have been machines for fifty years, and the closed form has not arrived.

A bound instead of an answer is the usual consolation prize in this subject, and it is not available: the quantity in question is a single bit and there is nothing to bound. What is available is what this essay has done — measure the cost, measure the distance to where the computing has actually reached, and be exact about which of the two produced the results. Fifty years of computing Sprouts further has bought forty-four numbers and a great deal of technique. It has not bought a reason, and the search is not the thing that will.