Sprague-Grundy Values of Octal-Games

Introduction

These are special cases of Nim Games --- the so called Take-and-Break Games.
Given a heap of size n and two players who alternately have to make a move. On each turn a player must decrease the heapsize by a certain number and divide it possibly into several smaller heaps. The player who can't make a legal move, loses. Hence a heap of size 0 ist always lost and gets value G(0)=0. The rule is coding into an digit-string of the form d₀.d₁d₂d₃... where the i-th digit d_iindicates in how many non-empty heaps the chosen heap must be broken if its size was decreased by i.The digit d_i is interpretated as a binary-value, containg the two-power 2^k if and only if the heap is allowed to be divided into k non-empty heaps. Octal-Games are a subset of these games, where both players has the same move options and are restricted at each move to dividing a heap into at most two parts, hence restricting any digit d_i to be atmost 1+2+4 < 8.
Generally a heap of size n has the value G(n) = min{ N₀ \ {successor_positions} }.
The set of these Spargue-Grundy-Values G(n) can be divided into a sparse set and its complement, called the common set. Values of the sparse set occur extremly rare, mostly only finite often. If these sparse values die out the infinte sequence of the G(n) must become periodic.
A value G(n) belongs to the sparse set if and only if parity( G(n) AND m) = 0 for a fixed game specific bitstring m.

Until 1982 Open Octal-Games with at most 3 digits

Game     bitstring      sparse      last   max n  max G       index     deep     period  preperiod value
--------------------------------------------------------------------------------------------------------
Grundy's 01111111111...   1284  48399022   5*2^32   297 21544358589  50248198         ?
.6       01110111111...   1584     20627    2^29    325    19739543    800268         ?
.06               ?                         2^20   3971     1007558          
.14      00111111111...   1896    178727    2^26     84    29317530    199686         
.16      01111111111...     53     13935     -       23      229790     21577    149459     105350    16
.36      01111111111...    516     11798    2^30    207  1001950698     13451
.56      11011011111...     46      1795     -       64       22778      1564       144     326639    26
.64      01111101111...    488    156751    2^29    256        3833    124709?
.74      11011011111...   1386     15929    2^24    470    10804722     46327 
.76   ?? 00000001100... 192318              2^20  10337     1005578
.004     00011111111... 156316   1048574    2^20   3141      901645
.005              ?                         2^20   1024      928227 
.006              ?                         2^20   4096      902301 
.007     00011101111...  22476   5029983    2^25   1401     6193903                   ?  
.016     00101111111...  21345   1331888    2^21   1029     1194023
.104      no sparse          -         -    2^20     27      327725 
.106      no sparse          -         -    2^20     27       52692 
.114     11111111011...  60453   1047543    2^20   1326      775984 
.127     11111111111...   2805     39511     -       56       24734     11396         4      46577    11
.135              ?                         2^20   3306     1034439
.136              ?                         2^20   3619      926278
.142      no sparse          -         -    2^20    409      465343
.143     10111111111...   9417   2561883    2^22     95     4096633   1510328
.146     10101111111...   5817    307166    2^21   1387     1028448    184944
.162              ?                         2^20   3600     1044206
.163              ?                         2^20   2154     1037986               CONTINIOUSLY INCREASING
.172     10110011111...   2352     51381    2^25    349     1901671     68816
.324              ?                         2^20     94      828428
.336     00111111111...    223     53899    2^30     88   630289010    150327
.342              ?                         2^20   3173      972043
.362     00111111111...    529     43110    2^28    128     8392915    184271
.371              ?                         2^20   2627     1033504
.374     01111111111...    246      2354    2^30    224   964461549      5049?
.376     01111111111...    510   1140540     -      176      341612    505866         4    2268247    42
.404     11011010111...    369      8024    2^27    259     2271405   1217231 
.414              ?                         2^20  14388     1011295
.416     10101111111...   1014     10965    2^25    712    27273329      9563
.444     11011111111...    364  72416309    2^29    208    90173476     33.6*
.454     10111111111...     17       124     -       41    14456117      4858  60620715  160949018    16
.564     01100111111...   1687     13275    2^23   1417     6951471     11470
.604              ?                         2^20  10415     1018198
.606     01111111111...  17281   2093126    2^21   1024      635867
.644     01111111111...     31       511     -       64         333       604       442       3255
.744     00110111111...    876     11268    2^25    702    24352816     28352
.764     01110011111...  12078    941007    2^20   4907      475149    505419
.774     01011111111...    352      3519    2^28    257        3285      4413
.776     10011110111...    503      7348    2^26    296        5487      4838

legend:

Game name of the game
bitstring bit-mask for sparse space
sparse no of sparse values found
last highest sparse index
max n maximum search n
max G maximal found value
index index of found maximum
deep maximal back-track deep for verification
period minimal period (if known)
preperiod minimal preperiod (if known)
value last exceptional value

Reference: E.R. Berlekamp, J.H. Conway, and R.K. Guy, Winning Ways -- for Your mathematical Plays, Vol.1, Chap. 4, Academic Press 1982.
Further Links: Combinatorial Game Theory

Achim Flammenkamp
2000-12-31