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. Generally a heap of size n has the value G(n) = min{ N0 \ Uj G(successor_positionj) } with j indicating all possible successor_positions.
The rule of these Take-and-Break Games is coded into a digit-string of the form d0.d1d2d3... where the i-th digit diindicates in how many non-empty heaps the chosen heap must be broken if its size was decreased by i.The digit di is interpretated as a binary-value, containing the two-power 2k if and only if the heap is allowed to be divided into k non-empty heaps. Of course d0 never contains 1 or 2. 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 di to be atmost 1+2+4 < 8.
In the case of the range type (0) of the sparse space phenomenon, the set of these Sprague-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 rare values die out then the infinte sequence of the G(n) must become periodic. A value G(n) belongs to the sparse set (in the range) if and only if population_count( G(n) AND m) AND 1 = 0 for a fixed game specific bitstring m.

A compendium of all 2 and 3 place octal games to find or match the missing ones.
And a listing of these 'normalized' octal games with 2 or 3 places.

Nontrivial Octal-Games with at most 3 places


Game sgv-sequence type bitstring rare last max n max G index lost depth period preperiod except
.60012012312340342... 0 0111011111111... 1584 20627 233 363 7775706554 14 1008823
.040000111220331110... 0 0001110111111... 22476 5029984 228 1689 248902928 38 5218954
.060001122031122334... 0 ? 224 22097 16360327 37
.140100102122104144... 0 0011111111111... 1896 178727 232 85 1839780623 172 576735
.160100122140142140... 0 0111111111111... 53 13935 - 23 229790 7 21577 149459 105351 16
.360102102132132430... 0 0111111111111... 516 11798 234 208 1762187846 14 17168
.370120123123403421... 0 0111011111111... 1583 20626 233 363 7775706553 13 1008822
.450011223114432211... 0 1111111111111... 11 198 - 8 37 2 37 20 498 8
.560102241132446621... 0 1101101111111... 46 1795 - 64 22778 2 7405 144 326640 26
.640012341532154268... 0 0111110111111... 488 156751 233 262 1911635806 2 470403814
.740101232414623215... 0 1101101111111... 1386 15929 231 512 76103606 2 137102
.760102341623416732... 0 0000000110011... 219248 5208068 224 16814 4995486 2
.0040000011112220333... 0 0001111111111... 184854 15869181 225 6063 22057995 32
.0050001011222033411... 1 1110101001011... 95660 67070800 226 1059 3022366 -
.0060000111222033111... 0 0000000101111... 470413 16772624 224 6532 4798522 40
.0070001112203311104... 0 0001110111111... 22476 5029983 228 1689 248902927 37 5218954
.0140010010122123401... 0 0111111111111... 2037 64126 231 365 169860345 13 126438
.0150011010212230142... 0 0111111111111... 237 11973 235 101 2350397235 7 27036
.0160010122201014422... 0 0010111111111... 21439 102335997 227 1093 102705419 18 41416941
.0240001122304112532... 0 ? 225 12371 30810166 26
.0260001122304112533... 0 ? 225 37903 33220674 27
.0340011022314014312... 0 1111111111111... 1079 374473 234 256 26376 10 596840
.0540010122234411163... 0 1011111111111... 38 796 - 41 33671802 3 16284 10015179 193235616 18
.0550011122231114443... 0 1111111111111... 6 43 - 8 51 2 20 148 259 2
.0640001122334115533... 0 0111111111111... 6795 528569986 229 523 275511554 3 28677643
.1040100010221224104... 1 1110111111111... 20 284 - 29 186892397 - 4178 11770282 197769598 9
.1060100012221440106... 1 1011011111111... 15 1103 - 31 1937780317 - 15343 328226140474 465384263797 25
.1140110011202120411... 0 1111111101111... 100891 33547932 225 1610 20501458 11
.1250102110213011302... 0 ? 224 44496 16775217 145
.1260100213321042503... 1 0111001110001... 20444 102973539 228 2222 265978 - 40637003
.1270102210441220144... 1 1000001111111... 693 27106 - 56 24734 1190 13551 4 46578 11
.1350112011203110312... 0 ? 224 27960 16768149 91
.1360110021302110223... 0 ? 224 25272 15750407 40
.1420100222110332410... 1 1100011101111... 1357 117323 234 441 17142768844 - 411815
.1430101222010422150... 0 1011111111111... 9417 2561883 227 148 26789789 13 3047015
.1460100222411133244... 0 1010111111111... 5817 307166 229 1521 200428954 3 324505
.1560110222441113224... 0 1101111111111... 15 357 - 23 1032 2 243 349 3479 8
.1620100223110422610... 0 ? 224 41410 16639694 44
.1630102231042261042... 0 0001110111111... 2800497 33553435 225 39456 33326322 417
.1640100122344511632... 0 0000011001111... 333812 16657862 224 20543 3402756 3
.1650102132134436231... 0 1101111111111... (17#+87) - - 25 620 2 2597 1550 5181 4
.1660100223411662244... 0 1011111111111... 176 4281 234 173 3561617983 3 12850
.1670102234116224411... 0 1011111111111... 60 1303 237 64 332129728 2 7645
.1720110223011322440... 0 1011001111111... 2352 51381 231 387 2116001133 10 116905
.1740110213221445642... 0 1101111111111... 57 674 239 82 312784191354 2 12547
.2040010120101231212... 1 0101110111111... 2245 83860 231 445 38455 - 143454
.2050012010123123134... 1 1110010111111... 112 33944004 237 91 3114909246 - 63095619
.2060010123201012323... 0 0011011111111... 10339 5668113 229 803 191546903 19 9861529
.2070012120301245312... 1 0110100111111... 154 433920 236 126 60119768867 - 776549
.2240012012312314304... 0 0000001111111... 1620812 224 25035 16678174 26
.2440010123234515673... 0 1000111111111... 65367 7596617 225 6654 9117412 3 6830617
.2450012123451567321... 0 0101111111111... 151 1352 235 142 10549340935 2 40663
.2640012345163251867... 0 1001111111111... 1992 46544 231 946 488110831 2 205974
.3140120120212312453... 0 0000011111111... 180146 16216527 225 3105 4636848 56 7063960
.3240102130134023421... 1 1110010111111... 126 129608 237 109 7776114395 - 386895
.3340120120312312435... 0 0000100101111... 2781793 224 22528 15585922 47
.3360120312403120341... 0 0011111111111... 223 53899 234 90 4591503605 14 169971
.3420101232010323450... 0 ? 224 19797 16777215 68
.3440101232451462321... 0 0011111111111... 8679 313574 228 1347 1158568 2 307675
.3460101232451672321... 0 ? 224 76376 16123562 2
.3540120124312352435... 0 1111110111111... 132 3227 - 113 1152 2 705 1180 10061916 44
.3560120212451675128... 0 1101111111111... 7 43 - 19 86 2 19 142 7315 2
.3620102341023415237... 0 0011111111111... 529 43110 234 131 1614638854 11 239495
.3640102132134534231... 0 1111011111111... 977 13573224 233 564 6784 2 94736011
.3660102345162345768... 0 0111111111111... 827 643528 232 533 609293376 2 1115356
.3710123103240234012... 0 0000001110111... 1480278 224 16408 16191950 42
.3740120124312352435... 0 0111111111111... 246 2354 235 230 19481269639 2 6861
.3760120312435243514... 0 0111111111111... 510 1140540 - 176 341612 2 505866 4 2268248 42
.4040001122334115633... 0 1101101011111... 369 8024 234 263 5398126274 7 4621382
.4140011022344011322... 0 ? 224 114502 15435401 21
.4160011223411663221... 0 1010111111111... 1014 10965 233 726 8167109156 3 11367
.4440001122334115633... 0 1101111111111... 364 72416309 234 212 4139813739 3 170177024
.4540011223411663221... 0 1011111111111... 17 124 - 41 14456117 2 4858 60620715 160949019 16
.5640102244113254768... 0 0110011111111... 1687 13275 231 1459 139723698 2 18757
.6040012012312345345... 0 ? 224 102404 16775619 15
.6060012340123451234... 0 0111111111111... 41738 33451663 225 1031 9556435 18 9556435
.644001234516325896a... 0 0111111111111... 31 511 - 64 333 2 604 442 3256 32
.7440101232451672321... 0 0011011111111... 876 11268 232 733 382560700 2 43665
.7640102345162345768... 0 0111001111111... 12078 941007 225 4978 21751262 2 1221585
.7740123145671328954... 0 0101111111111... 352 3519 234 257 3285 1 25238
.7760123416321674581... 0 1001111011111... 503 7348 234 296 5487 1 18381











4.0040010123231454323... 0 0111111111111... 8914 43090760228 1996 20532406 3 23050686
4.0070012123454132825... 0 1111110101111... 2259 186900230 938 47129291 2 240392
4.0260012345613274165... 0 1000111111111... 384929 16773949 224 16817 4081741 2
4.0440010123234541673... 0 0011111111111... 184 1688235 293 17139683973 3 18849
4.0450012123454167828... 0 1111101111111... 34 497237 93 15355901532 2 4155
4.0640012345613285764... 0 1101011111111... 52 470 - 111 19114 2 420 16132 94272 45
4.3240120312435241352... 0 1110110111111... 271 5956 235 256 654707 2 19904
4.3270124312435213524... 0 1111111011111... 7111 1084182228 2247 7409767 1 1290657
4.344012021246164812a... 0 1110111111111... 14 271 - 35 190 2 164 51 998 4
4.3640120312435243521... 0 0111111111111... (6#+992) - - 33 2141 2 4221 62 11687 14
4.3670124312435213524... 0 0111111111111... 142 3508 236 101 64466228791 1 23739
4.4040012314324523513... 0 0111101111111... 132 1852 - 208 229872163 2 17840 145 6872982644 71
4.4060012345621874598... 0 1101111111111... 23 205 - 50 231573 2 212 44 294097 32











.6111...0012312341321461... 0 1011111111111... 171 2026 236 73 15336888688 2 21401399











Grundy's0001021021021321... 0 0111111111111... 1287 48399022 238 297 21544358589 42 50657340
Couples0001201231234034... 0 0111011111111... 1585 20628 232 335 2135301626 15 1008824

Grundy's Game: the only option is to break any heap (of size greater than 2) into two heaps of different size.
Couples-are-forever: the only option is to break any heap of size greater than 2 into two heaps. It is the shifted variant of officiers (also denoted as .6) and the two-times shifted variant of .37.

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

Game period* preperiod* miss density rare last+t max Gdepthautocorrelsolved
.45 20 498 67 0.134511200 837 1956
.156 349 3479 1919 0.551615360 2324366 0.8367 1967
.055 148 259 129 0.4980646 82028 0.8378 1976
.644 442 3256 2208 0.678131514 64604207 0.7285 1976
.356 142 7315 6419 0.8775746 191926 0.9155 1976
.165 1550 5181 251 0.0484- 252597620 0.9277 1976
.127 4 46578 15622 0.335469327109 5613551- 0.0000 1988-10-??
.56 144 326640 291858 0.8935461797 64740559 0.6042 1988-10-??
.16 149459 105351 3634 0.0345531393723215773 0.9148 1988-10-??
.376 4 2268248 1104157 0.48685101140543 176505866- 0.0000 1988-10-??
.454 60620715 160949019 147240872 0.914817127 41485898 0.3424 2000-12-31
.104 11770282 197769598 163669736 0.827620287 29417812 0.4993 2001-07-01
.106 328226140474 465384263797 151106 3115343152 0.3548 2002-05-21
.054 10015179 193235616170776546 0.883838799 4116284108 0.5809 2002-05-27
.354 1180 100619167912461 0.78641323230 113705193 0.7517 2002-05-28
*the length of the minimal (pre) period is given

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 56 unsettled 2-place- respectively 3-place-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 remaining 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 containing 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 2n-1(2k-1)+1with n,k positive integers, there are at most 2n 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

(1st and 2nd edition, german & english):

Further informations on the 0.00...007 games

Game bitstringrarelastmax nmax Gindexlost
.017 ----986*
.027 00011101111111...224765029983228168924890292737
.037 00011111111111...18483778971432235774292528231
.047 ?> 2796000 22316390832582029
.057 01111010111111...805259651422613065516970521
.06700010011111111...349058242860223868811037420
.077?01111110111101...> 2422056 22311268825465123
.08701111111111111...4196136991742266285588109921
.09701111111111111...1594278631522514631205174223
.010701111101111111...> 615153838685322311777762550225
.011701111111011111...17898877752022232187292636824
.012701111111111111...91442581842269453488685026
.013701111110111111...18418334592532259792682440727
.014701111111011111...8954602415022612162795519128
.015701111111001111...27946083885612236020815873329
.0167?> 2690000 22310250804441030
.017701111111111111...5498183804372232226438421130
.018701111111111111...1552148388224223244084556831
.019701111111111111...4243046091072232876125305133
.020700000000111011...> 946372 22311164820306434
.021701111101101111...26367583873202234104750794734
.022701111111111111...6380321268332234096416005137
.023701111111101011...> 721581838860522312359762235337
.0247?> 2068425 22310951835069637
.025701111111111111... 14803277728702234114508794538

References

Richard K. Guy and Cedric B. Smith, The G-values of various games, Proc. Cambr. Philo. Soc. V 52 (1959), pp. 514-526.
Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways -- for Your mathematical Plays, Vol. 1, Chap. 4, Academic Press 1982.
Anil Gangoli and Thane Plambeck, A Note on Periodicity in Some Octal Games, International Journal of Game Theory V 18 (1989), pp. 311-320.
Richard K. Guy, Unsolved Problems in Combinatorial Games, pp. 475-491, in Games of No Chance, ed. R. Nowakowski, MSRI Publications Vol. 29, 1996
Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways -- for Your mathematical Plays (2nd edition), Vol. 1, Chap. 4, A.K. Peters, 2001.
Combinatorial Game Theory
Listing of these at most 3-place Octal Games sorted by size of sparse space
Listing of these at most 3-place Octal Games sorted by largest index of a rare value
Listing of these at most 3-place Octal Games sorted by maximal size of nim-value
Listing of these at most 3-place Octal Games sorted by index of maximal nim-value
Study the increase of the maximum as n climbs
Listing of these 3-place Octal Games sorted by size of sparse position space



URL created 2000-12-??
last updated 2012-11-30 16:35 UTC+1
Achim Flammenkamp