Sprague-Grundy Values of Octal-Games

Introduction

Nontrivial Octal-Games with at most 3 digits

legend:

Game

name of the game

sgv-sequence

the sequence of the G-values starting from size n=0

type

kind of sparse space phenomenon: 0 = in range / 1 = in domain (sparse-position-space)

bitstring

bit-mask describing the sparse space

rare

number of known rare values / size of sparse set

last

largest known index of a rare value

max n

maximum searched n

max G

maximal found value g(n)

index

index of known maximum

lost

nunber of known lost values (g(n)=0)

depth

maximal number of last values for computing next value

period

minimal period (length)

preperiod

minimal preperiod (length)

except

last exceptional value

miss

number of values in the preperiod not covered by the period values

auto

shift < period length of maximal autocorrelation of the sg-sequence

correl

maximal autocorrelation coefficient (shift is given by auto)

length

length/depth (<= last+t) of the MEX-shift register to simulate the game after the last rare value has occured

Nontrivial Octal-Games with known Structur

To prove a period length p of such a game computationally, it is sufficient to verify the equation G(i+p) = G(i) only for t+ max { last, depth } many successive sg-values with t the largest index of a non-zero digit of the game's name (in the case of a sparse position space p should be even).
There are still 8 and 55 unsettled 2-digit- respectively 3-digit-octal games (and Grundy's Game and 0.6111...).

Remark: if there are only finitely many rare values, the game will become ultimatively periodic. For a given octal game, let a denote the number of digits which allows a take remaing still something, i.e. the number of digits containing 2, and let b denote the number of digits which allows a break in two heaps, i.e. the number of digits containg 4. Each rare value can prohibit a common value. Thus if all the, say s, rare values cover different (and the smallest) common values for all the move options, then at last the a+s*b+1 common value must be the sg-value. For a given mask m having the unique 1-complement representation 2^n-1(2k-1)+1with n,k positive integers, there are at most 2ⁿ successive rare respectivley common values (n-1 is the number of successive lowest 0-bits in m). So we get a quantitive upper bound for the maximal occuring sg-value. Thus, the mex-rule can be considered as a shift-register of length largest rare index + t and its sum of period length and preperiod length must be bounded by (a+s*b+1)^last+t.

Corrections in Winning Ways Chapter 4

• Officers (.6): G(10344)=256
  
• Sparse Space Spells Speed (column .000007): G(15857)= 512
  
• Sparse Space Spells Speed (column .000007): ...1101011110
  
• Sparse Space Spells Speed (new column .007): ...1110111000
  

Further informations on the 0.00...007 games

References