如何在 python 中正确实现 n-branching 因子的树？

Question

我正在尝试在 python 中实现极小极大算法，但我在创建分支树结构时遇到了一些问题。我仍然是一个业余程序员，所以请不要介意我的代码看起来很糟糕。这是我的节点结构

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)

在我做的情况下，根节点必须有7children，每个child本身应该有7children。每个 child 都将在 parent 节点中有一个修改后的初始矩阵克隆。

出现的错误是在添加子children（即二级children）后没有被添加到children列表中，而是被添加了改为根节点。

children的创建调用如下。

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

    self.evaluateChildren(2)

    self.evaluateSubChildren(1)

   #more calculations go here

我首先尝试调用相同的 evaluateChildren() 函数，如下所示：

    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()

如果我在评估后检查根节点的 children 的数量，它应该是 7，但是它不断地向它添加更多的 2 级 children，这让我的无限循环中的程序。

请让我知道哪里出错了。请询问是否需要更多信息。

Answer 1

您遇到了 Python 中列表和变量绑定的常见问题 - 您将 children = [] 设为 class 变量，这使得它成为 每个节点中的相同列表。内存中有一个列表，每个节点都指向它。更改它，所有节点都会看到更改。将其移至 __init__ 以使其成为每个实例的新实例。

Class Node:

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

        self.children = []

各种各样的人都被同一个问题绊倒了'many things referencing the exact same list by mistake'，关于正在发生的事情、原因、如何避免的大量讨论：

Python Strange Behavior with List & Append

Weird list behavior in python

Python array weird behavior

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

Nested List Indices

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

如何在 python 中正确实现 n-branching 因子的树？

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

python

algorithm

minimax