Combinatorial Game Theory
who wins, and by how much
Theme

The thread: A theorem that names no move — page 2

Knowing who wins and knowing what to play are different achievements, and the subject is full of results that supply the first and refuse the second. A bound is sometimes all there is.
Toads and frogs. Toads move right and frogs move left, one square into a gap or hopping over exactly one opponent. A player unable to move loses. It can be played on squared paper by anybody, and its values are immediately stranger than the game looks. Particular games

The strip nobody has a formula for

Some toads, a gap, some frogs. Two counts and a spacing is the whole description, and the values that come out of it are integers, stars, switches with eighth-point options and a down — four classes inside one two-parameter family, which is why nobody has written the formula.

 Three things the word “solved” is used for. The three standard senses of a solved game, priced on positions this solver can settle completely. Ultra-weak names the winner; weak supplies a strategy from the opening; strong supplies one from every position. They differ by orders of magnitude, and a claim that a game is solved is nearly useless until it says which of the three it means. What it costs

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.

 Subtraction of 1, 3, 4 — and the window that proves the period. The Grundy values of a subtraction game, with the window that certifies the period marked. Everything after the window follows from it by induction, because a value is a mex over values at most one move back — so a finite check settles the whole infinite sequence, and the thousands of further values computed here agree with a claim that was already proved. What it costs

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.

 Grundy values for subtraction of 2, 5, 7. The Grundy value of every heap size for a take-away game, computed by the mex rule. A period, if the figure marks one, was found by searching the computed sequence rather than assumed — and where no period is marked, none was found in the range drawn, which is not the same as there being none. Impartial games

The period is small and the proof does not say so

Every subtraction game repeats eventually — that is a theorem, and its proof gives a bound of sixteen thousand for a three-move set. Over 112 sets the longest period measured is twenty-two. The proof and the fact are four orders of magnitude apart, and the rule of thumb that closes the gap is broken by one set in the sweep.

 the temperature that bounds the loss. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake. What it costs

A rule that is never right and cannot be far wrong

Playing the hottest component is not optimal — over 440 measured lines it costs something on 17 of them. What makes it worth having is that the cost is bounded by the temperature, provably, and that the same test run with the ordering reversed breaks the bound on 54.

 Generalized Geography. A token on a directed graph. A move slides it along an edge to a vertex not yet visited, and a player who cannot move loses. That is the whole game, and deciding who wins it is as hard as anything decidable in polynomial space — which is the strongest hardness claim anybody makes about a combinatorial game. Impartial games

A token on a graph

Geography is an impartial game whose position is a vertex and a history, so a ten-vertex graph has ten thousand states rather than ten. Take the arrows off and the same game is decided by a maximum matching — first player wins exactly when every maximum matching covers the start, verified on 41 vertices across eight graphs. One word in the rules separates a polynomial criterion from a PSPACE-complete problem.

 Knowing who wins, and knowing what it is worth. Nine positions, each evaluated twice by an instrumented evaluator that starts with an empty cache. The third column counts what deciding the winner costs and the fourth counts what the canonical form costs, in the currency each question is actually paid in. What it costs

Knowing who wins, and knowing what it is worth

Deciding a winner expands positions. Computing a canonical form expands pairs of positions, because a comparison unfolds as a recursion over one subposition of each and the reduction makes many comparisons. Measured on the same nine positions by an evaluator that starts empty every time, the second costs between 1.3 and 279 times the first, and the ratio grows with the tree.

 What the rule costs. Every sum of three components from a fixed pool, played out twice: once with one side following the rule "move where the stake is largest" and once with both sides evaluating exactly. The rule is not optimal, the gap is bounded, and the bound is the largest temperature on the board. Temperature

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.

 Hydras, and how long each takes to kill. Six small hydras with the ordinal the termination proof assigns to each and the exact number of chops it takes to finish it. Two of them are not finished here: the fight is guaranteed to end and the machine runs out of memory long before it does, which is the gap between a termination proof and a bound. Where it stops

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.

 How many different values a Grundy sequence has used. One curve per octal code: the number of distinct Grundy values among the first n heaps. A periodic game runs out of values and its curve levels off. The codes nobody has settled are still climbing at six thousand heaps. Impartial games

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.

 Two ways to be certain and ignorant at once. Ten positions from two games that both terminate for reasons no bound comes out of. Sylver Coinage's proof counts something that goes down and can be counted; the hydra's counts an ordinal, which cannot, and the last column shows what that difference is worth. Where it stops

Two ways to end with no bound

Sylver Coinage and the hydra are both guaranteed to finish and neither will say when. The difference is that one of them carries its own bound: every move in Sylver removes at least one gap, the gaps can be counted in a moment, and over ten openings the longest play uses every single one. The hydra has no decreasing quantity a solver can hold — three hydras of five nodes each take seven chops, twenty-one, and a number past two hundred and seventy-nine that this machine never reaches.

 Four rules over 220 sums. Each rule plays every sum against an opponent evaluating exactly. Two of the rules come with a bound and two do not; the coldest rule is the control, and it violates the bound often enough to show that being inside it is a real constraint rather than a description of the pool. Temperature

A rule with no promise at all

Playing in a hottest component comes with a bound: never more than the largest single temperature below the mean of the board. Over 220 sums the bound holds 220 times — and so does the bound for a rule with nothing behind it, which scores exactly what perfect play scores on 205 sums against the hottest rule's 196. The control that shows the bound is doing work is the rule that plays the coldest component, which breaks it 74 times and loses up to eleven points.

 What an approximation is worth. Every pair of Clobber rows up to six squares, judged twice: by their up-brackets and by the comparison itself. The bracket is never wrong where it speaks, and most of what it declines to answer has no answer. Particular games

When the bracket decides

A Clobber row's value is an all-small game nobody can hold in their head, so the practical answer is the up-bracket: a pair of integers between which its atomic weight must lie. As an approximation it is worth exactly what it settles — 1,585 of 7,875 pairs of rows are ordered by it, every one of those orders is right, and of the 6,290 it declines, 4,222 have no answer either.

 Five rules over 120 sums built to punish greed. Each rule plays every sum against an opponent evaluating exactly, on a pool whose components are traps: a large immediate gain that hands the opponent a larger follow-up. The pool was built to punish the greedy rule and does not — that rule scores a move by the stop it leaves, and a stop already contains the follow-up. What the traps catch is the rule below it, which scores a move by the territory it takes and loses up to 16. Temperature

A pool built to punish greed

The rung below found a rule with no theorem behind it beating the rule with one, and predicted that a pool of deliberate traps would reverse the result. It does not. The traps miss, because the rule called greedy scores a move by the stop it leaves and a stop already contains the follow-up — and the rule the traps do catch, losing sixteen points where the guaranteed rule loses five, had to be written to make the point.

 7 symmetries, and the one that is a strategy. 4 games and 7 candidate symmetries, each tested by playing the strategy out against every opponent line rather than by argument. A pairing strategy needs a map that fixes the start, is an involution, and carries one player's moves to the other's — and the last condition is where most of these fail. Impartial games

The strategy that is a symmetry

A pairing strategy is a symmetry of the board that turns one player's moves into the other's, and it wins without computing anything. Tested by playing it out rather than argued, it wins one of seven candidate symmetries across four games — exactly the Cram boards with both sides even, which is exactly where no domino is its own image.

 The number nobody needs. The shortened selective compound — move in any non-empty set of components, and the game stops as soon as any one component stops — solved directly on 1,176 three-heap positions across four subtraction sets, with four predictions beside it. The suspense number was introduced for this compound and it is right; so are three cheaper things, and the shortening leaves the winner unchanged. Sums and comparison

The number nobody needs

The compound theory carries a third quantity — the suspense number — computed by the remoteness recursion with both preferences reversed, for the compound that stops as soon as any component stops. It governs that compound correctly. So does remoteness, so does the plain Grundy value, and the shortening does not change the winner on any of 1,176 positions.

 Four rules, asked of compounds made of two different games. Compounds whose two components come from different subtraction games, solved in full and compared with what each rule predicts. The three rules the compound theory supplies are exact on every position; the shortcut a reader carries instead is not. Sums and comparison

A compound of two different games

Every rule the compound theory has survives mixing exactly — the minimum-remoteness rule is right on all 5,184 mixed pairs and all 7,560 triples — and the reason is not that the rules are strong. It is that each of them reads one number per component, and a number does not remember which ruleset produced it. The thing mixing damages is the shortcut a reader carries instead.

 A thousand shapes, and twelve pairings. Cram on every connected shape of at most eight squares, with the search for a symmetry that answers each of the opponent’s moves. Every pairing found is a second-player win, most shapes have no involution at all, and the strategy accounts for a sixth of the second-player wins there are. Impartial games

Looking for the symmetry

Answering every move with its mirror image wins Cram on a board with both sides even, which is the argument everybody meets. Asked of every connected shape of at most eight squares instead of of thirteen rectangles, it wins twelve — and accounts for a sixth of the second-player wins there are, because 852 of the 1,042 shapes have no symmetry to answer with in the first place.

 How much a domino count knows about a region. The difference between the two players' largest domino packings, set against the value of the region. On the regions worth numbers the count is the value under half the time; on the rest it lands somewhere between the two stops on 85 per cent of them. Particular games

Counting the moves each side has

How many dominoes could each player still place? Subtract, and there is a whole number computable from the drawing with no game theory in it. Over 1,042 regions it is the value on 141 of the 315 worth numbers, lands between the stops on 619 of the other 727, and its failures are two different kinds — one of which was inevitable and one of which is a fact about the game.

 Three counts, and two of them are the same number. Rows of End-Nim that read the same backwards, rows equal to their own negative, and rows worth a nimber. The second and third counts are identical over every row in the sweep, so being its own negative is exactly the condition for being worth a nimber in this game. Particular games

The rows that are their own mirror

Four hundred and ten End-Nim rows are worth nimbers and 168 of them are palindromes, so a condition covering the other 242 was outstanding. It is that the row is equal to its own negative — and on this game that condition is not merely sufficient but exact, which is more than the group law promises and is a fact about End-Nim rather than about games.

 Parity decides it before the shape does. For each size, how many first-player wins can reach a position a half-turn pairs in a single move. Every odd size is nought and cannot be anything else, because a pairing needs an even number of squares and a move removes two. Impartial games

The symmetry one move away

A pairing argument proves the second player wins and names no move to do it with. Asked of every shape of up to eight squares it settles twelve boards. Asked one move later — can the first player reach a position a half-turn pairs? — it settles 288, and which boards those are is decided by parity before anything about their outline is looked at.

 How far down the stack the guarantee reaches. The temperatures of a sum's components, sorted largest first, with each position asked whether playing in the hottest component can lose more than the temperature sitting there. The first two never fail; the third fails on 681 sums. Temperature

A schedule instead of a number

Playing in the hottest component loses at most the largest temperature on the board — the classical guarantee, stated against one number. Sorting the temperatures and reading the guarantee one step further down gives a promise 47 per cent smaller that is never breached over 1,734 sums. Two steps down it fails 120 times, so the schedule has exactly one step of slack in it.

 What the correction buys. The packing count as a point against the packing count as an interval, on the regions worth numbers. The point is right on 141 of 315; the interval contains the value on 209, at a mean width of about half a move. Particular games

The moves a player can be talked out of

The difference of the two players' largest domino packings is the value of a Domineering region on 141 of the 315 worth numbers. The count is optimistic for its owner and pessimistic for the other, and one number cannot be both — so it becomes an interval, from what a player can be reduced to against what the opponent can achieve. The interval contains the value on 209, is a single point on 505 of the 1,042 regions, and never exceeds two moves wide.

 Three strips a criterion cannot tell apart. Three Push strips identical in length, reading, coin counts and run structure, whose readings are wrong by a quarter, a half and a quarter more than one. The order of the colours inside the run is the only thing separating them. Particular games

The criterion that cannot exist

The rung below asked for a quantitative version of its condition — turn 'the reading survives mixing three quarters of the time' into a statement about the strip. Three strips of four squares settle it. `.LLR`, `.LRL` and `.RLL` have the same length, the same reading, the same coins and the same single run, and their readings are wrong by 1¼, ¼ and ½. The error is a fact about the order of the colours, and 207 of 805 statistical classes carry more than one of them.

All themes