Combinatorial Game Theory
who wins, and by how much
Generator

Three rules, three patterns nobody put there

Three rules, three patterns nobody put there
Three rules, three patterns nobody put there. The value of a lone head at each place, for three coin-turning games whose rules differ by a few words. One gives the counting numbers, one the odious numbers — those with an odd number of ones in binary — and one the ruler function, the tick heights on an imperial ruler. Every value is a mex over the moves; none of the three patterns appears anywhere in the rules.

The value of a lone head at each place, for three coin-turning games whose rules differ by a few words. One gives the counting numbers, one the odious numbers — those with an odd number of ones in binary — and one the ruler function, the tick heights on an imperial ruler. Every value is a mex over the moves; none of the three patterns appears anywhere in the rules.

3 essays call coin-values. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

Where it is called

Changing this generator changes every one of these figures.

Turning Turtles: a row of 12 coins. A row of coins, some heads and some tails. A move turns some of them over, and the rightmost coin turned must go from heads to tails — which is what makes the game end. The number under each place is what a lone head there is worth, and the row is worth the exclusive or of the places showing heads. Impartial games

A row of coins is already a sum

Everywhere else on this site a sum is several positions side by side. In a coin-turning game it is one row — each coin showing heads is a game in its own right, and the row is worth the exclusive or of them. The decomposition is inside a single picture.

 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. Impartial games

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.

 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. Impartial games

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.

The whole library · The position index · The figures that play back