Combinatorial Game Theory
who wins, and by how much
Concept

Partition — where it appears

A splitting of a set into pieces, used here both for a board's regions and for the two trees a switching game's criterion asks for. The same word covers two different jobs here, and neither is the number-theoretic sense a reader may be expecting.

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

A golden ratio in a table that never mentions it. Grundy values for Wythoff's game, computed by the mex rule alone — a queen moving left, down or diagonally toward the corner, and whoever cannot move loses. The circles are Wythoff's 1907 description of the losing positions, which came thirty years before any of this machinery: the pairs formed from the golden ratio. They land on the zeros exactly. Nothing in the computation knows about φ and nothing in Wythoff's argument knows about Grundy values.

A golden ratio thirty years early

Wythoff described the losing positions of his game in 1907 with an argument about partitions of the integers, and no Grundy value anywhere in it. The theory that arrived thirty years later computes the same positions — and has never produced a closed form for the values, which the older argument had for the zeros from the start.

history · Wythoff's game a path with every link doubled: the criterion and the game. A Shannon switching graph with the two marked vertices in gold. Short secures links and Cut deletes them; Short wins by joining the two marks. Lehman's criterion says Short wins moving second exactly when some subgraph holding both marks splits into two edge-disjoint spanning trees — drawn here in blue and red where one exists. The verdicts beside the graph come from playing the game out, and the criterion is computed without looking at the game at all.

A winning strategy that is a spanning tree

The Shannon switching game was sold in a box in 1960 and solved in 1964, and the solution is not an assertion that somebody wins. It is a property of the graph anybody can check, and the strategy falls straight out of it — whichever link the opponent cuts, take its partner in the other tree.

applied · Switching The same position, two conventions, two winners. Three-player Nim with the last counter winning. The two columns differ only in what a player does when they cannot win themselves, which is a question the rules do not answer — and the answer decides who wins.

Three players and no answer

Every theorem here is about two players, and the reason is not convenience. With two players the game is zero-sum, so 'play well' needs no further explanation. Add a third and the winner of a Nim position becomes a fact about the convention: two reasonable ones disagree on 56 of the 71 positions swept. The one question no convention touches — can a player force a win against the other two together — is answered 'nobody' in 65 of the 71.

limits · Multiplayer A bridge circuit, with a link that is not there. The switching graph drawn as a bridge circuit, with an imaginary link from A to B dashed in gold. The graph alone does not split into two edge-disjoint spanning trees, so Short moving second loses; with the imaginary link it does, drawn in blue and red, so Short moving first wins. The green links are the links of the red tree that cross between the two halves the blue tree falls into without the imaginary link — the first moves the trees name.

The first move is a link that is not there

Lehman's criterion answers one question about a switching game — who wins when Short moves second. The other question has the same answer asked of a different graph: add one link from A to B, and Cut is forced to spend its first move deleting it. The trees of that larger graph then name Short's opening, and on every subgraph of seven graphs they name a winner.

applied · Switching

Named alongside it

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

Exhaustive searchOutcome classStrategyCertificateDeterminacyImpartialNimNormal playThe Shannon switching gameBackward inductionBeatty sequenceBridg-It

All concepts