How to properly implement trees with n-branching factor in python?

Question

I am trying to implement a minimax algorithm in python, but I am having some issues creating the branching tree structure. I am still an amateur programmer so please don't mind if my code seems bad. Here is my Node Structure

class Node:
    parent = None
    state = None
    pmax = 0        #this represents the MAX player symbol; i.e. SELF
    pmin = 0        #this represents the MIN player symbol; i.e. OPPONENT
    stateCost = 0   #this represents utility cost of leaf nodes based on the matrix state
    bestCost = None    #this represents the chosen path in the minimax algorithm
    children = []

    def __init__(self,mat,up,mx,mn):
        self.parent = up
        self.state = mat
        self.pmax = mx
        self.pmin = mn
        stateCost = 0

    def addChild(self,newState,up):
        n = Node(newState,up,self.pmax,self.pmin)
        self.children.append(n)

    def evaluateChildren(self,minmax):
        ln = len(self.state[0])
        for x in range(ln):
            #newState = insertIntoSink(self.state[0],x)
            cloneState = cloneMatrix(self.state)
            newState = insertIntoSink(cloneState,x,minmax)
            print "state being added"
            for list in newState:
                print list
            self.addChild(newState,self)

        print "done Evaluating CHILDREN"


     def evaluateSubChildren(self,minimax):
        ln = len(self.state[0])

        for l in self.children:
            for x in range(ln):
              cloneState = cloneMatrix(self.state)
              newState = insertIntoSink(cloneState,x,minimax)
              l.addChild(newState,l)

In the case of what I'm doing, there must be 7 children for the root node, and each child should have 7 children of itself. Each child will have a modified clone of the initial matrix in the parent node.

The error occurring is that after adding the subchildren (i.e. second level children) do not get added to the children list, but rather they get added to the root node instead.

The creation of children is being called as follows.

 def getBestMove(self):
    move =0
    maxVal = -1;
    i=-1;
    #evaluate all the 7 children

    self.evaluateChildren(2)

    self.evaluateSubChildren(1)

   #more calculations go here

I first tried calling the same evaluateChildren() function as below:

    def getBestMove(self):
    move =0
    maxVal = -1;
    i=-1;
    #evaluate all the 7 children

    self.evaluateChildren(2)


    #evaluate second level children
     for n in self.children:
         print "evaluating SECOND LEVEL CHILDREN"
         n.evaluateChildren()

If I check the number of children of the root node after evaluation, it SHOULD be 7, but it keeps adding more level-2 children to it, which is throwing my program in an infinite loop.

Please let me know where I'm going wrong. Please ask if there are any more information is required.

TessellatingHeckler · Accepted Answer

You're hitting the common trip-up with lists and variable bindings in Python - you make children = [] a class variable, and that makes it the same list in every Node. There's one list in memory and every Node points to it. Change it, and all Nodes see the change. Move that into __init__ to make it a new one for each instance.

Class Node:

    def __init__(self,mat,up,mx,mn):

        self.children = []

All sorts of people tripping over the same problem 'many things referencing the exact same list by mistake', tons of discussions of what's happening, why, how to avoid it: