Combinatorial Game Theory
who wins, and by how much
Out in the world

Two reflections and a corner

Hex boards of n rows and n + 1 columns are won by the player with the nearer edges, by a pairing, and the count of pairings that do it ran two, three, three. It is three again on five by six, against 1,225 chains, and three on six by seven, against 16,097. They are the same three every time, and they are not three strategies: one is the classical reflection, and the other two are a reflection across the board's other diagonal, which joins its two far corners, in two versions that disagree about six cells. Each is a rule a sentence long, and each holds on every board out to ten by eleven.
17 min read 7 figures A theorem that names no moveWhat a search costs

Assumes: Three pairings and no order · A board one column wider

Three pairings and no order counted, on the Hex boards where the player joining the nearer pair of edges wins moving second, every set of disjoint pairs of cells that meets each of the other player’s chains in a whole pair. Such a set is a complete strategy: whenever Across takes one cell of a pair, Down takes the other, and Across can never finish a chain because every chain has a pair in it that Across can only ever half own. The counts along boards of n rows and n + 1 columns were two, three and three, on 2 × 3, 3 × 4 and 4 × 5. The essay ended on the obvious question. The chains that constrain a pairing multiply about eightfold with each row, and a flat count across three boards could be the start of a pattern or the end of a coincidence: if five by six has three again, the family has a small fixed set of strategies; if it has one, the classical reflection is forced; if it has many, four by five was narrow rather than typical.

It has three, and so does six by seven. What makes the answer worth a page is that the three turn out to be the same three on every board, each written by a rule short enough to state in a sentence, and that the rules then say why the count does not grow.

Three, again. Every set of disjoint pairs meeting each of Across's minimal chains in a whole pair, on Hex boards 2 × 3 to 5 × 6: 2, 3, 3 and 3 pairings on 5, 25, 148 and 1,225 chains. Every one uses every cell, is unchanged by a half-turn, and is written by one of three rules.
Fig. 1 Every set of disjoint pairs meeting each of Across’s minimal chains in a whole pair, on the boards of shape n × (n + 1) from 2 × 3 to 5 × 6. The chains go 5, 25, 148, 1,225; the pairings go 2, 3, 3, 3. Every pairing uses every cell, is unchanged by a half-turn of the board, and is written by one of three rules, of which the diagonal and corners rules coincide on 2 × 3.

Counting where the cells run out

The earlier count stopped at twenty cells for a reason that had nothing to do with Hex. It stored a set of cells as the bits of one machine word, and it listed Across’s minimal chains by walking every simple path from the left edge to the right and then discarding any path that contained a shorter one. Both steps are fine on twenty cells and neither survives thirty: the paths on 5 × 6 run into the millions, almost all of them not minimal.

Two changes carry the count further, and both are about what a minimal chain is. A chain is minimal exactly when it is an induced path — one in which no cell touches any earlier cell except the one before it — touching the left edge only where it starts and the right edge only where it ends. A path that doubles back to touch itself contains a shortcut, and a path that touches an edge twice contains a shorter chain from the second touch. So the minimal chains can be generated directly, by a walk that refuses to step next to its own past, and the list comes out already minimal: 148 on 4 × 5, the same as the old filter, 1,225 on 5 × 6 in three milliseconds, and 16,097 on 6 × 7.

The second change is to the search for pairings. The old search went cell by cell, deciding for the lowest unpaired cell whether it was left alone or paired with some later cell, and it visited 1,607,305 partial pairings on 4 × 5. The new one goes chain by chain: at each step it takes the unmet chain with the fewest unpaired cells and tries every pair of those cells, since some pair inside that chain has to be in the final answer. A pair tried and abandoned is forbidden to the branches after it, so that each set of pairs is found exactly once. On 4 × 5 that is 2,427 steps rather than 1.6 million; on 5 × 6 it is 85,561, under a second.

Five by six, and six by seven

The count on 5 × 6 is three. Each of the three uses all thirty cells, so none leaves a cell for Down to answer freely, and each is its own image under a half-turn of the board, as every pairing on the smaller boards was.

Five by six has three pairings. The three sets of pairs meeting every one of Across's 1,225 minimal chains on the 5 × 6 board: the diagonal pairing, the cross pairing, which pairs the two acute corners, and the corners pairing, which is the cross pairing with the six cells at those corners paired locally.
Fig. 2 The three pairings of 5 × 6, the only sets of pairs meeting every one of Across’s 1,225 minimal chains. The first is the classical diagonal reflection; the second reflects across the board’s other diagonal and joins its two far corners; the third is the second with the six shaded corner cells paired among their neighbours instead.

A separate run of the search on 6 × 7, with a branching rule that also counts the pairs already forbidden inside each chain, took thirty-nine minutes and 4,543,739 steps against 16,097 chains, and found three again: twenty-one pairs each, every cell used, each unchanged by a half-turn. That run is too slow to repeat every time the page is drawn, so the figures stop at 5 × 6 and the 6 × 7 count is reported from it. The sequence along the family is now two, three, three, three, three, against chain counts of 5, 25, 148, 1,225 and 16,097.

The first question the earlier essay asked is answered, then: the classical reflection is not forced, and four by five was not narrow. The second question — whether three is a small fixed set — needs the pairings read rather than counted, and reading them turns three into two.

Three rules

Number the cells of an n × (n + 1) board by row r from the top and column c from the left. The three pairings found on every board are these:

  • diagonal: cell (r, c) with (c, r + 1), for every cell with c no greater than r. This is the reflection across the board’s long diagonal, shifted one column, and it is the pairing a board one column wider proves wins every board of the shape.
  • cross: cell (r, c) with (n − 1 − c, n − r). This is the reflection across the board’s other diagonal, again shifted by one, and its most visible pair joins the top-left cell to the bottom-right — the two cells of the board furthest apart.
  • corners: the cross rule, except that the six cells at those two corners are paired with neighbours — the top-left cell with the one beside it, the cell below it with the second-to-last cell of the right-hand column, and the bottom-right cell with the one beside it.
Three rules, one board larger. The diagonal, cross and corners rules written out on the 6 × 7 board, twenty-one pairs each. Each meets every one of Across's minimal chains in a whole pair, and the cross and corners pairings differ only in the six shaded corner cells.
Fig. 3 The three rules written out on 6 × 7, twenty-one pairs each, with the six corner cells shaded where the cross and corners rules part. Each is a sentence about coordinates and needs no search to produce; each meets every one of Across’s minimal chains on this board.

On 6 × 7 the rules write exactly the three pairings the long search found, and they do the same on every smaller board: every pairing the census produces is written by one of the three rules and nothing is left over. On 2 × 3 the corners rule and the diagonal rule happen to write the same pairing — the board is too small for the corners and the diagonal to be different things — which is why that board has two pairings and every larger one has three.

The cross rule is the surprise. The argument usually given for Down on these boards is the reflection across the long diagonal, and the reason is that it comes with a short proof: a chain of Across’s has to get from one side of that diagonal to the other, and the shift by one column arranges that wherever it crosses, it holds a cell and its partner. The cross rule is the reflection across the other diagonal, the short one, and no such proof is given for it here. Yet the search finds it on every board, and it was already there on 4 × 5, where the earlier essay noticed the corner-to-corner pair as the strangest thing in the table.

Six cells, paired two ways

The corners pairing is not a third idea. It is the cross pairing with a local repair at its two ends.

Six cells, paired two ways. On the 3 × 4 board, the pairs of the cross and corners pairings that touch the six shaded corner cells. The cross pairing joins the two far corners and the cells beside them across the board; the corners pairing joins each to a neighbour. On every board from 3 × 4 to 5 × 6 the two pairings differ in exactly these three pairs.
Fig. 4 The pairs of the cross and corners pairings that touch the six shaded corner cells of 3 × 4. The cross pairing joins the far corners, and the two cells beside one corner to the two beside the other, across the board; the corners pairing joins each of the six to a neighbour. Everywhere else the two pairings are the same, on every board.

The cross rule pairs (0, 0) with the far corner, (0, 1) with the cell beside the far corner in the right-hand column, and (1, 0) with the cell beside it in the bottom row: three pairs that each span the whole board. The corners rule replaces them with three pairs that span nothing: the top-left cell with its right-hand neighbour, the bottom-right with its left-hand neighbour, and — the one long pair it keeps — (1, 0) with the right-hand column’s second cell from the bottom. Both versions work on every board checked, and on every board they agree on every other pair.

The way two such different local arrangements can both work is the condition itself. A pair does not have to be two neighbouring cells; what it needs is that every minimal chain through either of its cells contains some whole pair, whether that pair or another. Near an acute corner a chain has very little room — a chain starting in the top-left cell must leave it through one of its two neighbours, and a chain ending in the bottom-right cell must arrive the same way — so the six cells at the two far corners are crossed by few chains, and those chains pass through the rest of the board, where the cross pairs they share are the same under both rules. That is where two different coverings of the same six cells can both be complete, and the census finds no other place where it happens. A pairing that is not a symmetry found the same phenomenon in an impartial game, where searching every pairing rather than every geometric one turned up arrangements no symmetry suggests; here the corners pairing is exactly that, a pairing that is a symmetry everywhere except where the board ends.

Two strategies in three pairings

Counting the pairs the three share makes the structure exact.

Two strategies in three pairings. Pairs shared by each two of the three winning pairings on boards 3 × 4 to 6 × 7. The cross and corners pairings share all but three pairs on every board; the diagonal shares 1, 0, 1, 0 with the cross pairing.
Fig. 5 Pairs held in common by each two of the three pairings, on boards 3 × 4 to 6 × 7. The cross and corners pairings share all but three pairs on every board. The diagonal pairing shares only the few pairs that both reflections agree on.

The cross and corners pairings share every pair but three on every board, while the diagonal pairing shares only a handful with either — the pairs both reflections happen to agree on, near where the two diagonals cross. So the family has two strategies, not three: the reflection across one diagonal and the reflection across the other, the second in two versions that differ at six cells. Read that way, the flat count is less mysterious. A board of this shape has two diagonals and two corners at the ends of the second one, and each new row adds chains in proportion without adding any new place for a different arrangement to start. A pairing that met every chain some other way would have to be a third reflection or a repair somewhere other than the corners, and on five boards in a row there is none.

That is a description, not a proof that there are always three. A rhombus has no third diagonal, but a pairing need not be a reflection at all — the corners pairing already is not one, quite — and nothing here rules out a board large enough to admit a repair in the middle. What the census establishes is that on every board it reaches, the pairings are the two reflections and one corner repair, and nothing else.

A theorem with no move, and a board with two

The family exists because strategy stealing cannot reach it. The theorem that names a winner and no move proves in four lines that the first player wins Hex on a square board, and the proof needs the two players’ positions to be interchangeable; add a column and they are not, and the theorem says nothing. What replaces it on the asymmetric boards is the opposite kind of argument — an explicit strategy that names every reply — and the strategy usually cited is one, the reflection across the long diagonal. The census says that on every board from 3 × 4 to 6 × 7 there are exactly two such strategies of this kind, and the second has been sitting beside the first the whole time.

That makes the family unusual among the games where a pairing is the whole of the theory. In the switching game on points, the condition is the same one — every smallest cutting set holds both points of some pair — and the pairings there are found graph by graph, with no rule behind them; on the graphs where none exists, a pairing that changes once is what a winning strategy has to become. In Welter’s game, a matching turned out to be the pairing the formula hides, one specific matching extracted from a closed form. Here the pairings come with formulas from the start, the formulas are geometric, and there are two of them on a board whose only symmetry is a half-turn.

None of it changes the cost of the general problem. Deciding the winner of Hex on an arbitrary position is among the problems no general method solves quickly, and the rules here say nothing about a board with stones already on it in some other pattern. What they describe is the empty board of one shape, from the second player’s side, and on that board the second player has a choice of two complete strategies, each of which a person could carry out from a sentence.

How much slack each one leaves

The three pairings all meet every chain, which is all a pairing needs. They differ in how many chains they meet more than once.

One pair is enough. For the three winning pairings on 3 × 4, 4 × 5 and 5 × 6: how many whole pairs each minimal chain of Across's contains, summed and per chain, and how many chains each pairing holds with exactly one pair. The cross pairing has the least slack on every board.
Fig. 6 For each pairing on 3 × 4, 4 × 5 and 5 × 6, the whole pairs each of Across’s minimal chains contains, summed and averaged, and the chains held by exactly one pair. The diagonal pairing holds the most chains twice; the cross pairing holds 62 per cent of the chains on 5 × 6 by a single pair.

On 5 × 6 the diagonal pairing has 2,336 whole pairs across the 1,225 chains, nearly two a chain, and only 359 chains rely on a single pair. The cross pairing has 1,859, and 762 chains rely on one pair. The corners pairing sits between them on both counts. So the cross reflection is the leanest of the three: it covers every chain, but on most of them by exactly the minimum — the measurement the winning reply is the fourth choice could not have made, since it ranked replies one turn at a time rather than strategies whole — and a defence that is right everywhere by the smallest possible margin is a strange object to find growing out of a family whose textbook answer is so generous. Slack does not change who wins — Down wins against every line of Across’s with any of the three — but it is the measurement that separates the strategies a reader would call robust from the one that only just works, and the one that only just works is the one nobody wrote down.

It is also the reason the cross reflection is hard to see from outside. A procedure that scores a pairing by how often its pairs sit together in Across’s chains, every chain counted equally, rates the cross pairing lowest of the three on every board here, because it puts the fewest whole pairs into the chains; on 3 × 4 no weighting of the chains can rate it above either of the others, which the weights were not the argument found from the other side. The census finds it because the census does not rank pairings at all. It asks only whether every chain is met.

The rules, past the census

The census cannot reach 7 × 8: its chains run into the hundreds of thousands and the search with them. But a rule needs no search to write down, and whether a given pairing meets every chain can be decided without listing the chains.

The rules, past the census. The diagonal, cross and corners rules checked on every Hex board n × (n + 1) from 2 × 3 to 10 × 11, by a search for a minimal chain of Across's holding no whole pair. All three hold on every board.
Fig. 7 Each rule written out on every board from 2 × 3 to 10 × 11 and checked by searching for a minimal chain of Across’s that holds no whole pair. The search is pruned by the pairing — a path may not take both cells of a pair — and stops at the first chain it finds. It finds none, for any rule, on any board.

The check runs the induced-path walk again, with one more refusal: a path may not step onto a cell whose partner it already holds. If any walk reaches the right-hand edge, it has found a chain holding no whole pair and the pairing fails. If none does, the pairing meets every chain. The pruning is heavy — the walk on 10 × 11 visits about 682 million partial paths for the cross rule, far fewer than the chains themselves — and the answer is the same for all three rules on every board from 2 × 3 to 10 × 11: each holds.

That is the furthest the rules are checked, and it is a check, not a proof. The diagonal rule has one, a short argument about where a chain crosses the diagonal. The cross and corners rules have only the census and this search behind them, on boards up to 110 cells. Nothing here suggests they fail beyond it, and the reflection structure suggests an argument of the same shape as the diagonal’s, across the other diagonal, but no proof is given.

How the boards are drawn and counted

Every board is a rhombus leaning right, rows numbered from the top and columns from the left, each interior cell adjacent to six others. Down moves second and joins top to bottom across the n rows; Across joins left to right across the n + 1 columns. A minimal chain is an induced left-to-right path meeting each of Across’s edges once, which is equivalent to a set of cells joining the edges from which no cell can be removed. A pairing is a set of disjoint pairs; it meets a chain when the chain contains both cells of some pair. The census searches every set of disjoint pairs, not only those using every cell, so “every pairing uses every cell” is a finding rather than an assumption, and so is the half-turn symmetry. The 6 × 7 count is a separate run of the same condition with a different branching rule; the rule check on boards past 5 × 6 decides the condition for one pairing at a time and does not count anything.

What a count of three does not settle

It is not a theorem that the count is always three. Five boards agree, and the structure — two reflections, one repair — explains the agreement without proving it. A board large enough to admit a second repair somewhere other than the corners would add pairings, and the census stops at 6 × 7.

Neither of the cross-diagonal rules is proved. They are checked to 10 × 11 by a search that would find a failing chain if there were one, which is as strong as a check can be on those boards and says nothing about larger ones.

Pairings are not the only strategies. A strategy that changes its answer to a cell depending on what else has happened is not a pairing, and three pairings and no order established only on boards up to 3 × 4 that every winning table of fixed replies is a pairing. The count here is of pairings and of nothing wider.

Still open: a proof across the other diagonal

The diagonal pairing is proved by watching a chain cross the long diagonal: the shift by one column arranges that where an Across chain passes from one side to the other, it occupies a cell and its partner. The cross pairing invites the same argument across the short diagonal, and no version of it is attempted here. What the census does say is where to look. Every chain the cross pairing holds by a single pair is a place where the argument has no slack, and on 5 × 6 those chains are 62 per cent of the board; the corner repair says the argument has to treat the two far corners as a special case. A proof that handles the corners separately and the rest by a crossing argument would turn the cross rule from a pattern on nine boards into a second theorem for the whole family — and would make Hex’s asymmetric boards one of the few places where a game has two essentially different simple winning strategies, each provable in a paragraph.

Part 7 of 7

One argument about Strategy stealing. The parts either side of it:

Orders, weights and pairs. For five Hex boards Down wins moving second: whether any fixed order of cells holds the board, whether the Erdős–Selfridge potential holds it, and how many sets of pairs meet every one of Across's chains in a whole pair. A fixed order holds only 2 × 4; the potential holds every board but 4 × 5; 4 × 5 has exactly three pairings. Three pairings and no order Part 6 — The potential lost four-by-five Hex for Down, and fifty-five re-weightings lost it too, which left the question whether anything that orders the cells can hold the board. The plainest ordering — one fixed list, whatever the position — holds none of the boards the pairing is known for, and on four by five the best it can do is the left column. At the other end, every table of replies that wins a small board is a pairing, and four by five has exactly three pairings, each using all twenty cells.

Where this goes next

Orders, weights and pairs. For five Hex boards Down wins moving second: whether any fixed order of cells holds the board, whether the Erdős–Selfridge potential holds it, and how many sets of pairs meet every one of Across's chains in a whole pair. A fixed order holds only 2 × 4; the potential holds every board but 4 × 5; 4 × 5 has exactly three pairings. Three pairings and no order The potential lost four-by-five Hex for Down, and fifty-five re-weightings lost it too, which left the question whether anything that orders the cells can hold the board. The plainest ordering — one fixed list, whatever the position — holds none of the boards the pairing is known for, and on four by five the best it can do is the left column. At the other end, every table of replies that wins a small board is a pairing, and four by five has exactly three pairings, each using all twenty cells. Hex on 3 × 4: the nearer edges win whoever starts. Two copies of a Hex board of 3 rows and 4 columns. On the left each cell is coloured by whether Down, joining top to bottom, wins by taking it first: all 12 do. On the right each cell is coloured by whether Across, joining left to right, wins by taking it first: none do. Down's edges are one row nearer together than Across's, and Down wins whoever moves first. A board one column wider Strategy stealing proves the first player wins Hex, and it needs three things: no draws, an extra stone never hurting, and rules that treat the two players alike. Add one column to the board and the third goes. The player whose edges are now nearer together wins whoever moves first — and does it with a table of pairs that names every reply, checked against every line to a board of twenty cells. A pairing no motion of the square gives. The smallest Cram shape carrying a pairing that is not a rigid motion, with its three pairs drawn as lines between the squares they join. A pairing that is not a symmetry Every pairing strategy found so far for these boards is a rigid motion of the square, and the requirement mentions no geometry at all. Searching all 8.8 million fixed-point-free involutions instead of the eight maps more than doubles what a pairing explains — and the smallest new one turns out to be a reflection with its two fixed squares swapped.

What links here

Essays that reach for this one mid-argument — the half of a link its own author cannot write down.

The objects named here

The third axis, after the field and the series: the games, values and theorems themselves, and every essay that touches each one.

CertificateExhaustive searchHexPairing strategyStrategyStrategy stealingSymmetry