A pairing is checked, not measured

The machine Shannon and Moore built to play Hex measured the board and moved where the measurement pointed. A circuit asked once made that measurement commit — consulted on the empty board, turned into a pairing, and never asked again — and found the pairings it chose sitting near the winning ones without ever being one. Under eight ways of reading the circuit’s scores, one found the winning pairing of three by four and lost two by four; none held three by five or four by five.

That leaves a question the circuit cannot answer on its own behalf, because it is a question about all measurements rather than about one. The winning pairings on these boards are certificates: sets of disjoint pairs of cells such that every minimal chain Across could build contains a whole pair, so that Down, answering each of Across’s stones with its partner, can never be crossed. The textbook pairing for boards of $n$ rows and $n + 1$ columns has a sentence — reflect each cell across the board’s diagonal and move one column — and a sentence is a fact about coordinates, not a measurement of anything. Is there a score of a pair of cells, computed from the board alone and knowing nothing of diagonals, whose best pairing is a winning one?

A board offers one score before any other. Every minimal chain of Across’s can be listed, and a pair of cells can be scored by how many of those chains contain both of its cells. A pair that shares many chains is a pair that, kept together, breaks many of them at once — which is exactly what a pairing is for.

Four scores and one board they cannot hold #

The chain count has obvious defects as a score, and each has an obvious repair. A cell in the middle of the board lies on many chains, so its pairs share many chains whether or not they belong together; dividing by how many chains each cell lies on corrects for that, and there are three standard ways of doing it — the cosine of the two cells’ chain sets, their Jaccard ratio, and the lift, which compares the shared count with what independence would predict. Four scores in all, each computed from the list of chains and nothing else.

Each score is then made to choose. Of every way to split the board into pairs, the best is the one whose pairs’ scores add to the most, and it is found exactly — on four by five that is a search over all twenty cells by dynamic programming over subsets, not a greedy guess. The pairing chosen is then checked against every chain: if each holds a whole pair, the pairing holds the board.

All four hold two by three. None of them holds four by five, and three by four is a draw that goes the wrong way. On three by four the plain count does not choose at all: of the 10,395 ways to pair the board, three tie for the highest score, and two of those three hold the board. The recursion that breaks the tie meets the third first. The three corrected scores each have a single best pairing — the same one, which leaves one chain of 25 without a whole pair — and they rank the best winning pairing fourth, second and fourth. On four by five every score’s best pairing loses: the plain count misses seven of 148 chains, Jaccard five, the cosine and lift four each, and no pairing that holds is tied with any of them.

Every one of these boards has a pairing that holds it — two on two by three, three on each of the others — so the failure is not that the board has no certificate. It is that the scores rank something else first, or, at best, no higher.

The three-by-four failure is worth looking at, because it is the first and the smallest. The chain count pairs each cell with its horizontal neighbour, row by row, which makes sense: horizontal neighbours share a great many of Across’s left-to-right chains. And it leaves exactly one chain open — a staircase from the bottom-left corner climbing to the top-right, one cell in the bottom row, two in the middle, one in the top. Each of the four cells on it has its partner beside it in the same row, off the staircase. Across walks up the staircase and Down, answering each stone with its partner, never puts a stone on it.

What a sum rewards #

The reason is not that the counts are poor measurements. It is the shape of what any additive score asks for, and the plain count makes it exact. A pair’s score is the number of chains containing both its cells, so a pairing’s score — its pairs’ scores added — is the number of whole pairs lying on chains, counted chain by chain. The plain count’s best pairing is precisely the pairing that puts the most whole pairs on Across’s chains in total. That is the quantity it maximises, with nothing approximate about it, and it is the wrong quantity.

On three by four the diagonal pairing and the losing pairing both put 36 whole pairs on the 25 chains. The diagonal spreads them so that every chain gets at least one; the losing pairing stacks a second pair on some chains and leaves one with none. A total cannot see the difference, which is why the plain count ties them, and the corrected scores, which weigh the same pairs by how crowded their cells are, break the tie the wrong way. The four-by-five board shows the same thing without a tie.

The pairing the chain count prefers covers more than any winning pairing does. Summed over all 148 chains of four by five, it puts 264 whole pairs on them; the winning pairings put 237, 231 and 187. It is, by the measure it maximises, a better pairing than any that holds the board. And it leaves seven chains with none, where every winning pairing leaves none.

A winning pairing needs one whole pair on every chain and nothing beyond that; a second pair on a chain is wasted. A score that adds pairs’ values has no way to express “every” — it rewards total cover, and total cover can always be raised by giving up one chain to put a second pair on several others. On three by four the trade is one chain for a few doubled; on four by five it is seven. The best pairing under a sum is the best at the wrong thing, and the better the score is at measuring how much a pair helps, the more confidently it makes the trade.

That is the general form of the circuit’s failure, with the circuit taken out. The resistance rule weighed cells; these scores weigh pairs, and they read the chains directly rather than through an electrical analogy. Both fail for the same reason: a certificate is a statement with a universal quantifier in it, and a measurement is a sum.

A measurement allowed to listen #

There is an obvious way to put the quantifier back. Run the chain count, take its best pairing, find the chains it leaves empty, and make those chains matter more: multiply each missed chain’s weight by some factor, recompute every pair’s score as a weighted count, take the new best pairing, and repeat. The board is telling the measurement where it failed.

On three by four this works at once. The first pairing misses one chain; with that chain’s weight raised, the second pairing misses none — and it is the diagonal pairing, at every factor tried. On four by five it is a different matter.

At a factor of 1.5 the misses wander for forty-five rounds and then reach none: round 46 produces a pairing that holds, and it is the diagonal one. At 1.25 the corrections are too gentle — the same few chains are missed round after round, and the best it manages is two. At 2 they are too sharp: each round’s correction raises some chains so far that the next pairing abandons others, and the misses swing between four and twenty-six without settling. The trace at 1.5 is no smoother than the other two until the round it lands.

The listening score is a version of a rule Hex has already been played by. A potential that names every move is the Erdős–Selfridge rule, which weights each of Across’s unfinished chains by a power of two and plays where the weight is heaviest; its weights grow as a chain fills, which is feedback from the board in play. The rule here grows its weights from the pairing’s failures instead of the board’s, before any stone is placed, and it inherits the potential’s habit of working on small boards and needing tuning on larger ones.

What it found is worth noticing. Four by five has three pairings that hold it, listed in three pairings and no order, and the listening score reached the diagonal one, not either of the others — which share two and none of its ten pairs. On three by four, too, it reached the diagonal. Whether that is because the diagonal is in some sense the most natural certificate of the three, or because the chain count starts nearer to it, the reweighting cannot say. Read one way it is encouraging: the measurement, given enough correction, converges on the pairing that has a sentence.

By the time it holds, it is checking #

Read another way, the listening score has stopped being a measurement somewhere in those forty-six rounds.

Each round of the listening score does two things: it finds the heaviest pairing, and it checks that pairing against every chain to see which ones it missed. The second step is the certificate check — the very test that decides whether a pairing holds — and the loop runs it forty-six times on four by five, 6,808 chain checks in all, before it stops. What stops it is not the measurement becoming good; it is the check returning nothing. The weights are a way of choosing which pairing to check next, and the procedure is a search, guided by a score, whose termination condition is the certificate.

That puts it in a family with the other two routes. The full pairing search — the one that lists every winning pairing — visits 1,607,305 partial pairings on four by five, pruning each the moment some chain can no longer get a whole pair; on three by four it visits 2,752. It is a search guided by nothing but the chains. The listening score is a much cheaper search guided by a weight that the chains keep correcting. Both are certain only because each candidate is checked against every chain, and the check is the part that carries the proof.

And then there is the diagonal, which consults nothing. It is not cheaper than the search because it searches cleverly; it does not search at all. It is an argument: a stone of Across’s in a cell is answered by the stone in the cell’s mirror image across the diagonal, moved one column, and any chain from left to right must cross the diagonal somewhere in a way that puts both cells of one such pair on it. That argument holds on every board of $n$ rows and $n + 1$ columns at once, which is a thing no search and no measurement of any finite set of boards can deliver.

What the machine was missing #

The circuit essays ended on a question about the Hex machine: was it missing a better measurement, or a willingness to stop measuring? The answer here is that a better measurement does not exist in the form the question imagined. A score of pairs, added up, can be made to agree with a winning pairing on a given board — weight the winner’s pairs by one and everything else by nought — but only by already knowing the answer. Among scores that read the board honestly, the plain ones tie or fail at three by four and fail outright at four by five, and the one that succeeds on four by five does so by running the check that a pairing is.

The machine itself was additive all the way down. Its board was a network of resistors, and a resistor network obeys Kirchhoff’s laws, which are linear: the potential at every junction is a weighted average of its neighbours’, and the current through the network is a sum of currents through its branches. Every way the earlier essay found of turning those potentials into a pairing — ranks, rescaled scores, shares, raw values — weighed each pair and added the weights. The arithmetic of sums above applies to every one of them. A device that computes averages can be very good at telling which cells matter, and it is built to trade, which is the one thing a certificate forbids.

The growth of the board shows how quickly that trade becomes available. Two by three has five minimal chains for Across and six cells to pair, and with so few chains every pairing that covers them well covers each of them; the scores cannot go wrong because there is nothing to trade. Three by four has 25 chains and the first tie. Four by five has 148, a sixfold jump for one more row and column, and room for a score to give up seven chains while beating every winning pairing on total cover by 27 whole pairs. Each added row multiplies the chains faster than it adds cells, and every new chain is another place a sum can decide to save its effort.

The difference matters historically. Shannon and Moore’s machine, like the Nim machine a decade before it, was built to play rather than to prove, and playing well on most positions is what a measurement can do — the circuit was right on ninety-eight positions in a hundred. Holding a board against an opponent who searches for the hundredth is a different task, and it needs a certificate, because the opponent’s search will find any chain the strategy has left open. The theorem that names no move proved the first player wins Hex without saying how; a certificate says how and proves it in the same breath; a measurement says how without proving anything. The three are not stages of one thing.

The surprising connection is to equality, of all things. A pairing holds when every chain contains a pair, and two games are equal when no context tells them apart. Both statements quantify over a whole family — every chain, every game there is — and in both a summed or sampled reading of the family comes out coarser than the statement: the 184 contexts merge games that differ, and the chain count prefers a pairing that leaves chains open. In both, the repair is not a larger sample but a finite certificate checked to the end: the difference of two games played out, a pairing tested against every chain. A winning strategy that is a spanning tree is the case where the quantifier collapses into a count, two edge-disjoint trees, and it is the exception that makes the rule visible: when a certificate can be counted, a theorem says so, and the theorem is the sentence.

The convention named #

Hex on rhombic boards of $n$ rows and $n + 1$ columns, Down joining the top and bottom edges — the nearer pair — and moving second, Across joining left and right. A minimal chain is a set of cells joining Across’s edges from which no cell can be removed. A pairing is a set of disjoint pairs covering every cell, and it holds the board when every minimal chain contains both cells of some pair. “Best” under a score means the pairing whose pairs’ scores add to the most, found exactly; ties go to the pairing the recursion meets first. The listening score starts every chain at weight one and multiplies the weight of each chain the current pairing misses by the stated factor, a hundred rounds at most.

What the scores cannot show #

That no board-only score works. Four scores were tried, plus one rule that reweights. Some other function of the board might single out a winning pairing on every board of the family; the arithmetic of sums above says it would have to avoid trading chains for double cover, and nothing here proves that impossible for every score one could write down.

How the listening score behaves past four by five. Five by six has thirty cells, past what these tables can hold, and the rate at which the reweighting converges — or whether any fixed rate does — is unmeasured there. The fact that the three rates tried split two to one on four by five is a warning that the answer on larger boards may depend on tuning that only a search could supply.

And why the diagonal is the pairing it finds. Two boards, two convergences, two diagonals. That is suggestive and not a pattern.

Still open: whether the listening converges on a rule #

Both times the reweighted count held a board, the pairing it held with was the diagonal one, the pairing that has a sentence. If that persists — if on every board where the reweighting converges it converges to the reflection across the diagonal — then the chain weights it ends with are a numerical shadow of the argument, and reading them might say which chains the argument is really about. The measurement is the final weights themselves on three by four and four by five: which chains the loop had to raise, by how much, and whether those chains are the ones crossing the diagonal at the place the reflection argument uses. Where the needle has a sentence found Chomp’s opening describable on exactly the two families where it is a pairing; the same question asked of Hex would ask whether the weights, too, can be said in a sentence.