A point with three neighbours

Three essays have taken the Shannon switching game apart and each one found it tame. A winning strategy that is a spanning tree settles Short moving second by a pair of trees; the first move is a link that is not there settles Short moving first by the same test on a graph with one more link; Cut is Short on another graph settles Cut’s side by the same test on the dual. Every question the game asks is answered by looking for trees, and trees can be found quickly.

All three are about links. Short secures a link, Cut deletes one, and a tree is a set of links.

Hex is not played on links. A stone goes on a cell, and a cell of the Hex board is a point of a graph — joined to its six neighbours — rather than a link between two points. The switching game played that way has Short claiming points and Cut deleting them, with A and B fixed at the ends, and it is the game Hex is an instance of. The question is what survives the move from links to points, and the answer is: the game, and nothing that settles it.

A point in the middle of every link #

The first thing worth knowing is that the point game is not a different game from the link game. It is a larger one, with the link game inside it.

Take a switching graph and put a new point in the middle of every link. Hand the old points to Short in advance — they cannot be taken, and they only ever matter through the links that touch them. Now play the point game on the new points.

Claiming a middle point is securing its link, and deleting it is deleting the link. A route from A to B through claimed points is a route through secured links, with the old points free; a route destroyed by a deleted middle point is a route destroyed by a deleted link. Nothing else can happen, because nothing else is contested.

So the link game on any graph is the point game on its subdivision. And the subdivision has a shape that is easy to state: every contested point has exactly two neighbours. A link has two ends, and its middle point is joined to both and to nothing else.

That is the whole of the relationship. The link game is the point game with one restriction — every point the players fight over has two neighbours — and Hex is the point game without it, since a cell in the middle of a Hex board has six.

Every subgraph, as both games #

The identity is a sentence long and checked anyway, by the two computations it relates.

416 subgraphs, and the two games agree on every one, both ways round. The two solvers do not share their move rules — one merges the ends of a secured link, the other adds a point to a set and asks whether a route of claimed points exists — so the agreement is a check on both, and on the translation between them.

The check does not strengthen the argument, which needs no strengthening. What it establishes is the thing that is easy to get wrong in practice: that a point Short already owns really does change nothing, and that the old points of a subdivision have been handled as the argument handles them rather than left open to be deleted.

The same picture, fought over differently #

Because the relationship runs through the subdivision, a point game and a link game on the same drawing are not related at all, and it is worth seeing how unrelated.

Four of the six give a different verdict. Three paths between two points is Cut’s whoever starts as a link game and Short’s whoever starts as a point game: with three inner points each on its own route, Cut deletes one point and Short claims another, and that single claim is a whole route. The bridge goes from whoever-moves-first to Short’s whichever way, because its two inner points are each a complete route on their own.

In all four the change is toward Short, and on these graphs the reason is visible. A claimed point secures every link through it at once, and the graphs here are small enough that one point is very often a whole route. That is a fact about small graphs rather than about points — on a large board a single point is a small fraction of any route — and nothing here suggests it generalises. What does generalise is the negative finding: the verdict on a drawing depends on what the players are fighting over, and knowing one game tells nothing about the other.

What the count was doing #

The criterion for links is a count with an arrangement condition attached. A graph passes when some part of it has twice as many links as its points less one, arranged so that the links split into two trees — and a condition that looks like a search is, underneath, the statement that every way of carving the points into groups leaves enough links running between the groups. It is, in the end, counting.

The natural count for the point game is how many routes from A to B share no point — Menger’s number, the largest set of routes a single deleted point can damage only one of. It is the obvious analogue of two edge-disjoint trees, and if the point game has a counting criterion, this is where it should show up.

The two ends of the table behave. With no route Cut has already won, 2,504 times out of 2,504. With exactly one, some point lies on every route, whoever moves first can take it, and Short never wins moving second — which is what the link game’s criterion would predict, since one route is not two.

Two routes contain all three outcomes. 3,480 graphs are Short’s whoever starts, 1,824 go to whoever moves first, and 48 are Cut’s whoever starts, and those 48 have two routes from A to B that share no point. Short, moving second on them, is never allowed to finish either.

The rows for three and four routes are all Short’s, and that is an artefact rather than a finding. On six points there are only four inner points, so three separate routes are three routes of one or two points each, and Cut runs out of deletions. A graph on twenty points with three long separate routes is a different matter entirely, and nothing on this page measures it.

Same counts, opposite winners #

A count that fails on 48 graphs out of 5,352 might still be a count with a correction attached. The way to find out is to look at the smallest failure and ask what the correction would have to see.

Six points, six links, two separate routes, on both sides — and opposite winners. On the left, A is joined to four points and two of them go on to B; each route from A to B passes through exactly one contested point. Cut deletes one of the two and Short claims the other, and the claim is a whole route. On the right, each route passes through two points, and the two routes are drawn crossing between them without sharing a point. Cut deletes a point on one route, Short claims a point on the other, Cut deletes the second point of that route, and Short’s claim joins A to nothing.

So what the count misses is length, and length is exactly what the link game cannot see. In the link game a route of length five and a route of length one are both just a place a tree can run; the criterion counts links against points, and a long route contributes as many points as it does links. In the point game every contested point on a route is one more point Cut can delete, and a route of two points is a route Cut can break with its reply.

It would be natural to try adding length to the count. Nothing here tries, and the reason is not modesty: the complexity result two sections below says that no rule of this kind — nothing computable in polynomial time, however clever — can decide the point game unless a famous inclusion between complexity classes is an equality.

Hex is this game, on a board that can be drawn #

Put a point on every cell of a Hex board, join each to its six neighbours, join the top row to A and the bottom row to B. A stone of the colour joining top to bottom claims a point; a stone of the other colour deletes one, since that cell can never be on the first player’s route. The point game on that graph is Hex.

It is exactly Hex rather than approximately, and the reason is the no-draw theorem the theorem that names no move rests on. In Hex the second player wins by building a left-to-right chain; in the point game Cut wins when no top-to-bottom route survives. On a Hex board those are the same event, because a filled board contains exactly one of the two chains — so Cut’s goal and the second player’s goal coincide, and the point game needs no second colour at all.

The winning first cells agree with a direct Hex solve on all nine. Five of nine win on 3 × 3, exactly as the solve in the essay about strategy stealing finds, and the point game finds the same five without knowing that the board is hexagonal. On the 2 × 2 board the two agree on all four cells as well.

The degrees printed beside the board are the reason Hex is where the difficulty lives. A middle cell has six neighbours. A cell of a subdivided link game has two.

Why the trees cannot be rescued #

The link game’s criterion is fast for a reason, and the reason is precisely what points do not have.

A set of links with no cycle is a forest, and forests have an exchange property: a smaller forest can always be grown from a larger one by borrowing a link that joins two of its pieces. That property is what the packing in the previous essay uses — offer a link to a forest, and if it will not fit, swap it for one that will — and it is what makes finding two disjoint trees on the Bridg-It board of size eight a matter of swaps, on a board where trying subsets would mean trying 2¹¹⁴ of them.

Points have nothing comparable. A point lies on many routes at once; deleting it can break several of them; claiming it can complete several. There is no notion of a “forest of points” that grows by exchange, because the structure a claimed point belongs to is not a set of independent pieces but a web of routes that share it.

And the absence is not merely of a known method. The switching game on points is PSPACE-complete — Even and Tarjan proved it in 1976 — and Hex itself, played on its own planar boards, was shown PSPACE-complete by Reisch in 1981. Hard, proved sets out what such a result says and what it does not: it is a statement about the family of all boards, not about any single one, and it says that deciding the family is as hard as deciding who wins any game whose length is bounded by a polynomial in the size of its board. A polynomial-time criterion for the point game would collapse that class into polynomial time, which almost nobody expects.

How hard is it puts the same fact the other way up: every theorem about who wins stays true at any size, and the answers stop being reachable long before the boards get interesting. The point game is a clean instance of that gap, because its link-game special case shows what reachable looks like — a certificate made of two trees, the kind of short proof a strategy is not a certificate says a game question usually does not have. The point game has no such certificate that anyone knows, and the complexity result says why none is expected: a short certificate for every win would put the problem somewhere the alternation it is made of is not expected to fit.

So the move from links to points is the step that costs the criterion. Not a step among several, and not a step that a cleverer count might undo: the restriction that every contested point has two neighbours is the whole difference between a game decided by counting and a game as hard as games get.

One word, twice #

The same shape has already turned up once in this collection, in a different game, and the parallel is exact enough to be worth drawing.

A token on a graph is geography: move a token along a link to a point not yet visited, and lose when stuck. On a directed graph the game is PSPACE-complete. Take the arrows off and it is decided by a maximum matching — the first player wins exactly when every maximum matching covers the start — which is a polynomial computation with a certificate anybody can check.

The switching game has the same two faces. On links it is decided by a pair of trees, found by exchange, checkable by anyone handed them; on points it is PSPACE-complete. In both games the easy version has a combinatorial structure with an exchange property — matchings in one, forests in the other — and the hard version is what is left when a single word of the rules removes it: directed for geography, points for switching.

That is the surprise in this essay. Two games with nothing in common at the level of play — one a walk, one a race to connect — both fall on the same side of the same line for the same kind of reason. The criterion was never really about the game. It was about whether the objects the players take have the property that lets a greedy exchange argument run.

What the census cannot say #

Six points is very small. The census covers every graph on six points and nothing bigger. The row claiming three routes always go to Short is a statement about routes of one or two points and nothing more, and the 48 graphs where Cut wins with two routes are the smallest witnesses rather than a sample of anything.

The point game is solved exhaustively here, and only because the boards are tiny. Hex as a point game reaches 3 × 3 in this form; the essay about strategy stealing takes Hex to 4 × 4 with a solver built for Hex, at six and a half million nodes, and 5 × 5 is out of reach of both. Nothing here shows the difficulty; the hardness result says it exists, and the census only shows that the obvious count does not capture it.

And PSPACE-completeness is about families. It says nothing about 11 × 11 Hex specifically, and it does not say every point game is hard — the subdivided link games are point games, and they are easy. What it says is that no method fast on the whole family is expected, which is a statement about methods rather than about any board in front of a player. What solved means keeps the distinction a player needs: a particular board can be solved — by search, by a database, by an argument — without the family having a formula, and every one of those senses has been used on Hex boards small enough to reach.

The rule this depends on #

Both games are won by connecting A to B, and the correspondence between them depends on it. A route of claimed points and a route of secured links are the same object only because the winning condition is a route. The Hex translation depends on it again, through the no-draw theorem: Cut’s goal and the second Hex player’s goal coincide only because a filled planar board contains exactly one chain.

What does not depend on it is the complexity. Geography is a last-move game and switching is a goal game, and both have an easy form and a PSPACE-complete form separated by one word. The line between them is drawn by the structure of what is being taken, not by how the game ends.

Still open: where between two neighbours and six #

The link game is the point game at two neighbours per contested point, and Hex sits at six. Nothing here says where between them the criterion stops existing.

A point game in which every contested point has three neighbours is already outside the reach of trees — the pair above has contested points with two and three — but it is not known from anything on this page whether such games are as hard as the unrestricted family, or whether some intermediate structure, weaker than a forest and stronger than nothing, still lets a count decide them. The planar case is the one Hex asks about, and for Hex the answer is already in: hard. For graphs with a bound on how many routes a point may lie on, the question is open here.