Combinatorial Game Theory
who wins, and by how much
Generator

a path with every link doubled: the criterion and the game

a path with every link doubled: the criterion and the 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 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.

4 essays call switch-graph. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

Where it is called

Changing this generator changes every one of these figures.

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. Out in the world

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.

 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. Out in the world

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.

 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. Out in the world

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.

 A bridge circuit, with a point on every link. The switching graph drawn as a bridge circuit, with a new point in the middle of every link in green and the original inner points in blue, already belonging to Short. Played as a game on the green points it gives the same verdict as the original game on links, because claiming a middle point is securing its link and deleting it is deleting the link. Out in the world

A point with three neighbours

The switching game on links is settled by counting — enough links, arranged as two trees. Played on points instead, it is the game Hex belongs to, and the count is gone. The link game turns out to be the point game in which every contested point has exactly two neighbours; give one a third, and two graphs with the same points, the same links and the same number of separate routes can have opposite winners.

The whole library · The position index · The figures that play back