Combinatorial Game Theory
who wins, and by how much
Particular games

Sprouts, and the game that is not one

Two games played with dots and curves, invented in the same room, all but indistinguishable on paper. One is unsolved past forty spots. The other has no decisions in it at all — the winner is fixed before the first curve is drawn.
18 min read 7 figures The theory runs outWho moves lastThe sum is the object

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.

One of these is a gameEvery length that came out of forty random games from each starting position. Brussels Sprouts always ends after exactly five crosses less two moves, so whoever is to move at that point was decided before the first curve was drawn. Sprouts ends at different lengths depending on how it is played, which is what makes it worth playing.051015how many moves the game lasted1 spotBrussels — always 3Sprouts — 2 in these games2 spotsBrussels — always 8Sprouts — anywhere from 4 to 53 spotsBrussels — always 13Sprouts — anywhere from 6 to 84 spotsBrussels — always 18Sprouts — anywhere from 9 to 10every Brussels length matched 5n − 2 across 40 random games from each startand the figure refuses to draw itself if any of them does not
Fig. 1 Every game length that came out of forty random games from each start. Brussels Sprouts produced one length each time and it is exactly five crosses less two. Sprouts produced a range, and the range is the only reason it is worth playing.

The move, in both games

One move, in each gameA move joins two unused ends with a curve that crosses nothing, and puts a new spot on it. In Brussels Sprouts the ends are the drawn arms of a cross and the new spot is a crossbar, so two ends go and two arrive. In Sprouts the ends are unused lives of a dot and the new spot has three of them, two of which the curve has just spent — so two go and one arrives.Brussels Sproutstwo arms used, two arrivefour ends before, four afterSproutstwo lives spent, one arrivessix lives before, five afterin both games the curve may not cross anything, so the two ends must lie on the same face of what is already drawna Brussels arm points somewhere definite; a Sprouts life does not, and that is why one of them is a game
Fig. 2 What a move does. On the left, a Brussels move joins two drawn arms and the crossbar returns two — so the number of free ends never changes. On the right, a Sprouts move spends two lives and the new spot returns one, so the lives run down. Both curves must stay inside one face of what is already drawn.

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 nn spots there are 3n3n lives and each move costs one net, which is why the game lasts between 2n2n and 3n−13n-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 nn crosses, every Brussels Sprouts game lasts exactly 5n−25n-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−25n-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.

One Brussels game from 2 crosses, countedOne randomly played game, with the map counted after every move. Joining two arms uses two up and the new crossbar puts two back, so the number of free arms never moves. Each move cuts one face in two, so the faces rise by one. The game stops when no face holds two arms, and nothing a player does changes when that happens.after movecrossesfree armsfacesfaces with a move in them02811138112482235833468435785368862798718108808 moves, which is 5 × 2 − 2the free arms stayed at 8 throughout — checked, and the figure will not draw if they movethe last row is the position nobody can move from, and both players reach it whatever they do
Fig. 3 One game followed through, with the map counted after every move. The free arms never move from eight. The faces go up by exactly one per move, because each curve cuts a face in two. The game stops when no face holds two arms, and both quantities are forced.

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. The short version: each move adds one vertex and two edges to a planar map, so it adds one face; the arms are conserved; and the game ends when the faces have separated the arms, which happens at a count fixed by the starting configuration.

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.

Where the search stopsEvery Sprouts position from a given number of spots, searched exhaustively, until it is not. One spot settles in a handful of positions and two in a few hundred; three runs past the budget this figure allows itself, so it has no answer and says so rather than quoting one from elsewhere.spotswinnermovespositions searched1the second player232the second player4–53133not settled here—over 1.0 million, and still goingthe bar is logarithmic, because the growth isthe winner for larger boards is known — from published machine searches, not from anything hereand the pattern those searches found repeats with period six in the number of spotswhich nobody has proved either
Fig. 4 Exhaustive search, until it is not. One spot settles in three positions and two spots in a few hundred. Three spots runs past the budget this figure allows itself, so it reports that it has no answer rather than quoting one from somewhere else.

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.

The site’s gate runs a hundred random Brussels games across four starting sizes and requires every one to last exactly 5n−25n-2 moves. It separately requires ordinary Sprouts from two spots not to have a fixed length, so that a bug making both games deterministic could not pass. And it requires the exhaustive searches for one and two spots to return the outcomes above.

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.

Nim with heaps of 2, 3Heaps of counters; a move takes any number from one heap. The position is a loss for the player to move exactly when the binary digits of the heap sizes cancel in every column — the nim-sum — and that is the whole of the theory of Nim.20103011nim-sum001= 1some column does notthe player to move winstake 1 from the heap of 3outcome N
Fig. 5 What decomposition buys where it is available. Two independent heaps, a nim-sum computed from them, and the outcome read off in one step. Sprouts positions fall into pieces that look like this and are not, because a move may join two pieces that share a face.

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.

One of these is a gameEvery length that came out of forty random games from each starting position. Brussels Sprouts always ends after exactly five crosses less two moves, so whoever is to move at that point was decided before the first curve was drawn. Sprouts ends at different lengths depending on how it is played, which is what makes it worth playing.0510how many moves the game lasted1 spotBrussels — always 3Sprouts — 2 in these games2 spotsBrussels — always 8Sprouts — anywhere from 4 to 53 spotsBrussels — always 13Sprouts — anywhere from 6 to 8every Brussels length matched 5n − 2 across 30 random games from each startand the figure refuses to draw itself if any of them does not
Fig. 6 The same measurement on a smaller sample, for the three starts where both games are cheap to run. Brussels produces a single length at each size and Sprouts a spread. Every figure on this page refuses to draw if a Brussels game ever comes out at a length other than five spots less two.

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.

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.

Which questions are answerableThe theory is exact and much of it is expensive. Values are computable by definition; computing one for a position of any size is a different matter, and deciding the winner of a generalised board game is complete for PSPACE — as hard as anything solvable in polynomial space.the value of a Nim positioninstantthe Grundy value of a small subtraction gamelinearthe canonical form of a moderate positionexponential in theorywho wins a general Domineering boardno efficient methodwho wins a generalised board gamePSPACE-completecostthe definitions are constructive, so everything here is computable in principleand the practical range of an exact evaluator is a few dozen moves, which is the working constraint
Fig. 7 The general situation this page is one instance of. Exact evaluation reaches a few dozen moves and then stops, and the games people play are far past that. Sprouts is unusual only in that the wall arrives at three spots rather than at three hundred squares.

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−25n-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.

Where this goes next

the value of a Nim positioninstantthe Grundy value of a small subtraction gamelinearthe canonical form of a moderate positionexponential in theorywho wins a general Domineering boardno efficient methodwho wins a generalised board gamePSPACE-completecostthe definitions are constructive, so everything here is computable in principleand the practical range of an exact evaluator is a few dozen moves, which is the working constraint How hard is it Every theorem on this site stays true at any size. The answers stop being reachable long before the games get interesting — deciding the winner of a generalised board game is PSPACE-complete, and an exact evaluator gives out after a few dozen moves. 6 classes under misère play4 under normal play — the Nim values 0, 1, 2, 3computed over all 28 positions with at most 6 heaps1{1}{2}{1,2}{2,2}{1,2,2}1{1}{2}{1,2}{2,2}{1,2,2}1{1}{2}{1,2}{2,2}{1,2,2}{1}1{1,2}{2}{1,2,2}{2,2}{2}{1,2}{2,2}{1,2,2}{2}{1,2}{1,2}{2}{1,2,2}{2,2}{1,2}{2}{2,2}{1,2,2}{2}{1,2}{2,2}{1,2,2}{1,2,2}{2,2}{1,2}{2}{1,2,2}{2,2}shaded — a lossfor whoever must movea dot is a sum thatleaves this universeeach class is named by the smallest position in it, and 1 is the empty positionthe table is a quotient of the universe drawn, not a proof about the whole game — which is a weaker claim, and the true one What survives misère play Misère play destroys the value theory, and something much smaller grows back. Fix one game, look only at sums of its own positions, and the classes that behave alike form a monoid — computed here, and larger than the normal-play answer every time. worth 2, outcome La burnt square is crossed out; the shading separates the regionsthe regions, evaluated aloneregion 1 — 5region 2 — -3their sum is 2which is what the whole board is worththe regions were found by walking the board, evaluated separately, and their values added — the equality is checked, not claimed Amazons, and when a position becomes a sum Every technique on this site starts from a position already broken into independent parts. Amazons does not begin that way — the board is one fight until the arrows cut it, and the moment of cutting is something the play produces rather than the analyst assumes.