Recursive Algorithm for Simplified Nim Game

Question

In a simplified game of Nim where two players take turns to take either 1 or 2 stones from a pile of n stones, and the player to take the last stone wins, a bit of thought or experimentation shows that where n % 3 == 0, the first player can't win, but for n % 3 == 1 or n % 3 == 2, they can.

I noticed in arriving at the above solution that I was using a recursive thought process, so rather than writing a program that just used the modulo operator, I want to write a recursive version that tells me whether I can win, and also what move to make at each step.

I've made a start with the Python code below, but am stuck on how to print the instruction for how many stones to take at each step. It's possible I've made a big conceptual error in that I haven't considered what player 2 will do at each step - I can't tell if this information is essential of if I can just use the the observations I have already made. Any help completing my program much appreciated.

def last_stone(n):
    # Base cases that guarantees player 1 will lose
    if n == 0:
        print("You can't win.")
        return False
    # Base cases that guarantees player 1 will win
    elif n == 1 or n == 2:
        return True
    else:
        return last_stone(n - 3)


for i in range(10):
    print(last_stone(i))

I want to output the sequence of winning moves or the message "you can't win from this position" if that is the case. Right now I'm just computing n % 3 as someone pointed out. I want to recreate the insight that made it clear that was the solution. With 3 stones left, winning is impossible. With 4 stones, I can refer to what happens previously to determine that I should take 1 stone to ensure winning. It may be that I need an argument for "current player" to make this work, but to get player 2 to always make a winning move I need to have already implemented the solution - catch 22. — Robin Andrews

Maruthi Adithya Maruthi Adithya · Accepted Answer · 2020-07-20T13:24:48

The idea here is simple. Player 1 starts the game. The player-1 would always make a move such that he wins it, same applies for player-2 as well.

Now, this of the problem this way.

n=1 -> Current Player wins!
n=2 -> Current Player wins!
n=3 -> Alternate Player wins!
n=4 -> Current Player wins!
so on...

So, just swap the players in alternate moves and take the stones optimally.

def get_current_player(moves):
    return "1" if moves%2==0 else "2"

def play_game(n,moves):
    if n==1:
        print("Player "+str(get_current_player(moves))+" moves 1 stone and wins!")
    elif n==2:
        print("Player "+str(get_current_player(moves))+" moves 2 stones and wins!")
    else:
        if n%3==0:
            print("Player "+str(get_current_player(moves))+" moves 1 stone")
            moves+=1
            play_game(n-1,moves)
        else:
            if n%3==1:
                #Move 1 stone and make the opponent lose
                print("Player "+str(get_current_player(moves))+" moves 1 stone")
                moves+=1
                play_game(n-1,moves)

            if n%3==2:
                #Move 2 stones and make the opponent lose
                print("Player "+str(get_current_player(moves))+" moves 2 stones")
                moves+=1
                play_game(n-2,moves)



play_game(6,0)
play_game(5,0)
play_game(3,0)

Recursive Algorithm for Simplified Nim Game

2 Answers