2
$\begingroup$

I am trying to understand the Stones game stated here.

The stones game is a simple game, it is also a very old game which is unknown to almost everyone.

The game starts with N stones and M players, the players are numbered from 1 to M. The players play in turns, player number 1 plays first, then player number 2 and so on until player number M plays, after this player number 1 plays again and they keep playing until the end of the game. For each turn, the players do the following 2 steps:

  1. The player gets a chance to remove a stone, and he/she should remove a stone in this step if he/she decided to do so.

  2. Regardless of the decision of the current player (whether or not he/she removed a stone in the first step), if this is not the first turn and in the previous turn the player decided not to remove a stone in his/her first step, then the current player must remove a stone in this step (if in the previous turn the player decided to remove a stone in his/her first step, then the current player must not remove a stone in this step).

This means in some turns a player might remove 0, 1 or 2 stones according to the above rules. In this game, the player who removes the last stone wins the game. Now you are given the total number of stones, the total number of players and a player number and you are asked to answer the following question: Is there a strategy for this player to win the game regardless of the actions taken by the other players in their turns?

In the sample example it is also stated that 2 players are playing with 2 stones and 2nd player can win the game regardless of the actions taken by the first player. How is it possible? A player can remove either 0 or 1 or 2 stones. If the first player removes 2 stones in his first turn 2nd player will not have any stones left to play then how 2nd player will be able to win?

$\endgroup$
1
$\begingroup$

The first player is not allowed to remove 2 stones on his first turn. The description of step 2 says "if this is not the first turn". So the game goes like this.

  • First player may remove either 0 or 1.
    • If first player removes 0, second player may now remove either 1 or 2.
    • (Second player will remove 2 and win.)
    • If first player removes 1, second player may now remove either 0 or 1.
    • (Second player will remove 1 and win.)

The second player always wins. (In the setup where N=M=2, that is.)

This wasn't part of the question, but let's work out what happens for 2 players in general. It's an impartial game in the sense of combinatorial game theory; a position is specified by saying how many stones are present (initially N) and whether the next player is choosing 0-or-1 or 1-or-2. And there's a little bit of tricksiness because reducing #stones to 0 is always a win even if the next player would otherwise have had the option of removing 0 stones; so we need to say that when #stones=0 there are no legal moves.

So, from (n,0-or-1) you can move to (n,1-or-2) or to (n-1,0-or-1) except that if n=0 you have no moves at all; from (n,1-or-2) you can move to (n-1,1-or-2) or (n-2,0-or-1). And after a bit of scribbling it becomes clear that the situation is as follows (easy proof by induction):

  • For n=0 the next player loses (nim-value is 0).
  • For n=1 the next player wins (nim-value is 2 for 0-or-1, 1 for 1-or-2).
  • For n=2 the next player loses (nim-value 0) for 0-or-1; wins (nim-value 2) for 1-or-2.
  • For larger odd n, the next player wins (nim-value 1) for 0-or-1 and loses (nim-value 0) for 1-or-2.
  • For larger even n, the next player loses (nim-value 0) for 0-or-1 and wins (nim-value 1) for 1-or-2.

(In case you aren't familiar with the theory: the nim-value of a position is the size of the single pile in the game of Nim it's equivalent to, assuming "normal play" where the last player able to move wins; the nim-value of a position equals the smallest nonnegative integer that isn't the nim-value of any of the positions you can move to from it. A position is a win for the next player if its nim-value is non-zero and a loss if it's zero.)

$\endgroup$
  • 1
    $\begingroup$ The way I understand it, neither player 1 nor 2 can remove 2 stones in their first turn. (the first round) $\endgroup$ – Aaron Dietz Jul 6 '16 at 20:08
  • $\begingroup$ I don't think that's right; my reading is that it's only on the very first play that step 2 isn't done. (Equivalently, we can pretend that in the initial position the non-existent previous player took the option of removing an extra stone.) If you don't allow player 2 to remove two stones on their first turn, then player 1 wins by removing 0; then player 2 has to remove 1; then player 1 removes 1 and wins. But the linked problem statement says (2 stones, 2 players) is a win for player 2. $\endgroup$ – Gareth McCaughan Jul 6 '16 at 20:11
  • $\begingroup$ As per my understanding, previous turn's Step 1 drives the current turn's step 2 then in first turn both the players will do only step 1 $\endgroup$ – user3595026 Jul 6 '16 at 20:18
  • $\begingroup$ Yes, previous turn's step 1 drives current turn's step 2. In the first turn player 1 does step 1, then player 2 does steps 1 and 2. Otherwise you get an outcome for n=2 that doesn't match the description in the original problem statement. $\endgroup$ – Gareth McCaughan Jul 6 '16 at 20:30
  • $\begingroup$ (where, to be clear, by "the original problem statement" I mean the A2OJ page linked from the question.) $\endgroup$ – Gareth McCaughan Jul 6 '16 at 20:30
4
$\begingroup$

Here's a clearer statement of the rules. Each player has two options:

  • Remove a stone on this turn.
  • Remove a stone on the next turn.

This is because not removing a stone causes one to be removed next turn.

We now see that the game will last at most N+1 turns, because by then every player has removed a stone, whether or not they decided to delay or not. If the Nth player decided to remove a stone immediately (i.e. took the first option), then the game lasts N turns; if they delayed, it lasts N+1 turns.

Therefore, player N decides whether or not the winner is player N or N+1, so only player number N can force a win. It is possible for player N+1 to win, but only if player N decides for some reason to delay their stone removal.

If N is bigger than M, then the pivotal player is the remainder of N divided by M. A simple program to calculate whether player X can force a win is simply

def can_force_win(N,M,X):
     return N % M == X
$\endgroup$
  • $\begingroup$ The restatement might be easier to see by reversing the two parts of each turn. $\endgroup$ – f'' Jul 7 '16 at 2:50
  • $\begingroup$ 2 % 2 == 2 will return false. $\endgroup$ – user3595026 Jul 7 '16 at 5:21
  • $\begingroup$ 'return (N%M == 0 && M==X) || N % M == X;' $\endgroup$ – user3595026 Jul 7 '16 at 6:41
  • $\begingroup$ return (N-X)%M == 0 $\endgroup$ – Gareth McCaughan Jul 7 '16 at 12:32
  • $\begingroup$ This is a very nice way of looking at it. [EDITED TO ADD:] For the avoidance of doubt, "this" means the answer, not my trivial tweak to the return statement in the previous comment. $\endgroup$ – Gareth McCaughan Jul 7 '16 at 12:36

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.