Combinatorial Game Theory
who wins, and by how much
Concept

Loony — where it appears

A move so bad that the player making it hands the game away outright, whatever else is on the board. Naming it is what lets a Dots and Boxes analysis skip most of a position, and it is a relation to the rest of the board rather than a value.

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

Top Entails, one heap at a time. Each heap with the outcome of playing it alone, the Grundy value an ordinary solver would give it, and the moves that win from it. Taking the top coin of a heap forces the opponent to answer in that heap, which is a kind of move an ordinary sum of games has no room for.

A move that must be answered

Every argument about sums assumes the parts are independent: a move in one leaves the others alone, and the reply may go anywhere. Top Entails denies it — take the top coin of a heap and the opponent must answer in that heap. The nim-sum then misreads 9 of 36 two-heap positions, and two heaps of two coins are a first-player win, which no impartial game the theory covers can be.

limits · Entailing 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.

What a component has to carry

Three impartial games — Fibonacci Nim, Top Entails and Nim with a held pass — 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.

limits · Memory What control is worth, to a box. The margin the player who does not have to open nets, beside the formula that predicts it: the total less four boxes for every long chain after the first. Computed against the solver on every endgame of long chains in range.

Four boxes for every chain after the first

Nimstring answers who is forced to open and says nothing about the score. The margin has a formula: the controller nets the total less four boxes for every long chain after the first — two surrendered and two not taken, each time control is kept. Checked against the solver on 175 endgames it is exact on 172, never too generous, and exact wherever it promises the controller anything at all. The three it misses are the three where it promises nothing.

applied · Dots and Boxes The fee the geometry charges. The same endgames solved with the cost of declining changed. Two boxes on a chain and four on a loop are what a single cut and a pair of cuts complete; altering them changes the winner of a large share of positions, which is what says the law depends on them.

Two and four are not conventions

Declining costs two boxes on a chain and four on a loop, and those numbers are read off the geometry rather than chosen: one cut completes the last two boxes of a chain and two cuts complete the last four of a loop. Solved again with the fee changed, 418 endgames give a different winner on up to a third of themselves — so the endgame's law is a law about the fee as much as about the shapes, and the fee is not a free parameter.

applied · Dots and Boxes A nimber or loony. The value of every heap from one to ten in Top Entails and in entailing Nim, read by pairing each heap with every Nim heap. Even heaps are loony in both games; odd heaps are nimbers, nought or star in Top Entails and ∗(h + 1)/2 in entailing Nim.

One value more than Nim

Top Entails broke the nim-sum: nine of thirty-six two-heap positions came out wrong when a move could compel the reply. The repair is one extra value. Read each heap off the heap itself, and every heap of Top Entails and of a second entailing game is either a nimber or loony — a win for the mover in any company. One rule then decides every sum of those games and Nim together: 4,016 positions, and it is never wrong. A loony heap is a pass, and the compulsion is what buys it.

limits · Entailing The arrow reversed. Values of heaps 1 to 10 in entailing Nim and Top Entails, read off their pairings with Nim heaps, when an entailing move compels the reply in the same heap and when it compels it in a different heap. Pointed elsewhere, entailing Nim's heaps are worth their size, as in Nim, and no heap of either game is loony.

A compulsion that points elsewhere

Top Entails and entailing Nim are decided by one value more than Nim because the compelled reply stays in the heap that compelled it. Point it at a different heap instead and the two games part company. Entailing Nim does not notice — its heaps are worth exactly what Nim's are, because Nim's winning reply was never in the heap just moved. Top Entails loses its loony heaps and then every value of the Nim kind: no assignment of nimbers explains its sums, because a heap of three beside two heaps of one is a win and beside two heaps of two is a loss.

limits · Entailing

Named alongside it

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

Exhaustive searchComponentDisjunctive sumEntailing moveImpartialNim-sumCounterexampleDecompositionGrundy valueCountingDots and BoxesEndgame

All concepts