A potential that names every move

Three essays have measured the distance between knowing who wins a game and knowing how. The theorem that names a winner and no move proves the first player wins Hex and supplies nothing to play. Where the needle has a sentence finds Chomp’s winning moves nameable on exactly the bars that carry a pairing. And a board one column wider takes away one hypothesis of strategy stealing and finds the game becoming easier: on boards of n rows and n + 1 columns, the player joining the nearer edges wins with a table of pairs that names every reply.

Every construction met so far that names moves has needed structure the game happens to have — a symmetry of the board for a pairing, a pair of spanning trees for the switching game. That essay closed by pointing at the kind of construction that needs almost none. It names a move at every turn and asks nothing of the board’s shape. It gives up exactness in exchange, and the question it left was where its guarantee reaches and how far past the guarantee it keeps winning.

A number that says which cell matters #

The construction is a potential, and the form used here is the one Paul Erdős and John Selfridge published in 1973.

Across wins Hex by claiming every cell of some chain from the left edge to the right. A chain that contains a smaller winning chain adds nothing, so the sets that matter are the minimal chains. Give each chain Down has not yet touched a weight of one half for every cell of it Across still needs. A chain of five untouched cells weighs a thirty-second; the same chain with Across holding three of them weighs a quarter. The potential of a position is the total weight of Across’s live chains, and it measures how close Across is to completing one, with a half for every cell of distance.

Down’s strategy is a single sentence: take the empty cell whose live chains weigh the most. Taking a cell kills every chain through it, and the heaviest cell is the one whose removal lowers the potential most.

The theorem attached to it is just as short. If Down moves second and the potential at the start is below one half, Down never loses. The proof is an accounting argument over one exchange. Across’s stone doubles the weight of every live chain through it, so the potential rises by what those chains weighed. Down then takes the cell whose live chains weigh most, which is at least as heavy as the cell Across just took, and removes every chain through it. Over the exchange the potential cannot rise, so it stays below one half for the whole game — and a chain Across had completed would weigh one on its own.

The chains a board holds #

Hex has no draws, so on these boards blocking every chain of Across’s is the same as Down joining top to bottom. The sets are counted by walking every left-to-right path and keeping only those that contain no smaller one: 5 chains on a board of two rows and three columns, 25 on three by four, 148 on four by five.

The picture of where the theorem reaches is almost empty. Only three of the eleven boards start below one half — two rows deep and four, five or six columns wide. A board two rows deep and three wide starts at 0.563, and every board of three rows or more starts near or above one: 1.078 on three by four, 1.008 on three by five, 0.945 on three by six. The four-by-five board, the widest the pairing essay checked, starts at 1.992.

The two-row boards show why the line is so hard to cross. Widening a board lengthens Across’s shortest chain, and every extra cell halves a chain’s weight; but it also multiplies the chains, since a longer route has more places to turn. On two rows the halving wins quickly and the potential falls below one half by the fourth column. On three rows the count of chains keeps pace much longer, and the potential is still just under one at six columns. On four rows it has not begun to fall by five.

A theorem that promises Down the win only on the three shallowest boards of eleven promises very little about Hex. So on these boards the guarantee is nearly empty, and everything interesting is past it.

Past the guarantee #

Past the line the theorem says nothing, and the only way to learn what the potential does there is to play it. Down’s strategy is a function of the position, so it can be checked the way the pairing was: every sequence of moves Across can make is enumerated, and Down’s replies are computed by the potential rather than searched for.

On the two-by-three board, and on three by four, three by five and three by six, the potential wins against every line, with starting weights between 0.563 and 1.078 — well past anything the theorem covers. On three by six that is a check over 9,094 positions, and it is a certificate in its own right: a strategy that holds against every line of Across’s is a proof that Down wins moving second, and this one was never searched for.

On the three square boards it loses, and there it could do nothing else. Strategy stealing proves the first player wins a square board, and with Across moving first Down cannot win whatever it plays. The square rows of the table are the control: they show the checks reject a strategy when rejection is right.

That leaves one row, and it is the one the essay exists for.

The board where the pair wins and the weight does not #

On the four-by-five board the potential loses. And Down can win that board: the pairing from a board one column wider was checked against every line Across can play, 59,049 positions, and it holds everywhere. A table of ten pairs wins where the potential, computing weights over 148 chains at every move, does not.

The two strategies part company at once. Across’s first stone on the losing line goes in the top-left corner, and the pairing’s answer is the cell immediately to its right. The potential answers somewhere else entirely.

The labels are the potential’s reasoning, laid out. Across’s corner stone doubles the weight of every chain through the corner, and the potential then takes whichever empty cell carries the most weight — here the cell in the second row and fourth column, heavier than the cell beside the corner. The pairing is not reading weights at all. It takes the corner stone’s partner, the cell beside it, because that partner is the other half of a structure that holds on every line.

Neither choice is a blunder in itself. The difference is that the pairing’s reply belongs to a plan that covers every later move, while the potential’s belongs to a plan that is recomputed from the position each time, and a greedy recomputation can leave an edge undefended while defending the middle.

The lightest row on the board #

The labels in that figure are worth reading as a map rather than as a list, because the map shows where the loss comes from before a single further stone is placed.

The heaviest cells are in the middle two rows: after Across’s corner stone the six cells weighing between 0.87 and 1.01 all sit there. The top row, which the corner stone has made more dangerous, carries between 0.51 and 0.71. And the bottom row is the lightest row on the board, its five cells weighing between 0.33 and 0.62. The potential’s first reply went to the heaviest cell of all, at 1.010, and it beat its neighbour in the same row, at 1.000, by one hundredth.

A cell’s weight is a count of how many of Across’s routes it would block, each discounted by how far Across is from finishing it. The middle of the board lies on the most routes, because a chain from left to right can bend through it in the most ways; a chain along the bottom edge has fewer ways to be built and so fewer ways for any one cell to matter. So the weights point Down at the middle, where Across has the most options, and away from the edge, where Across has fewest.

That is also where Across wins. The chain it completes is the bottom row itself — the lightest route on the board after the first stone, and still light enough, stone after stone, that the potential always finds a heavier cell somewhere above it. The potential defends every route in proportion to how many routes run through a cell, and it loses to the one route it rated least.

The same shape of failure appears in a different subject in a rule that is never right and cannot be far wrong, where playing the hottest component loses a point on boards with a fight nested inside a cooler one: a rule that ranks by the present measurement cannot see a move whose importance is about to change. Here the measurement is weight rather than temperature, and what it cannot see is a route that becomes decisive precisely because nothing was defending it.

The pairing does not have this problem because it has no ranking to be wrong about. Its reply to the corner stone, the cell beside it, weighs 0.715 — lighter than six other empty cells on the board. By the potential’s accounting it is a mediocre move, and it wins.

That is what happens on the line drawn. Across’s second stone goes to the fourth cell of the top row, and the potential answers at the end of that row. Then Across drops to the bottom row. Each of its next four stones there is answered somewhere in the row above, each reply the heaviest cell at the time it was chosen, and none of them on the bottom row itself. By Across’s seventh stone the bottom row is complete from edge to edge.

Two answers to the same stones #

Set the two strategies side by side along that line and they agree on nothing. To every one of Across’s six stones that Down answers, the pairing’s reply is a different cell from the potential’s. The table has to be read carefully, and its footer says so: after the first exchange the two strategies would be playing different games, so the pairing column is what the pairing answers to each stone, not a game it played. What it shows is how little the two constructions have in common, even on a board both of them are trying to win for the same player. The pairing’s column does not track the heaviest cells and was never meant to; its answers fall on the top row, the bottom row and both edges, wherever the partner of Across’s stone happens to be.

That is the real content of the comparison. A pairing is a global object. It is computed once, it covers every position, and its correctness is a property of the whole table — which is why the pairing essay could check it once and trust it on every line. A potential is a local rule. It is recomputed at every position from the chains still alive, it needs no structure at all, and its correctness is a theorem only below one half. Everywhere else it is a heuristic with an unusually good track record on the boards tried here.

A bound, a heuristic and a table #

A rule that is never right and cannot be far wrong drew a line between a heuristic, which has a track record, and a bounded approximation, which has a theorem. The potential is both at once, and which it is depends on the board. On two rows and four columns it is a strategy with a proof. On three rows and five columns it is a strategy that happens to win every line, established by checking rather than by the theorem. On four by five it is a strategy that loses a won game.

That makes the potential an unusual kind of object in this subject. The guarantee is exact where it applies, the checks are exact where they were run, and between them the only claim that can be made is the one the table makes: board by board, what happened. Three different claims are all called solved separates the senses of solving a game, and a board like three by six sits in a sense that list does not name — solved by a strategy that nobody designed for it and nobody can prove in general.

It also qualifies what a certificate costs. A strategy is not a certificate found strategies generally too large to hand over, and a pairing too small to be anything else. A potential is smaller still — a rule of one sentence and a list of chains — and it turns into a certificate only by being checked against every line, which on three by six is 9,094 positions and on a board of any real size is out of reach.

Names: Erdős, Selfridge, and the games they were about #

Erdős and Selfridge’s 1973 paper was about games in which one player tries to claim every element of some set and the other tries to stop it, now called Maker–Breaker games, and the potential was their proof that Breaker wins when the sets are few and large. The argument was not a strategy for Hex; it was a counting device that happened to be a strategy. Its descendants, weight functions tuned to particular families of sets, are the main tool for proving that one side can prevent the other in games like generalised tic-tac-toe.

Hex fits the framework because it has no draws, so preventing Across is the same as winning for Down. That is also why the square boards behave as they do: the strategy-stealing argument of the first of these essays proves Across wins moving first, so no strategy for Down can succeed there, the potential included.

What the checks cannot show #

The boards stop at twenty cells. Every board in the table was checked against every line, and the positions a check visits grow quickly with the board. Whether the potential goes on losing boards one column wider from four by five onward, or whether four by five is an isolated failure, is not measured.

Only one weighting is tried. A half per cell is the weighting the theorem uses. Other weightings — heavier for chains near an edge, or adjusted for how many routes pass through a cell — are the natural repairs, and nothing here says whether any of them wins four by five.

The line drawn is the first one found. The check stops at the first sequence on which Across joins; there may be many others on four by five, and nothing here counts them.

And ties matter. When two cells weigh exactly the same the potential takes the first in reading order. A different tie-break is a different strategy, and on the boards tried it could change which lines win and which lose.

The rules the counts assume #

Hex on a rhombic board of r rows and c columns, each cell with up to six neighbours. Across joins the left column to the right one and moves first; Down joins the top row to the bottom and moves second. Down’s potential is the sum, over Across’s minimal left-to-right chains containing no cell of Down’s, of one half raised to the number of that chain’s cells Across does not yet hold, and Down takes the empty cell through which that sum is greatest. A board is settled for Down by a strategy checked against every line of Across’s, by the pairing on boards of n rows and n + 1 columns, or by the search of the square board for squares up to four.

Still open: the weighting that wins four by five #

The potential loses four by five by defending the middle and leaving an edge. That points at a particular repair: weight a chain by more than its length, so that a chain along an edge, which has fewer ways to be blocked, counts for more than a chain through the middle. Whether some weighting of that kind wins every board the pairing wins — four by five first, then five by six, where the pairing is fifteen pairs and the check is past what a single run can reach — is a finite question on the smaller board, and it is the next measurement to take.