The first move is a link that is not there

A winning strategy that is a spanning tree states Lehman’s criterion for the Shannon switching game and checks it against a solver on every subgraph of a ten-link graph. The criterion is exact, and it answers exactly one question: whether Short, moving second, wins. A graph with two edge-disjoint spanning trees on some set of points holding both marks is a win for Short whatever Cut does first, and a graph without one is not.

That leaves a second question standing, and it is the one a player sitting down to a board actually faces half the time. Who wins when Short moves first? The earlier essay handles it in a sentence — Short moving first wins whenever Short moving second does, plus some further graphs — and the further graphs are where most of the interest is: on the ten-link survey, five hundred and two of the 1,024 subgraphs are won by whoever starts.

The answer turns out not to need a second criterion. It needs one more link.

A link Cut has to delete #

Take a switching graph and draw one extra link, straight from A to B. Now give Cut the first move on that larger graph.

Cut has no choice about what to do with it. If Cut deletes anything else, Short secures the new link on the reply, and A is joined to B by a secured link — the game is over and Short has won. So Cut’s first move is forced: delete the link from A to B. After that deletion the graph is exactly the original graph, nothing on it has been decided, and it is Short’s turn.

Short moving first on a graph is Short moving second on the same graph with a link from A to B added. That is the whole argument, and it is complete: the two games are not similar, they are the same sequence of positions with one forced exchange in front.

The bridge is the smallest graph on which this matters, and it earns its name. Two routes run from A to B, one through each of two middle points, and a rung joins the middle points — the Wheatstone bridge of every circuit diagram. It has five links and four points. Two edge-disjoint spanning trees on four points need six links, so no set of links on it passes Lehman’s test and Short moving second loses. Add the imaginary sixth link and every pair of points is joined: the complete graph on four points, which splits into two trees with nothing left over. So Short moving first wins, and whoever moves first on the bridge wins it.

The imaginary link is a tempo drawn as an edge. Everywhere else in this subject the value of having the move is a game in its own right — a star, an up, the incentive a move carries — and it is priced by comparing positions. Here the value of moving first is one link, and it is priced by asking the same yes-or-no question of a graph with one more edge in it.

Both questions, on every subgraph #

A one-sentence argument about forced moves is the kind of argument that is easy to state wrongly, so it is checked against play rather than trusted.

The check runs two computations that share nothing. The solver plays the game out: a position is the set of undecided links together with the partition of the points produced by what Short has already secured, since securing a link merges its two ends and deleting one removes it. Short has won as soon as A and B are in one part; Cut has won as soon as no route between them survives even if Short took every remaining link. It knows nothing about trees. The tree test knows nothing about play: it looks through subsets of the surviving links for one that holds both marks, has exactly twice as many links as its points minus one, and splits into two spanning trees of those points.

Each subgraph is solved twice, for Short moving second and for Short moving first, and tested twice, once as drawn and once with the link from A to B added.

1,384 subgraphs, and the two pairings agree on all of them. The survey is a check on the solver and the tree test rather than on the mathematics — the argument above is a proof, and a proof does not become truer by being run on the complete graph on five points — but it is a check with teeth. A tree test that accepted a subset one link short, or a solver that let Cut’s first move be free, would disagree with the other column on the bridge within its first handful of subgraphs.

The row for five points all joined repeats the earlier essay’s census — 71 subgraphs won by Short whoever starts, 502 by whoever moves first, 451 by Cut whoever starts — and the difference is where the numbers now come from. There they came from playing each subgraph out. Here they come from two tree tests and no play at all.

Three outcomes from two questions #

That last observation is worth having in a form a reader can check by looking, because it says something about switching games that is not true of games in general.

The outcome class of a switching game is two bits, and each bit is a property of a graph. Pass both tests and Short wins whoever starts. Pass only the one with the imaginary link and whoever moves first wins. Fail both and Cut wins whoever starts.

The fourth row, passing on the graph and failing with the link added, is empty, and it has to be. A link added to a graph can only help Short: every set of links that passes the test without it still passes with it. That is the same monotonicity strategy stealing rests on — an extra stone of one’s own never hurts — and in this game it has a visible consequence. It rules out the outcome where the player to move loses.

In the vocabulary of who moves last, the three classes are an L-position, an N-position and an R-position, with Short as Left, and the missing P-position is the one this game cannot have. A position where having to move is fatal needs a move that hurts the mover, and in a switching game no move hurts its maker: securing a link never harms Short and deleting one never harms Cut. There is no zugzwang anywhere in the game, which is exactly why a blocked pawn ending looks nothing like it.

For a normal-play game the class of a position is found by searching both players’ replies, or by computing a value and comparing it with nought. For a switching game it is found by asking a graph two questions, and neither question is about a move.

Where the first move comes from #

The equivalence says whether Short moving first wins. It does not, by itself, say what to play — Cut’s forced deletion of the imaginary link is a move in the larger game, and Short’s actual opening in the real game is the reply to it. The trees of the larger graph supply that reply, and the reasoning is short enough to follow on the bridge.

Two spanning trees of the larger graph are drawn blue and red. One of them, blue, holds the imaginary link. Take the imaginary link out of blue and blue falls into two halves, one holding A and one holding B, because a tree with one link removed is two trees. Red spans the same points, so somewhere red crosses between blue’s two halves.

Secure any red link that crosses. Blue, less the imaginary link, is now joined up again through the secured link, since securing a link merges its two ends. Red, less the link just secured, is still connected for the same reason. The two are disjoint, both span the points, and it is Cut’s turn — which is precisely the position Lehman’s criterion says Short wins.

On the bridge, blue is the imaginary link with the rung and one link into B; removing the imaginary link leaves A on its own and everything else on the other side. Red is the two links out of A and one link into B. The red links crossing from A’s side to the rest are the two links out of A, and those are the two first moves the trees name. Either one wins.

Five winning openings, and one that leads nowhere #

A graph where every opening wins does not test whether the trees pick well. A graph with a bad opening in it does, and the smallest one the survey turns up is the bridge with a spur: one more link, hanging off A into a point that leads nowhere.

Six openings, five of which win, and the one that loses is the spur. That is what a reader would guess and it is right for the reason a reader would give: securing a link into a point with no other link changes nothing about any route from A to B, so it is equivalent to passing, and passing on the bridge hands Cut the first move on a graph whoever-moves-first wins.

The trees name A–1 and A–2, both winners. They do not name the other three winners — the rung, and the two links into B — and it is worth seeing why those win too. Securing the rung merges the two middle points, and the bridge collapses into a path from A to B with both of its links doubled, which is the clearest case the earlier essay draws: two edge-disjoint routes and a partner for every link. The trees cannot see that opening because the rung is in blue, and the construction only ever reaches for red.

So the construction is sound and incomplete: it names a winning move whenever there is one, and never a losing one, and it does not list the winning moves. The footer of the figure makes the first half a count rather than an impression. Over the 502 subgraphs of the complete graph on five points that the first mover wins, there are 2,674 openings, 1,654 of them winning; the trees name 550, and every one of the 550 is among the 1,654.

That is the right shape for a strategy to have. A player needs one good move from each position, not a catalogue of them, and the construction supplies one from a pair of trees that can be found without looking at the game.

The rule, played against every reply #

A construction that names the first move and then hands Short over to a criterion is only half a strategy until the criterion’s own strategy has been played. The earlier essay states it — whichever tree Cut damages, Short repairs with the other — and it is stated for trees; after a few exchanges the sets Short holds are no longer trees of anything obvious, because secured links have merged points.

So the rule is stated in the form that survives that, and played out in full. Short holds two disjoint sets of undecided links, each of which connects its points once secured links are merged. When Cut deletes a link that disconnects one set, Short secures a link of the other set crossing the break. When Cut’s deletion disconnects nothing, Short secures any link of the set it came from.

840 lines, all won by Short, and not one of Short’s 1,084 replies was searched for. The count is the number of distinct games Cut can make Short play against the rule, because every one of Cut’s deletions is tried at every point, and a single line ending with A and B apart would have stopped the enumeration at that line.

It is worth setting that number beside a strategy is not a certificate, where a winning strategy for three heaps of Nim is written out as a tree of 56,167,022 nodes. The switching strategy here is also, played out, a tree — 840 leaves of it — and it does not need to be written down at all. It is a pair of link sets and a sentence, and the sentence regenerates any branch on demand. That is the difference what solved means draws between a strategy that is a database and a strategy that is a rule, arriving on a small graph with the database size measured.

The first-mover version is the same rule after one named move. On the bridge Short secures A–1, the two remaining sets are blue less the imaginary link and red less A–1, and Cut’s seven possible lines all end with A joined to B. The bridge is small enough to check by hand, which is a good reason to have drawn it: after A–1 is secured, A and point 1 are one point, joined to B directly and through point 2 by two disjoint routes, and Cut cannot cut both.

What a tempo costs when it can be drawn #

The surprise in all of this is not that a first move is worth something. It is that its worth has a shape.

In the theory of sums, the difference between moving first and moving second is exactly what distinguishes the four outcome classes, and it is measured by values — comparison is a search precisely because the extra move interacts with everything else on the board. A position where the first move is decisive is a hot position or a nimber or an infinitesimal, and which of those it is changes what happens when it is added to something.

A switching game has no such arithmetic, and it turns out not to need one. The tempo is a single link placed between the two marks, and whether that link makes the difference is a question about the graph with the link in it. There is no need to know what the tempo is worth in any other company, because the question is never asked in any other company: the whole board is one graph, and a switching game is not played as a sum of switching games.

The nearest thing elsewhere in this collection is a pass drawn as a component, where a shared pass in Nim is modelled as a heap of one, and the modelling works or fails depending on whether the pass is a move in the game or a change to it. The imaginary link is the clean version of that idea. It is a move in the larger game — Cut really does delete it — and it changes the smaller game in exactly one respect, which is who moves next.

What two trees do not say #

They do not list the winning moves. The construction names links that cross the gap the imaginary link leaves, and the bridge with a spur has three winning openings that cross no such gap. A player using only the trees plays well; a reader wanting to know how many good moves a position holds has to solve every opening, as the figure does.

They do not rank moves or say how long Short needs. Every line on the complete graph on five points ends within five exchanges, and that bound is read off the enumeration rather than off the trees. Two winning openings on the same graph can differ in how quickly they win, and nothing here distinguishes them.

Nor does the tree test drawn here scale. It looks through subsets of links and splits of those subsets, which is exponential in the number of links and is adequate on ten. Lehman’s own route finds the trees by matroid union in polynomial time, and the imaginary link costs that route nothing — it is one more element — but the polynomial algorithm is not what these figures run, and a graph of a hundred links is beyond them.

And the graphs are small. Seven base graphs, the largest with ten links, and every subgraph of each. The equivalence itself needs no evidence, since its proof is the forced deletion; what the survey establishes is that two independent computations agree with it everywhere they can reach.

The rule this depends on #

A switching game ends when A and B are joined or separated, and the winner is whoever did it. That is a goal, not the last-move convention the rest of this subject is built on, and the imaginary-link argument uses the goal twice.

It uses it once when Cut’s first move is forced: Short winning the instant the marks are joined is what makes ignoring the imaginary link fatal for Cut. Under a rule where a player won by making the last move, securing the link from A to B would be one move among many and Cut could let it go.

And it uses it again when the fourth outcome class is ruled out. A goal that each player works towards, with no move ever harming its maker, is what makes an extra link harmless to Short — and that monotonicity is what empties the fourth row. Take the goal away and the equivalence goes with it, which is the sense in which this essay is about switching games rather than about games.

Still open: what Cut’s side looks like #

Everything above is written from Short’s side. Cut appears only as the player whose moves are enumerated, and the two tests are tests for Short’s trees.

Cut deserves a criterion of its own, and on a graph that can be drawn without crossings it has one that uses the same test on a different graph — the dual, whose points are the faces of the drawing and whose links cross the original links one for one. Deleting a link in one is securing the crossing link in the other, so Cut on a graph is Short on its dual. The game in the box, Bridg-It, is two dot grids that are each other’s duals, and that is the reason its first player wins. What that duality buys, where it stops, and whether a non-planar graph has anything like it are the next questions this game poses.