Extending the table for one unsolved take-away game to four times its published length

The game is played with heaps of counters. On your turn you take exactly three counters from one heap, and you may then split what is left of that heap into two heaps. (A heap of exactly three can be taken whole.) The player who cannot move loses. The name 0.007 is a code: the digit in the k-th place after the point says what you may do when you take k counters, adding 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. Only the third digit is non-zero here, and 7 = 1 + 2 + 4, so taking three is the only move and all three options are allowed. Played on a strip of squares, the same game is Treblecross: players take turns putting an X in an empty square, and the first to complete three in a row wins.

Every heap size has a nim value: the smallest whole number that is not the value of any position you can move to. A position made of several heaps is lost for the player to move exactly when the heaps' values combine to 0 under nim addition (adding in binary without carrying). So a table of nim values, heap size by heap size, is a complete guide to playing the game, as far as the table goes.

Richard Guy conjectured that in every game of this kind the list of 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: Guy and Smith showed in 1956 that a long enough stretch of repeating values guarantees the repetition goes on forever. How long is long enough depends on the largest number of counters a move may take. For 0.007, where that number is three, it means: if the values repeat with a cycle of length p from some heap size n onward, and this has been checked up to heap size 2n + p + 2, they repeat forever. What no table can show is the opposite, that a game never repeats. For 0.007 no repeating cycle has turned up yet.

Achim Flammenkamp, who keeps the reference tables for these games, sorts each game's values into two classes with a fixed binary test. For 0.007, a value is rare when a certain set of its binary digits contains an even number of 1s. Values in that class turn up only rarely; the others are called common. His page notes that if the rare values stop for good, the values must eventually repeat. The reason is that, once no more rare values come, each new value depends on a fixed-length stretch of earlier ones and can take only a limited range of values, so the sequence can only be in finitely many states and has to cycle. That is why the thing to watch in a longer table is whether new rare values turn up.

An AI agent wrote the program under a rule I set: no new value counted until the run had reproduced everything the old table recorded. That meant the largest value and where it sits; how many heap sizes have value 0 and where the last one is; the same two numbers for the rare values; and, for each value that is a power of two (1, 2, 4, 8 and so on), the first heap size that has it. All of it matched.

The last rare value is still the one at heap size 5,029,983^▲, far inside the old table. None appeared anywhere from about 268 million to about 1.07 billion, and the largest value stayed at 1,689. That is evidence that the rare values may have stopped for good, which would make the game eventually repeat. It is not a proof, because a rare value could still appear further out.

Flammenkamp reviewed the code and reran the old table's range with his own program, getting the same numbers. He then took the game to about 2.1 billion heap sizes. His run found the same count of rare values and the same largest value, which also covers my range, though we compared those summary numbers rather than every value. The furthest values for this game are now his. The other games from the same July work are on the results page for that work.

0.007 is Treblecross. The computation is a checkpointed sparse-space computation in the style of the reference tables. It computed every value from heap size 0 to 2^30^▲, which includes the prior bound of 2^28. It was required to reproduce the published invariants at the prior bound, and it was cross-checked against a naive quadratic enumerator on the initial segment. Past the prior bound there is no rare value beyond the last known one, and the maximum is unchanged.

Rare values are the sparse-space class in Flammenkamp's sense: G(n) is rare when popcount(G(n) AND m) is even for the game's bitstring m. If the rare values die out, the mex computation becomes a bounded shift register over bounded values, so the sequence is ultimately periodic. No period has been detected, so the octal periodicity test (Guy and Smith, 1956: G(n + p) = G(n) for n0 ≤ n ≤ 2n0 + p + 2 implies ultimate periodicity for a three-digit code) does not yet apply. The extended table moves the point from which any future periodicity argument for 0.007 has to start.

The published artifacts are the full table as a binary file with a recorded checksum, the list of rare-value pairs as the compact citable table, the run log, and a one-line reproduce command. Flammenkamp reviewed the solver source, reproduced the 2^28 range with his own program, and later doubled the range for this game on his own hardware, with the rare count and the maximum unchanged.