The thread: A theorem that names no move — page 5
Out in the world
A thousand positions and no exception
The parity law was fitted to constructed bags of chains and loops inside a string budget. A board's positions are a different population — the sizes are what the geometry allows, the components come correlated, and a six-box board holds exactly one position that is a loop of six. Tested on all 1,032 of them and all 160 of the four-box board's, the law is right every time, against a verdict computed from the strings by a walk that has never heard of a component.
How it was found
The step nobody took for thirty-four years
Bouton's criterion is that the heap sizes exclusive-or to nothing. The 1935 theorem is that the heap Grundy values do. The exclusive-or is the same operation in both and it is his, so the whole of the intervening thirty-four years is one substitution — and run over eight games and 672 positions, the substituted criterion is exact on every one while the original is exact on Nim and nowhere else.
How it was found
The picture Bouton's proof leaves behind
His argument is two closure properties of one set, and the Sprague–Grundy theorem is the same two sentences with nought replaced by a variable — checked here on five games and every value in range, with no move staying inside a class and no class failing to be reachable from above. What the argument also leaves behind is a picture in which the values descend, and that is false: 99 of 444 moves here raise a value, and none of them is in Nim.
Out in the world
A different question at every depth
A Sylver Coinage proof that deepens over survivors was never cheaper than the search that skips struck moves and finishes. Keep everything it proves and refutes and it gets cheaper — 41 per cent at twenty gaps, and more when the opponent's positions are kept too — and it is still never cheaper, on any of 1,766 positions, and the gap widens with the gaps. Told the right depth in advance it wins on seven. The finishing search asks one question of a position; a proof asks a different one at every depth.
Out in the world
Three pairings and no order
The potential lost four-by-five Hex for Down, and fifty-five re-weightings lost it too, which left the question whether anything that orders the cells can hold the board. The plainest ordering — one fixed list, whatever the position — holds none of the boards the pairing is known for, and on four by five the best it can do is the left column. At the other end, every table of replies that wins a small board is a pairing, and four by five has exactly three pairings, each using all twenty cells.
Impartial games
The pairs are read from the bottom bits
Some matching of Welter's coins reads the position's value, and usually only one does — but which? The rule is short: pair the two coins whose squares agree in the most low-order bits, and repeat. It reads the value on every one of 3,696 positions of two to eight coins, where no other natural rule manages half. And it has a proof two lines long, because x − 1 flips a number's trailing bits, so a pair's animating value depends on where its squares part on the binary trie read from the bottom. What it is not is a strategy: a move from a lost position can be answered inside its pair only two times in five.
What it costs
A proof inside a budget
A certificate — two depths of search that agree — was always dearer than the search that finishes, but that compared proofs with answers. Its whole purpose is the board where nothing finishes, so the fair test is a budget: cap the positions a search may expand and count the proved verdicts each method returns inside the cap. On a thousand deep positions of 4 × 5 Domineering, the search that finishes proves more at every budget from sixteen to eight thousand. The best certificate, with a one-sided two-move window, proves at most three positions finishing cannot, at any budget, and plain deepening proves none. Where deepening earns its keep is the guess it holds while it works, not the proof it ends with.
Out in the world
The seven were the order
A Sylver Coinage proof told its depth beat the search that finishes on seven positions of 1,766, and on all seven the winning move came fifth when moves were tried smallest first. Run both searches under five orders and the seven vanish under every other one; try the largest move first and there are fifty-five new ones instead. Give both searches the winning move first, free, and the proof is cheaper on none. The exceptions were never positions where proving is easy. They were positions where one order made the finishing search stumble — and what is left when the order is perfect is the price of asking a proof's question.
What it costs
The plays do not say who chose them
Every way a game of edge geography can go is a maximal trail, and the parity of each trail says who moved last. So the list of their lengths ought to decide the game, and over every connected graph to six vertices it nearly does — 780 of 810 starts, 108 of 114 on one cycle, where no rule on the matching and the cycle reached 91. It still fails, and the smallest failure is two trees: the same two plays from each start, and a different player choosing between them. Keep that choice one move at a time and the ambiguity falls from eighteen profiles to seven, one and none. The list costs sixteen times the search.
Impartial games
One square for every coin
Nim's strategy has two halves: every heap has exactly one target, the nim-sum of the others, and the heaps carrying the top bit of the nim-sum are the ones that can reach it. Welter's game keeps the first half on every one of 18,470 coins tried — one square per coin makes the value nought, and the winning moves are the coins above theirs — and the square is found by walking up the binary trie from the value of the other coins. It loses the second half. And at four coins it loses nothing: the losses and the winning moves are Nim's exactly, by a two-line proof, while at six coins no Welter loss is ever a Nim loss, because the last bit of a losing position is a count of pairs.
Out in the world
Start at four
Every order a program could compute had made the Sylver Coinage search that finishes dearer than trying the smallest move first, and the free oracle that puts a winning move first costs under a third of it. Two orders a game program would actually use do better: a history table of numbers that have won before wins back 27 per cent of that gap, and a fixed order learned on small positions the same on larger ones. Both are learning one thing. Trying the smallest move first, but from four, wins back 31 per cent and beats smallest first on 1,695 of 1,766 positions — because naming 2 leaves a two-generator semigroup, which is symmetric and never lost for the opponent, unless 3 is already reachable.
How it was found
A machine that knew one theorem
In 1940 a machine of relays played Nim against the public at the New York World's Fair, on four rows of up to seven lamps, and is reported to have won about nine games in ten. Everything it knew was Bouton's theorem, which is three column parities and one test per row. The record is the interesting number, and it is a measurement of the visitors rather than of the machine: against a visitor choosing at random the machine wins 98.5 per cent, and nine in ten is what a visitor earns by playing perfectly once seven lamps or fewer are lit. On the board the game is usually set up on, a visitor handed the first move cannot win at all.
How it was found
A current through the board
In the early 1950s Shannon and Moore built a machine that played Hex by wiring the board as a network of resistors and reading its move off the electrical potential. There is no theorem behind that rule, and on every Hex board small enough to solve it can be scored against perfect play. On boards to twelve cells it takes a winning cell on more than 98 per cent of the positions where one exists, far above chance. And it loses: every board of three rows or more it has to defend, and four by four moving first, because an opponent needs only one of the two per cent and can steer the game to it.
How it was found
A circuit asked once
The Hex machine's circuit rule loses every board past two rows that it has to defend, and the strategy that holds those boards is a pairing — a partner for every cell, fixed before the game begins. So make the circuit commit: consult it once per cell on an empty board and never again. Its table answers twelve openings with four cells, and loses every board the running circuit lost. Forced to choose a whole pairing, it picks a losing one under seven of eight ways of reading its scores; the eighth finds the winning pairing of three by four by a margin of rescaling and gives up two by four for it.
How it was found
A pairing is checked, not measured
The Hex machine's circuit chose pairings near the winning ones and never at them, which left a finite question: does any score of a pair of cells, computed from the board alone, have a winning pairing as its best? The obvious scores count the chains a pair shares. All four hold two by three; on three by four the plain count cannot choose between a winning pairing and a losing one, and the corrected counts choose the loser; on four by five every one loses. The reason is arithmetic — a sum will give up one chain to cover two others twice. Told which chains it missed, the count finds the diagonal pairing at one rate in three, and by then it is checking, not measuring.
Out in the world
Two neighbours keep a pairing, three lose it
In the switching game on points, Short wins moving second by a pairing when every smallest set of points that cuts A from B holds both points of some pair. On every graph of seven points — 971,104 of them — every Short win has one, at every degree. In random link games, where each contested point has two neighbours, every win has one too, although the winning strategy follows trees that change as the game goes. The first wins with no pairing appear at nine points with four neighbours and at ten points with three: a cubic graph Short wins whoever moves, which no fixed set of answers explains.
How it was found
The weights were not the argument
A chain count corrected by its own misses held the four-by-five Hex board with the diagonal pairing, the one pairing there with a sentence behind it, and the hope was that its weights were the sentence in numbers. They are not. One rate in twelve holds the board and one start in twenty; the weights it ends on survive five per cent of noise and not twenty; and weighting exactly the chains the argument relies on finds no winning pairing at all. Told which pairing to prefer, a measurement reaches any of the three in a dozen corrections. What chain weights can do is rule a pairing out, and on three by four they rule out one that wins.
Out in the world
A pairing that changes once
The cubic ten-point graph is a win for Short that no fixed pairing explains, and the full strategy that does explain it is a tree of 68 decisions. One change is enough: after Cut's first deletion Short claims a stated point, and from then on a fixed pairing of what is left holds every cutting set. Four such plans, eight pairs between them, answer every opening. Of the 23 pairless wins in the samples, 21 need one change and two need a second, and in both the second is a forced claim. Unless the hard problems collapse, no fixed number of changes can be enough for every graph.
Out in the world
Two reflections and a corner
Hex boards of n rows and n + 1 columns are won by the player with the nearer edges, by a pairing, and the count of pairings that do it ran two, three, three. It is three again on five by six, against 1,225 chains, and three on six by seven, against 16,097. They are the same three every time, and they are not three strategies: one is the classical reflection, and the other two are a reflection across the board's other diagonal, which joins its two far corners, in two versions that disagree about six cells. Each is a rule a sentence long, and each holds on every board out to ten by eleven.
How it was found
The teacher's game
A machine that weighs Across's chains could be taught every winning Hex pairing on four by five, and on three by four it could never be taught the one pairing another winner covers chain by chain. Whether anything else could hide from it — a winner covered not by one rival but by a mixture of several — is a question about a game between a teacher choosing weights and a rival choosing pairings, and Jean Ville's 1938 theorem of the alternative, written for von Neumann's games, answers it in general. On five by six and six by seven every winner is taught in sixteen corrections or fewer, and nothing hides at all.
How it was found
Two losers that average to a winner
On Hex boards to 6 × 7, a machine that weighs the opponent's winning sets could be taught every winning pairing except one, which another single winner covered. Ville's alternative allowed a second way to be out of reach — covered only by a mixture — and the switching game on points, where winners are many, is where it turns up. None in all graphs of seven points or in 4,000 of eight; 35 covers at nine and ten points. Every one is the even average of two losing pairings, and on six graphs Short wins and no weighting can teach the machine any winning pairing at all.
How it was found
A stable marriage is a stable set
Draw a graph whose positions are pairs of people, with a move from a pair to any pair one of its members prefers. Its stable sets are exactly the stable marriages, on all 46,656 profiles of three men and three women. So Gale and Shapley's theorem of 1962 is an existence theorem of the kind Richardson's was, on graphs where 49 per cent have odd cycles and his hypothesis is useless. The reason it holds is that every clique in the graph is one person's list, and four roommates show what happens when it is not.
How it was found
The list that cannot run out
Give each cell of an n × n square its own list of n colours, and ask for a colouring from the lists with no repeat in any row or column. Dinitz asked in 1979 whether that is always possible, and reading the cells in order fails about four times in ten. Galvin's proof of 1994 needs one page. Use an ordinary Latin square to turn each row and column into a preference, so that every cell has exactly n − 1 moves, and peel off a stable set for one colour at a time. A list of n cannot run out against n − 1 moves.
Out in the world
Blocking is not enough
Everybody knows noughts and crosses is a draw, and the usual explanation is that the second player can always block. That explanation is false. Against an opponent who can only block, the first player wins, from the centre or any corner. The game is a draw only because the second player's blocks build threats of their own. On fifteen boards solved outright, it is the only one where those two things come apart: everywhere else a draw is a draw because blocking is enough.