Every essay — page 7
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.
Twelve classes, seven questions
Twelve misère classes of Dawson's chess were found by testing 715 positions against 715 others. Seven of those tests are enough to tell every class from every other — a greedy choice against a floor of four, since each test is one yes-or-no question. Kayles needs nine of 715 and Nim sixteen. The seven cost almost nothing to use and cannot be found without the whole closure, and they do not carry: the tests found with heaps up to seven tell apart only seven of the twelve classes with heaps up to nine.
A staircase, not a slope
With the misère closure cut forty-fold, Dawson's chess can be classified at heaps far beyond nine. The count of classes is a staircase: six from heap three to eight, twelve from nine to twelve, seventeen from thirteen to sixteen. Normal play steps once in that range, from four to eight at heap thirteen, where a Grundy value of four first appears. Misère play steps there too, and once more at heap nine, where normal play does not move at all — the first wild heap. Heaps eleven, fifteen and sixteen are also wild and move nothing.
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.
A golden ratio thirty years early
Wythoff described the losing positions of his game in 1907 with an argument about partitions of the integers, and no Grundy value anywhere in it. The theory that arrived thirty years later computes the same positions — and has never produced a closed form for the values, which the older argument had for the zeros from the start.
A chess problem that turned out to be an octal game
Dawson posed it in 1934 as a puzzle about pawns. It is the octal game ·137, its Grundy sequence is eventually periodic with period 34 from heap 52 — and the word doing the work in that sentence is eventually, because five values below the start disagree with their repeats and always will.
The sequence nobody has settled
Guy and Smith surveyed the octal games by hand in 1956 and conjectured that every finite one is eventually periodic. Seventy years and a great deal more arithmetic later, some of them have settled and some have not — and the evidence for the conjecture is entirely that nobody has found a counterexample they were looking for.
The numbers came out of the game
The construction is always taught numbers first and games second, and the discovery ran the other way. Conway arrived at the number system from positions, which is why the definition quantifies over sets of previously built objects rather than over cuts — and why it produces a genuinely different collection at every finite stage.
The notation was the argument
Up, star and the brace form are not abbreviations for case analyses. They are the claim that these objects add — and the arithmetic they support is arithmetic that no table of outcomes could ever produce, because two positions with identical outcomes can have different sums.
"Hopeless" was a claim about a method
Misère analysis was declared intractable in the 1970s, and the verdict was correct about what was being attempted. Quotients did not refute it thirty years later — they changed the question from a value per position to a monoid per universe, and the computed sizes show why the first question has no good answer.
A conjecture from hand play
Sprouts was invented over tea and its outcome pattern was guessed from games played with a pencil. Computers have checked it far past where a person could go, and this site's own solver gives out at three spots — so the honest figure states the frontier it reaches rather than the number somebody else published.
The first time it told somebody something
A theory earns its keep when it produces an answer nobody had. Temperature did that for Go endgames — the orthodox account gives a move order that is provably right and is not the one experience offers, and the position it is right about is small enough to check here completely.
What computing further has bought
Sprouts has been searched harder and longer than almost any game, and the period-six pattern has survived every extension. This site's own exhaustive search settles three spots; the published results reach forty-seven, and the gap is not a gap in hardware — the gentler of the two measured growth factors puts forty-seven spots at ten to the hundred and twenty-fifth positions. Beside it sits Brussels Sprouts, which has five million positions holding a choice and not one choice that changes who wins.
Where the braces stop
The brace notation names every game exactly — 1,474 games born by day three, 1,474 different expressions, no two alike. It also gets long: the middle one is twenty-two characters and the abbreviations everybody actually writes cover one game in twenty-three. And it has two hard edges. A game with a cycle in it has no finite expression at all, and the equation the minus sign encodes — that a game and its negative cancel — is false under misère play on every one of those 1,474.
All ladders · Every object named here · The position index · Figures that play back · Search