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 4 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 no other game on this site has.

A move that must be answered

Every argument on this site 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 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.

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

Named alongside it

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

ComponentExhaustive searchDecompositionCountingDisjunctive sumDots and BoxesEndgameEntailing moveGrundy valueImpartialNim-sumRule change

All concepts