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:

class Minimax: def __init__(self, nimState, minMaxLevel): self.state = nimState self.level = minMaxLevel self.child = [] 

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:

for each pile k in node.state do if k > 2 then list of possibilities = split k for each pair (i,j) in possibilities do newstate=node.state replace pile k in newstate with pile i add pile j in newstate sort newstate node.addChild(newstate) end for end if end for  

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.

create root with starting number of tokens call root.build() 

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:

print_tree(indentation, last) print indentation if last then print '\-' indentation += " " else print '+ ' indentation += "| " end if print node.state if last print node.level for all children of node last = false if last child then last = true child.print_tree(indentation, last) end for 

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.

Choose your initial size of the pile. Should be more than 2: abc Choose your initial size of the pile. Should be more than 2: 2 Choose your initial size of the pile. Should be more than 2: 6 \-[6] MAX + [1, 5] | + [1, 1, 4] | | \-[1, 1, 1, 3] MIN | | \-[1, 1, 1, 1, 2] MAX | \-[1, 2, 3] MAX | \-[1, 1, 2, 2] MIN \-[2, 4] MIN \-[1, 2, 3] MAX \-[1, 1, 2, 2] MIN

6 tokens 3 tokens 3 tokens Not a legal move Resulting piles should be of different sizes 6 tokens 4 tokens 2 tokens 6 tokens 5 tokens 1 token Acceptable moves