Three pairings and no order

The winning reply is the fourth choice tried to repair the Erdős–Selfridge potential on four-by-five Hex — Down moving second, joining top to bottom against Across joining left to right — and failed fifty-five times. The potential weighs each empty cell by the unfinished chains through it and takes the heaviest; no weighting of edge cells or middle cells or anything else held the board. The essay’s diagnosis was that ordering cells by weight is ordering them by the wrong thing, and its open question went past weights: is there any way of ordering the cells that holds four by five?

That question is too wide to answer as asked, because any strategy at all can be dressed up as an ordering — score the move the strategy wants at one and every other cell at nought. What can be answered is where the family of orderings stops working, from the plainest end, and what the strategies that do work look like, from the other.

The plainest ordering there is #

A fixed order is a single list of the board’s cells. Down’s rule is to take the first cell on the list that is still empty, and the position is never consulted beyond that. It is the ordering with the least information in it — the potential recomputes its weights at every turn, and the fixed order computes nothing — so it is where “anything ordered by a number” begins.

Whether some fixed order holds a board is a finite question, and it can be answered completely. The list is grown one cell at a time. Each prefix is played against every line Across could choose, with Down taking the first empty cell on the prefix whenever one exists. If some line of Across’s wins before Down ever runs past the prefix, the prefix is dead and so is every list that begins with it, because the losing line never needed a later cell. The search stops when a complete list survives every line, or when every prefix is dead.

No fixed order holds 2 × 3, 3 × 4, 3 × 5 or 4 × 5. The only board in the table a list can hold is 2 × 4, where two rows are so few that Down needs only a pair of stones stacked or leaning, and the search finds a list of all eight cells that wins against every line. Every other board is settled negatively, and quickly: 43 prefixes on 2 × 3, 1,273 on 3 × 4, about 75,000 on 4 × 5 — out of 20! possible lists, most of which are never looked at because they begin with a dead prefix.

The three boards of shape $n \times (n + 1)$ are the ones a board one column wider proves Down wins, by a pairing, and no fixed order holds any of them. On 4 × 5 the longest list that survives every line is four cells long, and it is the obvious one: the left column, top to bottom. Each of its sixteen continuations loses.

A column, and a row #

The reason is visible on the board.

A fixed order is a plan made in advance, and Across can read it. Against the column-by-column order, Across takes the top-left corner — the first cell on Down’s list — and then simply walks along the top row. Down, obeying its list, takes the other three cells of the left column and moves on to the second column, one row down, and never contests the row that matters. Across joins left to right on its fifth stone.

Every fixed order fails the same way, only less obviously. Whatever Down’s list, the cells Down will take are determined by which cells Across has taken, and Across can choose a chain that runs through the parts of the list Down will reach late. A strategy that wins Hex has to answer where Across is playing, and a list answers only where Down planned to be. The potential does answer — its weights change with every stone — which is why it holds every board the fixed order cannot, until four by five.

The other end: a table of replies #

The strategy that does hold four by five is a pairing: the cells are grouped in pairs, and whenever Across takes a cell Down takes its partner. That is a strategy of a different shape — not an order of cells but a table of replies, one answer for each cell Across might take — and it invites the opposite question. If a list is too little information, is a table always enough, and how many tables win?

A table assigns to each cell Across might take one cell for Down to answer with, and it fails if that answer is already occupied when it is needed. The same prefix search works: fill the table one entry at a time, as the lines of play demand entries, and drop any partial table that Across beats. On 2 × 3 it examines 131 partial tables and finds two that win. On 2 × 4 it finds 34, on 3 × 4 three.

Every winning table is a pairing — the answer to the answer is the cell Across took. Nothing in the search asked for that. A table may answer cell 3 with cell 7 and cell 7 with cell 12; the search tried such tables and every one of them lost. So on these boards the pairings are not merely a convenient way of writing a winning table. They are all of them.

Three pairings on four by five #

The table search does not finish on four by five; its partial tables run into the tens of millions. But the pairings can be counted directly, and on the smaller boards the count agrees with the table search exactly.

A set of disjoint pairs is a winning pairing when every chain Across could complete contains both cells of some pair — then Across can never finish a chain, because each time it takes one cell of the pair Down takes the other. That is the condition every Maker–Breaker pairing argument rests on, and it is a condition on a list of chains. Four by five has 148 minimal left-to-right chains.

Exactly three sets of pairs do it, and each uses all twenty cells. No set of pairs that leaves any cell unpaired meets every chain. The first is the pairing a board one column wider describes — each cell on or below the diagonal paired with its reflection across it, one column to the right. The other two are the only alternatives there are, and all three are symmetric under a half-turn of the board.

The other two are stranger than the first, and the strangeness is informative. They agree with each other on seven of their ten pairs and differ only in how they pair six cells near two corners. The third pairs the top-left corner with the bottom-right — two cells on opposite corners of the board, as far apart as the board allows — and the cell to the right of the top-left corner with the right-hand end of the third row. A pair does not have to be two neighbouring cells, and nothing in the condition says it should; it has to be two cells such that every chain through either passes through both, or through some other whole pair. On four by five no chain uses exactly one of the two corners without also containing some whole pair elsewhere, and the search found that before anyone would have thought to try it.

The board one row smaller has three as well, and there the table search confirms the count completely: three winning tables, all three pairings, and these are they. On 2 × 3 there are two. The pairings do not multiply as the board grows along this family; they stay at two or three, which is a sign of how tightly the chains constrain them. Every row of four by five is itself a chain, so each row must contain a pair lying within it; every diagonal staircase is a chain too; and the 148 constraints together leave three solutions.

No pairing is nearer the potential #

Three pairings where one was known reopens the comparison the winning reply is the fourth choice made. It ranked the diagonal pairing’s reply in the potential’s order at every one of Down’s turns along every line, found the two agreeing 26.1 per cent of the time, and concluded that the potential orders cells by the wrong thing. With two more winning pairings in hand, the obvious suspicion is that the comparison was made against the wrong pairing — that one of the others answers Across the way the potential would, and the potential was one repair from it after all.

It is not so. The diagonal pairing reproduces the earlier figures exactly — 393,660 turns, 26.1 per cent agreement, an average rank of 3.68, as low as seventeenth. The second pairing agrees 26.0 per cent of the time with the same average rank. The third agrees less, 24.8 per cent, and its reply sits as low as nineteenth. The potential is equally far from all three winning pairings, which turns the earlier essay’s conclusion from a statement about one strategy into a statement about all the strategies of this shape the board admits: whatever it is that makes a reply win on four by five, it is not what the potential weighs.

Where there is no perfect pairing #

One board in the first table behaves differently from the rest, and it is worth a paragraph because it shows what a pairing is not required to be. Three by five has fifteen cells, so no set of pairs can use them all, and yet 114 sets of pairs meet every one of its 56 chains. Each leaves at least one cell unpaired, and when Across takes an unpaired cell Down may answer anywhere — an extra stone never hurts Down in Hex, which is the fact strategy stealing runs on. So a pairing strategy does hold 3 × 5, but not as a table in which every entry is a partner. The table search, which insists on a fixed answer to every cell, is the wrong instrument there, which is why it is not run; the pairing count is the right one, and it finds pairings in abundance on the board where the fixed order and the potential are also fine. It is on the boards of the pairing’s own family, $n \times (n + 1)$, that the pairings are few and complete.

What the two ends say about the middle #

The question left by the potential was about the middle: functions of the position computed cell by cell, of which the potential is one and the fixed order the barest. The two ends bracket it.

At the bottom, the fixed order fails on every board of the pairing’s family and succeeds only where Down’s task is easy. A potential that names every move is the step up from it, and the step is exactly the one the column picture shows is needed: a rule whose choice changes when Across plays somewhere Down did not expect. A cell-by-cell function has to do better than ignore the position, and the potential does, holding every three-row board. At the top, the strategies that are known to hold four by five are three pairings, which are not orders of any kind: a pairing’s reply depends on exactly one thing, the cell Across has just taken, and on nothing else about the position. The winning reply is the fourth choice found that the pairing’s reply sits on average 3.7th in the potential’s order; there is no reason it should sit first in any order computed from the board, because it is not computed from the board.

That is the sense in which the potential’s family and the pairing’s family are different kinds of object. The potential asks which cell matters most; the pairing asks what did Across just do. On four by five only the second kind of question is known to have a winning answer, and it has three.

How the searches were run #

Every board is a rhombus leaning right, cells numbered by row and column from the top left, each cell adjacent to six others. Down moves second. A position is Across’s stones and Down’s stones; Across wins on completing a left-to-right chain and Down on completing a top-to-bottom one, and a full board always has exactly one winner, which the theorem that names a winner and no move relies on.

The fixed-order search plays every line of Across’s against each prefix, memoising positions, and discards a prefix at the first line Across wins. It uses the board’s half-turn, which preserves both players’ edges, to try only one of each pair of equivalent first cells. The table search is the same with a table in place of the list, and the pairing count enumerates sets of disjoint pairs, discarding a partial set as soon as some chain has fewer than two cells left that could still form a pair inside it. The minimal chains are every simple left-to-right path, with any path containing a shorter one removed.

What the searches cannot show #

The middle is not searched, and it cannot be searched the same way. The family of fixed orders has 20! members and a prefix search disposes of it with 75,201 trials because a dead prefix kills every extension. A rule that reads the position has no prefixes — its choice at one position constrains nothing about its choice at another — so the family is as large as the set of all strategies, and deciding four by five for it is deciding four by five, which how hard is it places among the problems no general method solves quickly.

Between a list that ignores the position and a table that reads only Across’s last move lie all the strategies that read more — the potential, the re-weightings, anything computed from the whole board. The searches here say the plainest of those fails and that the known winners are not of that kind; they do not say no cell-by-cell rule holds four by five.

The table search on four by five does not finish, so “every winning table is a pairing” is established on the three smaller boards and not on four by five. What is established there is that exactly three pairings exist; a winning table that is not a pairing would be a strategy of a new kind, and none is known.

And five boards is five boards. The pairing’s family continues to 5 × 6 and beyond, where the chains number in the thousands and a pairing count is still feasible, and whether the count stays at three is the obvious thing to ask.

Still open: whether the pairings stay few #

Two, three, three: the count of pairings along $n \times (n + 1)$ is flat so far, and the chains that constrain it grow quickly. The measurement is the same count on 5 × 6 — thirty cells, several thousand minimal chains — together with the question of symmetry, since every pairing found so far is its own image under the half-turn. If 5 × 6 has three pairings again, the family has a small fixed set of strategies of this shape and the diagonal reflection is one of a handful; if it has one, the reflection is forced; and if it has many, four by five was a narrow board rather than a representative one. A pairing that is not a symmetry is the same question asked of an impartial game, where searching every pairing rather than every geometric one more than doubled what pairings explain.