A bit of a deviation from pure statistics, because tonight I wrote something interesting, while attempting to learn the Python programming language for work. The program is simple, a normal play subtraction (Nim) game.
The object of the game is simple: given a pile of N elements (stones, we will call them), each player is allowed to select between 1 and k (where k is any number greater than or equal to 2, and less than N) elements to take. The winner is whichever player takes the last element from the pile.
The winning strategy of this game is simple, if one does a modular division of the number of elements in the pile by the sum of the maximum move and 1 is zero, the player has a winning strategy if the opponent is moving, and a losing one if they are moving (example: a maximum move game of 2 and a pile of 9, the player is in a winning position if the opponent is moving, since 9 Mod 3 = 0). Therefore if, at the start of the game, N Mod (k+1) = 0, then a player would want to go second in order to have a winning strategy, first otherwise.
How can one write a program in Python that can simulate this? Well, it's easy, and took me just 84 lines of code. First, the full program:
#!C:/Python32
#Joe Regan
#nims.py
#5/15/11
import math
import random
def play_nims(pile,maxRemove):
print("Starting with ",pile," stones, select up to ",maxRemove," stones")
while(pile>0):
p1move=int(input("Select stones to remove "))
while(p1move>maxRemove):
p1move=int(input("Select stones to remove "))
pile=pile-p1move
print("Player 1 took ",p1move," stones, and ",pile," stones remain")
if(pile==0):
print("Player 1 wins!")
else:
p2move=int(input("Select stones to remove "))
while(p2move>maxRemove):
p2move=int(input("Select stones to remove "))
pile=pile-p2move
print("Player 2 took ",p2move," stones, and ",pile," stones remain")
if(pile==0):
print("Player 2 wins!")
def play_nims_comp(pile,maxRemove):
print("Starting with ",pile," stones, select up to ",maxRemove," stones")
turn=int(input("Enter 1 to go first, any other number to go second: ")) #allow user to decide in what order he wants to go
while(pile>0):
if(turn==1):
move=int(input("Select stones to remove "))
while(move>maxRemove):
move=int(input("Select stones to remove "))
pile=pile-move
print("Player took ",move," stones, and ",pile," stones remain")
if(pile==0):
print("Player wins!")
else:
if(math.fmod(pile,(maxRemove+1))==0):
CPUmove=random.randint(1,maxRemove)
else:
CPUmove=math.fmod(pile,(maxRemove+1))
pile=pile-CPUmove
print("CPU took ",CPUmove," stones, and ",pile," stones remain")
if(pile==0):
print("Player loses!")
else:
if(math.fmod(pile,(maxRemove+1))==0):
CPUmove=random.randint(1,maxRemove)
else:
CPUmove=math.fmod(pile,(maxRemove+1))
pile=pile-CPUmove
print("CPU took ",CPUmove," stones, and ",pile," stones remain")
if(pile==0):
print("Player loses!")
else:
move=int(input("Select stones to remove "))
while(move>maxRemove):
move=int(input("Select stones to remove "))
pile=pile-move
print("Player took ",move," stones, and ",pile," stones remain")
if(pile==0):
print("Player wins!")
#Allow the user to select which game they would like to play
CPUorHuman=int(input("Let's play nim! First, select if you're playing a human (1) or the computer (2): "))
while(CPUorHuman!=1 and CPUorHuman!=2):
CPUorHuman=int(input("Let's play nim! First, select if you're playing a human (1) or the computer (2): "))
params=input("Enter the starting pile and max move, separated by commas: ").split(",")
P=int(params[0])
M=int(params[1])
while(P<=M):
params=input("Enter the starting pile and max move, separated by commas: ").split(",")
P=int(params[0])
M=int(params[1])
if(CPUorHuman==1):
play_nims(P,M)
else:
play_nims_comp(P,M)
Now let's break it down to the functional levels.
#!C:/Python32
#Joe Regan
#nims.py
#5/15/11
import math
import random
Here's where I write the shebang, telling the system that I want to use python. After some documentation, I import the math package (redundant here) and the random package (which will provide highly useful for the CPU logic).
def play_nims(pile,maxRemove):
print("Starting with ",pile," stones, select up to ",maxRemove," stones")
while(pile>0):
p1move=int(input("Select stones to remove "))
while(p1move>maxRemove):
p1move=int(input("Select stones to remove "))
pile=pile-p1move
print("Player 1 took ",p1move," stones, and ",pile," stones remain")
if(pile==0):
print("Player 1 wins!")
else:
p2move=int(input("Select stones to remove "))
while(p2move>maxRemove):
p2move=int(input("Select stones to remove "))
pile=pile-p2move
print("Player 2 took ",p2move," stones, and ",pile," stones remain")
if(pile==0):
print("Player 2 wins!")
This is the method used in a human v. human game. As order of player does not matter to the computer, this is simple: we pass to the function the size of the original pile, and the maximum number of moves. While there's still elements within the pile, we allow players to take turns.
First, player 1 makes his move (and continues to be asked until giving a valid response), and his move is subtracted from the pile. If he takes the last stone, player 1 wins, and if not, the same process goes to player 2. If player 2 does not win, we go back to the top of the while loop.
def play_nims_comp(pile,maxRemove):
print("Starting with ",pile," stones, select up to ",maxRemove," stones")
turn=int(input("Enter 1 to go first, any other number to go second: ")) #allow user to decide in what order he wants to go
while(pile>0):
if(turn==1):
move=int(input("Select stones to remove "))
while(move>maxRemove):
move=int(input("Select stones to remove "))
pile=pile-move
print("Player took ",move," stones, and ",pile," stones remain")
if(pile==0):
print("Player wins!")
else:
if(math.fmod(pile,(maxRemove+1))==0):
CPUmove=random.randint(1,maxRemove)
else:
CPUmove=math.fmod(pile,(maxRemove+1))
pile=pile-CPUmove
print("CPU took ",CPUmove," stones, and ",pile," stones remain")
if(pile==0):
print("Player loses!")
else:
if(math.fmod(pile,(maxRemove+1))==0):
CPUmove=random.randint(1,maxRemove)
else:
CPUmove=math.fmod(pile,(maxRemove+1))
pile=pile-CPUmove
print("CPU took ",CPUmove," stones, and ",pile," stones remain")
if(pile==0):
print("Player loses!")
else:
move=int(input("Select stones to remove "))
while(move>maxRemove):
move=int(input("Select stones to remove "))
pile=pile-move
print("Player took ",move," stones, and ",pile," stones remain")
if(pile==0):
print("Player wins!")
This is far more complex. First, we have to ask the player (who is opposing the computer, so now order does matter), whether he wants to go first or second (after passing the initial game rules again). If the player decides to go first, the same logic as before is followed for the human player. The second player, aka the computer, is designed to play an optimal game, however. Therefore, if the player leaves a pile of M where M Mod (k+1) > 0, the computer will simply take M Mod (k+1), and will have a winning strategy (and eventually win). If not, the computer will select a random amount between 1 and k, and continue to have a losing strategy, unless the human player makes an error. If the player decides to go second, the reverse order is followed.
CPUorHuman=int(input("Let's play nim! First, select if you're playing a human (1) or the computer (2): "))
while(CPUorHuman!=1 and CPUorHuman!=2):
CPUorHuman=int(input("Let's play nim! First, select if you're playing a human (1) or the computer (2): "))
params=input("Enter the starting pile and max move, separated by commas: ").split(",")
P=int(params[0])
M=int(params[1])
while(P<=M):
params=input("Enter the starting pile and max move, separated by commas: ").split(",")
P=int(params[0])
M=int(params[1])
if(CPUorHuman==1):
play_nims(P,M)
else:
play_nims_comp(P,M)
Here's where the user interacts with the command line to decide the game options. First, the user immediately decides if they are playing a human (1) or a computer (2), and this is asked until the user answers with a 1 or 2. From there, the user is asked to provide a starting pile and maximum move, and is asked again if the pile is less than or equal to the maximum move (comma separated). Finally, we pass to the if statement, where the program decides whether to call the human v. human, or human v. computer game.
So how does this look? Let's play the computer, start with 30 stones, and allow a maximum move of 4.
Let's play nim! First, select if you're playing a human (1) or the computer (2): 2
Enter the starting pile and max move, separated by commas: 30,4
Starting with 30 stones, select up to 4 stones
Enter 1 to go first, any other number to go second: 2
CPU took 4 stones, and 26 stones remain
Select stones to remove 1
Player took 1 stones, and 25 stones remain
CPU took 1 stones, and 24 stones remain
Select stones to remove 4
Player took 4 stones, and 20 stones remain
CPU took 4 stones, and 16 stones remain
Select stones to remove 1
Player took 1 stones, and 15 stones remain
CPU took 4 stones, and 11 stones remain
Select stones to remove 1
Player took 1 stones, and 10 stones remain
CPU took 2 stones, and 8 stones remain
Select stones to remove 3
Player took 3 stones, and 5 stones remain
CPU took 3 stones, and 2 stones remain
Select stones to remove 2
Player took 2 stones, and 0 stones remain
Player wins!
As you can see, I elected to go first (since 30 Mod (4+1) = 0, I had a winning strategy if the computer went first), and won the game by following this basic rule.
So, if you have python installed on your own system, try it out, and see if you can keep your friends stumped.
No comments:
Post a Comment