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.
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:
Python Strange Behavior with List & Append
Some strange behavior Python list and dict
Strange behavior of lists in python
List of lists changes reflected across sublists unexpectedly
Generating sublists using multiplication ( * ) unexpected behavior
List of lists changes reflected across sublists unexpectedly
Function changes list values and not variable values in Python
Why does my original list change?
Python: why does my list change when I'm not actually changing it?
python: list changes when global edited
python: changes to my copy variable affect the original variable