A current through the board

The Nim machine of 1940 could play perfectly because Nim has a theorem that names every winning move, and a relay cabinet can compute it. Hex has a theorem too, and it names nothing. Strategy stealing proves that the first player wins Hex on every square board, in a few lines, and the proof contains no move and no way of finding one. A machine that was going to play Hex needed a rule that was not a theorem.

Claude Shannon and Edward Moore built one at Bell Laboratories in the early 1950s, and Shannon described it in a 1953 survey of what computing machines could do. Shannon had a particular reason to think about connection games as circuits: the game he designed himself, the one whose winning strategy is a spanning tree, is literally played on a network of links, and Hex is the version of it played on points instead. The machine did not search. It represented the board as a network of resistors, applied a voltage across it, and chose its move from the shape of the electrical potential that resulted. The idea was taken up again half a century later by Hex programs that read a position as a circuit, and it is a good idea: a connection game is about routes, and a network of resistors is a machine for summarising all the routes across a board at once.

Because Hex boards up to about sixteen cells can be solved outright, the rule can be scored against the truth — every position, every reply. The score is the surprising part. The circuit is almost always right, and it still loses.

A board wired as a circuit #

Hex is played on a rhombus of cells, each with six neighbours. One player, here called Down, joins the top edge to the bottom; the other, Across, joins the left edge to the right. Players take turns placing a stone on any empty cell, and a filled board is always won by exactly one of them. The boards here are small rhombi of r rows and c columns, and on a board that is not square the player whose edges are closer together has a head start.

The circuit is built for one player at a time. For Down, every empty cell is a unit resistor, a cell Down already holds is a wire of no resistance, and a cell Across holds is cut out of the circuit altogether. Neighbouring cells are connected, the top edge is one terminal and the bottom edge the other, and the resistance of the network between them is a single number describing Down’s prospects. It is low when there are many short routes still open, because parallel routes lower a resistance and short ones lower it most; it is high when Across has cut most of them; it is infinite when Down has no route left at all.

Two ways of turning that number into a move are measured here, because the historical descriptions are not precise enough to say which the machine used and the difference between them turns out to be informative.

The ratio rule looks one move ahead. For every empty cell it imagines the mover’s stone there, solves both players’ circuits, and takes the cell after which the opponent’s resistance divided by the mover’s is largest. That is the form the idea took in later programs, and it costs two circuit solutions per candidate.

The current rule does not look ahead at all. It solves both circuits for the board as it stands, measures the current flowing through each empty cell in each, adds the two, and takes the cell carrying the most. That cell is where the routes of both players are squeezed together — a bottleneck, which is what the potential-field language of the original description suggests. It costs two circuit solutions per move, whatever the size of the board.

Both are rules of exactly the kind the stealing argument cannot supply: a function of the position that names a cell. The question is how often the cell is right.

Right on nearly every position #

On a board small enough, “right” has an exact meaning. A cell is a winning move if the player who takes it can then win against every defence, and the solver decides that for every position by searching all the continuations, working backwards from filled boards with a table of positions already settled. On the full-size board that search is out of reach for any machine — deciding who wins a general Hex position is among the hard problems — which is the whole reason a rule like the circuit is needed, and the reason small boards are the only place it can be graded.

The numbers are high by any standard. On three by four there are 69,666 positions from which the player to move can win, and the ratio rule takes a winning cell on 99.1 per cent of them, the current rule on 99.2. A cell chosen at random manages 62 per cent. On three by three, where the winning cells are fewer, random falls to 55 per cent and both rules stay above 98. On four by four the sample is harder — 88 per cent for the ratio rule and 92 for the current rule — and the rule that looks no move ahead is the better one there, which says that the extra computation of the look-ahead buys nothing the plain bottleneck does not already know.

A rule that picks a winning cell ninety-nine times in a hundred sounds like a solved problem. It would be, in a game against an opponent who plays at random: the rule would almost never meet one of its bad positions, and when it did the opponent would almost never exploit it. The count above treats every reachable position as equally likely, which is the right measure of how good the rule is as an evaluator and the wrong measure of whether it wins.

The misses are not spread evenly. They cluster early, when few routes have been cut and many cells look alike to the circuit — each is on roughly as many routes as its neighbours, so the current divides almost evenly and the choice between them is decided by small differences that do not track who wins. Late in the game the board is nearly decided, most cells are either on a player’s only remaining route or on none, and the circuit reads that correctly almost every time. That is exactly backwards from where a player would want the rule to be good, because an early mistake has a whole game in which to be punished. It is also the opposite of the usual story about evaluations inside a search, where a search may stop at a quiet position and trust the evaluation there: a quiet Hex position, with few stones and many routes, is exactly where the circuit is least trustworthy.

The opponent picks the position #

So the question that matters is a different one. Give the rule one side of a board that side wins with perfect play, let it play from the empty board, and let the opponent try every reply at every turn. If there is a single line along which the rule loses, the rule does not hold the board — an opponent who knows the line, or who searches for it, will play it every time.

The table divides cleanly along one line, and the line is not the size of the board.

Moving first, the rule mostly wins. On three by three, three by four, four by three and three by five, the rule playing the side that wins wins every line — often the side with the nearer edges, which can afford an imprecise move. The exception is the one board here where the first player’s advantage is the only advantage: four by four, square, where strategy stealing says the first player wins and nothing more. Both rules lose it.

Moving second, the rule loses every board past two rows. On a board of n rows and n + 1 columns, the player joining the nearer edges wins even moving second — a board one column wider shows how, with a pairing of cells that names a reply to every move. On two by three and two by four the circuit holds that side. On three by four, four by three and three by five it does not. It is winning at the start, it has a winning cell at every turn until the one where it slips, and an opponent who plays the right three stones walks it to that turn.

Defending is where a heuristic is weakest because a defender has to be right at every turn and an attacker needs to be right about which turn to press. The first player on a board it wins has slack: it can play a second-best cell and still be winning, because its position was winning with room to spare. The second player on a board it wins only narrowly has none, and an opponent who searches will find the one turn where the circuit’s second choice was the only choice.

The slip, drawn #

The losing line on three by four is short enough to show whole.

What each rule does is recognisable. The ratio rule blocks: Across’s stone in the bottom row threatens to link towards Down’s bottom edge from the left, and the cell beside it is the one that most raises Across’s resistance. The current rule takes the bottleneck in the middle of the board, the cell through which the most routes of both players still pass. Both are sensible Hex moves, of the kind a beginner is taught — block the threat, take the centre. Neither wins. The cells that win are the ones that build Down’s own connection toward the bottom edge in a way Across cannot answer twice, and the circuit, which averages over every route rather than asking which routes survive a reply, ranks them in the middle of the pack.

This is the heart of it. A resistance is a sum over routes, weighted by how short and how many; Hex is decided by whether some route survives an opponent who cuts one cell per turn. Those are different questions, and they agree most of the time — which is why the census is so high — and disagree exactly where a route is threatened in two places at once, which is where games are decided.

The four-by-four slip is the same shape: a block that the circuit prefers because it raises the opponent’s resistance most, where the winning move is a cell that makes the mover’s own connection unbreakable. The opponent’s two stones have been placed precisely so that blocking looks urgent and is not.

How far wrong the circuit is when it is wrong #

A natural hope is that the misses are near-misses — that the winning cell is always the rule’s second choice, so that a little look-ahead would repair it. The census says otherwise.

The winning cell is in the rule’s top three on about three quarters of its misses, so the circuit is rarely far wrong. But it is most often third rather than second, and on more than a quarter of the misses it is fourth or lower. A repair that consulted the rule’s top two would miss most of them; a repair that searched the top three would need to search deeply enough to tell them apart, and that is the search the circuit was supposed to replace. The same shape appeared when the winning reply turned out to be the fourth choice for a different ranking of cells on a different board: a heuristic ordering puts the right move near the top and not at it, and near the top is not good enough when the opponent picks the position.

Two rules that fail in opposite places #

That comparison is the surprising connection in the measurement. One other rule of the same kind has already been scored against Hex. A potential that names every move gave Down, defending, the cell through which Across’s unfinished chains weigh most in the Erdős–Selfridge sense — each chain weighted by one half for every cell Across still needs. That rule held every board three rows deep that Down can win, including three by four and three by five, and lost only when the board reached four by five.

The circuit loses three by four and three by five. As an evaluator it is far better than the potential — it reads the whole network at once, knows that two parallel routes are better than one, and is right on ninety-nine positions in a hundred. As a defender it is worse. The potential is a defensive rule by construction: it weighs only the opponent’s chains and blocks the heaviest, and its theorem guarantees a defence on the smallest boards and nothing else. The circuit weighs both sides at once and takes the cell that matters most in the aggregate, and in the aggregate the cell that builds one’s own route and the cell that blocks the opponent’s are traded off against each other — which is fine on a board with slack and fatal on a board without any.

Neither rule is the pairing that actually wins those boards, and three pairings and no order found that no fixed ordering of cells can reproduce what the pairing does. The circuit is not a fixed ordering — it changes with every stone — and it still fails, one board earlier than the potential. Whatever holds a board with no slack is not a better score for cells; it is a reply to the opponent’s particular move, which is what a pairing is and what neither potential nor current contains.

What the machine’s builders could not have known #

Nothing in this essay could have been computed in the 1950s. The exact solution of a board of twelve cells is a search over a hundred thousand positions with a table to hold them; four by four is millions. Shannon and Moore had a rule, a board and human opponents, and no way to know how often the rule’s move was right. The only check available to them was playing it, which measures something closer to the second number here than the first — how often the rule wins against the opponents it happens to meet — and a human opponent who does not search will rarely find the one line that beats a rule so often right.

That is also why the machine is a better piece of history than a curiosity. The Nim machine showed a theorem computed in hardware; the Hex machine showed the first move rule of the kind every game-playing program since has depended on — an evaluation that summarises a position without solving it. Its failure on small boards is the failure every evaluation has: it is scored by the positions it is shown, and it loses on the positions it is steered to.

The conventions under the counts #

The board is a rhombus of r rows and c columns stored row by row, with neighbours in six directions, Down joining top to bottom and moving first unless a row of the table says otherwise. In each circuit an empty cell is a unit resistance, a stone of the player’s own a wire (a resistance of one millionth, so that the linear system stays solvable), and an opponent’s stone is removed; each edge is a terminal connected to every cell along it through that cell’s own resistance. The current through a cell is half the total current on the connections that meet it. A rule breaks ties by taking the lowest-numbered cell. “Winnable” means the player to move has at least one cell after which it wins against every defence, as decided by exhaustive search. The census counts each distinct position once, however many move orders reach it; the four-by-four sample is three thousand positions taken at uniformly random move numbers along random games, with a fixed seed.

What the counts cannot show #

The machine’s own rule is not reconstructed here. The descriptions that survive say it chose its move from the potential field of a resistance network and do not say precisely how, and the two rules measured are the two natural readings of that description, not a replica of the hardware. Nothing here says how the machine did against people, how large a board it played on, or whether its builders tuned it. And the scores are for boards of at most sixteen cells, where exact play is computable; whether the circuit’s per-position accuracy rises or falls on the eleven-by-eleven board people actually play is not something a small board can say, though the four-by-four sample, lower than every smaller board, points one way.

Still open: what a pairing knows that a reply does not #

The failures all have the same shape — a position where the right move answers the opponent’s last stone rather than being the best cell on the board in general — and the obvious repair is in the table above. Made into replies, taking their best cell among those touching the opponent’s last stone, both circuit rules hold and lose exactly the boards they held and lost before. Locality is not what they were missing.

A pairing, the strategy that does hold these boards, is also a reply: it answers each cell with a fixed partner, often though not always a neighbour. What it has that a local circuit lacks is commitment. It answers the same cell with the same partner every time, whatever else is on the board, so that each of the opponent’s threats is met by a response fixed before the game began; the circuit re-measures the whole network at every turn, and on the turn that matters it measures a block as better than the partner. Whether any rule that measures can be made to commit — a circuit consulted once, at the start, to choose a table of replies, and then never again — and whether such a table holds three by four where the running circuit fails, is a finite question on boards this small. It would say whether the thing the circuit is missing is a better measurement or a willingness to stop measuring.