The teacher's game

The machines in this history have one thing in common: each of them scores something on the board and moves where the score is highest — except the first, the Nim machine of 1940, which computed a theorem and scored nothing. Shannon and Moore’s Hex machine of the early 1950s scored cells by the electrical potential across a network of resistors, and a current through the board found it taking a winning cell almost every time and still losing every board it had to defend past two rows. Its descendants in this history scored pairs of cells by the chains of Across’s that hold both, and played the heaviest set of pairs; a circuit asked once had already found that committing the resistor machine to a fixed table of replies did not save it. The weights were not the argument took that machine as far as it would go on four by five and found two things. Told which winning pairing to prefer — corrected, Rosenblatt-fashion, each time a rival outscored it — the machine could be taught any of the three winners in a dozen steps. And on three by four there was a winner it could never be taught, because another winning pairing held at least as many whole pairs as it on every one of the board’s 25 chains; whatever the weights, the rival scores at least as much.

That left a sharper question than either result. Being covered chain by chain by one rival is a reason a winner can be out of reach. Being covered on average by a mixture of rivals — some outscoring it on these chains, others on those — would be another, harder to see and impossible to check one rival at a time. The question was whether the second ever happens, and the boards on which to ask it were five by six and beyond, where the subset table the machine had used to find its strongest rival gives out.

A rival found by a theorem from 1965 #

The machine has three parts and only the last one changes size badly. Each of Across’s minimal chains carries a weight; a pair of cells scores the total weight of the chains that hold both; and the machine plays the pairing of all the cells whose pairs score most. Teaching it means finding, at each step, the strongest rival to the pairing it is meant to prefer — the heaviest pairing that differs from the target somewhere — and moving weight toward the chains where the target holds more whole pairs than that rival and away from the chains where it holds fewer.

Finding the heaviest pairing of thirty cells is the step that broke. The earlier machine did it by recording the best pairing of every subset of the cells, which is a table of 2²⁰ entries on twenty cells and 2³⁰ on thirty, a billion. But a pairing of all the cells is a perfect matching of the complete graph on them, and the heaviest perfect matching of any graph is what Jack Edmonds’ blossom algorithm of 1965 computes, in time that grows as the cube of the number of cells rather than as two to its power. It was checked here against the subset table on 1,950 sets of random weights on boards up to twenty cells, ties and zero weights included, and agreed every time; on 6 × 7 it finds the heaviest of the board’s pairings of 42 cells in milliseconds. The strongest rival is then the heaviest pairing with one of the target’s pairs forbidden, taken over each pair in turn, since any pairing other than the target lacks at least one of them.

The census of two reflections and a corner supplies the targets: three winning pairings on every board from 3 × 4 to 6 × 7, the diagonal reflection, the cross reflection that joins the board’s far corners, and the cross reflection with its corners repaired.

Taught, every winner from four by five on #

On 4 × 5 the new machine reproduces the old one’s counts exactly — six corrections for the diagonal pairing, four for the corners pairing, twelve for the cross pairing — which is the check that the blossom rival and the subset rival are the same rival. On 5 × 6 it takes ten, six and sixteen. On 6 × 7, with 16,097 chains to weigh, it takes thirteen, nine and twelve. Every winning pairing on every board from 4 × 5 to 6 × 7 can be made strictly the heaviest, and none of them needs more than sixteen corrections from weights that all start at one.

The count of corrections does not grow with the board in any way that matters. Chains multiply eightfold from 5 × 6 to 6 × 7 and the corrections go from ten to thirteen for the diagonal and down from sixteen to twelve for the cross pairing. What a correction does is move many chains at once — every chain where the target and its rival differ — and the number of rivals the teacher has to see off is small because the winners are few and the losers are far behind them. The machine’s difficulty was never the size of the board.

The last column of the table is the margin by which the target ends heaviest, divided by the total weight on the chains. It is the number that matters for the question this essay is about, and the next sections say why.

Covered on every chain #

The one failure is the same as before, and seeing it whole is what makes the general question precise.

On three by four the cross pairing holds every chain once and three of them twice. The corners pairing holds the same chains at least as often and eight of them more. A machine that scores a pairing by adding up chain weights times whole pairs gives the corners pairing at least the cross pairing’s score whatever the weights, so the cross pairing can never be the strict maximum. The perceptron discovers this at its first step: the strongest rival covers the target chain by chain, there is no direction to move the weights in, and it stops. The diagonal pairing covers the cross pairing too, on eight chains of its own.

This is the strongest statement a chain-weighing machine’s failure can carry, and it is a statement about the board, not about the machine. Any procedure of the same shape — any circuit reading, any learned score, any hand-tuned potential that adds a weight per chain per whole pair, like the one a potential that names every move plays with — is blind to the cross pairing of 3 × 4 for the same reason. It wins, and it is invisible.

The question as a game #

Now the question the earlier essay left. Suppose no single rival covers a winner chain by chain, but a mixture does: a third of the time this rival, two-thirds of the time that one, and on every chain the rivals’ average holding is at least the winner’s. Then no weighting can make the winner heaviest either, because a weighting under which the winner beat every rival would have it beat their average, and their average is at least as large on every chain. So mixtures are a second way to be out of reach, and the question was whether it ever happens without the first.

The way to settle it in general is to see that teaching the machine is a game. The teacher picks weights on the chains; a rival picks a pairing other than the target; the teacher’s payoff is the target’s score minus the rival’s. The teacher wants a weighting under which every rival loses. The rival, choosing after, wants a pairing that scores at least as much. This is a finite zero-sum game in the sense von Neumann defined in 1928, and its value — what the teacher can guarantee when both sides play their best mixtures — is positive exactly when some weighting makes the target strictly heaviest.

Von Neumann’s minimax theorem says the value is the same whichever side commits first, and the form of it this question needs is the one Jean Ville proved in 1938, in the paper that gave the theorem its first elementary proof: a theorem of the alternative. Exactly one of two things is true. Either there are non-negative weights on the chains under which the target outscores every rival, or there is a mixture of rivals that holds, on every chain, at least as many whole pairs on average as the target. There is no third case. A winner the machine can never be taught is, with no exception, a winner some mixture of other pairings covers — and a winner it can be taught is one no mixture covers.

That turns the open question into a finite check on each board. Every winner the perceptron reaches has a weighting that makes it heaviest, so by Ville’s alternative no mixture covers it. The one winner it does not reach is covered by a single rival. So on every board from 3 × 4 to 6 × 7, the winners a chain-weighing machine can never choose are exactly the winners another single winner covers chain by chain, and mixtures add nothing. The margin per unit of weight in the first table is a lower bound on the game’s value for each winner: it is above nought for every winner but one.

A few chains of its own #

The cross pairing is out of reach on 3 × 4 and within reach on every larger board, and the reason it escapes is visible in the chains.

To be out of reach a winner has to be behind or level everywhere. On 3 × 4 the cross pairing is: zero chains ahead of either rival. On 4 × 5 it is ahead of the corners pairing on three chains of 148, and that is enough — three chains on which no weighting of the corners pairing can match it, and a teacher who piles weight on those three chains can lift it clear. On 5 × 6 it is ahead on 20 of 1,225, on 6 × 7 on 170 of 16,097. Against the diagonal pairing it leads on many more, 17, then 199, then 3,440.

The narrowness of the escape against the corners pairing is not an accident of the counting. The two pairings share every pair but three, at the board’s two far corners, so a chain can tell them apart only if it passes through those six cells, and it favours the cross pairing only if it holds more of the three long cross pairs than of the three pairs that replace them. On 3 × 4 no minimal chain does. On the larger boards a few do, and they are the whole of the cross pairing’s escape.

On 4 × 5 the three chains can be drawn. Each runs from near the top-left corner to near the bottom-right, eight or nine cells long, and each takes in both ends of two of the cross pairing’s long pairs: the pair joining the cell beside the top-left corner to the right-hand column, and the pair joining the cell below the corner to the bottom row. The corners pairing has a long pair of its own across the same region, and each of these chains holds it — one whole pair against two. Nowhere else on the board is the cross pairing ahead of its near twin. A chain-weighing machine cannot see a strategy; it can see where one strategy holds more than another, and on 4 × 5 the cross pairing’s whole claim to be seen rests on three diagonal chains through the two far corners. On 3 × 4 no chain does that, and the claim does not exist.

The distribution on 5 × 6 shows how thin the margin is. Against the corners pairing, the cross pairing is level on two chains in three and behind on almost all the rest; the twenty chains on which it leads lead by a single pair. That is still a strict lead somewhere, and Ville’s alternative needs nothing more: if a winner is ahead of every single rival on at least one chain, a mixture could still cover it, but the perceptron’s success shows that on this board none does. The thinness says only that a teacher has to find those few chains, and the last figure shows that it does.

Where the weight goes #

The perceptron starts every chain at a weight of one and moves the weights by a quarter at a time, never below nought. What it ends on, when taught the cross pairing, is not a scattering.

On 5 × 6 the chains where the cross pairing holds more whole pairs than the corners or the diagonal pairing are 215 of 1,225, eighteen per cent, and at the end they carry 57 per cent of the weight. On 6 × 7 they are 22 per cent of the chains and carry 66 per cent. Of the remaining chains, most have been driven to nought: on 5 × 6 only 432 chains keep any weight at all. The teacher has done exactly what the theorem of the alternative implies a successful teacher must do — found the chains on which no rival covers the target as well, and leaned on them.

The surprise is the other column. The chains the cross pairing holds by a single pair — the places where its defence has no slack, which two reflections and a corner found are 62 per cent of the chains on 5 × 6 — end with only 32 per cent of the weight, and on 6 × 7 with 16. A reader might expect a machine learning a strategy to concentrate on where the strategy is most fragile. It does the opposite, and the reason is the game: every winner holds every chain at least once, so a chain the target holds once is a chain on which every rival winner ties it or beats it. Those chains cannot separate the target from anything. The weight goes where the target is better, not where it is weakest, and what the machine learns is not the strategy’s argument but its difference from the other strategies.

Two theorems that were there first #

The order in which these ideas arrived is the reverse of the order in which they are needed here. Von Neumann’s minimax theorem is from 1928 and Ville’s elementary proof, with the theorem of the alternative inside it, from 1938; Paul Gordan had published a version of the alternative for linear inequalities in 1873, before any of it. Rosenblatt’s perceptron was built in 1958 and the theorem that it converges whenever a separating weighting exists was proved by Novikoff in 1962. Minsky and Papert’s 1969 book on what perceptrons cannot represent made the separability condition famous as a limitation. Shannon and Moore’s resistor machine, which began this history, predates the perceptron and was never taught anything.

So every ingredient of the answer predates the question. The theorem of the alternative says what a perceptron can be taught before the perceptron existed: a target is learnable by a weighting exactly when no mixture of rivals covers it, which is separability stated as a game. What it could not say is which winning Hex pairings are covered, and that is a fact about Hex — the same kind of fact the winning reply is the fourth choice measured from the other side, ranking each pairing’s reply among the potential’s choices one turn at a time. On these boards it comes out simple: the covered winners are the singly dominated ones, there is one of them, on the smallest board where three winners exist, and from 4 × 5 on, a machine that weighs chains can be taught any winning pairing there is — if, as a pairing is checked, not measured found, somebody tells it which one.

How the machine is built #

Boards are n × (n + 1) Hex rhombi with Down joining the nearer edges and moving second, as in the essays before this one. Across’s minimal chains are listed exactly, as induced paths, and every count is over all of them. A pair of cells scores the summed weight of the chains holding both; a pairing scores the sum over its pairs; the machine plays the heaviest perfect pairing, computed by Edmonds’ blossom algorithm in the primal–dual form of Galil’s survey, with each weight shifted to be positive so that the heaviest matching is a perfect one. Teaching starts every weight at one; each correction adds a quarter for every whole pair the target holds on a chain and subtracts a quarter for every whole pair the strongest rival holds there, and clips at nought; it stops when the target is strictly heaviest, or when the strongest rival holds at least as many whole pairs as the target on every chain. The margin per unit of weight is the target’s lead over its strongest rival divided by the total of the final weights, and is a lower bound on the value of the teacher’s game.

What the machine cannot be asked #

Whether the result holds past 6 × 7. The perceptron runs on larger boards in principle — the blossom algorithm is cubic in the cells — but the chains run into the hundreds of thousands on 7 × 8, and nobody has counted that board’s winning pairings, so the targets there would be the three rules and whatever else exists would be unknown.

Anything about strategies that are not pairings. The machine’s output is a pairing by construction. A winning strategy that answers a cell differently according to what else is on the board is outside the machine’s vocabulary and outside this argument.

Why the corrections are so few. Sixteen corrections at most, on boards whose chains number in the tens of thousands, is consistent with the winners being few and well separated from the losers, and Novikoff’s bound would turn a measured margin into a guaranteed count of corrections for the plain perceptron. The machine here clips weights at nought, which the bound does not cover, and no bound is computed.

Still open: whether a winner can be covered only by a mixture #

Through 6 × 7 Ville’s alternative is satisfied in its simplest way: every out-of-reach winner is covered by one rival. A board where some winning pairing is ahead of each rival on a few chains, and behind a blend of them on all, would be out of reach while no single comparison showed it, and every machine of this kind would be blind to it for a reason no reader checking pairs could see. Hex’s family is a poor place to look, because its winners are few and two of them differ only at the corners. The switching game on points, where winning pairings are found graph by graph and some graphs have many, is a better one: there the same perceptron, with the same blossom rival, could be pointed at every winning pairing of every graph of seven points, and a single graph with a winner covered only by a mixture would be the first strategy in this history that is out of every measuring machine’s reach without being beaten by any one alternative.