Combinatorial Game Theory
who wins, and by how much
Theme

The thread: One clause decides it — page 2

Change a word of the rule and the values change completely. A cliff or a wall, a jump allowed or forbidden, a pass that may or may not end the game — the same board, and nothing in common.
Three take-and-break games, three kinds of answer. The Grundy sequences of Nim, Lasker's Nim and Kayles over the first heaps. Adding a move that removes nothing takes Nim's sequence from the identity to a four-line formula; bounding how much may be taken instead takes it somewhere with no formula at all. Impartial games

Splitting is a move

Add to Nim a move that removes nothing — break a heap in two — and the Grundy sequence gets simpler, not harder. Lasker's Nim has a closed form with one clause per residue modulo four, exact on all 2,001 heaps checked: the identity with every fourth pair transposed. Kayles is the same kind of game with the taking bounded instead of the splitting, and it has no closed form at all, settling into a period of twelve only from heap 71 with fourteen values outside it for ever.

 The whole Domineering catalogue, chilled. Every Domineering board this site evaluates, with its value, its temperature, and what cooling by exactly one does to it. Thirteen of the fifteen become cold — a number, or a number plus a star — and the two that do not are the two whose temperature was above the tax. Temperature

The operator chosen for one game

Chilling is cooling by exactly one, and the one is not derived from anything. It is chosen because Domineering mostly runs at that temperature — and measured against this site's whole Domineering catalogue it turns thirteen of fifteen boards into numbers or numbers plus a star, and warms thirteen of the fifteen back exactly. They are not the same thirteen: eleven boards do both, two freeze too far to be recovered, and two stay hot and come back on the nose.

 Every heap up to 40, won or lost. Heap sizes with the outcome for the player who moves first. The lost ones are shaded; they are exactly the Fibonacci numbers, which is a fact about a game with one heap, no board and no geometry in it anywhere. Impartial games

The heap is not the position

Fibonacci Nim bounds a move by twice the previous move, which puts the state outside the board: a heap of six with a cap of two and a heap of six with a cap of five are different games. So there is nothing to add and no Grundy value to compute — and the game is completely solved anyway. The opener loses on exactly the nine Fibonacci numbers up to 120, and the smallest term of the Zeckendorf numeral is a winning move in all 110 winnable heaps.

 What each heap is worth. The value of a single heap of each size. Nothing here repeats: the forms grow deeper as the heap grows, which is what stops the impartial theory's periodic table from having an analogue. Particular games

Two players, two lists

Give each player their own list of how many counters they may take and the impartial theory stops applying. What survives is the outcome: it settles into a repeat, for every pair of lists, and that is a theorem. What does not survive is the value — on four of six pairs swept it has no repeat inside sixty heaps, and the birthdays are still climbing at the edge of the window.

 Twenty-two codes, swept to 600 heaps. Octal codes and hexadecimal ones under the same search, which looks for a period and for a period with a constant added. The second kind occurs only in the wider family here, and a search that looks only for plain repetition reports those sequences as unsettled. Impartial games

A period with a constant added

An octal code says what a player may do when removing k counters, in three bits; a hexadecimal code adds a fourth — leave three heaps — and the digits run to fifteen. Over twenty-two codes swept to six hundred heaps, five hexadecimal ones repeat with a fixed amount added each time round and no octal one does. Their values climb for ever and never repeat, so a search that looks only for repetition reports them unsettled.

 The same row, cut and toppled. Rows of blue and red drawn once and evaluated twice: as a Hackenbush string, where a player cuts an edge of their own colour and everything above it falls, and as Toppling Dominoes, where a player knocks one over and everything on the chosen side falls. Both values are computed by the same recursion from the two rulesets. Particular games

Topple it from either end

A row of blue and red is the picture this site opens with, and under Hackenbush's rules it is always a number. Knock the pieces over instead of cutting them — everything on the chosen side falls — and 480 of the 510 rows up to eight pieces stop being numbers. The two games agree on sixteen rows, every one of a single colour, and the temperature of the hottest row climbs by exactly a half for each domino added.

 Two operators that undo the same tax. Heating leaves every number alone; the warming operator leaves every number alone except an integer, which comes back with a star on it. That single clause is the whole difference between them, and it is what the Go endgame literature needs, because a chilled integer is usually a fight that has been frozen. The rows shown are the ones whose four entries fit in sixteen characters — a warmed day-three value runs to fifty-two, and the clause is legible only in the short ones. Temperature

The operator that puts the star back

Chilling is not invertible: it freezes, and 400 values born by day three collapse onto 29. Both heating and Norton's warming operator are exact right inverses of it — each lands back where it started, on all 400 — and they pick different preimages, differing on 396 of them and differing by exactly a star on 335. The clause that separates them is one line long and it is about the integers.

 Push and Shove over every strip up to 6 squares. The same strips under both rules. A cliff lets coins fall off and a wall does not, and the census says what that one clause is worth: both games are entirely made of numbers, they never agree on a value, and the obvious board-reading is right far more often under the wall than under the cliff. Particular games

The other way to move a row

Shove has a cliff and Push has a wall, and that is the whole of the difference. Both games make every one of the 728 strips up to six squares a number, so neither ever has anything worth fighting over — and the two rules do not agree on the value of a single position. The obvious board-reading is exact on 446 strips under the wall and on 140 under the cliff, and 486 strips contain a coin its owner cannot move at all.

 Every empty NoGo board a build can solve. The empty boards, with the value the recursion returns and the outcome that follows from it. The one-row boards run 0, star, switch and repeat, which is a pattern with no reason behind it that survives past six squares. Particular games

Every group must keep breathing

NoGo is Go with no captures at all: a stone may be placed only if, afterwards, every group on the board still has a liberty. That makes a move's legality a fact about the whole board rather than about the squares it occupies — and a board therefore almost never breaks into independent parts. Of 117 boards here whose empty points fall into two regions, 24 are the sum of their regions and 93 are not.

 Every strip, without the hop. Toads and Frogs with the jump deleted, over every strip up to eight squares. The fourth column is the argument: whenever the value is a number it is a whole number, without exception, so the fractions the ordinary game produces are made by the hop and by nothing else. Particular games

The strip where every number is a whole one

Delete the hop from Toads and Frogs and the halves, quarters and ups vanish completely: over 9,801 strips, every value that is a number is an integer, without a single exception. The guess that the hopless game therefore has a formula reading the gaps is half right and exactly wrong — 1,460 strips of eight squares are switches, and three strips with the same counts of toads, frogs and empty squares are worth 1, {2 | 1} and 2.

 Where running out of moves is permanent. Eleven rulesets, each walked position by position from three small boards, with every position at which a player has no move examined for whether any continuation gives them one back. Nothing here is evaluated: dead-ending is a property of the rules, and two boards worth the same value can differ on it. 9 of the 11 are dead-ending and 2 are not. Where it stops

Nobody comes back

There is a class of games in which running out of moves is permanent, and it is the setting almost every modern misère result is stated in. Nine of this site's eleven rulesets belong to it across 5,334 positions; the two that do not are Toads and Frogs and Amazons, and Toads and Frogs loses the property to a single clause — delete the hop and it joins the list.

 What a component has to carry. Four impartial games, one of which is Nim. In the other three a component cannot say what its own legal moves are without knowing something about the past or about the rest of the board, so the Sprague–Grundy recipe does not apply — and the table says by how much. Every outcome was obtained by solving the sum outright rather than by any formula. Where it stops

What a component has to carry

Three impartial games on this site break the sum, and they break it for the same reason: a component cannot say what its own legal moves are. Measured with one instrument — one number per part, exclusive-ored — the failure rate runs from a quarter to nearly half, against a control where the same recipe is a theorem and is never wrong.

 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.

 A sequence with a rule and no period. The values of the subtraction game with Left taking 1 or 2 and Right taking 1 or 3, from heap 5 up. Each is the game whose only Left option is nought and whose only Right option is the value three heaps below — checked at every heap rather than asserted, and the two heaps where it fails are the two below the seeds. Particular games

A sequence with a rule and no period

The values of the subtraction game where Left takes one or two and Right takes one or three never repeat — thirty-one heaps, thirty-one different values. They are nonetheless completely described: three seeds and the rule v(k + 3) = {0 | v(k)} generate every one of them, which is what a pattern without a period looks like.

 Where sente stops, by what the answer costs. The largest ambient temperature at which a local move is still answered, sorted by how deep the fight below the answer runs. When the answer ends the fight the crossover is the follow-up's temperature; when the answer starts another fight it is exactly half of it, and a third level does not halve it again. Temperature

The answer that starts another fight

A local move is answered while the ambient temperature stays below the follow-up's — and that rule, which this site has carried since the anchor opened, is exact only when the answer ends the fight. When the answer starts another one the crossover is exactly half the follow-up's temperature, on every position tested, and a third level of fight does not halve it again.

 What a Domineering region is worth, by size. Every connected shape of at most six free squares, sorted by whether its value is a number, an infinitesimal distance from a number, or hot. Hot shapes do not appear at all until four squares, and the hottest shape of six is the two-by-three rectangle. Particular games

Which shapes are worth fighting over

Forty-four of the 104 Domineering regions of at most six squares are worth numbers and the rest are not, and the rung below said no visible property of a shape predicts which. Half of that is wrong: a region only one orientation fits in is a whole number, on all eleven of them, for a reason a reader can supply in a sentence. The other half stands, and thirty-three shapes are what makes it stand.

 When counting the free squares gets Push right. Every Push strip of at most seven squares, split by whether any line of play can bring two coins of opposite colour together. Where none can, the count of free squares in front of each coin is the value, without exception; where one can, the count is right more often than not. Particular games

The reading that survives too much

Counting the empty squares in front of each coin gets a Push position right half the time, and the rung below said the failures were exactly the positions with two coins of opposite colour side by side. Sixty-six of the 1,072 failures have no such pair, the smallest is five squares long, and the condition that does decide it is not about the board at all — it is about every position the board can reach.

 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.

 Moore’s rule, reversed. Moore’s Nim under the misère convention at three values of k, with the normal-play rule and the same rule plus a clause about heaps of one. The patch is the one Nim takes, with the modulus the normal-play rule already carries, and it is right on every position swept. Impartial games

The patch that generalised

Misère Nim takes a one-line patch: play the normal-play strategy until every heap holds a single counter, then invert. Moore's Nim, where a move may take from up to k heaps at once, takes exactly the same patch with exactly the same modulus — and the two rules disagree on six positions out of 923.

 How two genus symbols make a third. The composition rule for genus symbols, stated with its cases and checked on every pair of heaps of nine games. The base exclusive-ors, the sum is fickle only when every component is, and the symbol follows from those two. Where it stops

The rule the symbols follow

Two genus symbols make a third by three lines and no lookup table: the base exclusive-ors, the sum is fickle only when every component is, and the symbol follows. Checked on 252 pairs across nine games it is right on 238 — and the fourteen failures are exactly the fourteen pairs with a wild heap in them, which is the boundary the genus is defined up to arriving as a measurement.

 Which description of a surviving option is right. The two candidate readings of what the reduction keeps, scored over every Domineering option list on six boards. Taking the most room is right on under half the lists, which is what a description with no content scores on lists this short. Leaving the opponent fewest replies is right on nine in ten. Values

Which option the reduction keeps

Domination deletes an option when another is at least as good, so what survives is the top of an order. On a board that order is made of moves, and two descriptions of the surviving move suggest themselves. Over 1,586 Domineering option lists one of them is right 47% of the time and the other 90%, and the one that wins is not the one a player would guess.

 Thickness is not the variable; the wall's own groups are. The same strips split by whether the wall is all one colour. A wall of one colour is a single group with liberties on both sides and it never separates them, at any thickness. A wall of two colours is two groups breathing in opposite directions and it nearly always does. Particular games

How thick a wall has to be

A single stone between two empty stretches of a NoGo board couples them, and the obvious repair is a thicker wall. Over 590 walled strips a thicker wall does help — and splitting the same 590 by the colour of the stones shows that thickness was never the variable. A wall of four one colour couples the sides exactly as one stone does.

 The Fibonacci numbers are one row of a table. The losing heaps of Fibonacci Nim with the factor two replaced by one, three, four and up to eight. Each factor gives a different integer sequence: the powers of two, the Fibonacci numbers, and four more with no common name. Impartial games

The family the Fibonacci numbers belong to

Fibonacci Nim lets a player take at most twice what the last one took, and the heaps the opener loses are the Fibonacci numbers. Two is an arbitrary number. At one the losing heaps are the powers of two, at three and four and five they are four more sequences, each with a linear recurrence whose lag is twice one less than the factor — until the factor is six, where the pattern stops.

 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.

All themes