Combinatorial Game Theory
who wins, and by how much
Concept

The Shannon switching game — where it appears

A game on a graph with two marked points, in which one player secures links and the other deletes them until the points are joined or cut apart. Who wins is a property of the graph rather than of the play — a pair of edge-disjoint spanning trees, looked for on the graph and on the graph with a link between the marks.

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

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 a claim 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 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 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 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.

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.

applied · Switching A win with no pairing. A graph of ten points, each with three neighbours, in which Short claiming points and Cut deleting them, Short wins moving second. No pairing of the eight contested points puts a whole pair inside all 10 minimal separating sets; the closest misses {e, f, h}, the three neighbours of A.

Two neighbours keep a pairing, three lose it

In the switching game on points, Short wins moving second by a pairing when every smallest set of points that cuts A from B holds both points of some pair. On every graph of seven points — 971,104 of them — every Short win has one, at every degree. In random link games, where each contested point has two neighbours, every win has one too, although the winning strategy follows trees that change as the game goes. The first wins with no pairing appear at nine points with four neighbours and at ten points with three: a cubic graph Short wins whoever moves, which no fixed set of answers explains.

applied · Switching A pairing that changes once. The ten-point cubic graph that no pairing certifies, drawn four times, once for each plan of a one-change certificate: after Cut's first deletion Short claims one point and then answers by a fixed pairing. Deleting c: claim d, pair e–f, g–i, h–j. Deleting d, e, g, i, j: claim c, pair f–h. Deleting e, f, g, i, j: claim h, pair c–d. Deleting h: claim f, pair c–g, d–i, e–j.

A pairing that changes once

The cubic ten-point graph is a win for Short that no fixed pairing explains, and the full strategy that does explain it is a tree of 68 decisions. One change is enough: after Cut's first deletion Short claims a stated point, and from then on a fixed pairing of what is left holds every cutting set. Four such plans, eight pairs between them, answer every opening. Of the 23 pairless wins in the samples, 21 need one change and two need a second, and in both the second is a forced claim. Unless the hard problems collapse, no fixed number of changes can be enough for every graph.

applied · Switching Three winners, none of them teachable. A graph of ten points on which Short, claiming points to join A to B while Cut deletes them, wins moving second. Three pairings of the contested points win, each holding one whole pair in every one of the six minimal separating sets; one, ce df gh ij, is drawn. No weighting of the separating sets makes any winning pairing outscore every losing one.

Two losers that average to a winner

On Hex boards to 6 × 7, a machine that weighs the opponent's winning sets could be taught every winning pairing except one, which another single winner covered. Ville's alternative allowed a second way to be out of reach — covered only by a mixture — and the switching game on points, where winners are many, is where it turns up. None in all graphs of seven points or in 4,000 of eight; 35 covers at nine and ten points. Every one is the even average of two losing pairings, and on six graphs Short wins and no weighting can teach the machine any winning pairing at all.

history · Machines

Named alongside it

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

CertificateExhaustive searchStrategyCounterexamplePairing strategyCriterionIntractableHexOutcome classPartitionBridg-ItComplexity

All concepts