How to properly implement trees with n-branching factor in python?
<p>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 </p>

<pre><code>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)
</code></pre>

<p>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.</p>

<p>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. </p>

<p>The creation of children is being called as follows.</p>

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

    self.evaluateChildren(2)

    self.evaluateSubChildren(1)

   #more calculations go here
</code></pre>

<p>I first tried calling the same evaluateChildren() function as below: </p>

<pre><code>    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()
</code></pre>

<p>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.</p>

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

<p>You're hitting the common trip-up with lists and variable bindings in Python - you make <code>children = []</code> a class variable, and that makes it <em>the same list</em> 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 <code>__init__</code> to make it a new one for each instance. </p>

<pre><code>Class Node:

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

        self.children = []
</code></pre>

<p>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:</p>

<p><a href="http://stackoverflow.com/questions/11216783/python-strange-behavior-with-list-append">Python Strange Behavior with List &amp; Append</a> </p>

<p><a href="http://stackoverflow.com/questions/18263374/weird-list-behavior-in-python">Weird list behavior in python</a></p>

<p><a href="http://stackoverflow.com/questions/12995679/python-array-weird-behavior">Python array weird behavior</a></p>

<p><a href="http://stackoverflow.com/questions/16102777/some-strange-behavior-python-list-and-dict">Some strange behavior Python list and dict</a></p>

<p><a href="http://stackoverflow.com/questions/10191749/strange-behavior-of-lists-in-python">Strange behavior of lists in python</a></p>

<p><a href="http://stackoverflow.com/questions/240178/python-list-of-lists-changes-reflected-across-sublists-unexpectedly">Python list of lists, changes reflected across sublists unexpectedly</a></p>

<p><a href="http://stackoverflow.com/questions/17702937/generating-sublists-using-multiplication-unexpected-behavior">Generating sublists using multiplication ( * ) unexpected behavior</a></p>

<p><a href="http://stackoverflow.com/questions/240178/python-list-of-lists-changes-reflected-across-sublists-unexpectedly">Python list of lists, changes reflected across sublists unexpectedly</a></p>

<p><a href="http://stackoverflow.com/questions/13058458/python-list-index">Python List Index</a></p>

<p><a href="http://stackoverflow.com/questions/17686596/function-changes-list-values-and-not-variable-values-in-python">Function changes list values and not variable values in Python</a></p>

<p><a href="http://stackoverflow.com/questions/16626013/why-does-my-original-list-change">Why does my original list change?</a></p>

<p><a href="http://stackoverflow.com/questions/11993878/python-why-does-my-list-change-when-im-not-actually-changing-it">Python: why does my list change when I&#39;m not actually changing it?</a></p>

<p><a href="http://stackoverflow.com/questions/14301560/python-list-changes-when-global-edited">python: list changes when global edited</a></p>

<p><a href="http://stackoverflow.com/questions/19951816/python-changes-to-my-copy-variable-affect-the-original-variable">python: changes to my copy variable affect the original variable</a></p>

python algorithm minimax