我正在尝试创建一个创建树的递归函数.每个节点保持一个井字游戏的状态,每个节点的子节点是下一个可能的移动.
我将板的状态传递给递归函数.对于每一个可能的动作,我创建一个状态的副本,然后进行移动.这个新状态被传递给递归函数.
#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)
输出:
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
从print语句可以清楚地看到,对状态所做的更改将被传回到函数的父实例.有谁知道为什么?
问题是,您正在修改类变量,它们将由特定类的所有对象共享.要解决这个问题,make state
和children
实例变量就像这样
class node: def __init__(self,st): self.state = st self.children = [] def addChild(self,child): self.children.append(child) #if only giving birth was this easy
按照这条线,
newState = cState #create copy of state
您正在尝试创建cState
并存储它的副本newState
.请记住,在Python中,赋值运算符永远不会将一个值复制到另一个.它只是在左侧创建变量以指向赋值语句的右侧表达式的求值结果.
所以,你实际做的是,制作两者newState
并cState
指向同一个列表.因此,如果您修改newState
,它也会cState
受到影响.要实际创建列表的副本,可以使用切片运算符,如下所示
newState = cState[:] #create copy of state