A move that must be answered

The Sprague–Grundy theorem is the strongest result in the impartial theory and it rests on one sentence that nobody thinks about: a move in one component of a sum leaves the other components exactly as they were, and the opponent may reply wherever they like. Independence is what lets a heap be replaced by a number, and the numbers be combined.

Top Entails is a game that breaks the sentence. Heaps of coins; a move is either

• take the top coin of a heap — after which the opponent must move in that heap; or
• split a heap into two non-empty heaps, which compels nothing.

The first kind of move reaches across the sum and names the component the answer has to be made in. Everything that follows is the price.

What independence was buying #

It is worth naming what the disjunctive sum assumes, because the assumption is invisible until a game breaks it.

Three clauses. A move is made in exactly one component. The other components are unchanged by it. And the opponent may reply in any component, including the one just moved in and including any other.

Everything the impartial theory does rests on the third. The Sprague–Grundy proof works by showing that a sum behaves like a Nim position whose heaps are the components’ values, and the argument at each step is “whatever the opponent does in one component, answer in the component that restores the nim-sum” — a strategy that requires the answer to be free to go anywhere.

An entailing move deletes that freedom for one turn. The mover names the component, and the strategy that would have restored the nim-sum somewhere else is simply illegal. One turn is enough: the whole theorem is a chain of such answers, and a chain with one broken link is not a chain.

The wrong theory, run anyway #

The wrong theory is worth writing down, because it is what a solver produces if it is not told about the compulsion. Treat each heap as an ordinary take-and-break game — remove the top coin, or split — and apply the mex rule. The values come out $1, 2, 0, 2, 0, 2, \ldots$, and the nim-sum of them ought to decide any sum.

Nine failures in thirty-six is not a small discrepancy to be patched. It is the theorem failing, and the reason is visible in the position that fails hardest.

Two heaps of two #

Two heaps of two coins. The nim-sum says $2 \oplus 2 = 0$, a second-player win. The search says the first player wins, and the only winning moves are entailing ones.

The line runs: take the top coin of one heap, leaving heaps of one and two, with the opponent compelled to move in the heap of one. Their only move there is to take its coin, which empties it — and the compulsion is discharged with nothing gained. The board is now one heap of two, and it is the first player’s turn again, in a position that whoever moves wins.

The mover has, in effect, played twice. That is not something a move in a disjunctive sum can do — and “played twice” is the exact currency every temperature argument on this site is denominated in, which is why a rule that hands out a free move breaks so much.

That figure is the whole essay in one line. $G + G = 0$ is not a deep theorem; it is the first thing proved about sums, it holds for every position on this site, and its proof is one sentence. Entailing moves delete the sentence.

Why the even heaps are the loony ones #

The rule the census confirms has one clause that does the work — an even heap wins for the mover whatever else is present — and the mechanism is worth following on the smallest case.

A heap of two: the mover splits it into two heaps of one. That leaves $1 + 1$, which is a second-player win, so the split wins. Note that the winning move here is the non-entailing one.

A heap of four: the mover takes the top coin, leaving a heap of three and compelling the opponent to move in it. The opponent’s options inside a heap of three are to take its top coin — compelling the mover back into a heap of two, which the mover then splits — or to split it into $1 + 2$, which leaves an even heap on the board again.

What the entailing move buys is a tempo: the opponent is spent answering a compulsion, and the position that comes back is one the mover wanted. That is why the effect survives company. A player with an even heap available always has this manoeuvre, and the rest of the board cannot interfere with it, because the compulsion names where the answer goes.

What the theory needs instead #

The outcomes are not lawless — they obey a rule, and the rule has a clause in it that no nimber can express.

The first clause is the interesting one. A value that wins for the mover whatever else is present is not a nimber: a nimber $\ast k$ can always be cancelled by another $\ast k$, and this cannot be cancelled by anything. Winning Ways gives such positions a symbol of their own and calls them loony — a move into a loony position is a move nobody would make, and a position containing a loony option is won by making it.

So the repair is not a better Grundy value. It is an extra value outside the nimbers, and a theory of when a position has one.

Where else this shape appears #

Top Entails is a small game chosen for being clean, and the phenomenon it isolates is not rare.

Nimstring, the impartial game underneath Dots and Boxes, has it in the form millions of people have played without naming it: taking a box gives another turn, and the position after it is one the opponent has no say in. The theory of that game is built around exactly the classification this essay meets — moves nobody would make, positions that win regardless — and the word “loony” comes from there.

Ko fights in Go have a version of it: a ko threat compels an answer, or costs the threatener something if it is ignored, and the whole apparatus of threats is an account of what a compelled reply is worth.

Carry-on moves and entailing moves in the modern literature are the general version, where a component can hand the opponent an obligation rather than a position, and the values live in a system built for the purpose.

What Top Entails contributes is that the failure can be exhibited at heap two — a position with two coins in it, an answer that fits on a line, and a theorem that visibly does not hold.

Where the boundary actually is #

It is worth being precise about what is lost, because it is less than “everything”.

The game is still impartial. Both players have the same moves from every position, including the compelled ones, so the outcome classes are still only two: first player wins or second player wins. Nothing here needs the partizan machinery.

The recursion still terminates. Every move removes a coin or splits a heap, and both reduce a quantity that cannot fall for ever, so the condition the recursion rests on is met. Positions are still solvable one at a time.

What is lost is the decomposition. A sum of positions cannot be evaluated part by part, because the state is not a list of heaps: it is a list of heaps and which heap the mover is compelled into. That extra field has no home in the Grundy theory, and it is what the solver here carries.

What the solver computed, and how #

The state is a pair: the heap list, and the index of the heap the mover is compelled into, or null when they are free. Moves are generated from that pair — when compelled, only moves in the named heap are legal — and the outcome is the ordinary backward induction, memoised on the pair.

Memoising on the pair rather than on the heaps is the whole implementation, and it is where a solver written for an ordinary take-and-break game would be wrong without erroring: it would look up [1, 2] and return an answer computed for the free position when the compelled one was asked for.

Three sweeps come out of it. The heap table is one heap at a time with the naive Grundy value beside it. The sum table is every two-heap position up to six a side, compared against the nim-sum prediction — 36 solved positions and 36 predictions. The rule census is 258 positions with up to three heaps of up to six coins, each solved in full and compared against the three-clause rule.

The clause the rules do not cover #

There is a case the two-line statement of the game leaves open, and it has to be settled before any of the numbers above mean anything.

Take the top coin of a heap, and the opponent must move in that heap. What if the coin taken was the heap’s last one? The heap is gone, and “must move in that heap” names something that no longer exists.

Three readings are available and they are genuinely different games. The compelled player might lose, having been sent somewhere with no moves in it. The compelled player might be free, the obligation lapsing with the heap. Or taking the last coin might simply be illegal, on the grounds that a move which cannot name a legal answer is not a move.

This site takes the second. Emptying a heap removes it and compels nothing; the opponent moves wherever they like.

The smallest position separates them, which is the useful thing about it. Two heaps of one: under the reading here, either take leaves a single heap of one, the opponent takes that, and the first player is stuck — a second-player win. Under the first reading the same position is a first-player win, because taking either coin sends the opponent to a heap that has gone. Under the third there are no legal moves at all and it is again a second-player win, but a heap of one on its own becomes a position nobody can move in rather than one the mover takes.

That propagates. Everything in this essay is built on $1 + 1$ being a second-player win — it is why a heap of two is won by splitting rather than by taking, which is the essay’s first observation about a winning move, and it is the base of the induction that gives the even heaps their rule.

So the convention is load-bearing and it is a convention. Naming it is not pedantry: a reader who solves these positions by hand under a different reading of the emptying case will get a different table and will be right about a different game. Nothing above distinguishes the three on the strength of the rules alone, because the rules do not reach the case.

It is also worth noticing what the choice does to the essay’s own argument, which is that entailing moves are powerful. The reading taken here is the weakest of the three: it is the one in which an entailing move buys the least, since the compulsion evaporates precisely when it would be most crushing. The failure of $G + G = 0$ and the nine misread sums survive anyway, which makes them findings about compulsion rather than about a harsh edge case.

Where the model stops #

The rule is checked, not proved. Three clauses agreeing with 258 solved positions is evidence of the kind this site trusts and does not call a theorem; a heap large enough to break the pattern would be a row rather than an exception, and none has appeared at this size.

The census is small. Three heaps of up to six coins is 258 positions; the state space grows quickly, because splitting multiplies the number of heaps and the compulsion doubles every state. The three-clause rule is checked, not proved, and this site does not claim theorems it has only tested.

Top Entails is one game. The general theory of entailing moves is a subject in its own right — it covers Nimstring’s compelled replies, “carry-on” moves, and the modern treatment where a component can hand the opponent a move rather than a position — and none of it is developed here. What this essay establishes is that the ordinary theory needs replacing, not what replaces it — and the difference matters, because a reader who takes “the Grundy theory fails here” as “impartial games are unsolved” has over-read it by a wide margin. Every octal game on this site has moves that entail nothing, and for those the theory is exactly as strong as it ever was.

And the failure is not misère. The two exits are worth keeping apart: misère play changes what winning means and leaves the moves alone, and entailing moves change the moves and leave winning alone. Misère play breaks the same theory by changing what winning means; entailing moves break it while leaving normal play entirely alone. Two different exits from the same theorem, and this site now has both.

What loony is, algebraically #

“Wins for the mover whatever else is present” is a phrase about play, and it has an exact algebraic reading that is worth setting down, because it says why no repair inside the nimbers was ever going to work.

Write the condition out. A position $L$ is loony when $L + G$ is a first-player win for every $G$. Now put $G = L$. The condition says $L + L$ is a first-player win, and in every impartial game the ordinary theory covers, $G + G$ is a second-player win, always, by the mirror.

So a loony position is not a value the theory happens not to have a symbol for. It is a direct witness that the theory’s first identity has failed — the two statements are the same statement, and the mirror figure above is the proof and the counterexample at once.

That also explains why the failure could not be a matter of degree. There is no nimber $\ast k$ with $\ast k + \ast k \neq 0$, and no larger family of nimbers to escape into, because cancellation is what a nimber is: $\ast k$ is the Nim heap of $k$, another heap of $k$ answers it move for move, and the answer is available because the reply is free. Every route to a fix inside the impartial theory is a route through that sentence.

And it explains the shape of the repair the literature made. A new symbol was needed rather than a bigger number, and the symbol had to be absorbing rather than invertible — a value that dominates a sum instead of cancelling in it. That is a different kind of object from anything the Grundy theory contains, which is why the essay’s census can state the rule in one clause and the theory cannot state it at all.

What survives, and what a solver has to carry #

The practical summary is short. A solver for a game with entailing moves cannot be a solver for the components: it must carry the compulsion in the state, and the state is a position plus a note about where the next move must go.

That is a small change to write and a large change to what the code means. The memo table is keyed on the pair, so [1, 2] free and [1, 2] compelled into the first heap are two entries with two answers — and a solver that keyed on the heaps alone would answer confidently and wrongly, with no error raised anywhere.

It also changes what a figure can show. Everywhere else on this site a picture of a position is a picture of the whole state; here it is not, and the essay’s figures say which heap the compulsion is in because a drawing of the coins alone would be ambiguous.

The failure is not that the game is hard. Top Entails is small and every position in the census is solved exhaustively in milliseconds. The failure is that the answers do not compose, which is a different and worse problem: a game that is hard can be attacked with a better search, and a game that does not decompose has to be searched whole for ever.

Where the ladder goes next #

The obvious rung above this is the theory the failures ask for: a value system in which loony is a first-class citizen, and a decomposition theorem that survives compulsion. The obvious rung beside it is Nimstring, where a compelled reply is not an exotic rule but the ordinary way Dots and Boxes is played — the same phenomenon in a game millions of people know.