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 7 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 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 — 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 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 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 searchImpartialDisjunctive sumGrundy valueNim-sumComponentCounterexampleLoonyNimNormal playMexSprague–Grundy

All concepts