Combinatorial Game Theory
who wins, and by how much
Concept

Entailing move — where it appears

A move that compels the opponent's reply to be in a named part, which destroys the independence a disjunctive sum assumes. It reaches across components, so the disjunctive theory does not apply and the damage has to be measured rather than assumed.

Named by 5 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 A pass that may not end the game is not a component at all. The same grouping with the pass forbidden as the final move. Each group now holds several values, and a group with several values is a proof that the parts do not determine the whole.

A pass is not a move

Put a single pass token on a Nim board and one clause decides everything. If it may be taken at any time — including as the move that ends the game — the value of the whole is the nim-sum with a one added, in all 120 positions swept: the pass is a heap of one. Forbid it as the final move and the value stops being a function of the nim-sum at all, and 3 and 1 + 2 come apart.

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

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.

impartial · Fibonacci nim 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 Two heaps and a held pass. Every pair of heaps up to 16 with one pass available that may not be the last move. Filled cells are the pairs the player to move loses: the empty board and the pairs one and two, three and four, five and six, and so on. Outlined cells are the equal pairs Nim calls lost, all of which are wins once the pass is there.

Three heaps and a pass

Nim with a single pass that may not end the game is easy on one heap and on two: a heap swaps each odd size with the even one above it, and two heaps lose exactly at (2k − 1, 2k). On three heaps the losses are known only as a list. Fix the smallest heap and each slice of the list settles into a pattern after an irregular start — period 4, 8, 10, then 160 at a smallest heap of ten, and nothing visible from eleven.

limits · Pass

Named alongside it

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

Exhaustive searchGrundy valueImpartialComponentDisjunctive sumNim-sumNormal playCounterexampleLoonyMexNimSprague–Grundy

All concepts