[hupfginj] Nim

Nim, the game of heaps of coins, is a solved game.  Here is how to compute the nim sum (Grundy value) of a nim position in Haskell.

nimsum :: [Integer] -> Integer;
nimsum = Data.List.foldl' Data.Bits.xor 0;

(It's might be surprising that Integer is an instance of Bits, but we will just run with it.)

If the nim sum of a position is zero, then the position is lost: any move loses (and makes the nim sum nonzero).  If the nim sum is nonzero, the position can be won: choose a move that reduces the nim sum to zero.  (What is the computational complexity of finding such a move?  Typically, how many winning moves are there?  Below, we will give some positions with more than one winning move.)

Important details omitted: if the nim sum is nonzero, there always exists a move that makes it zero.  If the nim sum is zero, there are no moves that keep it zero.

Call a nim position obviously lost if the following mirroring strategy is applicable.  The heaps can be organized into pairs of equal-sized heaps.  Whatever the first player does to one heap of a pair, the second player can do to the corresponding other heap of the pair and thereby eventually win.

All 2-heap nim positions that are lost are obviously lost.  In other words, the lost 2-heap nim positions are exactly those which have 2 equal sized heaps.

Call a position non-obviously lost if it is lost but not obviously lost.

The simplest non-obviously lost position is [1,2,3].

The positions [1,3,3] [2,2,3] [2,3,3] are the three simplest winning positions that have more than one winning move.  All can be reduced to [1,2,3] or to [a,a].

Below are the non-obviously lost 3-heap positions whose smallest heap has size 1.  All entries are [1, 2n, 2n+1].

[1,2,3],[1,4,5],[1,6,7],[1,8,9],[1,10,11],[1,12,13],[1,14,15],[1,16,17],[1,18,19],...

Below are the non-obviously lost 3-heap positions whose smallest heap has size 2.  All entries are of the form [2, 4n, 4n+2] or [2, 4n+1, 4n+3].

[2,4,6],[2,5,7],[2,8,10],[2,9,11],[2,12,14],[2,13,15],[2,16,18],[2,17,19],...

Below are the non-obviously lost 3-heap positions whose smallest heap has size 3.  All entries are of the form [3, 4n, 4n+3] or [3, 4n+1, 4n+2].

[3,4,7],[3,5,6],[3,8,11],[3,9,10],[3,12,15],[3,13,14],[3,16,19],[3,17,18],...

With more coins and more heaps, there continue to be patterns, but they are more complicated, so we will not attempt to describe them.

Below are the non-obviously lost 3-heap positions whose smallest heap has size 4.  Pattern involves 8n+k.

[4,8,12],[4,9,13],[4,10,14],[4,11,15],[4,16,20],[4,17,21],[4,18,22],[4,19,23],[4,24,28],[4,25,29],[4,26,30],[4,27,31],[4,32,36],[4,33,37],[4,34,38],[4,35,39],[4,40,44],[4,41,45],[4,42,46],[4,43,47]...

Below are the non-obviously lost 4-heap positions whose largest heap has size at most 15.

[2,3,4,5],[1,3,4,6],[1,2,5,6],[1,2,4,7],[1,3,5,7],[2,3,6,7],[4,5,6,7],[2,3,8,9],[4,5,8,9],[6,7,8,9],[1,3,8,10],[4,6,8,10],[5,7,8,10],[1,2,9,10],[5,6,9,10],[4,7,9,10],[1,2,8,11],[5,6,8,11],[4,7,8,11],[1,3,9,11],[4,6,9,11],[5,7,9,11],[2,3,10,11],[4,5,10,11],[6,7,10,11],[8,9,10,11],[1,5,8,12],[2,6,8,12],[3,7,8,12],[1,4,9,12],[3,6,9,12],[2,7,9,12],[2,4,10,12],[3,5,10,12],[1,7,10,12],[3,4,11,12],[2,5,11,12],[1,6,11,12],[1,4,8,13],[3,6,8,13],[2,7,8,13],[1,5,9,13],[2,6,9,13],[3,7,9,13],[3,4,10,13],[2,5,10,13],[1,6,10,13],[2,4,11,13],[3,5,11,13],[1,7,11,13],[2,3,12,13],[4,5,12,13],[6,7,12,13],[8,9,12,13],[10,11,12,13],[2,4,8,14],[3,5,8,14],[1,7,8,14],[3,4,9,14],[2,5,9,14],[1,6,9,14],[1,5,10,14],[2,6,10,14],[3,7,10,14],[1,4,11,14],[3,6,11,14],[2,7,11,14],[1,3,12,14],[4,6,12,14],[5,7,12,14],[8,10,12,14],[9,11,12,14],[1,2,13,14],[5,6,13,14],[4,7,13,14],[9,10,13,14],[8,11,13,14],[3,4,8,15],[2,5,8,15],[1,6,8,15],[2,4,9,15],[3,5,9,15],[1,7,9,15],[1,4,10,15],[3,6,10,15],[2,7,10,15],[1,5,11,15],[2,6,11,15],[3,7,11,15],[1,2,12,15],[5,6,12,15],[4,7,12,15],[9,10,12,15],[8,11,12,15],[1,3,13,15],[4,6,13,15],[5,7,13,15],[8,10,13,15],[9,11,13,15],[2,3,14,15],[4,5,14,15],[6,7,14,15],[8,9,14,15],[10,11,14,15],[12,13,14,15]

For casual play, let the initial position be a non-obviously lost position.  No move is objectively better than another from a lost position, so this will tend to produce varied games from as early as the first move.  (The first player explores different ways to try to swindle a win.)  [3,4,7] mentioned above is a nice small 3-heap initial position for casual play.  Some nice 4-heap (lost) initial positions that are easy to remember are [2,3,4,5] (14 coins total), [4,5,6,7] (22 coins), and [6,7,8,9] (30 coins).

We propose non-obviously lost initial positions with more heaps that satisfy the following aesthetic constraints: distinct heap sizes, minimize total number of coins, minimize largest heap, maximize smallest heap.  We avoid heaps of equal size in the initial position to make the mirroring strategy somewhat less likely to be usable toward the beginning of the game.  However, equal-sized heaps can easily appear after the first move.

The unique 3-heap satisfying these constraints is [1,2,3] (6 coins).

4-heap: [2,3,4,5] (14 coins).

5-heap: [3,4,6,8,9] (30 coins).

6-heap: [1,2,4,6,8,9] (30 coins).

The perfect triangle 7-heap [1,2,3,4,5,6,7] satisfies the constraints. It has size 28, smaller than the 5 or 6 heaps above.

8-heap: [2,3,4,5,6,7,8,9] (44 coins).

9-heap: [2,3,4,5,7,8,9,10,12] or [2,3,4,5,6,8,9,11,12] (60 coins).

10-heap: [1,2,3,4,5,6,8,9,10,12] (60 coins).

Best 11-heap is another perfect triangle: [1,2,3,4,5,6,7,8,9,10,11] (66 coins).

12-heap: [2,3,4,5,6,7,8,9,10,11,12,13] (90 coins).

13-heap: [1,2,3,4,5,6,7,9,10,12,14,16,17], [1,2,3,4,5,6,7,8,11,12,14,16,17], [1,2,3,4,5,6,7,8,10,13,14,16,17], or [1,2,3,4,5,6,7,8,10,12,15,16,17] (106 coins)

The values of n for which a perfect triangle [1,2,3,...,n] is a lost position: 0 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 67 71 75 79 83 87 91 95 99 ... The values are 4k-1.

There are no non-obviously lost positions with all heaps having the same number of coins.  An even number of identical heaps is obviously lost.  An odd number of identical heaps is won: just take an entire heap to leave your opponent with an even number of identical heaps, a position which is lost.

The following trapezoids (heap sizes of consecutive integers, at least 2 and at most 20 coins in a heap) are non-obviously lost.  It appears the number of heaps must be a multiple of 4, and the smallest heap must have an even number of coins.

[2,3,4,5],[2,3,4,5,6,7,8,9],[2,3,4,5,6,7,8,9,10,11,12,13],[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17],
[4,5,6,7],[4,5,6,7,8,9,10,11],[4,5,6,7,8,9,10,11,12,13,14,15],[4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19],
[6,7,8,9],[6,7,8,9,10,11,12,13],[6,7,8,9,10,11,12,13,14,15,16,17],
[8,9,10,11],[8,9,10,11,12,13,14,15],[8,9,10,11,12,13,14,15,16,17,18,19],
[10,11,12,13],[10,11,12,13,14,15,16,17],
[12,13,14,15],[12,13,14,15,16,17,18,19],
[14,15,16,17],
[16,17,18,19]

Future work: organize positions by their distance from being obviously lost.  (Previously, we analyzed Chomp in this way.)  What other classes of positions can be quickly recognized as lost?  (We noted [1, 2n, 2n+1] above.)

Future work: repeat this analysis for the "subtraction game" in which the number of coins that can be removed in one move is limited (up to k).  Surprisingly, optimal play can be calculated quickly: compute nim sum mod (k+1).