Every essay — page 8
What it costs
Every theorem here can be true and the answer still out of reach. What a search costs, what a proof of a win looks like, and where the shortcuts are.
The cheapest fight is not the yardstick
Hottest-first play was found to cost at most twice the coolest temperature on the board, on pools whose coolest parts sat at a quarter or a half. Put a fight worth an eighth on the board and the rule costs seven times it. On one board the cost falls as the cool part warms, which is the opposite of a bound in the coolest. The number that holds on all 14,946 lines of seven pools is the second-largest temperature.
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.
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.
The price of a tie
The second-largest temperature bounded hottest-first play on 14,946 lines, and the pool that should have broken it puts a threat on top. It does not break: over 2,254 more lines the cost never passes the second temperature and meets it on 97. What the pool finds instead is where the rule goes wrong — one move into the game about as often as at its start — and why. Almost every line that meets the bound is a tie: two parts equally hot and the rule taking the first on the board. Break ties well and the lines meeting it fall from 636 to 51 on the earlier pools, and to none on any board with the threat on top.
Answer where the opponent played
Most of what hottest-first play costs is the choice between parts equally hot, and a search could make that choice well. Six choices a player could make without searching were scored on all 17,200 lines of eleven pools. Answering where the opponent has just played wins back half of what board order loses, and 95 per cent of it on the pools with a threat on top; preferring a part with a follow-up of one's own wins back a fifth; the two together, 71 per cent. Preferring to deny the opponent a follow-up is worse than taking the first part on the board, and denying only an urgent one takes the combination back down to 52. What is left is mostly at the opening move, where there is nothing yet to answer.
Pieces that can only come apart
Amazons broke the promise that a board once split stays split, because a moving piece can step diagonally between two regions. Clobber keeps it with no walls at all: a move lifts a stone onto a neighbouring enemy stone, so it empties one square and fills none, and pieces of stones can only shrink. Checked on every move from every position of four boards — 16.3 million moves — not one joins two pieces. The promise holds and is worth less than it sounds. A four-by-four Clobber board is in two live pieces a third of the time, against nearly half for Domineering, and most of what a solver saves comes not from the split but from the stones that no longer have a move.
A repetition is a guess
Read an octal game's values one heap at a time and report the first pattern that fits, and the report is a guess that changes. Over the 291 short octal codes whose period can be proved, the guess is wrong 4,684 times before it settles; on ·45 it changes 181 times, is right from heap 538 and cannot be proved until heap 1,038. No false guess ever reaches the window that would certify it — the furthest gets 74 per cent of the way — and no fixed number of repetitions is a safe substitute, because the window asks for as many as the period's late start requires: two on some codes, twenty-seven on ·45.
The colour swap pays through a mirror
A Clobber piece with its colours swapped is the same piece with the players exchanged, so a solver could store one and read the other off by negation. On its own that folds the piece table by about a tenth, because a piece's negative is rarely in the table at all. Beside symmetry it nearly doubles the fold on three boards of four, because on a board with an even side a mirror carries every position to the negative of another. And the opening of every such board is worth its own negative — a theorem from the mirror, not a search.
A heap that loses under both endings
The misère classes of Dawson's chess climb in steps, and the two steps to heap sixteen landed on first appearances: the first wild heap and the first Grundy value of four. Run on to twenty, the count sits at seventeen through heap nineteen and then jumps to twenty-four, on a heap worth nought whose genus is tame. Heap twenty is the first heap that loses for the mover under both endings, it behaves like two Nim heaps of two, and most of what it adds is a new way of telling old positions apart. What every step to twenty shares is a genus no smaller heap has. The search that finds this stops at twenty-one, when the positions it remembers outgrow the table that holds them.
Growing is not climbing
The octal codes whose values grow were expected to be arithmetically periodic — repeating with a constant added each period — and to fool a reader with false climbs. Read for that pattern, the 220 octal codes of up to three digits with no certified period produce 246,048 readings in 1,200 heaps and not one holds for more than six periods. The false climbs are exactly as short as on the hexadecimal codes where the climb is real; the difference is that no right reading ever arrives, and the largest values grow more slowly than any constant climb allows.
A formula drawn as a game
Backward labelling answers who wins on any finite graph in time proportional to the arcs. Whether the same graph has a stable set is another matter: Chvátal showed in 1973 that it is NP-complete, by drawing a formula as a game whose variables are two-way pairs and whose clauses are triangles. On every one of the 255 formulas of this form on three variables the graph has a stable set exactly when the formula is satisfiable, and every position is drawn. The hard question lies entirely where the easy one says nothing.
The number in the rule
Draw on a repeated position and no result moves. Refuse the move instead, as Go does, and nothing is left drawn: over every game on four positions, 10,324 of 16,384 starts are drawn with no rule and every one of them acquires a winner. Which winner depends on the number written into the rule. Bar the third arrival rather than the second and 1,392 of those starts change hands. A question with a linear answer has become one that needs the history, and the extra difficulty lies entirely in the positions the labelling called drawn.
How it was found
The theory looks inevitable in retrospect and the record says otherwise. The older arguments are run here rather than recounted — and one of them still answers a question nothing since has answered.
The first theorem, and the winner it declines to name
Zermelo proved in 1913 that a finite game with no chance and no hidden information is decided before anybody sits down — every position is a win for one side or a draw, and which one is settled already. The proof is a labelling procedure, and watching it run shows exactly how little it says.
The theorem that needed none of the theory
Bouton solved Nim completely in 1901, with an argument that mentions no value, no sum of games and no Grundy number, because none of the three existed. The argument is two closure properties and it is airtight — and run on any other game it fails at the step that does the work.
Two people, four years apart, one theorem
Roland Sprague proved it in 1935 and Patrick Michael Grundy proved it in 1939, neither knowing of the other. That looks like coincidence until the alternatives are examined — and the rule they both reached turns out to be the only one that can work at all.
All ladders · Every object named here · The position index · Figures that play back · Search