Generalisation of Nim

Question

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.

Answer 1

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.