Generalisation of Nim

I'm asking for a general formula/algorithm that can be used in such a game.

There are $n$ piles, with varying number of pebbles. The number of pebbles in each pile is given by an array from $pile[1]$ to $pile[n]$. There is another array called the $validmove[\ ]$ array. It has any number of numbers. For example, we can define $validmove[\ ]=\{1,2,5,7\}$ This array is constant throughout the game. If $0$ is present in $validmove$, it means that an entire pile can be removed, irrespective of the number of pebbles it contains.

2 players play turnwise. On each turn, a player selects a single pile. He may remove any number of pebbles, as long as that number is present in the $validmove$ array. In the current example, suppose we have selected a pile with $13$ stones. The player can now remove $1$, $2$, $5$ or $7$ pebbles from that pile, leaving it with $12$, $11$, $8$ or $6$ pebbles respectively.

The person who removes the last stone wins (or I can specify 'loses' as well, that may require a slightly different algorithm).

If both players play perfectly, who wins?

I couldn't find an algorithm on the net, even though there is a huge Wikipedia page on it, so I thought SE could maintain one for future reference.

• Are you sure this isn't an open problem? – Rand al'Thor May 26 '15 at 8:25
• This problem is cool, but I think the solution won't be that easy. The Nim theory is quite complex (I mean, only for those who know a good bunch of math), its generalization is likely to be a pain. I'll give a try, though... – leoll2 May 26 '15 at 11:36
• If 0 and 1 are not in $validmove[]$, it is possible for there to be no legal moves even though some stones remain. – Julian Rosen May 26 '15 at 14:16

Sprague-Grundy theory gives an algorithm for determining the winning strategy.

First, we need to compute the nimbers of various pile sizes. This is a finite computation if $$validmove[]$$ is finite. We will recursively define an array $$nimber[]$$. To start, define $$nimber[0]=0$$. For $$n\geq 1$$, we define $$nimber[n]=\mathrm{mex}\big\{nimber[n-k]: 1\leq k\in validmove,k\leq n \big\}.$$ Here mex denotes the minimum excluded value, that is, the smallest non-negative integer which is not of the form $$nimber[n-k]$$. This is assuming $$0$$ is not in $$validmove$$; if it is, we should take the smallest positive integer instead.

Because $$validmove$$ is finite, the array $$nimber$$ will be eventually periodic. Each term only depends on the previous $$N$$ terms, where $$N=\max validmove$$, so we can stop computing once we see $$N$$ consecutive terms in $$nimber[]$$ that have already appeared previously as consecutive terms. This is guaranteed to happen, as none of the terms in $$nimber$$ can exceed the size of $$validmove$$. Actually, in all the examples I have computed (with $$0$$ not a valid move), $$nimber$$ turns out to be purely periodic, although it is not clear to me that this will always be the case.

Every game of generalized nim is equivalent to a game of ordinary nim, and a pile of size $$k$$ in generalized nim corresponds to a pile of size $$nimber[k]$$ in ordinary nim.

Once we have $$nimber$$ calculated, we need to evaluate $$nimber[k]$$ for $$k=pile[1],\ldots,pile[n]$$. If the nim sum (i.e., the binary xor) of these number is non-zero, the first player has a winning strategy. If the nim sum is zero, the second player has a winning strategy.

Example: Let's consider the example you gave: $$validmove[]=\{1,2,5,7\}$$. We recursively compute $$nimber[]=\{0,1,2,0,1,2,0,1,2,0\}.$$ This means that in general, $$nimber[k]=\begin{cases}0: k\equiv 0\mod3,\\1:k\equiv 1\mod 3,\\2:k\equiv 2\mod 3.\end{cases}$$ For any other array $$validmove$$, there will be a similar way to describe $$nimber$$ in terms of congruences, using a finite amount of data.

The nim sum of $$nimber[pile[1]],\ldots,nimber[pile[n]]$$ is $$0$$ if and only if the number of piles whose size is one more than a multiple of three is even, and the number of piles whose size is two more than a multiple of three is even. In this case, the second player can win, and otherwise the first player can win.

• When 0 is not in the validmove array, this game is called a "finite subtraction game" or a "subtraction game with a finite subtraction set". The nimber sequence will not always be purely periodic. For example, if the validmove array is $\{3,4,6,10\}$, the nimber sequence (with commas and braces omitted since the nimbers are all less than $10$) is $00011122203314\overline{00201312}$. These types of games are discussed in many combinatorial game theory texts, including the undergraduate textbook "Lessons in Play: An Introduction to Combinatorial Game Theory" where the above example comes from. – Mark S. Feb 27 '16 at 3:59