Récursivité infinie en Python

Question

La divulgation complète, cela fait partie d'un devoir (bien qu'un petit extrait, le projet lui-même est un jeu en IA).

J'ai cette fonction intégrée dans une classe de nœud de l'arbre:

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 

Sur un arbre de profondeur 1 (une racine et des enfants), il frappe la limite de récursivité Python déjà. La fonction est conçue pour utiliser la programmation dynamique pour construire un arbre min-max de bas en haut. Pour être honnête, je ne sais pas pourquoi cela ne fonctionne pas comme prévu, mais je suis assez nouveau pour Python. Bonnes personnes de Stack Overflow: Pourquoi ce code me donne-t-il un débordement de pile?

Toute la classe en question:

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 

La fonction qui interagit avec ce (S'il vous plaît noter, c'est à la limite sur le bord de ce qui est approprié pour poster ici, je vais retirer cette partie après que je l'accepte une réponse): [Il ne s'est pas avéré être la partie critique de toute façon]

Answer 1

Ce bit de votre code:

class TreeNode: 
    children = [] 

signifie que tous les cas des actions de classe de la même liste children. Donc, dans ce bit:

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

vous ajoutez à la liste "class-global". Donc, bien sûr, chaque nœud est un enfant de tous les autres nœuds, et un désastre est garanti.

Fix: changer votre classe

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 ... 

le reste n'a pas besoin de changer pour corriger ce bug (mais il peut y avoir des possibilités d'améliorer ou corriger d'autres bugs, je ne l'ai pas inspecté en profondeur) , mais ne pas attribuer self.children dans __init__ est à l'origine de votre bug actuel, et ne parvient pas à hériter de object (sauf si vous utilisez Python 3, mais j'espère que vous mentionner ce petit détail si oui ;-) est juste un bug en attente de se produire.

Answer 2

Il ressemble à self.children contient self.

EDIT:

La propriété est en cours d'initialisation children à la même instance de tableau pour chaque instance de la classe TreeNode. Vous devez créer une instance de tableau distincte pour chaque instance TreeNode en ajoutant self.children = [] à __init__. Le tableau board présente le même problème.