Combinatorial Game Theory
who wins, and by how much
Concept

Subtraction — where it appears

Removing one of a fixed set of amounts from a heap, which is the simplest family of games with an interesting answer. The impartial version always settles into a repeating sequence; giving each player their own list breaks that completely.

Named by 7 essays across 3 fields — each of them below, with the objects they name alongside it.

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.

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.

impartial · Fibonacci nim The repair, and where it stops working. Reducing each heap modulo one more than the cap and then applying Moore's column condition, checked against the search. It is exact at every cap when a move touches one heap and wrong at every cap when a move touches two or three.

The rule a smaller move breaks

Moore's Nim lets a player take from at most k heaps, and its winning condition is the binary columns summed modulo k + 1. Cap the amount as well and the obvious repair — reduce each heap modulo the cap plus one, then read the columns — is exact at every cap when k is one and wrong at every cap when k is two or three. The reason is stronger than a broken rule: at k ≥ 2 the residues do not determine the outcome at all, so nothing of that shape can work.

impartial · Moores-nim Two conditions, one of which survives. Two candidate conditions on a pair of subtraction lists, scored over all 961 pairs drawn from one to five. Translation holds on 83 pairs and every one of them repeats; all-odd holds on 49 and four of them do not.

The condition that survived the wider sweep

Which pairs of subtraction lists have a value sequence that repeats? Over the 49 pairs drawn from one, two and three, two conditions answer it identically — a translation and all-odd — and both are exactly right. Over the 961 pairs drawn from one to five, all 83 translations still repeat with no exception and four all-odd pairs do not, at heap ninety with a period as long as forty-two. Neither condition is necessary: 104 pairs repeat that satisfy neither.

positions · Partizan subtraction The birthday is a floor. How many more pieces a value's cheapest exhibit needs than the value has days. It is never fewer, on any of the 728 non-number values, and it is exactly none on 476 of them.

The birthday is a floor

The rung below measured a correlation of 0.73 between a value's birthday and the size of its cheapest exhibit, and asked which values are dearer than the birthday suggests. The relation is not a trend. Over all 728 non-number values the exhibit is never smaller than the birthday and is exactly the birthday on 476 of them, and the excess on the other 252 belongs to the game rather than to the value — the ruleset accounts for 40 per cent of its variance.

values · Realisability Four second parts, and none of them enough. The residues paired with each of four further counts, at three caps, with a move taking from two heaps. Every pairing leaves classes containing both a win and a loss.

The wider move is the easier game

An earlier essay ruled out every rule that reduces the heaps and reads the residues, and asked for a two-part statistic: the residues plus one more count. Four second parts are tested here and none of them decides. What turns up instead contradicts the premise the request was made under — a move that may reach three heaps is more predictable than one that may reach two, on every cap, every candidate rule, and after the change in the base rate is taken out.

impartial · Moores-nim Sorted by how many heaps are odd. The 2,002 positions of the census grouped by how many of their heaps hold an odd number of counters. Four of the six groups are entirely lost or entirely won.

The count of odd heaps

The rung below refused a family of two-part rules for bounded Moore's Nim and asked what the 364 losing positions have in common as a set. They have an invariant, and it is a statistic of the whole position rather than of a heap: how many heaps hold an odd number. Every all-even position is lost, at every width of move, by a restoring strategy — and the count settles every position at one heap a move and at four, and a little over half at two.

impartial · Moores-nim The digits they share. The condition satisfied by eighteen of the nineteen codes that climb by three. It says that splitting a heap into three is available on exactly one take and buys nothing else.

The only way to split into three

Nineteen three-digit hexadecimal codes climb by three, and the rung below asked whether they share a form and what digits they have in common. The digits are exact: on eighteen of them the only way to split a heap into three is by taking exactly three counters, and taking three counters can do nothing else. The form is not shared — the eighteen carry four distinct sequences, and exactly one of the four counts in base three.

impartial · Hexadecimal

Named alongside it

The objects these essays reach for when they reach for this one.

CounterexampleEnumerationInvariantImpartialGrundy valueHeuristicOutcome classPeriodicityBirthdayCanonical formExhaustive searchNim-sum

All concepts