Octal games: codes, nim-values and eventual periodicity
DefinitionOctalGames_CodeAn octal game is an impartial heap game in which a move removes some tokens from one heap and optionally splits what remains into two heaps. Its rules are given by an octal code with digits . Write with . For a heap of tokens:
- if and , the whole heap may be removed, leaving no heap;
- if and , one may remove tokens and leave a single heap of tokens;
- if , one may remove tokens and split the rest into two nonempty heaps of sizes with .
Digits beyond are . The nim-value of a heap of tokens is defined by the mex rule:
where is the least natural number not in and is bitwise exclusive or. The sequence is eventually periodic if there are and with for all .
For example, Kayles is , Dawson's Kayles is , and Nim is . By the Sprague–Grundy theorem, determines the outcome of every sum of heaps, so these definitions are the basis for stating periodicity results about octal games.
Formalization Note The code is a finite list of elements of Fin 8. The values are computed by a table built by structural recursion, so the definition is executable; the first 84 values of Kayles agree with Siegel's Figure 2.3. Rule 3 with (bit of ) splits a heap without removing tokens, as in Siegel's convention. Bits of are ignored: they would describe no move, or a move from a heap to itself.
import Mathlib
namespace OctalGames
/-- A finite octal code `d₀.d₁d₂…d_k` (Siegel, *Combinatorial Game Theory*, §IV.2),
given by its list of digits `[d₀, d₁, …, d_k]`, each in `{0,…,7}`. -/
structure Code where
digits : List (Fin 8)
/-- The `i`-th digit `dᵢ` of the code, as a natural number; `0` beyond the end of the list. -/
def Code.digit (c : Code) (i : ℕ) : ℕ :=
((c.digits[i]?).map Fin.val).getD 0
/-- Bit `j` of the digit `dᵢ` (`dᵢ = e₀ + 2e₁ + 4e₂`). -/
def Code.bit (c : Code) (i j : ℕ) : Bool :=
(c.digit i).testBit j
/-- The minimal excludant: the least natural number not in `s`. -/
def mex (s : Finset ℕ) : ℕ :=
Nat.find (Infinite.exists_notMem_finset s)
/-- The nim-values of the options of a heap of size `n`, given the nim-values `g m` of smaller heaps.
Removing `i ≥ 1` tokens and leaving no heap (`i = n`) is allowed when `e₀(dᵢ) = 1`; removing `i ≥ 1`
tokens and leaving one nonempty heap of size `n - i` is allowed when `e₁(dᵢ) = 1`; removing `i ≥ 0`
tokens and leaving two nonempty heaps of sizes `a, b` with `a + b = n - i` is allowed when
`e₂(dᵢ) = 1`. (The bits `e₀, e₁` of `d₀` describe no legal move.) Only values `g m` with `m < n` are used. -/
def optionValues (c : Code) (g : ℕ → ℕ) (n : ℕ) : Finset ℕ :=
(if 1 ≤ n ∧ c.bit n 0 then {0} else ∅) ∪
((Finset.Ico 1 n).filter (fun i => c.bit i 1)).image (fun i => g (n - i)) ∪
((Finset.Ico 1 n ×ˢ Finset.Ico 1 n).filter
(fun ab => ab.1 + ab.2 ≤ n ∧ c.bit (n - (ab.1 + ab.2)) 2)).image (fun ab => g ab.1 ^^^ g ab.2)
/-- The table `[𝒢(0), 𝒢(1), …, 𝒢(n-1)]` of nim-values of heaps, built by the mex rule. -/
def table (c : Code) : ℕ → List ℕ
| 0 => []
| n + 1 => let t := table c n; t ++ [mex (optionValues c (fun m => t.getD m 0) n)]
/-- The nim-value `𝒢(n)` of a heap of `n` tokens in the octal game with code `c`. -/
def grundy (c : Code) (n : ℕ) : ℕ :=
(table c (n + 1)).getD n 0
/-- The nim-sequence is eventually periodic: there are `n₀` and `p > 0` with
`𝒢(n + p) = 𝒢(n)` for all `n ≥ n₀`. -/
def EventuallyPeriodic (c : Code) : Prop :=
∃ n₀ p : ℕ, 0 < p ∧ ∀ n, n₀ ≤ n → grundy c (n + p) = grundy c n
end OctalGames