The losing positions are a code

A coin-turning game is a row of coins, some heads and some tails. A move turns over a set of them, subject to the game’s own rule, and the rightmost coin turned must go from heads to tails — which is what makes the game end. Whoever cannot move loses.

A row of coins is already a sum: a head at place k is a game on its own, the row is the disjunctive sum of its heads, and the row’s value is the exclusive or of the one-coin values. So the rows a player has already lost — the ones with value zero — are exactly the rows whose heads exclusive-or to zero.

That description has a consequence nobody put there. Take two lost rows and turn over every coin they disagree about. The result is lost as well.

Why the lost rows add #

The argument is two lines and it needs nothing but the exclusive or.

A row is lost for the mover exactly when the exclusive or of its heads’ one-coin values is zero. Write the row as a string of bits — one for heads, zero for tails — and “turn over every coin two rows disagree about” is bitwise addition of the two strings.

The value of the combined row is the exclusive or of the values of the coins showing heads in it, and each coin appears in the combination exactly when it appeared in an odd number of the two originals. Exclusive or is its own inverse, so the combined value is the exclusive or of the two originals’ values, which is 0 ⊕ 0 = 0.

A set of binary strings closed under bitwise addition is a linear code. That is the whole of the definition, and the lost rows satisfy it for a reason that has nothing to do with coding theory: they satisfy it because values add.

The addition doing the work is the nim-sum — exclusive or, column by column with no carrying — and it is the same operation twice over here: it is why a row of coins has a value at all, and it is why the rows of value zero are closed under combining.

Turning Turtles gives the Hamming code #

The plainest coin-turning rule is turn over one or two coins. Its one-coin values are 1, 2, 3, 4, … — a head at place k is worth a Nim heap of size k, which is why a row of coins is a Nim position in disguise.

Now take seven coins. The values are 1 through 7, which in binary are every non-zero three-bit string: 001, 010, 011, 100, 101, 110, 111.

A row is lost when the exclusive or of the values at its heads is zero — that is, when those three-bit strings sum to zero over the two-element field. The set of subsets with that property is exactly the code whose parity-check matrix has all seven non-zero columns of length three, and that is the [7, 4] Hamming code.

The correspondence is not an analogy. The one-coin values are the columns of the parity-check matrix, the exclusive-or condition is the parity check, and the lost rows are the codewords. Two constructions, built for unrelated reasons, producing the same sixteen strings.

Seven is not an arbitrary length to have chosen, and the way to see that is to add a coin. Place eight is worth eight, and eight is larger than any exclusive or of the values below it, so no combination of places 1 to 7 can cancel it.

That is the first sign of something the rest of the essay leans on: a game does not have a code, a game and a length have one between them. The rule is fixed and the answer changes with the number of coins, because what the rule determines is the sequence of place values and what the code is made of is the values that fit.

Mock Turtles gives its extension #

Change the rule by one word — turn over one, two or three coins — and the one-coin values change to 1, 2, 4, 7, 8, 11, 13, 14: the odious numbers, those with an odd number of ones in binary.

Every odious number has odd binary weight, so appending a parity bit to each of them gives strings of even weight — which is the standard way of extending a code. On eight coins the lost rows come out as the extended Hamming code: 16 words, minimum weight 4, and the weight enumerator 1 + 14x⁴ + x⁸.

Minimum weight four means no lost row can be reached from another by turning fewer than four coins. That is a statement about the game: from a lost position, every move of one, two or three coins lands in a position the opponent wins, which is exactly what being lost means, and the code’s distance is the reason.

The distance is forced by the rule #

That last observation is worth turning round, because read the other way it says something the coding side would have to work for.

A coin-turning game every one of whose small sets is a legal turn produces a code of minimum distance one more than the largest such set.

The argument is three lines. Take two codewords differing in $w$ places, with $w$ at most $k$. At the rightmost of those places one of them has a head; call that one $c$. Turning exactly the $w$ disagreeing coins, starting from $c$, is a legal move — its rightmost turned coin goes from heads to tails — and it arrives at the other codeword. But a codeword is a position the mover has lost, and from a lost position every move reaches a position the opponent wins. Contradiction, so no two codewords are within $k$.

The clause worth staring at is “turning exactly the $w$ disagreeing coins is a legal move”, because the tempting version of this theorem drops it. Written as a game whose moves turn at most $k$ coins gives distance at least $k+1$ it is false, and it is false about two of the four rules in this site’s own library.

So the dial is not how many coins may a move turn but which sets may it turn, and the two rules whose codes this essay opened with are the two whose answer to the second question is “all of the small ones”.

Which is the rate-distance trade, arriving from the game #

That reframing does something better than explain the two examples. It says the games and the codes are trading the same thing.

In coding theory the central tension is between rate — how many codewords a length supports — and distance — how far apart they are. More of one costs the other, and every good code is a point on that curve.

Here both quantities come from the move rule, and they move in opposite directions for a reason a player would recognise.

A more generous rule buys distance. Allowing moves of up to $k$ coins forces the codewords $k+1$ apart, by the argument above. Turning three coins rather than two takes the distance from 3 to 4.

And it costs codewords. Every extra move is another way to leave a position, so more rows have a move to a lost row, so fewer rows are lost. Sixteen codewords on seven coins with the smaller rule; sixteen on eight coins with the larger one — the same count over twice as many rows.

So the coding-theory curve is, on this family, the game-theory question how much may a move do? — and the two famous codes the family produces are not lucky coincidences but the two points a reader reaches first by turning that dial.

And it says what the family cannot produce. A code of distance $d$ needs a rule that always offers every set of $d-1$ coins, and such a rule is generous enough to leave few positions lost. Nothing in this family gives many codewords and a large distance at once, which is the same wall coding theory runs into and here it has a reading in play: a game where a lot is legal is a game where very little is safe.

Ruler is the case that shows the trade is about sets rather than sizes, and it is worth drawing because it is the one rule of the four whose code nobody has named.

The values are the reason. Ruler’s one-coin values are 1, 2, 1, 4, 1, 2, 1, 8 — the largest power of two dividing the place — so the parity-check matrix has repeated columns, and a code with two equal columns has a weight-two word by construction. A coding theorist would call that a bad code and be right; a player would say the rule is stingy about which coins it lets a mover touch, and both are describing the same matrix.

Where the odious numbers come from #

The values are not chosen and they are not looked up. Each one is a mex over the moves a lone head at that place has, and the pattern is what comes back.

A head at place n can be turned alone, leaving nothing; turned with one coin to its left, leaving a head there; or turned with two coins to its left, leaving two heads whose combined value is their exclusive or. So the value at n is the smallest non-negative integer not among those results, computed left to right with no search over rows at all.

Run that from the left and the answers are 1, 2, 4, 7, 8, 11, 13, 14 — every number with an odd count of ones in binary, in order, and no others.

Nothing in the rule mentions parity of binary digits. The connection is that a move turns one, two or three coins, so the value of what is left is a sum of at most two earlier values, and the odious numbers are exactly the set closed against being reached that way. That is the same kind of coincidence the Grundy sequences essay is about — a rule stated in one vocabulary producing a pattern stated in another — and it is why this family was worth sweeping in the first place.

Mogul, and a code with fewer words #

The third rule in this site’s library restricts Mock Turtles to a window: turn one, two or three coins, all within seven places. It is called Mogul, and the restriction makes its one-coin values repeat.

On seven coins Mogul’s lost rows are a smaller set than Turning Turtles’ — eight words rather than sixteen — with minimum weight four.

Fewer words with a larger minimum distance is the trade every coding theorist knows and every game player meets here from the other side: a game whose moves are restricted has fewer lost positions, and the ones it has are further apart.

And the eighth coin is where the restriction announces itself, in the values and then in the code. Mogul’s values repeat with period seven — 1, 2, 4, 7, 8, 11, 13, then 1 again — so places 1 and 8 are worth the same thing.

That is the same trade running backwards, and it is the sharpest case of the clause in the bound above: the number of coins Mogul turns has not changed, only which sets of them it may reach, and the code’s distance halved.

What the code buys the player #

A player at a coin-turning board does not need the code. They need the exclusive or, which is Bouton’s rule in a different costume: compute the value, and if it is not zero, find a move that makes it zero.

What the code adds is a description of the target set. The lost positions are not scattered. They form a structured object of dimension four out of eight — sixteen of 256 rows, one row in sixteen — and its structure is exactly what makes the winning move findable: from any position, the move to make is the one that lands on the nearest codeword.

That is the same computation as decoding, and it is a good illustration of what Sprague–Grundy buys in general. The theorem says every impartial position is a Nim heap; here it says more specifically that the whole set of lost positions is a linear subspace, and a subspace is a thing an algorithm can search.

Underneath all of it is the mex rule: a position’s value is the smallest non-negative integer that is not the value of any option, which is what makes a value-zero position one with no value-zero option and therefore one every move leaves. That is the sentence the distance bound above is a consequence of, and it is checked in the table there rather than assumed.

The check that can fail #

A closure test that passed whatever it was handed would establish nothing, so the figure runs a second test whose answer must be no.

The winning rows — the 240 of Mock Turtles’ 256 that are not lost — are also checked for closure, and they are not closed: adding two of them frequently lands inside the code rather than outside it. That is not an accident of these particular rows; the complement of a subspace is never a subspace, because it does not contain zero.

Reporting that failure beside the closure result is what makes the closure result mean something. It is the same discipline as the sabotage in the geography gate, where a deliberately broken reduction has to be rejected before the working one counts for anything — and the same lesson: a test that has never rejected anything has not been tested.

What had to be checked before any of this was believed #

Four separate claims are being made, and each has a test that could have failed.

That a row’s value is the exclusive or of its heads. Every coin-row figure computes the value twice — once by the decomposition and once by playing the entire row out as a single impartial game with a mex at every node — and refuses to draw if the two disagree. The site’s gate runs the same comparison over all 4,096 rows of twelve coins for three rules.

That the lost rows are closed. Tested over every ordered pair, not sampled: 256 pairs for a sixteen-word code, reported on the figure.

That the closure test is not vacuous. The winning rows are tested too, and must fail. They do.

That the weight enumerator is what it is claimed to be. Counted from the drawn words rather than quoted from a table of codes.

That last one matters more than it looks. The sentence “Mock Turtles on eight coins gives the extended Hamming code” is exactly the kind of claim a writer picks up from memory and gets subtly wrong — the Fibonacci-base rule this site got wrong from memory failed on 28 of 3,600 positions and was caught only by running it against machinery that shared no arithmetic with it. Here the identification rests on a weight enumerator counted off the computed words, which is the same discipline applied before the error rather than after it.

Where the model stops #

The code depends on the length as much as on the rule, as the eighth coin showed twice: Turning Turtles gains a coordinate no codeword uses, and Mogul gains a repeated value that halves its distance. Turning Turtles on six coins is smaller again — eight words, minimum weight three — and Mock Turtles on fourteen has 512 words of nine dimensions. The game does not “have a code”: a game and a row length have one between them.

Not every coin-turning game gives a famous code. Ruler’s sixteen words are a perfectly good linear code that nobody has named, for the reason drawn above: its parity-check matrix repeats a column four times. The Hamming coincidences are a fact about two particular rules whose one-coin values happen to be the columns somebody wanted.

And the codes here are drawn, not decoded. Nothing in this essay implements error correction, computes a syndrome or transmits anything. The code as an object belongs elsewhere — the sixteen words as a perfect packing of the seven-bit cube and the decoding that repairs a word without reading it — and what is claimed here is the game: a move rule, a mex, and the set that comes back.

Why a game produces a code at all #

It is worth asking why this should happen, because “a game rule produced a famous combinatorial object” is the kind of sentence that invites suspicion.

The answer is that both objects are defined by the same equation. A linear code is the kernel of a matrix over the two-element field — the set of vectors a parity check sends to zero. The lost positions of an impartial game are the set of positions whose Grundy value is zero.

For a coin-turning game those two definitions coincide, because the value of a row is a linear function of which coins show heads: exclusive or is addition in that field, and the one-coin values are the coefficients. Nothing else about the game survives into the description, and nothing else needs to.

So the right statement is not that a game happens to produce a code. It is that a coin-turning game is a linear map, and its lost positions are its kernel, and a kernel is a code. Which code depends only on the coefficients — the one-coin values — and those are what the move rule determines.

That also explains the limits of the phenomenon. The impartial theory stops at partizan games, and it stops at impartial games whose values do not add coordinatewise: a game where the row’s value is not the exclusive or of its parts’ has no linear structure to hand over, and the lost positions are just a set.

What the picture cannot show #

The figure draws sixteen rows of discs, and sixteen rows of discs is a set rather than a structure.

The closure property — the thing that makes the set a code — is a statement about every pair of members, and 256 ordered pairs cannot be drawn on a page. What the figure does instead is report the count of pairs tested, which is a promise rather than a picture, and the site’s gate re-runs the same test independently.

The other invisible thing is the dimension. Sixteen words is 2⁴, so four of the rows generate all sixteen by combination, and which four is a fact the drawing does not encode — any four independent words will do, and the code has no preferred basis. A reader looking for the four fundamental rows will not find them, because there are no such rows.

The convention, named #

Normal play, and one convention specific to coin-turning games that everything above depends on.

The rightmost coin turned must go from heads to tails. That single clause is what makes the game terminate: each move strictly decreases the position read as a binary number, so there are no infinite plays and the recursion has a bottom. Drop it and the game never ends and has no values at all.

The other convention is the indexing. The coins are numbered from 1, and a “one-coin value” is the value of the position with a single head at that place. Numbering from 0 would shift every value by one place and change every code on this page — the Hamming coincidence is a fact about places 1 to 7 under this convention, and it is worth saying so rather than letting a reader assume the labelling is inevitable.