quaternary game 0.3102

>> plambeck.org >> mathematics >> combinatorial games >> misère octal games >> 0.3102
































Stalking the Wild Quaternary Game 0.3102

I (Thane Plambeck) will pay US $500 for a complete analysis of the following impartial game, which (for lack of a better term), I'll call the WILD QUATERNARY GAME.

The game is played with an arbitrary number of variously-sized heaps of beans. There are two players. They take turns making legal moves.

There are three types of legal moves:

1) Remove a single bean from any heap.
2) Remove an entire heap consisting of exactly two beans.
3) Remove four beans from a heap, but only if the heap contains more than 4 beans.

The person who makes the last legal move loses the game.

In the Winning Ways "octal code" notation, this is the misère game .3102.

By a "complete analysis," I mean an explicit closed-form mathematical description of the first- or second-player winning positions of the game (ie, solutions that boil down to a recursive search of the game tree won't claim the reward).

Here's an example of such a solution. Suppose I had changed the problem statement so that the last player to make a legal move *wins* the game (ie, "Normal play"). In that case, a complete description of the second-player winning positions in best play is

All positions with
a) An even number of heaps of size (5k+1 or 5k+4) AND
b) An even number of heaps of size (5k+2).

There's more information on WILD QUATERNARY below, which I'll contribute to get things started. Here's some background on other misère quaternary games, and their solutions. This draft paper may prove of interest, too.

On the other hand, none of that may be useful—I don't know!

Normal Play

The 0.3102 nim sequence is periodic of length 5—the values in final row of the table repeat themselves indefinitely.


                                  1  2  3  4  5  
                                  -------------
                              0+  1  2  0  1  0
                              5+  1  2  0  1  0
                              10+ 1  2 ...

		      Table 1: The nim sequence of .3102
Misère Play

The single heap genus sequence is periodic of length 5, starting at heap 7:

1031 220 002 113 020
102 213 002 113 020
102 213 002 113 020
102 213 002 ...

Table 2: Genera for .3102


Friskies

We're interested in positions whose outcomes differ in normal vs misère play. We call them frisky.

One heap friskies

A glance at the Table 2 above reveals that the one-heap friskies are exactly those of the form 5k or 5k+1.

Two heap friskies

Table 3 plots two heap frisky positions x + y.


Table 3. Two heap friskies in .3102