Certificate — where it appears
Named by 54 essays across 6 fields — each of them below, with the objects they name alongside it.
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 theorem that names a winner and no move
Strategy stealing proves that the first player wins Hex and wins Chomp, on every board, in about four lines. It exhibits no move, contains nothing a move could be extracted from, and is not going to. The moves have to come from somewhere else, and where they come from runs out almost immediately.
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.
A winning strategy that is a spanning tree
The Shannon switching game was sold in a box in 1960 and solved in 1964, and the solution is not a claim that somebody wins. It is a property of the graph anybody can check, and the strategy falls straight out of it — whichever link the opponent cuts, take its partner in the other tree.
A puzzle asks once, a game asks alternately
Quantifier alternation is the whole difference between a puzzle and a game. One chooser is an existential and its answer is a witness somebody can check; two choosers taking turns is a prefix of alternating quantifiers, and the witness stops being an assignment and becomes a strategy.
"Left wins" has no short proof
A complete solution of Nim on heaps of 7, 11 and 13 is 480 table entries. A winning strategy for the same position — one move of the winner's at each of their turns, and an answer to every reply — has 56,167,022 nodes in it. The answer is smaller than the proof by a factor of a hundred thousand.
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.
Three different claims are all called solved
Hex is solved in the sense that the first player provably wins, by an argument that names no move whatever. Nim is solved in the sense that a formula gives the right move from any position at any size. Between them sit strategies for one opening, and databases of a few billion positions. The word covers all four.
Four values, and the sequence is settled for ever
The Grundy values of a subtraction game repeat with period 7, and proving it needs a window of exactly four of them — one for each size of move the game allows. Everything past the window follows by induction. A finite computation has settled a claim about every heap there will ever be.
The code names the move
If the lost rows of a coin-turning game are a linear code, then a won row is a codeword with errors in it and the winning move is whatever turns the errors off. Over all 256 rows of Mock Turtles on eight coins: 16 codewords, 240 won rows, none more than two coins from a lost one — and 64 of them whose cheapest winning move has to turn three coins anyway.
A rule with a guarantee
Evaluating a sum of a dozen fights is impossible; following a rule is not. Move where the stake is largest, and over 220 sums of three hot components the rule scores exactly what perfect play scores in 196 of them, is never more than one point behind, and never ends more than the largest single stake below the mean. The rule that is supposed to be different — answer the threat — chose differently in none of the 220.
No two heaps alike
Welter's game is Nim with one extra clause — no two heaps may be the same size — and the clause is fatal to the nim-sum, which gives the right answer in none of the 120 three-coin positions. What replaces it is a function of pairs: ⟨a | b⟩ = (a ⊕ b) − 1, exact on all 55 two-coin positions, and nim-added over every pair it is exact on the whole board provided the number of coins is even.
It ends, and nothing says when
The recursion this site runs needs every line of play to reach a position with no moves, and the condition is usually met by an obvious decreasing quantity. The hydra meets it with no such quantity anywhere: the tree grows at nearly every step and the fight ends regardless, because the only thing that decreases is an ordinal. A four-node hydra dies in twenty chops; one level deeper and 279 chops reach forty thousand nodes with no end in sight.
The values that keep arriving
A Grundy sequence that repeats uses finitely many values and stops needing new ones. Six thousand heaps into ·007 the count of distinct values is 187 and still climbing, and the share of heaps carrying something outside the twenty-two commonest rises from 32% in the first thousand to 85% in the sixth. The rare values a periodicity argument needs to thin out are getting commoner.
A pairing, and the pairing
The rung below repaired the half-turn check and asked whether a reflection would fire where it does not. It does — forty positions of 58,830 on the largest board — and it is sound, and it is worth one node in a thousand to a solver. It can never fire on an empty rectangle at all, which is why the ladder's whole subject is the half turn.
Wrong in one direction only
The rung below asked for the simplified comparison test the dead-ending hypothesis is supposed to license, and predicted it would agree with the quantifier on the dead-ending rulesets and not on Toads and Frogs. Written three ways and scored on 492 pairs, it agrees best on the ruleset that is not dead-ending — and never once refuses a comparison that holds, which makes it a sound filter and not a test.
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.
Three bits of rule
An octal code is three bits a digit. The Grundy sequence it determines costs anywhere from one bit to a hundred and thirty-six — a factor of two hundred and seventy-two across rules that differ by a single digit — or it cannot be written down at all. Of four properties of the rule table tested against that, exactly one holds on every code that never settles: whether a move may leave two non-empty heaps. It is necessary, it is not sufficient, and nine codes carry it and produce answers smaller than their own rules.
What the arithmetic cost in 1956
The rung below ends by respecting a hand computation without pricing it. Priced in the operations a person actually performs, ·137's certificate is 7,919 of them — and the same sweep says ·47's is sixty-three times that, that a splitting move is what makes the cost quadratic, and that seventeen of sixty-four codes have no certificate at any price.
The first move is a link that is not there
Lehman's criterion answers one question about a switching game — who wins when Short moves second. The other question has the same answer asked of a different graph: add one link from A to B, and Cut is forced to spend its first move deleting it. The trees of that larger graph then name Short's opening, and on every subgraph of seven graphs they name a winner.
Cut is Short on another graph
Everything proved about the switching game is proved from Short's side, and Cut appears only as the player whose moves get enumerated. On a graph drawn without crossings Cut does not need a theory of its own: deleting a link is securing the link that crosses it in the dual, so Cut's game is Short's game on a different graph. Bridg-It is the board that is its own dual — one link short of two trees at every size, which is why its first player wins.
A point with three neighbours
The switching game on links is settled by counting — enough links, arranged as two trees. Played on points instead, it is the game Hex belongs to, and the count is gone. The link game turns out to be the point game in which every contested point has exactly two neighbours; give one a third, and two graphs with the same points, the same links and the same number of separate routes can have opposite winners.
Where the needle has a sentence
Strategy stealing proves the first player wins every Chomp bar and names no square to take. On two families the square can be said in a sentence — a square bar and a bar two rows deep — and in both the sentence is a pairing that names every later move too. Three rows deep the needle wanders, and the observation that every bar has exactly one needle survives ninety-four rectangles and fails on the ninety-fifth.
A board one column wider
Strategy stealing proves the first player wins Hex, and it needs three things: no draws, an extra stone never hurting, and rules that treat the two players alike. Add one column to the board and the third goes. The player whose edges are now nearer together wins whoever moves first — and does it with a table of pairs that names every reply, checked against every line to a board of twenty cells.
Where a search may stop
A search deepened until two consecutive depths agree carries a proof of its verdict, and on 4 × 5 Domineering it stops before the longest line on 17,589 of 48,670 positions. It also costs three times what the search that simply finishes costs. The rule that pays is the other one. Search on wherever the two players' counts of placements are within one, and at depth 2 the wrong verdicts fall from 2,140 to 86 for about a quarter more work per search.
Using up the edges instead
Undirected geography is decided by a maximum matching when a move uses up the vertex it leaves. Use up the edge it crosses instead and the matching is exact on every tree — on a tree the two games are one game — and on nothing else. Over every connected graph on up to six vertices it names the winner at 480 of 745 starts once there is a cycle, it gets a four-cycle wrong from every start, and the more cycles a graph has, the more of its misses are wins that are really losses.
A potential that names every move
Strategy stealing names no move, and the pairings that do name moves need a board with the right symmetry. The Erdős–Selfridge potential needs neither: Down, moving second in Hex, takes the empty cell through which Across's unfinished chains weigh most. Its guarantee reaches only boards two rows deep. It wins far past the guarantee — on every board of three rows that Down can win — and then, on a four-by-five board that a table of pairs wins for Down with certainty, it answers Across's first stone in a different cell and loses along the bottom edge.
The pairing removes moves it cannot name
Symmetric positions were settled by an argument that names a winner and no move. Turned on the moves instead, the same one-pass test strikes off 27,215 of the 159,728 moves in the census and not one of the 21,234 winning ones — a quarter of a full search — and still names nothing. On 583 paired positions nine arithmetic descriptions of the winning gap reach at most 123, and 367 of those positions have exactly one winning move.
Two graphs a rule cannot tell apart
The repair proposed for the matching criterion was to read the cycle as well. Over every connected graph with exactly one cycle up to six vertices — 21 graphs, 114 starts — eleven such rules reach at most 91, and the winner is not a function of the matching, the cycle's length, the start's distance from it, its degree and the edge count together: six cells of that table hold both verdicts, the smallest a pair of five-edge graphs.
The winning reply is the fourth choice
The repair proposed for the potential was to weigh an edge chain more heavily. Fifty-five weightings later, none holds the four-by-five board, and an edge bonus costs Down four boards it was already holding. The reason is not the numbers: over 393,660 turns of the pairing that does hold that board, the potential would take the same cell 26.1% of the time, and the winning cell is its 3.7th choice on average and as low as its seventeenth.
Search on in pairs of moves
Deepening until two depths agree gives a proved verdict, and searching on where the counts are close gives a better one; put together the obvious way, they stop on a wrong verdict at 3,231 positions of 4 × 5 Domineering. A guess one move past the cut has the other player to move and flatters the wrong side. Searching on two moves at a time keeps the proof, and the window that suits it is one-sided — but however it is widened, the certificate gets cheaper only by turning into the search that finishes, and on four boards it never gets below it.
A move whose every reply is struck
Read two moves at a time, the Sylver Coinage shortlist is no better ordered than read one at a time: preferring the survivor that leaves the opponent the fewest surviving replies puts a winner first on 24.7% of 583 positions against 22.3% by chance, and places it deeper than chance does. Read as a proof, the same count does what no order could. On 57 positions a survivor leaves no surviving reply at all, and wins by a certificate a few lines long; searched deeper, the survivors prove every position by thirteen moves — at a price that is never below the search that simply finishes.
Twelve turns, and three different prices
The earlier essay prices a universal quantifier at a doubling and leaves it there. Twelve turns with six of them the opponent's cost 6, 63 or 384 decisions to write down, depending on nothing but the order the turns come in — and the cheap arrangements are cheap for only one of the two players. What a claim costs is the number of times the choosing changes hands.
Proving a loss means answering everything
A win is established by one move and a loss by every move, so the two verdicts are certified by objects of different shapes. Measured over every position of four games, a loss costs between 1.07 and 2.31 times a win — a small constant, never an exponential. The obvious explanation is the branching and it is wrong: Nim answers six options at a losing turn and pays 2.18, not six.
A turn is not a bit
The prefix a game is read as gives each player one quantifier a turn, and a turn on a board is a choice among however many moves there are. Nim on heaps of 3, 4 and 5 lasts twelve moves and carries 23.6 bits of choice; a Toads and Frogs strip lasts eleven and carries two. Corrected for that, the model predicts a strategy 539 times too large on one board and 67 times too small on another, and the two failures have different causes.
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.
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 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Three ways to know a draw
A draw on a board too large to search has to be certified, and there are two standard certificates: a pairing of cells and the Erdős–Selfridge sum over lines. Set against exhaustive search, both miss 4 × 4, and a rule taken from the sum holds there anyway. The sum looks far stronger until pairs are allowed to serve several lines at once. Then across 440 boards up to 12 × 12, the sum certifies no draw that a pairing does not, and a pairing certifies 36 that the sum cannot.
A win priced in stones
Change the rate of play and a yes-or-no question becomes a number. Against a Maker placing one stone a turn, Breaker needs two stones to stop three in a row on every board up to 4 × 4 and six by three, and three on 5 × 4. Against a Breaker placing one, a Maker needs two stones on most boards drawn at one, and three to make four in a row on 4 × 3. The extra stone is enough to erase noughts and crosses altogether, and the biased sum is exact there and high everywhere else.
Taking turns removes the hard part
Whether a graph has a stable set is NP-complete, and every hard instance depends on odd cycles. A real game's position graph has none. A position records whose turn it is and every move changes that, so all cycles are even, Richardson's theorem applies, and the set of all drawn positions with one player to move is a stable set of the drawn part, always. Mū tōrere and Three Men's Morris both confirm it. The hard question never reaches a game with turns, and the sets it hands over carry no information at all.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchStrategyCounterexampleComplexityPairing strategyHeuristicIntractableSearch costGrundy valueHexPeriodicityStrategy stealing