The code names the move

The rung below this one establishes something odd: in Mock Turtles on eight coins, the rows a player has already lost are closed under adding two of them together, so they form a linear code — the extended Hamming code exactly, sixteen words with weight enumerator $1 + 14x^4 + x^8$, produced by a move rule that knows nothing about coding theory.

A code that is only a classification is a curiosity. This one is not, because a code comes with a decoder, and the decoder is a move-finder.

What a coin-turning game is #

The family is worth restating, because everything below depends on one structural fact about it.

A row of coins, each showing heads or tails. A move turns over a set of coins subject to the game’s own rule, with the constraint that the rightmost coin turned must go from heads to tails. A player with no legal move — every coin showing tails — has lost.

The constraint is what makes the game end: each move moves the rightmost head strictly leftwards, so play cannot go on for ever. And it is what makes the whole family decomposable. A row is the disjunctive sum of its heads, each head treated as a one-coin game at its own place, because a move’s rightmost coin belongs to exactly one of them and the coins it drags along are the options of that one.

So a row of coins is a Nim position in disguise: a heap for each head, of the size that place is worth. The decomposition is inside a single picture, which is what makes coin-turning games the most compressed illustration of the disjunctive sum on this site.

Grundy value, syndrome, same object #

The dictionary is exact rather than analogical, which is what makes the rest of the essay computation instead of metaphor.

A row is a set of heads, and the theory that makes it a sum assigns each head a value. Each place $n$ has a value $\mathcal{G}(n)$ — for Mock Turtles the odious numbers, those with an odd number of ones in binary — and the row is worth the exclusive or of the values of its heads. A row is lost exactly when that exclusive or is zero.

In coding terms the values are the columns of a parity-check matrix, a row of coins is a word, and the exclusive or is its syndrome. Zero syndrome means codeword; non-zero syndrome means an error pattern is present, and the syndrome says which one.

The move is the error pattern #

A move in Mock Turtles turns one, two or three coins, with the rightmost of them going from heads to tails. As a change to the word, that is adding a pattern of weight at most three, subject to a constraint about where the leftmost — highest-indexed — flipped bit is and which way it flips.

A winning move is one that reaches a codeword, so it is a pattern whose value-sum equals the syndrome. That is syndrome decoding: given $s$, find an allowed error pattern $e$ with $\bigoplus_{i \in e} \mathcal{G}(i) = s$.

The row with heads in the first three places is the same story with one answer instead of three. Its value is $1 \oplus 2 \oplus 4 = 7$, the nearest codeword is again one coin away and again behind a coin showing tails, and the single winning move turns all three heads at once — the maximum the rule allows, to cover a distance of one.

Which errors the rules allow #

A decoder is defined by its error patterns — the set of changes it may make to a word — and this game’s set is unusual enough to be worth writing out.

For Mock Turtles the pattern is any one, two or three places, with a constraint: the highest place in the pattern must currently show heads. Turning it moves it to tails; the other one or two coins flip either way.

Two features of that set matter. It is not closed under complement or shift — patterns are constrained by the state of the row, not merely by their own shape — and it is not symmetric: the same three places form a legal pattern from one row and an illegal one from another. Standard syndrome decoding assumes neither constraint, which is why the answers here are not simply the coset leaders of the code.

That is the sense in which the game is a decoder with a rulebook. The syndrome tells it what to fix; the rules tell it which fixes are available; and the essay’s central number — 64 rows needing three coins when the code says two — is the gap between the two.

The natural test of that claim is another rule, and the plainest one is next door. Turning Turtles turns one or two coins rather than one, two or three, and its code on seven coins is the Hamming code — so it has a decoder too, and the question is whether the gap between what the code allows and what the rules allow is a fact about Mock Turtles or about the family.

That settles the shape of the answer. The gap is caused by the clause about the rightmost coin, which every rule in the family has, so every decoder in the family has some version of it — and how large the gap is depends on which sets the rule offers rather than on how many coins it turns.

Where the extra coin goes #

The two columns of the hero figure disagree, and the disagreement is the finding.

The code says two. The extended Hamming code has covering radius 2: every eight-bit word is within two coins of a codeword, and 128 rows are at distance 1 with the other 112 at distance 2. Nothing is further.

The rules say up to three, and on 64 rows all three are needed. The reason is the clause about the rightmost coin. A move may flip any pattern of one to three positions provided the largest-indexed flipped coin is currently a head — a player turns a head over and drags at most two other coins with it. A two-coin pattern that would reach a codeword is illegal when its higher coin is showing tails, and the cheapest legal alternative adds a third coin.

So the game’s rule is not quite the code’s neighbourhood structure. It is the neighbourhood structure with one asymmetry, and the asymmetry costs exactly 64 rows a coin.

How many moves win #

A won row has between one and seven winning moves, and 3.07 on average.

That spread is worth a moment. A game whose losing positions are rare tends to have few winning moves, and here the losing positions are one row in sixteen while the average won row has three ways to reach one. The reason is the code’s structure rather than its size: a word at distance 1 from a codeword is at distance 3 or more from most others, but the allowed patterns overlap, so several different triples of coins land on the same or on different codewords.

The rows with exactly one winning move are the interesting ones for a player. There, the decoder is not choosing between answers — it is finding the only one.

So the 64 rows are not an inevitability of the family either. They are what happens when a code’s radius is smaller than the reach its own game needs, and a rule with fewer words to aim at can leave every row a legal cheapest move.

The strategy this hands a player #

The practical upshot is a strategy that fits on a card, and it is worth stating because most game strategies on this site do not.

Compute the syndrome. Add up, with exclusive or, the odious numbers at the places showing heads. If it is zero, the position is lost and nothing helps.

Otherwise find a legal pattern with that value. Any one, two or three places whose values exclusive-or to the syndrome, with the highest place currently a head.

That is it. No search over the game tree, no lookahead, and the whole of the tactical difficulty replaced by a small arithmetic problem — which is exactly what the impartial theory promises everywhere and delivers only when the values are known in closed form.

Mock Turtles’ values are known in closed form: the odious numbers, in order. So the strategy is not merely computable but sayable, and a player who has memorised “1, 2, 4, 7, 8, 11, 13, 14” can beat anybody who has not, on any row of eight coins, without thinking about the game at all.

Mogul is the same game with the moves confined to a window of seven, and its values agree with Mock Turtles’ for seven places and then repeat where Mock Turtles’ climb. So the memorised list above is a fact about the rule and the length together, and a player who learnt it would be wrong from the eighth coin of a Mogul row onwards.

What the two exhaustions have in common #

Both halves of this essay are exhaustions and neither is a sample, which is worth one paragraph because the alternative was available and would have been misleading.

The code is found by enumerating all 256 rows and keeping those whose value is zero — not by writing down a generator matrix for the extended Hamming code and checking that the game agrees with it. That direction matters: the code is the output of the game, and a check against a quoted matrix would have proved that this site can transcribe a textbook.

The decoding is found by generating every legal move from every won row, not by computing coset leaders and then checking they are legal. Again the direction is the point, because the 64 rows are exactly the case where the coset leader is not a legal move, and a decoder-first calculation would have reported a strategy the game refuses.

Both are small — 256 rows, at most a few dozen moves each — and the smallness is what allows the argument to be made this way. The site’s habit is to compute the thing being claimed rather than the thing that implies it, and coin-turning games are where that habit is cheapest to keep.

What the solver computed, and how #

One sweep over all $2^8$ rows.

Each row’s value is the exclusive or of the odious numbers at its heads; the codewords are the rows with value zero, found by enumeration rather than by construction, which is how the rung below confirmed the code is the extended Hamming one. For every non-zero row, every legal move is generated from the rules — a head at $n$, and a turn set from the game’s own move list ending at $n$ — and the ones landing on value zero are the winning moves.

Two further quantities per row: the cheapest winning move, being the fewest coins any of them turns, and the Hamming distance to the nearest codeword, computed against all sixteen. The first is a fact about the game, the second is a fact about the code, and the essay is about the gap.

The arithmetic underneath all of it is the nim-sum: the value of a row is an exclusive or of place values, exactly as the value of a Nim position is an exclusive or of heap sizes. A coin-turning game is a Nim position in disguise, and the code is what that disguise looks like when the place values are the odious numbers rather than the integers.

The sweep is worth running on a rule whose sets are genuinely unlike Mock Turtles’, because everything above has been measured on rules that offer every small set.

Why the covering radius is the right quantity #

Coding theory has two distances and they answer different questions. The minimum distance — 4 for this code — is how far apart the codewords are, and it bounds how many errors a decoder can correct. The covering radius — 2 — is how far the furthest word is from the nearest codeword, and it bounds how much correcting a decoder can be asked to do.

For a game it is the second that matters, and the reason is the direction of play. A player is not trying to recover a codeword that was sent: they are trying to reach one, from wherever the position is, in a single move. So what they need is a bound on the distance to the nearest codeword, and that is the covering radius exactly.

The minimum distance is not useless here, though — it is what makes the winning move nearly unique. A row at distance 1 from one codeword is at distance 3 or more from every other, so most of its winning moves land on the same one. The two distances between them say that a winning move always exists and that the answers do not spread out, which is a much better description of the game than either alone.

The constraint that costs a coin is the constraint that gives the theory #

The clause about the rightmost turned coin reads like an awkwardness — a rule of the game with no counterpart in coding theory, charging 64 rows an extra coin for nothing. It is worth turning round, because it is not an awkwardness at all. It is the entire reason any of this works.

Go back to the decomposition. A row is a sum of one-coin games, one per head, and that is what licenses adding the values with exclusive or and invoking Sprague–Grundy at all. For it to be a sum, every move has to be a move in exactly one component, leaving the others untouched — and a move here flips up to three coins scattered along the row, which does not look like a move in one component.

The clause is what makes it one. A move’s rightmost turned coin must be a head; that head is a component; and the other coins the move drags along are not moves in their components but part of the option this one has. So “which head is the rightmost coin turned” is “which heap is being played in”, and the constraint is the sum structure written as a rule about coins.

Take the clause away and two things go at once. The game stops ending, because nothing forces the rightmost head leftwards and a player could turn coins back and forth for ever. And the row stops being a sum, because a move flipping an arbitrary set of coins belongs to no single component, so there is no heap decomposition, no exclusive or, no Grundy value and no code.

So the 64 rows are the price of the theory rather than a defect in it. A decoder working from the code alone would name two-coin moves the game refuses; the game refuses them because the same rule that forbids them is the rule that produced the code in the first place. There is no version of Mock Turtles with the code and without the clause.

Which guarantee is doing the work #

That reframing settles a question the previous sections leave open, and the answer is the opposite of what the essay’s title suggests.

Two separate facts appear to promise a player that a winning move exists. The covering radius says every row is within two coins of a codeword, so there is always somewhere close to go. The mex says a position with non-zero value always has a move to a position with value zero, which is the whole content of the impartial theory.

Only the second is a guarantee. The covering radius is a statement about the code — about which words are near which — and it says nothing whatever about whether a legal move reaches them. On 64 rows it does not, and those rows are the proof that the coding fact, taken alone, promises something the game does not deliver.

The mex, by contrast, delivers. Its argument is the ordinary Nim one and it never mentions distance: take the highest bit where the row’s value differs from zero, find a head whose place value carries that bit, and play in that component — the component’s options run over every smaller value, so the required one is there. That is a legal move by construction, because it is a move in the component at a head.

So the honest reading of the whole dictionary is narrower than “the code names the move”. The code names the destination — sixteen words, and a player wants to hand one of them over. The game names the move, and it names it through a mechanism the code has no access to. What the coding side contributes is a picture of the target set and a good measure of how far away it is; what it cannot contribute is the assurance that the target can be reached, which is exactly the thing a player needs and exactly the thing the 64 rows show it does not have.

That division is what the other three decoders on this page confirm rather than test. Turning Turtles has a radius of one and still charges half its rows a second coin; Ruler has a radius of four and charges some of its rows all eight; Mogul on seven charges nobody. In every case the covering radius says how far the nearest codeword is and says nothing about whether the game can get there, and in every case the mex still hands over a legal move.

Where the model stops #

Eight coins. The extended Hamming code is a fact about length 8, and the values that produce it are the odious numbers; longer rows of Mock Turtles are a different code, and the covering radius, the distance distribution and the “three coins” count all change with the length.

And the strategy is a strategy for one game. Turning Turtles is the same board with a rule one coin shorter and its values are the plain integers, so a player computes its syndrome as an ordinary nim-sum of place numbers rather than of odious ones — sixteen codewords of 128 rows, and a different sixteen. Mogul is Mock Turtles with a window, and its values are different again from the eighth coin on. The dictionary between games and codes is real and the particular code is not portable.

And the dictionary is one-way in one respect. Every coin-turning game whose lost rows are closed gives a linear code, and the decoding story follows; but not every code arises from a game with a legal move for each pattern. The constraint that the rightmost turned coin be a head is a rule of the game with no counterpart in coding theory, and it is exactly what the 64 rows are about — a decoder that ignored it would name illegal moves.

Where the ladder goes next #

One direction is now closed and the reason is worth recording. Whether the other rules’ decoders carry the same asymmetry was the obvious next measurement, and the sweep answers it for all three: they do, in wildly different amounts, and the amount is set by which sets the rule offers rather than by how many coins it turns. Ruler is the extreme — a radius of four and rows that need all eight coins — and Mogul on seven is the case where the clause costs nothing at all.

What is left is the direction the coding theory points: the code’s dual, which for the extended Hamming code is itself, and what a self-dual code means for a game that produced it without being asked to. A game reads a codeword as a position to hand over; nothing in the game reads a dual codeword as anything, and finding out whether it should is the rung above this one.