The Game of Nim (python 3) In this assignment, you will be asked to write a clas
ID: 3702064 • Letter: T
Question
The Game of Nim (python 3)
In this assignment, you will be asked to write a class Minimax that simply allows you to build a minimax tree with states of a Nim game and also display it. You will use this class and write a program that asks for the number of tokens then builds the tree with all the possible states from that number of tokens then display the tree. The goal of this assignment is to display or print out the minimax tree, not to implement the game.
The constructor for the class Minimax looks like this:
The attribute state is a list while the level is a string, either "Max" or "Min".
For instance, the state of the root node in our previous example is [6]. The state of the left-most leaf node in our tree above would be [1, 1, 1, 1, 2]. Notice that the list is sorted. You can sort the list by calling the sort() or sorted() functions in Python.
The algorithm for building the tree is as follows:
This algorithm is called after starting the first node which is the root of the tree and contains as a state a list with the initial pile.
Notice that you would also need to implement add_child() in your class. You must also implement the split() function, which gets a list which represents the state and generates a list of possible splits. For the state [6], it would generate [[1, 5], [2, 4]]; for [8] it would generate [[1, 7], [2, 6], [3, 5]] and for [1, 5] it would generate [[1, 1, 4], [1, 2, 3]]. These are all possible combinations. Hint: To make it easier to implement the split() function, you could think about writing another function that splits single values instead of a whole state.
To print the tree you need to traverse it. Here is an algorithm to do so depth-first and print the nodes of the tree with an indentation like when displaying folders in your disk directory. The function would be invoked for a node and be called recursively. Each time you pass it the indentation for the next level. If you want to display the last child of a node differently, you may also pass the information whether the receiver is supposed to be the last. So the print function receives as parameters a string for the indentation and a boolean indicating if the node receiver is the last child of the children list. The algorithm would look like this:
Here is an example execution below. Here, the '+' a new child for the parent of the indented block of output and '-' indicates the last child in the children list of the parent node. The '|' indicate the level of the tree and so connect child nodes that are siblings i.e., nodes in the same list.
Explanation / Answer
Surce Code
import random
import time
def welcomeMsg():
print("""
----------------------------------------------------------------------------
WELCOME TO THE GAME OF NIM!
----------------------------------------------------------------------------
""")
def display_board(board):
print(" ----------------------------------------------------------------------------")
print(" ",*board, sep=" ")
print("---------------------------------------------------------------------------- ")
def who_starts(qstn):
ch = None
while ch not in ("F", "S","f","s"):
ch = input(qstn)
if ch.upper() == "F":
f_player = "USER"
s_player = "USER"
elif ch.upper() == "S":
f_player = "CMP"
s_player = "CMP"
else:
print(" Invalid ch. Please re-enter your choice.")
return f_player, s_player
def userPick(qstn,minStick,maxStick,userIn,board):
print(" --USER'S TURN--")
while userIn not in range(minStick, maxStick) or userIn >= len(board):
try:
userIn = int(input(qstn))
if userIn not in range(minStick, maxStick) or userIn >= len(board):
print(" You can cannot choose that many sticks!")
userIn = int(input(qstn))
except Exception as e:
print(" An error has occured. Error: " + str(e) + " Please re-enter your ch.")
f_player = "CMP"
return userIn, f_player
def update_board(board,move):
valid_moves = (1,2)
if len(board) > move:
for i in range(move):
board.remove("/")
return board
elif len(board) <= move:
if move in valid_moves:
for i in range(move):
board.remove("/")
return board
else:
print(" " + str(move) + " sticks cannot be taken. The move you made was inavalid. Please re-enter.")
return board
def computers_move(board,userIn,s_player,winningPos,earlier_move):
best_move = 1
print(" --COMPUTER'S TURN--")
if s_player == "CMP" and winningPos == False:
if len(board) % 4 ==1:
best_move = 0
while best_move not in range(1,len(board)+1):
best_move = random.randint(1,3)
else:
if userIn + earlier_move < 4:
best_move = 4 - (userIn + earlier_move)
winningPos = True
elif userIn + earlier_move > 4:
best_move = 8 - (userIn + earlier_move)
winningPos = True
elif s_player == "USER" or winningPos == True:
best_move = 4 - userIn
earlier_move = best_move
print(" The computer chooses to remove...")
time.sleep(1)
print(": " + str(best_move) + " stick(s).")
for sticks in range(best_move):
board.remove("/")
f_player = "USER"
return board, f_player, winningPos, earlier_move
def gameOver(board,f_player):
if len(board) == 1 and f_player == "USER":
winner = "COMPUTER"
loser = "USER"
elif len(board) == 1 and f_player == "CMP":
winner = "USER"
loser = "COMPUTER"
else:
winner = None
return winner, loser
def continue_playing():
while True:
another_go = input(" Do you want to play again?[Y/N]: ")
if another_go in ("y","Y"):
return True
elif another_go in ("n","N"):
return False
else:
print(" Inavlid ch. Please re-enter.")
def main():
anotherGo = True
welcomeMsg()
while anotherGo == True:
earlier_move = 0
winningPos = False
nimBoard = ["/","/","/","/","/","/","/","/","/","/","/","/","/","/","/","/","/"]
winner = None
userIn = 0
print("----------------------------------------------------------------------------")
display_board(nimBoard)
print(" We begin with " + str(len(nimBoard)) + " sticks.")
f_player, s_player = who_starts(" Do you want to start first or second? [F for fisrt/S for second]: ")
while len(nimBoard) != 1:
if f_player == "USER":
time.sleep(0.5)
userIn,f_player = userPick(" Enter your ch [1, 2 or 3]: ", 1, 4, 20,nimBoard)
nimBoard = update_board(nimBoard,userIn)
display_board(nimBoard)
print(" There are " + str(len(nimBoard)) + " stick(s) remaining.")
else:
time.sleep(1)
nimBoard, f_player,winningPos, earlier_move = computers_move(nimBoard,userIn,s_player,winningPos,earlier_move)
time.sleep(1)
display_board(nimBoard)
print(" There are " + str(len(nimBoard)) + " stick(s) remaining.")
time.sleep(1)
print(" Finally... Only one stick remains...")
game_winner, game_loser = gameOver(nimBoard,f_player)
time.sleep(1)
print(" The " + game_loser + " is left with the last stick and so he is the loser...")
print(" The winner of the game is... : " + str(game_winner))
anotherGo = continue_playing()
time.sleep(1)
print(" Thank you for playing!")
print(" --GAME OVER--")
if __name__ == "__main__":
main()
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.