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):
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!
Top comments (0)