# Trying to find the name of this Nim variant

Consider this basic example of subtraction-based Nim before I get to my full question:

Let $V$ represent all valid states of a Nim pile (the number of stones remaining):

$V = 0,1,2,3,4,5,6,7,8,9,10$

Let $B$ be the bound on the maximum number of stones I can remove from the Nim pile in a single move (minimum is always at least 1):

$B = 3$

Optimal strategy in a two-player game then is to always ensure that at the end of your turn, the number of stones in the pile is a number found in $V$, and that it is congruent to $0$ modulo $(B+1)$. During my first move I remove 2 stones because $8$ modulo $4$ is $0$.

My opponent removes anywhere from 1-3 stones, but it doesn't matter because I can then reduce the pile to $4$ because $4$ modulo $4$ is $0$. Once my opponent moves, I can take the rest of the pile and win.

This is straightforward, but my question is about a more advanced version of this, specifically when $V$ does not include all the numbers in a range. Some end-states of the pile are not valid, which implies that I cannot find safe positions by applying the modulo $(B+1)$ rule.

Does this particular variant of Nim have a name that I can look up for further research? Is there another way to model the pile?

-

In my case, $V$ follows a recurrence. My issue is that I don't even know where to begin analyzing in order to develop a strategy that doesn't rely on brute scanning/trial and error/etc. – NullOverNull Jul 2 '12 at 18:51
@StevenStadnicki I vaguely understand it as the distance from winning position (a grundy number of 1 meaning you're one step away from a winning position or something to this effect). I am also not sure about periods, since my set $V$ has an exponential recurrence – NullOverNull Jul 2 '12 at 20:23
These are known as subtraction games; in general, for some set $S=\{s_1, s_2, \ldots s_n\}$ the game $\mathcal{S}(S)$ is the game where each player can subtract any element of $S$ from a pile. (So your simplified case is the game $\mathcal{S}(\{1\ldots B\})$) The nim-values of single-pile positions in these games are known to be ultimately periodic, and there's a pairing phenomenon that shows up between 0-values and 1-values, but generically there isn't much known about these games with $n\gt 2$. Berlekamp, Conway, and Guy's Winning Ways For Your Mathematical Plays has a section on subtraction games; as far as I can tell, it's still the canonical reference for combinatorial game theory. The Games of No Chance collections also have some information on specific subtraction games, and it looks like an article on games with three-element subtraction sets showed up recently on arxiv ( http://arxiv.org/abs/1202.2986 ); that might be another decent starting point for references into the literature.