Combinatorial Game Theory
who wins, and by how much
Concept

Euler formula — where it appears

The relation between a planar drawing’s vertices, edges and faces, V − E + F = 2. It is what turns the length of a game played by drawing curves into a count rather than an observation, and it is why Brussels Sprouts has a closed form and Sprouts does not.

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

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 How far a plain search gets. An exhaustive search of Sprouts and Brussels Sprouts, run on this site, with the number of positions each size costs. Sprouts settles at three spots and Brussels Sprouts at two crosses; the published results on Sprouts go to forty-seven.

What computing further has bought

Sprouts has been searched harder and longer than almost any game, and the period-six pattern has survived every extension. This site's own exhaustive search settles three spots; the published results reach forty-seven, and the gap is not a gap in hardware — the gentler of the two measured growth factors puts forty-seven spots at ten to the hundred and twenty-fifth positions. Beside it sits Brussels Sprouts, which has five million positions holding a choice and not one choice that changes who wins.

history · Sprouts The Bridg-It board of size 3, both players at once. A Bridg-It board of size 3: blue dots in 4 rows of 3, red dots in 3 rows of 4, interleaved. Every bridge blue can usefully build is drawn in blue and every bridge red can usefully build in red, and each blue bridge crosses exactly one red one. Blue's switching graph and its planar dual have the same numbers of points and links, because the dual is red's board turned a quarter.

Cut is Short on another graph

Everything proved about the switching game is proved from Short's side, and Cut appears only as the player whose moves get enumerated. On a graph drawn without crossings Cut does not need a theory of its own: deleting a link is securing the link that crosses it in the dual, so Cut's game is Short's game on a different graph. Bridg-It is the board that is its own dual — one link short of two trees at every size, which is why its first player wins.

applied · Switching

Named alongside it

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

CertificateExhaustive searchBrussels SproutsComplexityIntractableOutcome classPeriodicitySproutsCriterionEnumerationPairing strategyPlanar map

All concepts