4
$\begingroup$

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?

$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Note that OP is not asking for the change of rule so that the number of stones to remove from a pile is restricted. He is asking for a change of rule so that the number of stones remaining in a pile each time is restricted. It is entirely different. $\endgroup$
    – Cyriac Antony
    Apr 12, 2018 at 6:26
0
$\begingroup$

You have analyzed the game correctly. Wikipedia lists it as "the subtraction game" under "Other variations of Nim".

$\endgroup$
8
  • $\begingroup$ However it is not a standard subtraction game, which is what my question is about. In my particular case, not all states of the pile are valid. $\endgroup$
    – NullOverNull
    Jul 2, 2012 at 17:55
  • $\begingroup$ I don't know about a name, but you can use the Sprage-Grundy theorem to determine the winning positions and Nim values. It seems the valid removals will vary depending on the size of the pile. You will probably not see the nice periodicity that the basic game has. $\endgroup$
    – Ross Millikan
    Jul 2, 2012 at 18:41
  • $\begingroup$ 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. $\endgroup$
    – NullOverNull
    Jul 2, 2012 at 18:51
  • $\begingroup$ @NullOverNull Since the game is (ultimately) eventually periodic, once you find the period and saltus you have a strategy; and there are ways of knowing when you've found the period, but that period can be very large in terms of the subtraction-set (see, e.g., sciencedirect.com/science/article/pii/030439759500019S ). Are you at all familiar with the Sprague-Grundy theory of impartial games that Ross mentions? $\endgroup$
    – Steven Stadnicki
    Jul 2, 2012 at 19:26
  • $\begingroup$ @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 $\endgroup$
    – NullOverNull
    Jul 2, 2012 at 20:23
0
$\begingroup$

It is simply Nim. The change of rule doesn't introduce anything new.

I assume that we have a fixed set $S$ of numbers and the number of stones to remain in a pile after each move must be from $S$ (and in initial position, the number of stones in each pile is a number from $S$). In particular, i am assuming that the numbers allowed doesn't vary from pile to pile.

For an example suppose that the set $S=\{0,1,2,4,7,8\}$. Keep in mind that we are in a world of cardinal numbers here. So what you did here is just a change of symbols. I shall use the following notation: usual cardinal number ----> (number in your game).
0---->(0)
1---->(1)
2---->(2)
3---->(4)
4---->(7)
5---->(8)

Now simply do the "congruent to 0 modulo $(B+1)$ move" on usual cardinal number and you are done.

PS: Even when the set $S$ varies from pile to pile, the situation is similar. Just interpret the number of items in each pile according to the set $S$ for that pile in the way described above and using those numbers play nim.

Thank you

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .