I'm trying to make a recursive function that creates a tree. Each node holds a state of a tic-tac-toe game, and the children of each node are the next possible moves.
I pass the state of the board to the recursive function. For every possible move I create a copy of the state and then make that move. This new state gets passed to the recursive function.
#XXX
#O O = state [1,1,1,-1,0,-1,1,1,1]
#XXX
playerX = 1
playerO = -1
class node:
children = [] #holds all the children
state = [] #holds the state of the board as a list of ints
def __init__(self,st):
self.state = st
def addChild(self,child):
self.children.append(child) #if only giving birth was this easy
#returns a node with all it's children filled in
#cState is the state for this node
#currentPlayer flips sign every function call
#stateSize is the size of the board
def makeTreeXO(cState,currentPlayer,stateSize):
newNode = node(cState)
for i in range(stateSize):
print "looking at", i, "in", cState
if(cState[i] == 0): #found an open space
print "found an empty space"
newState = cState #create copy of state
newState[i] = currentPlayer #make the available move
print "made new state"
newNode.addChild(makeTreeXO(newState,currentPlayer*-1,stateSize))
print "Done with this instance"
return newNode
root = makeTreeXO([1,0,0,1,1,1,1,1,1],playerX,9)
output:
looking at 0 in [1, 0, 0, 1, 1, 1, 1, 1, 1]
looking at 1 in [1, 0, 0, 1, 1, 1, 1, 1, 1]
found an empty space
made new state
looking at 0 in [1, 1, 0, 1, 1, 1, 1, 1, 1]
looking at 1 in [1, 1, 0, 1, 1, 1, 1, 1, 1]
looking at 2 in [1, 1, 0, 1, 1, 1, 1, 1, 1]
found an empty space
made new state
looking at 0 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 1 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 2 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 3 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 4 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 5 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 6 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 7 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 8 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
Done with this instance
looking at 3 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 4 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 5 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 6 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 7 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 8 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
Done with this instance
looking at 2 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 3 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 4 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 5 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 6 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 7 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 8 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
Done with this instance
From the print statements it's clear that the changes made to the state are being carried back to the parent instance of the function. Does anyone know why?
One problem is this line:
newState = cState
from your comment it looks like you are trying to copy cState, however, you are only copying the reference to the list, not the contents of the list. Thus when you modify newState, you are also modifying cState. What you should have is:
newState = cState.copy()
EDIT
Since this is the accepted answer, the full solution also includes setting self.children = [] in the constructor of node, as mentioned by @thefourtheye