Extending an expert's tables for unsolved take-away games in a way he could check himself

In a take-away game, two players take turns removing counters from heaps, and the player who cannot move loses. Each game is named by a short code such as 0.007, in which the digit in the k-th place after the point says what you may do when you take k counters: add 1 if you may take a whole heap of that size, 2 if you may leave the rest as one heap, and 4 if you may split the rest into two. Mathematicians call these octal games because each digit is at most 7. Every heap size has a number called its nim value, which tells you how to play it. A value of 0, for example, means the player whose turn it is will lose against perfect play.

Richard Guy conjectured decades ago that in every game of this kind the list of nim values eventually repeats in a cycle. If it does, the game is solved, because a finite table then gives the value of every heap size. A finite table can prove this: by a theorem of Guy and Smith from 1956, once the values have repeated for long enough (a little more than twice the point where the cycle starts, plus one cycle), they repeat forever, and many games have been solved that way. What no table can show is that a game never repeats. None of the games here has started repeating yet, so people compute further and watch what the values do.

The values to watch are the rare values. Flammenkamp sorts each game's values into two classes with a fixed test on their binary digits, and one class turns up only rarely. His page notes that if a game's rare values stop for good, its values must eventually repeat. So the main question for each longer table is whether new rare values turned up past the old limit. (The page on game 0.007 explains the test and the reason in more detail.)

The largest run, for 0.007, took its table from about 268 million heap sizes to about 1.07 billion. In eight of the games, no new rare values appeared anywhere in the extended range, which fits with those games eventually repeating but does not prove it. Four games did turn up new heap sizes with rare values, so in those four the rare values had not stopped by the end of the new tables. That does not show they never repeat; it shows the end, if there is one, is further out.

• Game 0.114 had 185,576, with values from 160 to 1,021, lower than in the other three.
• Game 0.606 had 8,162^▲, with values packed into the narrow band from 1,026 to 1,069. I can't explain the band and have asked Flammenkamp about it.
• Game 0.006 had 2,932, with values spread from 1,537 to 4,605.
• Game 0.314 had exactly 1, at a heap size of about 131 million; its previous rare value was at about 40 million.

The old and new limits for each game are on the results page for this work.

Before any run computed new values, it had to reproduce the published tables exactly, not approximately. The published tables list several statistics at their limit, and every one of them had to match before a run could continue. Two further steps made it safe to leave the long runs unattended: the runs saved their progress with checksums, and before launch I confirmed that a run that is stopped and resumed gives bit-identical output. At the end, every new rare value was recomputed by separately written code, so that no number depended on a single program. The full list of checks, in the order they ran, is on the results page for this work. The same approach fits any project that extends someone else's published computation.

These are octal games from Guy's list of unsolved problems; the open question for each is Guy's conjecture that its nim-sequence (its sequence of Sprague-Grundy values) is ultimately periodic. Periodicity, when it holds, is provable by finite computation (Guy and Smith, 1956: G(n + p) = G(n) for n0 ≤ n ≤ 2n0 + p + k − 1, with k the number of code digits); no table can establish aperiodicity. Rare values are Flammenkamp's sparse-space class, and if they die out the sequence is ultimately periodic. Most of the games show no new rare values anywhere in their extensions. The remaining four differ from each other: one has many new rare positions with small values, one has new rare positions with values in a tight high band, one has them scattered over a wide range, and one has a single new rare position far out. I have no explanation for the tight band and have asked Flammenkamp. Every run first reproduced every published invariant at the prior bound, including the zero counts, and only then extended. Afterwards, a from-scratch recomputation gave byte-identical output. The per-game counts and value ranges, stated as new rare positions whose values lie in a range, are on the results page for this work.