Combinatorial Game Theory
who wins, and by how much
Theme

The thread: The sum is the object — page 4

Real positions break into independent parts that are played at once, and adding them up is what the theory was built to do. The hard step is the splitting, not the addition.
Every part on its own is worth nothing. The Grundy value of each chain and loop considered as a game by itself, and three real Dots and Boxes boards used to check the turn-by-turn walk against the win-or-lose solver already used here. Every component alone is a second-player win, which is exactly what makes the nim-sum useless. Out in the world

The parts are worth nothing and the sum is not

Every chain and every loop in Nimstring, taken alone, has Grundy value nought. So the Sprague–Grundy theorem predicts that every position built from them is worth nought — and ninety-six of the two hundred and seven positions checked here are not. The theorem is not being misapplied; it does not apply, because a capture keeps the turn. What replaces it is smaller and sharper: count the short chains, and one long component of any kind reverses the parity.

 What the notation costs to write. Every game born by each day, written in the brace notation and measured. The expressions are all distinct, which is what the notation is for, and by day three the typical one is twenty-two characters and the longest is fifty. How it was found

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.

 What the theorem replaces. Every grid a brute-force solve can reach, valued both ways, with the grid the theorem is normally drawn at underneath. Twelve squares is four thousand arrangements against twelve products; sixty-four squares is eighteen quintillion against sixty-four. Impartial games

Four hundred and seventy steps

The tartan theorem replaces a search with a multiplication. Measured on every grid a brute-force solve can reach, the two agree on all of them — and the ratio doubles with every square added. On the 8 × 8 grid the theorem is normally drawn at, the search would have to value eighteen quintillion arrangements; the theorem needs twenty-six different nimber products, and computing all of them by the rule that defines them looks at four hundred and seventy pairs.

 What one king costs a decomposition. Two pawn files and one king a side, solved as a joint position and again as the sum of its files. With the kings unable to move the two answers agree on every configuration, because a king that cannot choose between files is not a shared resource. Give each king a waiting move and the answers come apart, and on some configurations the sum of the parts names the wrong winner rather than merely the wrong value. Independence is a hypothesis about the position and this is the price of assuming it wrongly. Out in the world

One king, and two files to be in

The whole apparatus needs the files to be independent, and a king is what makes them not. With the kings unable to move the sum of the parts is exact on every configuration; give each king a single waiting move and the sum names the wrong winner on one configuration in six, and on a hundred and twenty-six of two hundred and forty-three with three files.

 A vocabulary that is not closed under its own arithmetic. Every pair of named values added together, with the answer sorted by whether it has a name. The named vocabulary covers every game born by day two and one in twenty-three born by day three, and coverage is the wrong measurement: the notation exists so that positions can be added. A sixth of the sums of two named values at day three cannot be written without opening a brace, and the first one to escape is a sum of two of the symbols anybody learns first. How it was found

Two names that add to nothing nameable

The special symbols reach one game in twenty-three at day three. Coverage is the wrong measurement. The notation exists so that positions can be added, and a sixth of the sums of two named values at day three cannot be written without opening a brace — starting with a sum of two of the six symbols anybody learns first.

 Writing a board as a sum, and as the value it is. Every sum of two, three and four games born by day two, written as the parts joined by plus signs and as the single value the sum equals, with the number of distinct values, the share that can be written without a brace, the share longer as one value than as a sum, the middle length each way and the longest single value. The single value is shorter in the middle and far longer at the top, and needs a brace more often the more parts there are. How it was found

A board is written as a sum

Every measurement of the brace notation so far has been of a single position, and nobody writes a single position. A board is several parts, and it can be written as the parts joined by plus signs or as the one value they add up to. Over every sum of up to four games born by day two, the one value is usually the shorter — and the share of boards that need a brace climbs with every part added, until the longest value is four times its sum.

 A count that forgets, at six rates of forgetting. The hit rate of a component table limited to 10, 20 and 40 entries under recency, under a use count halved every 25 to 5,000 lookups, under a use count never forgotten, and against the best fixed table chosen with the whole run in view. At every size some half-life beats recency, and the longest half-lives fall back toward the rule that never forgets. What it costs

A count that forgets

A Domineering solver with room for ten component values does better evicting whatever it used least recently than evicting whatever it used least often, and the explanation offered was that a use count never forgets. Halve every count at a fixed interval and the count overtakes recency at every table size — by less than half a point, and only with the right interval. The right interval grows with the table: a quarter of a game's worth of lookups at ten entries, five games' worth at forty.

 The board held fixed, and recency still wins. Each of the four board sizes played on its own for 650 games, with a component table of ten entries under recency, a use count never forgotten and the best of three half-lives, against the best fixed ten shapes chosen with the whole run in view. Counting beats recency only on the 4 × 5 board; on 5 × 5, 6 × 6 and 7 × 7 recency beats both counting and the fixed table, by the widest margin on 7 × 7. What it costs

One board, and recency still wins

A Domineering solver's table of component values did best evicting whatever it used least recently, and the explanation was that the run changed board size three times. Take the change away — play all 650 games on one board — and counting wins back its lead only on the smallest board. On 5 × 5, 6 × 6 and 7 × 7 recency still beats both counting and the best fixed table, by the most on the largest. The locality recency exploits is not between boards or between opening and endgame. It is inside a single move.

 A row of files, valued rather than won. Dawson's pawn diagram on a single row of one to 5 files, with the value of the position under each capture rule beside the nimber ·137 gives the corresponding heap. The winners agree throughout; the values agree until five files, where the diagram is worth ∗ and the heap is ∗3. How it was found

A wall the pawns cannot cross and the rule can

Two rows of Dawson's diagram separated by a file with no pawn on it: 1,616 moves were examined and not one crosses the gap. With captures optional the rows add on every diagram checked. With captures compulsory they do not, because the compulsion is a rule about the whole board — and the game that is a sum is the one ·137 does not describe.

 One more row, and the correction comes back. Dawson's diagram of three files beside a row of one, then two, then three, each drawn with the difference between the whole board's value and the sum of its rows. The correction is ∗2, then 0, then ∗2: adding a row removes it and adding another restores it. How it was found

A difference the rows cannot predict

The diagrams that are not the sum of their rows have been counted and never priced. Priced over 50 diagrams and 63,408,981 positions, the difference takes three values and is a function of nothing a reader can see: seven diagrams whose rows are worth ∗ and ∗ split five to two on it, the third value arrives only at the ninth file, and the one rule that survives is a parity — all twenty-one diagrams of three, five and seven rows add, and every failure carries an even number of rows.

 The components the theory does not name. Grundy values of strings-and-coins components with a branching coin, grouped by the value. A chain or a loop is worth nothing on its own whatever its size; a coin with three strings takes four different values depending on its arms, and a coin with four strings is back to nothing. Out in the world

A coin with three strings is worth something

Every chain and every loop is worth nought on its own, whatever its size, and that is exactly what makes their nim-sum useless. A coin with three strings on it is worth nought, one, two or three depending on its arms — 31 of the 35 measured are not nought, and the four that are are the ones whose arms are all long. A coin with four strings is back to nought every time.

 Lasker's Nim in sixteen cells. A four-by-four table. Each row and column is a residue mod 4 of one part of a split heap, with the residue of that part's Grundy value beside it; each cell is the residue mod 4 of the split's value, the nim-sum of the two parts. Every split of every heap to four hundred lands in the cell its residues name. Impartial games

The proof is sixteen cells

Lasker's Nim has a four-clause formula that was checked on two thousand heaps and never proved. The proof fits in a four-by-four table: the last two bits of a split's value are fixed by the last two bits of its parts, so no split can land in its own heap's class — except at 3 mod 4, where it lands exactly on the one value the takes leave missing and pushes the answer up by one.

 One split is enough, and some are not. Lasker's Nim beside five versions of it that allow only some splits, over the first twenty-four heaps, with every cell that leaves the formula outlined. Allowing only the split that takes one counter off reproduces the whole sequence; allowing only equal halves turns it back into Nim. Impartial games

One split is enough

A heap of n in Lasker's Nim offers ⌊n/2⌋ ways to split, and the values use at most one of them. Allow only the split that takes a single counter off and every heap to six hundred keeps its value; of all sixty-three sets of split sizes up to six, a set keeps the formula exactly when it contains 1 or 2. Equal halves alone give back plain Nim, because a split into equal parts is a move to nought.

 The formula as the limit of periodic games. Lasker's Nim above eight versions of it with the number of counters that may be taken bounded at one to eight. Each bounded game is periodic and agrees with Lasker's formula on its first few heaps; the region of agreement grows with the bound. Impartial games

The formula is a limit

Cap the take in Lasker's Nim at k counters and the game is a finite rule table, 4.33…3, whose Grundy sequence repeats with period k + 1 rounded up to even and follows Lasker's formula until the cap bites. The formula is what those periods converge to. And the same column of codes, with a free split in front, holds Kayles itself: the rule 4.4 on a heap of n + 1 is Kayles on a row of n.

 Three parts close most of the gap. The fifty sides four-position regions needed new names for, split by the smallest sum of earlier games that writes them: 23 by a sum of two, 16 only by a sum of three, and 11 by neither, with how often each group turned up in the samples. How it was found

Composition at every size

Twenty-seven of the fifty new four-position sides were written by no sum of two earlier games. Sums of three write sixteen of them — seven plain finite games born after day two, nine built on the names three positions forced — and leave eleven, met seventeen times in nine thousand regions. Run the same test one size down and the story the counts told falls apart: eight of the thirteen names three positions were thought to invent are sums of up to three older parts, two of them just two finite values. Every size composes. What each invents is a residue — five, then eleven.

 Ten classes, and a rule to name them. The classes of subtraction {1, 2} with one player against two: a grid of heaps of one counted modulo three against no other heap, a heap of two or a heap of three, each cell giving the lone player's result with each player to move, and a tenth class — anything with a heap of four or more, or two heaps from two and three — won by the coalition. Where it stops

Units modulo three, and one choice

Nim's rule for one player against two has a shape: count the heaps that always last one move, modulo three, allow one heap that offers a choice, and give any second choice to the coalition. Subtraction {1, 2} has exactly that table — ten classes, nine of them a count of ones against nothing, a two or a three — and so do Kayles, where a heap of three is a heap of two with a unit beside it, and Dawson's Kayles. Subtraction {1, 3} and {2, 3} do not: a board with two choices on it can still be the lone player's, and the short key fails. And {2, 3} and Dawson's Kayles give every heap to ten exactly the same menu of game lengths, so what a coalition reads is not how long a heap can last.

 A Clobber board in three pieces. A four-by-four Clobber position after seven moves: the stones form a live region along the top row, a second live region at the lower left, and a dead pair of red stones at the lower right that has no move for either player. The regions can split further but never rejoin. What it costs

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 piece, its mirror, and its negative. A Clobber piece of ..o/oox worth ↑∗, drawn as it stands, mirrored, with its colours swapped and both. The mirrored piece is worth ↑∗ and the two colour-swapped pieces ↓∗. What it costs

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.

 Seven clauses on one recursion. Seven operators built on the same recursion and differing only in the clause that stops it, each tested for f(G + H) = f(G) + f(H) on the 1,768 pairs of the earlier sweep. Failures: cooling 0, cooling with heating's clause 404, heating 263, heating exempting only integers 335, heating with a switch clause 1768, heating with no clause 0, Norton's product by t∗ 0. Temperature

The bonus an integer is owed

Heating fails to distribute over a sum where cooling never does, and the repair proposed for it was to change what its exception returns: heat a number into a switch instead of leaving it alone. Run on the same 1,768 pairs, that repair fails on every one of them, beginning with nought plus nought. What adds is a heating that changes which numbers it exempts and pays the bonus on the moves an integer holds in reserve — Norton's product, and heating with no exception at all, which at a whole-number bonus is the same operator. Given heating's exception, cooling stops adding too.

 Three rows that do not add. Four diagrams of Dawson's pawns valued whole and as the sum of their rows. 3 + 1 is worth ∗ against ∗3 by rows. 4 + 3 + 1, three rows, is worth ∗ against ∗3, a difference of ∗2, over 4,153,158 positions. 5 + 2 + 1 and 3 + 2 + 1 add. How it was found

The rows that cancel

Every one of Dawson's diagrams that failed to be the sum of its rows had an even number of rows, and twenty-one with an odd number all added. One file past the edge of that sweep, four files beside three beside one fails: three rows, worth ∗ against ∗3 by its rows. What the parity was tracking is two deletions a sum allows — a row worth nought, and two identical rows — which the compulsory board turns out to allow as well. Each of 44 diagrams is worth exactly what is left after them, and in the fifty-diagram sweep that remainder happened to have as many rows, odd or even, as the diagram it came from.

 Where exempting an integer starts to cost. Heating that leaves integers alone, tested for additivity at twelve bonuses from an eighth to two on two pools. It fails on no pair below a bonus of one and on dozens from one upward, while heating with no exemption fails at no bonus on these pools. Temperature

An exemption that costs nothing below one

Heating that leaves integers alone fails to add at a bonus of one and adds on everything at a bonus of a half, and the natural guess was that a half is where it starts to go wrong, since that is where a fraction's moves become worth fighting over. It is not. Across twelve bonuses nothing fails at any value below one, and dozens of pairs fail at one exactly. The reason is the simplicity rule: below one, the recursion sends every integer to itself, so the exemption is not doing anything at all.

All themes