Octal games Kayles & friends

Rows of pins. On your turn knock down a block of adjacent pins in one row, as the game's code allows; a gap in a row splits it in two. Whoever cannot move loses. The computer plays perfectly by Sprague–Grundy theory: every row of n pins is worth a nimber G(n), and a position is lost for the side to move exactly when the nim-sum of its rows is 0. With hints on, the winning moves are listed and lit up.

game code rows you move hints

winning moves

Grundy values of this game

every octal game with at most three digits

The code

An octal game is written d₀.d₁d₂d₃… Digit d_k says what may remain after taking k pins from one row: add 1 if the row may vanish, 2 if one row may remain, 4 if two rows may remain (the pins were taken from the middle). Kayles is 0.77: take one or two adjacent pins from anywhere. Dawson's Kayles is 0.07: always take exactly two. A leading 4 lets a move split a row without taking anything.

Periods, and how they are proved

The Grundy values of every octal game with finitely many digits that has ever been settled turned out to be eventually periodic: after a preperiod of v values they repeat with period p. Kayles has p = 12 and v = 71. A finite computation can prove this, by the Guy–Smith periodicity theorem: if G(n + p) = G(n) for every n from v up to 2v + p + t (with t the number of digits), it holds for all larger n too, because every option of a long row has a long part that the period already covers. This page computes the values, finds the smallest period that the theorem proves from them, and compares it with Achim Flammenkamp's tables. Many three-digit games, among them Officers (0.6) and 0.04, are still open: no period has been found in billions of values.