Today we are going to look at a small algorithm exercise in python, through the game called the nim game.

The rule

This is a two-player game. We have n matches to start with (for example 10).
In turn, each player will take 1, 2 or 3 matches. The player who takes the last match loses.

The algorithm

This is a fairly deterministic game, in the sense that when you know the trick, you can't lose (unless you started from a losing position).

Here is a table of the right number of matches to take (x representing a losing position):

periodicity

We can therefore observe an infinite periodic loop, with a period of 4.

The player has lost (if the other plays well), when we have a modulo 4 = 1 (in other words the remainder of the division is equal to 1).

The winning strategy is therefore to send the other player to a losing position.

1-player version

We will formalize this in the algorithm, using the modulo function, to write the computer's AI.

n = int(input("Enter the initial number of matches: "))
print("Number of matches : ", n)
while n>0:
    j=-1
    print("P1 turn")
    while j<1 or j>3 or j>n:
        j=int(input("How much do you take ? (1-3) "))
    n=n-j
    if n==0:
        print("You lost !")
    else:
        print("P2 turn (cpu)")
        print("Remaining ", n)
        if n%4==3:
            p=2
        elif n%4==2:
            p=1
        elif n%4==0:
            p=3
        else:
            p=1
        print("I take some", p)
        n=n-p
        print("Remaining ", n)
        if n==0:
            print("I lost !")

Two-players version

Here is a version if you want experiment with a friend, keeping in mind this strategy :

def nim_game():
    print("Welcome to the Nim Game!")
    print("Rules: Players take turns removing 1 to 3 objects from the pile.")
    print("The player forced to take the last object loses.")

    # Initialize the pile
    pile = int(input("Enter the initial number of objects in the pile: "))
    while pile <= 0:
        print("The pile must contain at least 1 object.")
        pile = int(input("Enter the initial number of objects in the pile: "))

    # Player names
    player1 = input("Enter Player 1's name: ")
    player2 = input("Enter Player 2's name: ")

    # Start the game
    current_player = player1

    while pile > 0:
        print(f"\nThere are {pile} objects in the pile.")
        print(f"{current_player}'s turn.")

        # Get the number of objects to remove
        try:
            remove = int(input("How many objects will you take (1-3)? "))
            if remove < 1 or remove > 3:
                print("Invalid move. You can only take 1, 2, or 3 objects.")
                continue
            if remove > pile:
                print("Invalid move. You cannot take more objects than are in the pile.")
                continue
        except ValueError:
            print("Invalid input. Please enter a number between 1 and 3.")
            continue

        # Update the pile
        pile -= remove

        # Check if the game is over
        if pile == 0:
            print(f"\n{current_player} is forced to take the last object and loses!")
            break

        # Switch players
        current_player = player2 if current_player == player1 else player1

    print("Game over. Thanks for playing!")

# Run the game
if __name__ == "__main__":
    nim_game()

Here is a little logic exercise, that you can use to practice algorithms in Python.

Also, you know the secret and will not be fooled by this game anymore, have fun!