Combinatorial Game Theory
who wins, and by how much
Concept

Toppling dominoes — where it appears

A row of blue and red dominoes, each player toppling one of their own to the left or the right and taking everything it falls on. Its positions are strings over two symbols, which makes it the cheapest partizan ruleset here to sweep exhaustively.

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

What the third colour reaches. Every row of Toppling Dominoes up to 7 long, over two colours and over three, with the number of distinct values each set of rows carries. Each value was computed by the recursion; the last column is the count of values three colours reach that two do not, cumulatively.

How long a row a value needs

Add a third colour that either player may topple and a row of seven dominoes reaches 1,047 distinct values where two colours reach 149. That makes the length of the shortest row worth a value into a measure of the value's complexity — one a reader can hold in their hand — and it is not the birthday: 1↑ is born on day three and needs seven dominoes.

positions · Toppling dominoes The yield, four sizes further. Toppling Dominoes rows to twelve, with the count of values not seen at any smaller size and the share of rows that is.

The mirror was the floor

Toppling Dominoes' share of genuinely new values had fallen from one to a half over eight sizes, and the rung below could not tell a floor from a slow fall. Four more sizes settle it: the distance above a half halves every two sizes. And the half is not a shortage of values but a symmetry — a row played from the other end is the same game, and the ruleset is as injective as that allows.

values · Realisability Same group, three different yields. The rulesets with a trivial symmetry group, which the conjecture predicts must all have a yield of one.

Three groups, and three yields

The conjecture was that each ruleset's yield tends to the reciprocal of its symmetry group's order. Three rulesets have a trivial group and predicted yields of one; they measure 1.000, 0.531 and 0.204. And every colliding value in Push and Shove — all 175 of them — has two rows no symmetry relates.

values · Realisability Every domino Left can topple in LRRL. A row of dominoes, blue for Left and red for Right, and each of the mover's options below it. Toppling a domino leftward removes it and everything to its left; rightward removes it and everything to its right. The value under each option is what the game recursion returns for the row that survives.

A recipe instead of a census

Counting a thousand values in seven dominoes suggests Toppling Dominoes reaches every short game, and a count is not a construction. The obvious construction — lay the two options either side of a Left domino and a Right one — is exact on day one, right on a third of day three, and cannot be applied to nine in ten values at all.

positions · Toppling dominoes

Named alongside it

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

EnumerationRealisabilityBirthdayCanonical formValueExhaustive searchHackenbushPartizanSymmetryClobberConstructionCounterexample

All concepts