A board one column wider

The theorem that names a winner and no move proves in four lines that the first player wins Hex, and spends the rest of its length on the gap between that bit and a move. Where the needle has a sentence measures the gap on Chomp and finds it closed on exactly the bars where a pairing exists — a square’s two arms, a two-row bar’s offset — and open everywhere else.

Both essays take the argument as given and ask what it leaves out. This one takes a board where the argument does not apply at all, because one of its hypotheses has been removed on purpose, and asks what the game does instead. The answer is that it becomes easier: not only is the winner known, the winner has a strategy anybody can hold in mind.

Three things the argument needs #

Strategy stealing is usually quoted as though it rested on one observation — an extra stone never hurts — and the earlier essay marks that line as the load-bearing one. It is load-bearing, but it is not alone, and the other two hypotheses are invisible on a square board because a square board satisfies them without effort.

No draws. Stealing rules out the second player winning; it can only conclude that the first player wins if nothing else could happen. Hex supplies that by a fact about the plane: a filled board contains exactly one of the two chains.

An extra stone never hurts. The first player plays anywhere, then follows the second player’s supposed strategy, and the spare stone can only help.

The rules treat the two players alike. This is the one nobody states, because it is so obviously true of a square board. The argument takes a strategy that wins for the second player and uses it as the first player. That only makes sense if a strategy for one player is the kind of thing the other player can use — if the board looks the same from both sides.

On a square board a player joining top to bottom and a player joining left to right are playing the same game turned a quarter, so a strategy for one, turned a quarter, is a strategy for the other. On a board of three rows and four columns they are not. The player joining top to bottom — call that player Down — has edges three rows apart. The player joining left to right — Across — has edges four columns apart. A quarter turn takes the board to one of four rows and three columns, which is a different board.

So the third hypothesis fails, and with it the argument’s conclusion. Nothing now says the first player wins. The first two hypotheses still hold, and on their own they say nothing whatever about who wins.

What the search finds instead #

The search is the one used for square boards, with the edges each player joins named rather than assumed. A position is the two players’ stones, a player wins as soon as their own two edges are joined, and — because a filled board has exactly one chain — the search needs no test for a draw.

On the 3 × 4 board, every one of Down’s twelve first stones wins, and every one of Across’s loses. Down wins moving first, and Down wins moving second: Across has no opening that survives.

That is a stronger result than the square boards give, and in a direction the stealing argument could never have predicted. Stealing’s conclusion is always the first player wins, because what it steals is the second player’s strategy. Here the second player — when that player is Down — wins. The advantage of the move, which stealing turns into a proof, has been swamped by a single extra column.

A column is worth more than a move #

The size of the swing is worth reading off the two tables rather than taking on trust. On the 3 × 3 board the first player wins with five of nine openings and loses with the other four, so the move is decisive and the choice of stone matters. On the 3 × 4 board, Down moving first wins with all twelve openings — no choice matters at all — and Across moving first wins with none.

So one column has done two things. It has handed the game to Down whichever player starts, which means the column is worth more than the move. And it has made Down’s first stone irrelevant, which means Down’s advantage is so large that even a wasted stone does not spend it. The move — which what a move is worth prices carefully elsewhere, in positions where it is the whole difference between the players — is here a small quantity next to a large one, and the stealing argument, which can only ever measure the small one, has nothing left to say.

Bridg-It makes an instructive contrast, because its board is rectangular too. Cut is Short on another graph draws it: one player’s dots stand in n + 1 rows of n, and the game is still symmetric and still a first-player win. The difference is that Bridg-It gives each player their own dots, and the second player’s grid is the first player’s turned a quarter, so the rectangle is balanced by a second rectangle the other way. In Hex the cells are shared. Both players place stones on the same board, and a board one column wider is wider for both of them — which is to say it favours whoever’s edges it brings together.

The table sets the square boards beside their one-line-longer neighbours, in both orientations. Square: first player wins, both ways. One line longer: the nearer edges win, both ways, and the other player has no winning opening at all. The two orientations of each rectangular board are mirror images and give mirror-image answers, which is the check that the search is treating Down and Across as names for edges rather than for who moves first.

A strategy that is a table of pairs #

A result that holds whoever moves first usually has a reason simpler than a search, and this one does. Down wins with a pairing.

Number the cells in pairs. A cell in row i and column j, with j no greater than i — on or below the diagonal — pairs with the cell in row j and column i + 1: its mirror image across the diagonal, moved one column to the right. Every cell of the board lands in exactly one pair, because the board has one more column than rows and the shift uses up exactly the extra column.

Down’s strategy is the table. Whatever cell Across takes, Down takes its partner. Down never looks at the board, never counts anything and never searches; the number written in the cell Across just took is the whole of Down’s reply. And the strategy works moving second, which is the harder case: if Down moves first, Down plays anywhere and follows the table, and an extra stone of Down’s own never hurts.

That last sentence is the second hypothesis of stealing doing its job inside a pairing. The first hypothesis does its job at the end, as the next section shows. Only the third — symmetry between the players — is gone, and the pairing is what replaces it: a symmetry of the board that Down can use and Across cannot.

Checked against every line #

A pairing is a claim that no sequence of Across’s moves produces a left-to-right chain, and a claim about every sequence can be checked by trying every sequence — with Down’s moves read off the table rather than searched for.

Across never joins left to right, on any line, on any of the three boards. On the 4 × 5 board there are ten pairs; Across takes one cell of each and Down the other, so a finished board is a choice of one cell from each pair — 1,024 of them — and the enumeration passes through 59,049 distinct positions on the way. Every finished board contains Down’s chain from top to bottom.

That last check is the no-draw theorem working for Down. The pairing is designed to stop Across; nothing in it mentions Down’s chain. But a filled Hex board has exactly one winner, so a board on which Across never joined left to right is a board on which Down joined top to bottom — and the check confirms it on every one of the 1,096 finished boards across the three sizes, rather than leaving it to the theorem.

The table has one feature that can be read straight off the picture. A cell on the diagonal itself, in row i and column i, pairs with the cell immediately to its right, so the diagonal is lined with pairs of neighbours running from the top-left corner to the bottom-right. That band of cells separates the part of the board left of the diagonal from the part right of it — no cell on one side touches a cell on the other — so every left-to-right chain of Across’s passes through it somewhere.

It would be pleasant to finish the argument from there, and it cannot be finished that simply. A chain can cross the band through a single cell, and the partner Down takes in reply sits beside that cell rather than across its path; the band on its own does not stop Across. What stops Across is the whole table working together, and the page does not offer a proof of that. What it offers is the enumeration: on these three boards every line Across can choose has been played against the table, and the table has held. That boards of n rows and n + 1 columns are won by the nearer edges at every size is a known result with a pairing behind it; the reasoning that carries it past 4 × 5 is not reproduced here, and the checks above are not a substitute for it.

That distinction matters for how the strategy is used. A player on a 4 × 5 board can follow the table with the certainty of an exhaustive check. A player on an 11 × 12 board following the same rule is relying on a theorem this page names and does not prove — which is the same position a Hex player on a square board is in with respect to strategy stealing, except that the theorem in hand this time names every move.

One game, played by the table #

The replay shows what the table looks like from the board. Across heads straight along the middle row, which is the shortest route between Across’s edges, and each stone is answered at once by its partner. The partners of a straight middle row are not a straight column; they are scattered by the reflection and the shift. What they accomplish is not visible move by move. It is visible at the end, where Across’s row has been broken and Down’s cells join the top to the bottom.

That is the property that makes a pairing so different from a search, and it is worth putting next to the strategy that is a symmetry. A mirror strategy can look aimless — its moves respond to the opponent’s rather than advancing a plan — and it wins anyway, because the plan is in the pairing rather than in the moves.

Finding a strategy, and checking one #

The square 4 × 4 board costs 6,550,914 nodes to search, and what that search produces is the list of winning openings — a strategy for the rest of the game is never written down. The 4 × 5 board, with four more cells, is settled by 59,049 positions, because the check is handed the strategy and only has to try Across’s replies against it.

That is the distinction between a strategy and a certificate run in the favourable direction. A certificate is normally unavailable because a strategy is a subtree of the game, exponentially large. A pairing is a strategy of exactly pairs many entries — ten on the 4 × 5 board, fifteen on 5 × 6 — and verifying it is a search over the opponent’s choices only. The strategy is small and the verification is moderate, where on a square board neither is small.

It also changes what solved means for these boards. The square boards past four are solved only in the stealing sense: the first player wins, and no move is known. The boards one column wider are solved in the strongest sense there is — a rule that names the move from any position, at any size — and they are solved that way because they are not square.

Where the argument’s silence was protecting nothing #

The earlier essays read strategy stealing as a proof whose weakness is that it names no move. This board suggests a sharper reading of the weakness.

Stealing proves the least interesting fact about a symmetric game. On a square board the two players are interchangeable except for who moves first, so the only thing that can distinguish them is the move, and stealing proves that the move is worth having. Break the symmetry and the move stops being the only difference — the geometry of the board is a second one — and in this family the geometry wins outright.

That suggests why square Hex resists construction. A pairing needs a symmetry of the board that one player can use and the other cannot. On a square board every symmetry of the board is available to both players equally — that is what makes the board square — so there is nothing for a pairing to be built from, and the search is left with nothing to do but look.

Every game has a negative uses a mirror between two copies of a game to make their sum a second-player win. The Hex pairing uses a mirror within one board, and it works for the same reason: the mirror carries every move of the opponent to a reply that undoes it. What the square board lacks is not a mirror but a mirror with a spare column in it.

What the boards cannot show #

The boards are tiny. The search reaches 3 × 4; the pairing check reaches 4 × 5. That the player with the nearer edges wins on every board of n rows and n + 1 columns is a known result, and the reflection argument above is the reason; what is established here is the check on three boards, not the general theorem.

Nor does anything here say what happens two columns wider. A board of n rows and n + 2 columns gives Down an even larger advantage and is not measured. The interesting boards are the ones where the advantage and the move pull against each other, and one column is the smallest such gap.

And the pairing is one strategy among many. The search shows every one of Down’s first stones wins on 3 × 4; the pairing uses one fixed table. There are other winning strategies, and nothing here compares them.

The rule this depends on #

Hex is a goal game — each player wins by joining their own two edges — and the whole argument leans on the no-draw theorem, which is a fact about a board of hexagons in the plane. On the rectangular boards it does two jobs. It supplies stealing’s first hypothesis, which survives here, and it turns the pairing’s defensive guarantee — Across never joins — into a win for Down, because a filled board with no chain for Across has one for Down. That second job is the one a pairing on a non-planar board would not get for free, and it is why the point game on a general graph is so much harder than the game on this board.

Still open: a strategy that names moves without a pairing #

Two constructions have now been seen where stealing names nothing: pairings, on Chomp’s square and two-row bars and on Hex boards one column wider; and trees, on every switching graph. Both are exact. Both need structure the game happens to have.

There is a third kind of construction that needs almost no structure at all and gives up exactness instead: a potential, a number computed from the position that one player keeps small, which guarantees a win whenever the total at the start is small enough. It names a move at every turn, like a pairing, and it can be wrong about who wins, unlike one. Where such a guarantee reaches, and how far past its guarantee it keeps winning, is the measurement this line of questions leads to next.