The Game of Nim (python 3) In this assignment, you will be asked to write a clas
ID: 3702063 • 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
import os
from random import randint
def defBoard():
hs = raw_input("Enter number of piles you want: ")
for i in range(1,int(hs)+1):
n = raw_input("enter the pile size %d: " % i)
h.append(int(n))
def display(h):
n = 0
for n,r in enumerate(h):
print n+1,
for match in range(0,r):
print " |",
def sm1():
return reduce(lambda x,y: x^y, h)
def wn_H():
return [x^sm1() < x for x in h].index(True)
def us_Mv():
r, n = raw_input("Give your choice").split()
r, n = int(r)-1,int(n)
try:
if r <= -1: raise
if n>0 and n<=h[r]:
h[r]-=n
display(h)
else:
display(h)
print "INVALID"
us_Mv()
except:
display(h)
print "INVALID"
us_Mv()
if done(): print "You Won the game"
def comp_move():
print "Computer turn"
if sm1()==0:
h[h.index(max(h))]-=randint(1,max(h))
else: h[wn_H()]^=sm1()
display(h)
if done(): print "You lost the game"
def done():
return all(z == 0 for z in h)
h = []
defBoard()
display(h)
while True:
us_Mv()
if done(): break
comp_move()
if done(): break
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.