4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you sure this isn't an open problem? $\endgroup$ – Rand al'Thor May 26 '15 at 8:25
  • $\begingroup$ 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... $\endgroup$ – leoll2 May 26 '15 at 11:36
  • $\begingroup$ If 0 and 1 are not in $validmove[]$, it is possible for there to be no legal moves even though some stones remain. $\endgroup$ – Julian Rosen May 26 '15 at 14:16
6
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mark S. Feb 27 '16 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.