Бесконечная рекурсия в Python

Question

Полное раскрытие, это часть домашнего задания (хотя это небольшой фрагмент, сам проект - игра, играющая в AI).

У меня есть эта функция, встроенная в класс узлов дерева:

    def recursive_score_calc(self):
        current_score = self.board
        for c in self.children:
            child_score = c.recursive_score_calc()
            if(turn_color == 1):
                if(child_score > current_score):
                    current_score = child_score
            else:
                if(child_score < current_score):
                    current_score = child_score
        self.recursive_score = current_score
        return current_score

На дереве глубины 1 (корень и некоторые дочерние элементы) оно уже достигает предела рекурсии Python. Функция предназначена для использования динамического программирования для построения дерева мин-макс снизу вверх. Честно говоря, я понятия не имею, почему это работает не так, как задумано, но я и новичок в Python.

Хорошие люди из переполнения стека: почему этот код дает мне переполнение стека?

Весь рассматриваемый класс:

from Numeric import *

class TreeNode:
    children = []
    numChildren = 0
    board = zeros([8,8], Int)
    turn_color = 0 # signifies NEXT to act
    board_score = 0 # tally together board items
    recursive_score = 0 # set when the recursive score function is called

def __init__(self, board, turn_color):
    self.board = copy.deepcopy(board)
    self.turn_color = turn_color
    for x in range (0,7):
        for y in range (0,7):
            self.board_score = self.board_score + self.board[x][y]

def add_child(self, child):
    self.children.append(child)
    self.numChildren = self.numChildren + 1

def recursive_score_calc(self):
    current_score = self.board # if no valid moves, we are the board. no move will make our score worse
    for c in self.children:
        child_score = c.recursive_score_calc()
        if(turn_color == 1):
            if(child_score > current_score):
                current_score = child_score
        else:
            if(child_score < current_score):
                current_score = child_score
    self.recursive_score = current_score
    return current_score

Функция, которая взаимодействует с этим (обратите внимание, это граничит с краем того, что уместно для публикации здесь, я удалю эту часть после того, как приму ответ): критическая часть в любом случае]

Answer 1

Этот бит вашего кода:

class TreeNode:
    children = []

означает, что каждый экземпляр класса имеет один и тот же список children.Итак, в этом бите:

def add_child(self, child):
    self.children.append(child)

вы добавляете в глобальный список классов.Поэтому, конечно, каждый узел является дочерним по отношению к любому другому узлу, и катастрофа гарантирована.

Исправлено: измените свой класс на

class TreeNode(object):
    numChildren = 0
    board = zeros([8,8], Int)
    turn_color = 0 # signifies NEXT to act
    board_score = 0 # tally together board items
    recursive_score = 0 # set when the recursive score function is called

def __init__(self, board, turn_color):
    self.children = []
    self.board = copy.deepcopy(board)
    self.turn_color = turn_color
... etc, etc ...

, остальные не нужно менять наисправить эту ошибку (хотя могут быть возможности для ее исправления или исправления других ошибок, я не проверил ее глубоко), но невозможность присвоить self.children в __init__ вызывает вашу текущую ошибку и не наследуется от object(если вы не используете Python 3, но я надеюсь, что вы упомянете эту маленькую деталь, если так ;-) - это просто ошибка, ожидающая своего появления.

Answer 2

Похоже, что self.children содержит self.

EDIT :

Свойство children инициализируется в один и тот же экземпляр массива для каждого экземпляракласса TreeNode.

Необходимо создать отдельный экземпляр массива для каждого экземпляра TreeNode, добавив self.children = [] к __init__.
Массив board имеет ту же проблему.