The theorem that names a winner and no move

Hex is played on a rhombus of hexagons. One player joins the top edge to the bottom, the other joins left to right, and stones once placed never move. The first player wins, on every board, and here is the whole proof.

Suppose the second player had a winning strategy. The first player could place a stone anywhere, ignore it, and then follow the second player’s strategy as though the extra stone were not there — and an extra stone of one’s own can never hurt. So the first player would have a winning strategy too, and both cannot. Therefore the first player wins.

Four lines, every board size, no counterexample possible. And it does not tell anybody where to put a stone.

What kind of proof this is #

The magenta line is the hypothesis and it is the whole argument: an extra stone of one’s own can never be a disadvantage. Games where that is false are games the theorem says nothing about, and this site is full of them — every position with a zugzwang in it is one, and a blocked pawn ending is the extreme case, where having an extra move is precisely what loses.

That is why the argument applies to Hex and Chomp and not to Dots and Boxes, not to Nim, and not to a game where passing would be welcome. It is not a general method; it is a method for games in which more of one’s own material is never bad.

Where the moves come from #

The argument having produced nothing, somebody has to produce something. On a small enough board that somebody is a search.

Five of nine, and the five are not a shape the proof could have predicted: they are the anti-diagonal and its neighbours, the cells that lie on the shortest route between both pairs of edges at once.

Then the board grows by one square in each direction.

That is the shape of the problem. The argument’s reach is infinite and its output is empty; the search’s output is complete and its reach is four.

Three sizes is enough to see whether the answers have a shape, and just about enough to see that the shape is not stable.

That middle board is the reason nothing here is safe to extend. Two of the three sizes give a clean geometric rule and the third does not, which is exactly the evidential position a reader is in about size five: the rule that fits most of the data is not the rule.

The step the four lines skip #

The proof at the top is the version everybody quotes and it has a gap in it — a small one, closed in a sentence, and worth closing because the sentence is where the hypotheses actually live.

The first player places a stone anywhere and then follows the second player’s strategy as though the extra stone were not there. Follow that instruction and eventually the strategy will call for a move at a square the spare stone is already sitting on. The strategy was written for a board without it, and it has no idea the square is taken.

The patch is to play another arbitrary move and carry on, letting the newly placed stone be the spare from then on. The imaginary board — the one the strategy thinks it is playing on — is always the real board minus exactly one of the first player’s stones, and the argument maintains that invariant to the end.

Two things have to be true for the patch to work, and both are properties of the game rather than of the proof.

There must always be somewhere to put the spare. The stolen strategy is being followed on a board that is one stone emptier than the real one, so whenever it has a move available the real board has at least one free square besides. Hex fills and ends; Chomp shrinks and ends; a game that could run out of arbitrary moves while the imaginary game continued would break the induction here rather than anywhere else.

And stones must not move. The invariant is that the real position is the imaginary one plus a stone of the first player’s. In a game where a piece can be moved or captured the real and imaginary boards can diverge in ways no single extra stone accounts for, and the correspondence the whole argument is carried on collapses.

So the four lines are four lines only if the reader supplies the bookkeeping. It is not a flaw — the bookkeeping goes through — but it is where the argument’s conditions are hiding, and a reader who has only seen the short version has not seen why the theorem does not apply to chess.

What the hypothesis actually says #

The essay marks an extra stone of one’s own can never hurt as the load-bearing line, and it is worth stating in the form that makes its failures obvious.

The requirement is monotonicity: for the player doing the stealing, adding one of their own stones to any position never turns a win into a loss. Not “usually helps”, not “helps on average” — never hurts, in every position of the game.

That is a strong condition and most games fail it. Every position with a zugzwang in it is a counterexample by construction, since there the whole content of the position is that having something extra to do is fatal. So is any scoring game where a move can be forced to give something away, and so is Dots and Boxes, whose entire endgame is about avoiding the obligation to act.

And note which way the monotonicity has to run. The argument steals the second player’s strategy and hands it to the first, so what it needs is that a first-player stone never harms the first player. It says nothing whatever about the second player, and there is no symmetric version to run in the other direction — which is why the theorem always concludes “the first player wins” and never anything else. A game where a spare move helped the second player and hurt the first would simply not be a game this argument speaks about; there is no dual theorem waiting to be stated.

That asymmetry is the reason the theorem is so cheap. It extracts one bit from a symmetry of the rules, and one bit is all a symmetry of the rules can be expected to give.

Why it cannot be made constructive #

It is natural to hope that the argument is merely written non-constructively and could be repaired. It cannot, and the reason is structural rather than a matter of effort.

The proof is a reductio. It assumes a strategy for the second player, builds a strategy for the first player out of it, and derives a contradiction. The object it constructs is therefore built from a thing that does not exist, so nothing survives the contradiction — there is no partial construction left over, no first move implied, no smaller claim rescued.

Compare with a proof that does yield a move.

In Nim, the argument that a position with nim-sum zero is lost is also about a symmetry — but the symmetry is displayed: it says which heap to reduce and by how much, because the argument is about repairing a parity and repairing is an action. Bouton’s proof and Nash’s differ in exactly that respect, and it is the difference between a criterion and an existence claim.

The mirroring argument that solves two-heap Nim is closer still to stealing and is fully constructive: keep the heaps equal, and the move that does it is named by the position. Every game has a negative is the general form, and the reason it produces moves while stealing does not is that the mirror is an actual map from the opponent’s moves to the mirroring player’s. Stealing has no such map; it has a map from a hypothetical strategy to another hypothetical strategy.

Chomp, and the needle #

Chomp is a bar of chocolate. A move takes a square and everything above and to the right of it; the square at the bottom left is poisoned and whoever eats it loses. The same stealing argument applies — a bigger bite is never worse than a smaller one, in the relevant sense — and proves the first player wins every rectangle bigger than a single square.

The striking column is the count of winning openings. Every rectangle in range has exactly one. A 5 × 5 board offers twenty-four moves and precisely one of them wins; a 5 × 4 offers nineteen and precisely one wins.

So the argument says the first player wins, and the truth is that there is a single needle in a haystack that grows quadratically with the board. For square boards the needle is known — take everything except the bottom row and the left column, leaving an L — and for a general rectangle nobody has a description of it.

An existence proof is not a small thing #

It would be easy to read all of the above as a complaint, and it is not one.

The stealing argument settles a question that exhaustive search settles for four board sizes, and it settles it for all of them, in a paragraph, with no computer. What it produces is a fact about an infinite family, and the fact is not obvious: it is entirely conceivable a priori that Hex favours the second player on some board sizes and not others, and the argument rules that out at a stroke.

It also stands on something it does not mention. Zermelo’s theorem says a finite game with no chance is decided before anybody sits down: one of the players can force a win, or both can force a draw. That leaves three outcome classes and stealing can only rule out one of them, so the argument would be stuck at the first player does not lose were it not for a second fact about Hex — it cannot end drawn. A filled board always contains a winning connection for exactly one side, which is a topological property of the hexagonal adjacency rather than anything about play, and it collapses the outcome classes to two before the stealing argument starts. Stealing then picks between the two, and having picked, it has said everything it is going to say.

That no-draw claim is checked here rather than cited.

That is a small check with a large job. The solver never tests for a draw: it plays until the board is full and asks which side connected, and the reason it is entitled to is exactly the two zeroes above.

The other kind of proof #

Set this beside a proof of the opposite kind, on a game of the same era.

The Shannon switching game was solved by Lehman in 1964 with a criterion that is a property of the graph rather than a claim about it: the second player wins exactly when some subgraph containing both marked vertices splits into two edge-disjoint spanning trees, and the strategy falls straight out of the pair — whichever link the opponent cuts, take its partner in the other tree. That is a winning strategy that is a spanning tree, and it is the constructive twin of this essay. Two games invented within a few years of each other, both about connection, both solved — and one solution is a paragraph that names nothing while the other is a criterion anybody can check and follow.

The difference is not that one field is more advanced. It is that Lehman’s game has structure the argument could get hold of, and Hex does not.

What a strategy would even be #

There is a further reason the gap does not close, and it belongs to the complexity field.

A strategy is not a certificate: the object that proves “the first player wins” is a subtree of the position graph, and subtrees are enormous. So even if somebody found the winning openings for Hex on a large board, writing down why they win is a different and much larger problem.

The sizes involved are the point. A strategy that certifies a win on a three-by-three board is already a large object, and it grows with the game rather than with the answer, because the answer is one bit and the certificate is a subtree. The stealing argument is a proof of a fact whose certificate nobody can hold.

So the position is this. Hex on the 11 × 11 board people play is a first-player win, proved. Nobody knows a winning first move. Nobody has a way of storing one if they found it. And the proof that it exists will not get any longer as the board grows.

What this costs the complexity field #

There is a reading of all this that belongs next door, in the field about what things cost.

A game can be decided — one player provably wins — and the winning move can be hard to find, and those are independent properties. Hex is the cleanest example on this site of the two coming apart completely: decided at every size by four lines, and the move unknown past four squares.

The general statement is how hard is it: a theorem about who wins is not a theorem about how to win, and the gap between them is where the whole complexity field lives. Hex on an n × n board is PSPACE-complete, so the gap is not an accident of nobody having tried — it is the expected state of affairs, and the existence proof is the only part anybody was ever going to get cheaply.

What is unusual about Hex is how far apart the two are. Most games on this site have either a theory that gives moves or no theory at all. Hex has a complete theory of who wins and no theory of how, which is a combination that requires the winning condition to be monotone and the position space to be enormous — and both are true of connection games in general, which is why the whole family behaves this way.

What the picture cannot show #

The boards drawn here are 2, 3 and 4 squares on a side, and nothing about them scales visually.

A reader looking at the 4 × 4 board sees four marked cells on the anti-diagonal and will reasonably guess that the anti-diagonal is the answer at every size. That guess is exactly the kind the essay is warning against, and here the warning is not hypothetical: the guess is already false at size three, which is one of the two sizes it was formed from. The argument that proves the first player wins says nothing whatever about where, and the three sizes that can be solved do not agree with each other.

The other thing not shown: how close the search came to finishing. The 4 × 4 solve took two and a third million positions and a second or so. The 5 × 5 board has 3^25 configurations before any pruning, and the growth from four to five is not a step to be taken on a laptop during a page build. That boundary — between “small enough” and “not” — is invisible in a picture of a board.

The surprise: the count of needles does not grow #

The Chomp column has a feature that is easy to read past, and it is the strangest thing in the essay.

Every rectangle in range has exactly one winning opening. Not a handful, not a fraction of the moves — one. And the number of moves grows: a 2 × 2 board offers three, a 5 × 5 offers twenty-four, a 6 × 6 offers thirty-five. The haystack grows and the needle count stays at one.

That is not what a random game looks like. In a game where positions were scattered arbitrarily between wins and losses, roughly half the openings would win, and the count would grow with the board. Chomp’s does not, which says the P-positions of Chomp are extremely sparse and extremely structured — there is essentially one way to hand the opponent a lost position at each size, and no redundancy at all.

Hex behaves the other way: two of four at size two, five of nine at size three, four of sixteen at size four. The share falls but the count does not collapse to one, and the winning cells sit on a recognisable geometric feature at two of the three sizes.

Two games, one argument, and two completely different answers to “how many winning moves are there” — which is a reminder that stealing tells nothing about the structure of the win either. It is a statement about one bit of one position, and everything else has to be found.

The comparison also says something about why Chomp’s needle has resisted description. A single winning move per size means the P-positions form a very thin set, and thin sets are exactly the ones with no simple characterisation: a period is a proof works when the losing positions fall into a pattern that repeats, and there is no evidence that Chomp’s do. The sequence nobody has settled is the same shape of problem one field over.

The convention, named #

Both games here are normal play in the sense that matters, and it is worth saying how.

Hex has no notion of running out of moves — the board fills and somebody has connected — so its winning condition is a goal rather than the last-move rule this site usually uses. Chomp is closer: whoever is forced to take the poisoned square loses, which is the last-move rule with the last move made unattractive rather than impossible.

The stealing argument does not care which. What it needs is only that having an extra stone is never bad, and that is a statement about the monotonicity of the game rather than about how it ends. That is why one argument covers both, and why it covers neither of the games in the essays on either side of this one.

Where the ladder goes next #

strategy-stealing opens here, and the rung above it is the one this essay keeps pointing at without taking.

It is the question of what happens when an existence proof and a construction are both available for the same game, and what the construction costs. Lehman’s criterion is the case where the construction is cheap; the Chomp needle is the case where nobody has one at all; and in between is a spectrum this field has not measured.