Combinatorial Game Theory
who wins, and by how much
Concept

Planar map — where it appears

A drawing of vertices, curves and faces on the plane, which is what a Sprouts position is rather than a heap or a board. The face a curve lies in is part of the position, which is why Sprouts needs a representation a heap game does not.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

One of these is a game. Every length that came out of 40 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.

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.

positions · Sprouts One Sprouts game from 3 spots, counted. One randomly played Sprouts game, with the map counted after every move. A move spends two lives and the new spot brings one, so the lives fall by exactly one every time — and unlike the arms of a Brussels cross they are not replaced. Every move either cuts a face in two or joins two separate pieces of the drawing, and how many of each a game contains is up to the players, which is why the length is not fixed.

A conjecture from hand play

Sprouts was invented over tea and its outcome pattern was guessed from games played with a pencil. Computers have checked it far past where a person could go, and this site's own solver gives out at three spots — so the honest figure states the frontier it reaches rather than the number somebody else published.

history · Sprouts

Named alongside it

The objects these essays reach for when they reach for this one.

Brussels SproutsExhaustive searchSproutsCertificateComplexityEuler formulaFixed length gameImpartialIntractableNimNormal playOutcome class

All concepts