Two losers that average to a winner

The teacher’s game ended with a question it could only ask. A machine that scores pairs of Hex cells by the weighted chains holding both, and plays the heaviest pairing, had been taught every winning pairing on the boards from four by five to six by seven; the one winner it could never be taught, on three by four, was out of reach because a single other winner held at least as many whole pairs on every chain. Jean Ville’s 1938 theorem of the alternative said there was exactly one other way to be out of reach — to be covered not by any one rival but by a mixture of them, each ahead here and behind there, and on average ahead everywhere — and on Hex it never happened. Hex was a poor place to look, the essay said, because its winners are few. The switching game on points, where winning pairings are found graph by graph and some graphs have dozens, was a better one.

It was. On every graph of seven points the answer is still no mixture, and on a sample of four thousand graphs of eight. At nine and ten points the mixtures arrive, and they have a shape nobody looking at Hex would have guessed: each one is two losing pairings averaged half and half. On six of the sampled graphs that shape swallows every winner there is. Short wins those graphs, has pairings to win them by, and no weighting of anything the machine can see will ever make it choose one.

The same machine on a different board #

The game is the one a point with three neighbours introduced. Short claims points and Cut deletes them; Short wins once a route from A to B runs through claimed points only. A cutting set is a smallest set of contested points whose deletion separates A from B, and a pairing wins for Short moving second when every cutting set holds both points of some pair: Short answers each deletion with its partner, Cut never gets a whole pair, and so never a whole cutting set. On graphs where every contested point has two neighbours the game is the link game and Lehman’s spanning trees decide it; the graphs here have more. The cutting sets play the part that Across’s chains played in Hex — they are the opponent’s winning sets, and a pairing is a certificate checked against them.

The machine is the Hex machine with chains replaced by cutting sets. Each cutting set carries a weight; a pair of points scores the summed weight of the cutting sets holding both; a pairing scores the sum over its pairs; the machine plays the heaviest complete pairing — every contested point paired, one left over when their number is odd — as the Hex machine played the heaviest perfect one. These graphs are small enough to try every complete pairing, so the heaviest is found by listing them rather than by Edmonds’ algorithm, and whether a weighting exists that makes a given winner strictly heaviest is settled exactly by a linear program rather than by hoping the perceptron converges.

What the machine sees of a pairing is a short row of numbers: how many whole pairs it holds in each cutting set. Call that row the pairing’s cover. A weighting scores a pairing by its cover and by nothing else, so two pairings with the same cover are, to the machine, the same pairing.

Every cover, sorted by how it can be reached #

Seven points means A, B and five contested points. Up to relabelling the five there are 10,925 graphs with a route from A to B, and Short wins 5,360 of them by a pairing. Their winning complete pairings fall into 6,062 covers. Of those, 5,480 can be taught — 34 of them trivially, because every complete pairing on the graph has that cover and the machine has nothing else to play — and the other 582 are covered by a single rival — which, holding at least as many pairs everywhere, is necessarily a winner too. None is covered only by a mixture. On the 4,000 sampled graphs of eight points, 2,253 of them won by a pairing, the same is true: 944 covers out of reach, every one of them covered by one rival.

At nine points it changes. Of 2,620 sampled graphs Short wins by a pairing, five carry covers that no single pairing holds down and no weighting lifts — nineteen covers in all. At ten points there are sixteen more, on eight graphs. Thirty-five covers, thirteen graphs, out of more than five thousand: rare, but present, and the lead is answered. A winner can be out of every measuring machine’s reach without any single alternative beating it.

A cover is not a strategy #

Before the mixtures, something the census shows that Hex never did, and that changes what “teaching a winner” can mean.

On every Hex board to 6 × 7, the winning pairings had different covers — each held more whole pairs than the others somewhere — and a teacher could aim at one. On points that is the exception. Of the 6,062 winning covers on seven points, 5,210 belong to two or more pairings: different sets of pairs, different answers to Cut’s moves, the same count in every cutting set. The graph above is the plainest case. Its three cutting sets are {c, d, g}, {c, e, g} and {d, f, g}; pairing c with e and d with g puts one whole pair in each, and so does pairing c with g and d with f. They are different strategies — after Cut deletes e, one answers by claiming c and the other, which leaves e unpaired, is free to claim anything — and no weighting of the three sets can prefer either.

So the unit a machine of this kind can be taught is a cover, not a pairing — a sharper form of what a pairing is checked, not measured found on Hex, that the machine has to be told which winner to prefer. That is harmless when every pairing with the cover wins, and it always does — a cover holding a pair in every set wins whichever pairing carries it — but it means the teacher’s game on points is a game over covers, and the history this essay belongs to has to be read with that in mind. The weights were not the argument found that the Hex machine’s weights never encoded why a pairing wins. On points they cannot even encode which one.

Two losers that add up #

Now the mixtures, and the ten-point graph at the top of the page, which is the clearest of them. It has six cutting sets and three winning complete pairings, and all three have the same cover: exactly one whole pair in every cutting set. They win with no slack anywhere.

Two losing pairings sit on either side of them. The first, c–g, d–e, f–h, i–j, misses the cutting set {c, d, f, i} entirely — no whole pair inside — and so loses: Cut deletes those four points and A is cut off. It makes up for it with two whole pairs in {d, e, i, j}. The second, c–i, d–f, e–g, h–j, does the opposite: nothing in {d, e, i, j}, two in {c, d, f, i}. Everywhere else both hold one, like the winners. Average them, and every cutting set holds exactly one whole pair — the winners’ cover, exactly.

That settles the machine’s fate on this graph without a single computation. Under any weighting at all, a winner scores the average of the two losers’ scores, because its cover is their average and a score is a weighted sum of a cover. One of the two losers therefore scores at least as much as the winner, whatever the weights. The machine, choosing the heaviest, can always be handed a loser; no correction a teacher makes can get it off the losers for good. Short wins this graph moving second, there are three ways to win it by pairing, and a machine that weighs the opponent’s winning sets — the instrument this whole history has been refining since a current through the board — is blind to all three. The Nim machine of 1940 could not have been, because it computed a theorem rather than weighing anything; every machine since has weighed, and this is the first board in the history on which weighing provably cannot reach any of the wins that exist.

The surprising part is not that a mixture covers the winners. It is what the mixture is made of. Every one of the 35 covers found out of reach only by a mixture is the half-and-half average of two complete pairings, and in all 35 both pairings lose. Not one mixture needed three ingredients, not one used unequal weights, and not one used a winner. The winners out of reach on points are not hidden behind better strategies, as the dominated Hex pairing was hidden behind another winner. They are hidden between two worse ones.

A graph with fourteen winners and no way to choose #

The ten-point graph has only three winners, and they share one cover, so “the machine can be taught no winner” is a statement about a single row of numbers. The nine-point graph below is the stronger case.

Fourteen winning pairings, in seven covers of two pairings each. Six of the covers hold one whole pair in five cutting sets and two in the sixth — a different sixth each time — and each of the six is the even average of two losers. The seventh holds exactly one in every set, and it is covered by a single rival, the pairing c–d, f–g, h–i, which beats it by holding two in {f, g, h, i}; but that rival is one of the six already out of reach. So the chain of coverings closes. For every weighting there is a losing pairing at least as heavy as every winner, and the linear program that asks for a weighting lifting any winner above every loser returns nought.

Six of the sampled graphs are blind in this way: two at nine points, four at ten. Three of them have fourteen winning pairings, two have three, and one has two. Short wins every one of them moving second — and moving first, too, as it happens — so these are not marginal games, only marginal for this machine.

Why points and not Hex #

The reason the mixture never showed up on Hex is visible in the covers. A Hex winner held many chains more than once, and a chain-by-chain comparison with any rival found places where the winner was strictly ahead; two reflections and a corner counted the chains each winning pairing holds by a single pair, and they were well under all of them. The teacher’s game showed the teacher putting its weight exactly there, on the chains where the target is better than the alternatives, and never on the chains held only once, because a chain every winner holds once cannot separate anything.

The ten-point graph is that observation pushed to its end. A winner holding every cutting set exactly once is better than the alternatives nowhere it can be seen from: every rival that wins holds each set at least once too, and a loser can hold some sets twice. Whether such a winner can be taught depends only on whether losers can arrange their extra pairs to fill in each other’s gaps — whether two of them, one doubling where the other misses, add up to a flat row of ones. On Hex the board’s geometry made that impossible on every board measured. On small graphs, where the cutting sets overlap heavily and each pair of points sits in several of them, it happens.

There is a cleaner way to say the same thing, and it is the surprising connection. A pairing’s cover is an integer row; a mixture’s cover is a fractional one. “Every cutting set holds at least one whole pair” is a covering condition, and the average of two losers is a fractional pairing that satisfies it — half of one pairing and half of another, each half-pair counting a half. The covers the machine can reach are exactly the corners of the shape all the pairings’ covers span — the corners that face towards holding more — and a winner lying on the segment between two losers is not a corner of anything. The same distinction between an integer solution and a fractional one is the whole subject of linear programming’s integrality gaps, and here it is in a game: Short’s integer pairings win, the fractional ones the machine cannot avoid lose, and no amount of weighting turns the second into the first.

The perceptron, where there is something to teach #

On every cover that some weighting can reach, the perceptron reaches it, and quickly: on seven points 5,126 of 5,446 are already heaviest at equal weights and the rest need one correction; at ten points the worst needs six. That is the Hex result again — winners few and well separated from the losers, when they are separable at all. What the perceptron cannot do is tell the difference between a cover it has not reached yet and one it will never reach, except when a single rival covers it, which is the one case its stopping rule recognises. On a mixture-covered cover it would correct, be beaten by the other loser, correct back, and run until it was stopped. That is why reach here is decided by the linear program — whose answer, by Ville’s alternative, is also a certificate: either a weighting with a positive margin, or a mixture of rivals that covers the target, and for every one of the 35 the mixture was found and checked pairing by pairing.

What was measured, and how #

Graphs have points A and B, not joined, and n − 2 contested points; at seven points every graph is taken once up to relabelling of the contested points, and at eight, nine and ten points 4,000 graphs are drawn with each possible link present at a density chosen at random between a quarter and three quarters, seeded so the same graphs come out every time. Cutting sets are the minimal sets of contested points whose deletion leaves no route; a pairing’s cover counts the whole pairs inside each. Complete pairings pair every contested point, leaving one out when the number is odd. A cover is teachable when the linear program maximising the least lead over every other complete pairing, per unit of total weight, has a positive optimum; covered by one rival when some complete pairing with a different cover holds at least as many whole pairs in every set; covered only by a mixture otherwise. A graph has no teachable winner when no weighting lifts any winning cover above every losing pairing, other winners allowed to tie. The perceptron starts at weight one on every cutting set and moves each weight by a quarter of the difference in whole pairs between target and strongest rival, never below nought.

What the census cannot say #

Whether mixtures become common. Thirty-five covers in 8,000 sampled graphs is a rate, and a sample of graphs drawn at random densities is not every graph; the exhaustive count stops at seven points, where there are none. Larger graphs have more cutting sets and more pairings, and whether the share of blind graphs grows with them or stays a curiosity is not something these samples show.

Whether a blind graph has a short description. The ten-point graph’s three winners hold every cutting set exactly once, and so do the out-of-reach winners on several of the others — but not all of the 35 covers are flat rows of ones, and nothing here turns “holds every set once and two losers interleave” into a rule a reader could apply to a graph without computing its covers.

Anything about a machine that sees more. A machine that weighed pairs of cutting sets, or the points themselves, would score pairings by something other than their cover, and nothing here bounds what it could be taught. The blindness is a property of this instrument, the one the history has followed from Shannon and Moore’s resistors to the perceptron, and not of every machine.

Still open: whether the blindness has a size #

Every mixture found is two losers, evenly. That is the smallest a mixture can be, and it is suspicious in the way a measurement that keeps landing on its floor is suspicious: either two is genuinely all a covering ever needs on graphs of this kind, which would be a theorem about cutting sets and pairings waiting to be stated, or larger mixtures exist on larger graphs and the samples are too small to have met one. The measurement is the same census on every graph of eight points, which is too many to list one by one but not too many to list up to relabelling with a better canonical form than the one used here — and a sample at twelve, where a pairing that changes once found pairings themselves beginning to fail, to see whether the covers a machine cannot reach and the wins no pairing explains begin at the same size.