Combinatorial Game Theory
who wins, and by how much
Series

Codes — the series

3 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Mock Turtles on 8 coins: every lost position. The rows a player to move has already lost, drawn in full. A filled disc is a coin showing heads. The set is closed under turning over every coin two of its members disagree about, which is what makes it a linear code, and the count of heads in the sparsest of them is the fewest coin turns that separate two lost positions.

    The losing positions are a code

    Turn over one, two or three coins, and the rows a player has already lost turn out to be closed under adding two of them together. That makes them a linear code — and on eight coins it is the extended Hamming code exactly, sixteen words with a weight enumerator of 1 + 14x⁴ + x⁸, produced by a move rule that knows nothing about codes.

    part 1 · impartial
  2. Mock Turtles on 8 coins: finding the move is decoding. Every row of the game, sorted by what it takes to win from it. The lost rows are the codewords; a won row is a codeword with errors, and the winning move is the error pattern that turns them off. The distance column is a fact about the code and the coins column is a fact about the rules, and the two do not quite agree.

    The code names the move

    If the lost rows of a coin-turning game are a linear code, then a won row is a codeword with errors in it and the winning move is whatever turns the errors off. Over all 256 rows of Mock Turtles on eight coins: 16 codewords, 240 won rows, none more than two coins from a lost one — and 64 of them whose cheapest winning move has to turn three coins anyway.

    part 2 · impartial
  3. The dual is the value table's span. The dual code against the span of the bit-planes of the one-coin Grundy values, on every game measured.

    The dual was the value table

    A coin-turning game's losing rows form a linear code, and a code has a dual that nothing in the game appeared to read. It reads it constantly: the dual is spanned by the bit-planes of the Grundy values — the parity checks are the value table stood on end — and on Mock Turtles over eight coins the losing rows are exactly the span of the table that decides them.

    part 3 · impartial

All series