A circuit asked once

The Hex machine Claude Shannon and Edward Moore built in the early 1950s, a decade after the Nim machine that knew one theorem, chose its moves by wiring the board as a network of resistors and reading the move off the current. Scored against exact play, its rule is right on ninety-eight or ninety-nine positions in a hundred on every board small enough to solve, and it still loses: every board of three rows or more that it has to defend, because the opponent needs to find only one of the bad positions and can steer the game there.

The strategy that does hold those boards is a different kind of object, and it is not the kind the theorem that names no move could have supplied. On a board of n rows and n + 1 columns the player joining the nearer edges wins even moving second, and a board one column wider shows the strategy: every cell has a partner, and whatever cell the opponent takes, the defender takes its partner. That is a pairing. It looks at nothing, measures nothing and is decided before the first stone is placed. The circuit does the opposite — it re-solves the whole network at every turn and takes whatever the measurement says.

The circuit essay ended by asking which of those differences matters. Making the circuit answer the opponent’s last stone, rather than ranking the whole board, changed nothing: the local version held and lost exactly the boards the board-wide version did. What was left was commitment. A pairing answers the same cell with the same partner every time, so each threat is met by a response fixed in advance; perhaps the circuit is missing not a better measurement but a willingness to stop measuring.

That is a finite question on these boards, and it has an answer. The circuit can be made to commit in several ways, each played against every line the opponent can choose, and none of them holds a board the running circuit lost. The reason is not that commitment fails. It is that the circuit, asked once, does not produce anything worth committing to.

A table that answers with four cells #

The simplest commitment asks the circuit once per cell. Put a single Across stone on cell x of the empty board, solve both players’ networks, and write down the cell the rule takes for Down. Do this for every cell and the result is a reply table — the same shape of object as a pairing, an answer for each of the opponent’s moves, chosen by the machine’s own judgement and then frozen. In play, Down answers Across’s stone on x with the table’s entry for x, without measuring anything, and measures only when the entry is already occupied and something has to be done.

On three by four the current rule’s table is in the figure above, and it has a striking shape: twelve openings, four answers. Whichever of the first three cells of the top row Across opens on, the circuit answers in the top-right corner. Cells 3, 5, 6 and 8 between them answer everything, three openings each. The ratio rule, which looks one move ahead, also uses four cells.

The pattern holds on every board measured. The current rule uses two answers on two by three, four on two by four and three by four, five on three by five and eight on four by five; the ratio rule uses two, two, four, four and four. On four by five, a board of twenty cells, the ratio rule’s busiest answer serves nine openings. And almost no cell’s answer answers it back — one such pair on three by four under the current rule, three on four by five.

The reason is in what a resistance is. A single stone on an empty board removes one cell from the opponent’s network and makes one cell a wire in its own. The effect on the network as a whole is small, and the cells the circuit valued before the stone — the ones through which the most routes squeeze — are mostly the cells it values after. The circuit is a summary of the whole board, and a summary is built not to be moved much by one detail. That is exactly what makes it a good evaluator, right on ninety-nine positions in a hundred, and exactly what makes it a poor source of replies: a pairing needs the answer to depend on the question, and the circuit’s answer depends mainly on the board.

A table with four entries is a commitment in name only. The first opening in each group of three is answered from the table; the second finds its answer already filled, and the rule is back to measuring the board as it stands. So it is no surprise that the table plays like the running circuit, but it is worth checking that it plays no better.

Every board the circuit lost, lost again #

Each strategy below is played for Down, moving second, from the empty board, against every cell Across can take at every turn. A single line along which Across joins its edges is a loss, because an opponent who has found the line can play it every time. That is the standard the circuit essay graded the machine by, and it is the only one that answers whether a rule holds a board.

The table changes nothing. On both two-row boards it holds, as the running circuit did; on three by four, three by five and four by five it loses, as the running circuit did. The losing lines are not the same lines — on three by four the line that beats the table runs through openings whose answers are already taken, so that the table hands the decision back to the measurement at the turns that matter — but the verdict is the same on every board.

Four by five deserves a sentence of its own, because it is new here. It has twenty cells, past what an exhaustive solution of Hex reaches here, so the circuit essay could not grade the running rule on it. Grading a rule needs no solution of the board: Down’s moves are fixed by the rule and only Across’s are searched, so the whole tree is at most a few hundred positions. The running circuit loses four by five, and so does its table.

The table was never really a commitment, so this is not yet the answer. The question was whether commitment as a pairing has it — whether the circuit, made to produce a whole pairing rather than a table, chooses one that holds.

Making the circuit choose a pairing #

A pairing is a partition of the board into disjoint pairs of cells, played by answering each cell with its partner — the same device that, in an impartial game, a pairing that is not a symmetry found explaining far more positions than any geometric mirror. On a board of twelve cells there are 10,395 of them. Which pairings win is known: Down’s pairing holds exactly when every one of Across’s minimal chains — every set of cells joining left to right with no cell to spare — contains both cells of some pair, because then each chain needs a cell Down has already taken by the time Across completes it. Three pairings and no order counted them: three on three by four, three on four by five, and on four by five each of the three uses every cell.

The circuit can be asked to choose one. For every pair of cells x and y, it has already said how good y is as an answer to a stone on x, and how good x is as an answer to y. Weigh each pair by those two judgements together, and the pairing the circuit likes best is the one whose pairs add up best. That is a fixed, finite optimisation, and it can be solved exactly by working through the cells one at a time.

There is a choice in what “how good” means, and it turns out to matter more than anything else. The plainest is the rank: y’s place in the circuit’s ordering of answers to x, first, second, third. Under that weighting, on three by four the circuit’s favourite pairing is the one on the left below.

The comparison is cleaner than anyone could have hoped. Both pairings keep every pair inside a row. A row of four cells can be paired in exactly two ways that keep the pairs inside it — the outer two together and the inner two together, or two neighbouring pairs side by side — and the circuit’s favourite and the winning pairing make opposite choices in all three rows. Where the winner pairs neighbours, the circuit nests; where the winner nests, the circuit pairs neighbours. By the circuit’s own weighting the winning pairing is not far down the list: it is somewhere from 21st to 37th of 10,395, tied with others of the same weight. It is far from the bottom and it is not the top.

And what the circuit chose loses.

The losing line shows exactly why. Across takes cell 0, and Down takes its partner at the far end of the top row; Across takes cell 1 beside it, and Down takes its partner, cell 2. Across steps down to the middle row, takes two neighbouring cells there, and Down answers each with its partner; and the same in the bottom row. Down has answered every stone with its partner, exactly as committed, and Across has joined its edges. The chain is a staircase, two cells a row, and in every row its two cells belong to different pairs. Of Across’s twenty-five minimal chains on this board, four contain no whole pair of the circuit’s pairing, and an opponent needs only one.

That is the precise sense in which commitment is not enough. A pairing is a promise to answer every move, and a promise is only as good as what was promised; the circuit’s pairing answers everything and blocks nothing on the staircase. The winning pairing, nesting in the middle row where the circuit paired neighbours, puts both of the staircase’s middle cells into one pair, and the staircase cannot be completed through it.

One reading in eight #

Rank is not the only way to read a circuit, and a careful reader of the last section should object that the result might be an artefact of it. Ranks throw away how much better the first choice was than the second. So the same construction was run with the scores themselves, read three more ways: rescaled within each consultation to run from nought for the worst answer to one for the best; divided by their total, so that each consultation’s scores are shares; and as measured, current in amperes or the logarithm of a resistance ratio. With two rules that is eight readings of one circuit into a pairing, and each was played strictly on all five boards.

One of the eight finds a winning pairing on three by four. The current rule with each consultation’s scores rescaled from nought to one picks exactly the winning pairing drawn above — nests in the middle row, neighbours in the top and bottom — and holds the board. It is the only reading that does, and it pays for it at once: on two by four, a board every other reading of the current rule holds, its pairing loses. On three by five and on four by five all eight readings lose. On four by five the best of them shares six of its ten pairs with a winning pairing, and the four it gets wrong are enough.

That table is the clearest single answer to the question this essay began with. If commitment were what the circuit lacked, one reasonable way of turning its judgement into a pairing should hold the boards the running circuit lost, and several would agree about which pairing to commit to. Instead, the choice between a winning pairing and a losing one on three by four turns on whether the scores were rescaled before they were added — a decision about arithmetic, not about Hex — and the reading that gets it right gets a smaller board wrong. The circuit’s preferences do not contain the winning pairing. They contain several pairings of nearly equal weight, and which one comes out on top is decided by details of the reading that have nothing to do with which chains Across can complete.

How far measurement and commitment drift apart #

The last measurement turns the question round. Instead of asking the circuit to choose a pairing, give it the winning one and ask how often the circuit would have chosen the same cells on its own.

Take the pairing that holds every board of n rows and n + 1 columns — the diagonal one, in which each cell is answered by its reflection across the board’s diagonal, moved one column right. Walk every line Across can play against it. At every turn where Down plays a partner, record the rank the running circuit gives that partner. If the circuit’s first choice were usually the partner, the circuit and the pairing would be nearly the same strategy, and the circuit’s losses would be a handful of unlucky turns.

It is not. On two by three the circuit would itself take the partner on 66.7 per cent of the 54 turns along the pairing’s lines; on three by four, on 40.9 per cent of 2,916 turns; on four by five, on 24.9 per cent of 393,660 turns, with the partner as low as the circuit’s eighteenth choice of the twenty cells. The share falls steadily as the board grows. On the smallest board the circuit and the pairing are close enough that the circuit holds it; by four by five, three quarters of the moves a winning commitment makes are moves the circuit would not make, and a quarter of them are outside its top six.

The same number was measured once before with a different rule. A potential that names every move weighs each cell by Across’s unfinished chains through it, and when the winning reply turned out to be the fourth choice, the Erdős–Selfridge potential took the diagonal pairing’s cell on 26.1 per cent of four-by-five turns. The circuit, a far richer evaluation that reads every route at once, takes it on 24.9 per cent. Two rules built on unrelated ideas — one a sum over Across’s unfinished chains, one an electrical network — agree with the winning strategy on almost exactly the same share of turns, and both fall short of it in the same way. Whatever the pairing knows, it is not more of what either of them measures.

Where the commitment comes from #

The connection worth carrying away is between this table and the one in three pairings and no order. That essay searched every fixed order of cells — one list, Down always taking the first empty cell on it — and found that none holds any of the boards the pairing is known for. A fixed order is the far end of a spectrum: an answer that depends on nothing at all, the same list whatever Across has done. The circuit’s reply table sits one step along it, an answer that depends on the opponent’s stone a little, so that twelve openings get four answers. A pairing is the other end, where the answer depends on the stone entirely and twelve openings get twelve different answers.

Measured on these boards, holding a board with no slack needs the far end of that spectrum. The circuit is built to be at the near end, because an evaluation that changed completely with every stone would be a poor evaluation; it would not be summarising the position, it would be reacting to the last move. So the two virtues pull against each other. The property that makes the circuit right on ninety-nine positions in a hundred — that it reads the whole board and is not moved much by any one stone — is the property that stops it producing a strategy of the kind that holds these boards.

Lehman’s solution of the switching game Shannon himself designed has the same shape and makes the point from the other side. There the winning strategy is a pairing of links between two trees, read off the structure of the graph rather than off any measurement of it, and once the trees are found the strategy commits completely: whichever link is cut, the partner in the other tree. Nothing in Lehman’s criterion is a score. The trees are a certificate that a particular set of answers works, and Hex pairings are certificates of the same kind, checked against every chain rather than estimated from a network — the distinction a strategy is not a certificate draws between what wins and what can be shown to win. A measurement can sit near a certificate. It does not produce one.

The arithmetic under each table #

The boards are rhombi of r rows and c columns, cells numbered row by row from the top left, with six neighbours each; Down joins top to bottom and moves second throughout, and every board measured is one Down wins moving second. The circuits are the ones scored in the circuit essay: an empty cell a unit resistance, one’s own stone a wire, the opponent’s stone removed, each edge a terminal. The current rule takes the empty cell carrying the most current in both networks together; the ratio rule takes the cell after which the opponent’s resistance divided by the mover’s is largest. Ties go to the lower-numbered cell.

A reply table entry for cell x is the rule’s choice with Across’s single stone on x and nothing else on the board. In play, if the entry is filled, Down falls back on the running rule. A pairing is a set of disjoint pairs covering the board, one cell left over on a board with an odd number of cells; its weight, under the rank reading, is the sum over pairs of the rank each cell gives the other as an answer on an empty board, and the pairing chosen is the lightest, found exactly by working through subsets of the board. Under the three score readings the weight is minus the sum of the two scores, read after the stated rescaling. When the partner of Across’s cell is filled, which a full pairing never allows but a fallback must cover, Down measures.

“Holds” means Down’s strategy joins its edges on every line Across can choose, checked by trying every Across move at every turn and remembering positions already settled. A winning pairing is one meeting each of Across’s minimal chains in a whole pair, and the agreement measurement walks every line against the diagonal pairing, one turn per Across move. The positions graded run from seven on two by three to about three hundred on three by five; the four-by-five agreement walk visits 393,660 turns, each one a circuit solved on twenty cells.

What eight readings cannot rule out #

There are more ways to read a circuit than eight. A pairing could be weighed by the circuit’s judgement in positions other than the empty board, by the product of the two scores rather than their sum, or by a weighting tuned on the board it is then tested on. Nothing here says that no function of the circuit’s output produces a winning pairing on four by five; the measurement says that eight natural ones do not, that they disagree with each other, and that the one which finds the three-by-four pairing loses a smaller board. A tuned weighting that found every winning pairing would be a curiosity rather than a defence of the circuit, because it would have been chosen by checking against the answer the circuit was supposed to supply.

Nor is any of this a claim about the machine of the 1950s, whose precise rule is not recorded; the two rules are the two natural readings of the descriptions that survive, as in the circuit essay. The pairings counted here are pairings in the strict sense, a partner for every cell; a strategy that commits to answers for some cells and measures for the rest sits between the table and the pairing, and is not measured. And every number is for boards of at most twenty cells, where every line can be tried. Whether a circuit’s choices come nearer to a winning commitment or drift further from it on the eleven-by-eleven board people play is not something a small board can settle, though the agreement measurement, falling with every row added, points one way.

Still open: whether a pairing can be read off any measurement #

The negative here is about a circuit consulted on the empty board. The winning pairings on these boards are certificates — sets of pairs that meet every chain — and the pairings the circuit chooses are near them but not at them: six of ten pairs right on four by five, none right on three by four under the rank reading, every pair right under one rescaling and wrong the next board down.

That leaves a question with a finite form. Is there any score of a pair of cells, computed from the board alone, whose best pairing is a winning one on every board of n rows and n + 1 columns? The diagonal pairing has a sentence — reflect across the diagonal, move one column — and a sentence is a function of the cells’ coordinates, not of any measurement. If the only scores that work are ones that already encode the geometry of the diagonal, then a pairing is not something a measurement finds but something an argument supplies, and the gap between the Hex machine and the strategy that beats it is the gap between estimating a position and proving a claim about it. If some score that knows nothing of diagonals works on every board to five by six, the gap is narrower than it looks, and the circuit was missing a better measurement after all.