Recursively Algorithm for the NIm game-CodePudding

I am trying to solve the Nim game. There are two players and a stack of sticks. Players can pick 1, 2 or 3 sticks on their turn. Player to pick the last stick will loose.

I have a function that takes two parameter, number of sticks and boolean. If the boolean pamater is true, means player1 will start the game and if false, means player 2. The function returns True if player1 wins, and false if player1 loose.

def num_game(no_of_sticks, player_one):
    if player_one and no_of_sticks == 1:
        return False
    elif no_of_sticks % 2 == 0:
        return True
    elif no_of_sticks % 4 == 0 or no_of_sticks % 4 == 1:
        return num_game(no_of_sticks - 3, not player_one)
    elif no_of_sticks % 4 == 2:
        return num_game(no_of_sticks - 1, not player_one)
    elif no_of_sticks % 4 == 3:
        return num_game(no_of_sticks - 2, not player_one)

So, for instance, when I call num_game(6, True), it returns True, Although, it should return False, because when the function runs and player1 takes 3 sticks form the stack, player2 takes 2, leaving player1 with one and hence player1 should loose and the function should return False.

If I call num_game(5, True), it returns True which is incorrect result, it should also return False.

I am not able to accuratly pin point where/what I am doing wrong here. Any help would be appreciated.

CodePudding user response：

I think this is your problem:

if player_one and no_of_sticks == 1:
    return False

This statement is true if there is one stick left AND it is player one's turn.

But what if there is one stick left and it is player two's turn?

CodePudding user response：

What happens specifically for calling num_game(6, True) is that 6 % 2 = 0 and therefore, the following condition will hold:

elif no_of_sticks % 2 == 0:
        return True

And you get an answer of True.

My question is What exactly are you trying to achieve, because num_game(6, True) can have multiple paths dependents on what the two players are doing (this is very much similar to an [adversarial problem solving][1] as many 2-player games are). For example:

player 1 draws 3 (3 remain), player 2 draws 2(1 remain), player 1 draws 1 and loses
player 1 draws 1(5 remain), player 2 draws 3(2 remain), player 1 draws 1(1remain), player 2 draws 1 and loses.

There are of course many different paths which can be taken and either one of the payers can win or lose.

If what you are trying to do is to see that if the beginning player plays ideally, will he win or lose regardless of the opponent's actions, perhaps this will work:

def num_game(no_of_sticks, player_one):
    if no_of_sticks == 1: return not player_one
    elif no_of_sticks == 2: return player_one  # drawing 1 will leave the oppenent with 1, forcing lose
    elif no_of_sticks == 3: return player_one  # drawing 2 will leave the opponent with 1 forcing lose
    else:  # number of stickes bigger than 3
        outcome1 = num_game(no_of_sticks-1, not player_one)
        outcome2 = num_game(no_of_sticks-2, not player_one)
        outcome3 = num_game(no_of_sticks-3, not player_one)
        # check if there is a way to win
        if player_one:
            return outcome1 or outcome2 or outcome3
        else:
            return not (outcome1 or outcome2 or outcome3)

[1]: https://www.sciencedirect.com/science/article/abs/pii/036402139290019Q#:~:text=In adversarial problem solving (APS,opponent's model of the agent.