蒙特卡洛树搜索Python代码递归深度超限错误原因排查

Hey Kevin, let's break down why you're hitting this RecursionError and fix the underlying issues in your MCTS code:

Your code has an unbroken recursive call chain that never terminates, which blows past Python's default recursion depth limit (usually ~1000). Here's the problematic cycle:

1. root.select() calls leaf.insert()
2. insert() creates child nodes and triggers simulate() on each
3. simulate() calls backpropagation()
4. If we reach the root during backpropagation, you call self.select() again—starting the entire cycle over
5. If we haven't reached the root, backpropagation() calls itself on the parent node, leading to deep recursion until the limit is hit

This is not normal for MCTS. The four stages (Select, Expand, Simulate, Backpropagate) should run iteratively for a fixed number of simulations, not recursively chain into infinite loops.

Beyond the infinite recursion, there are several logic flaws that will break your MCTS even if you fix the recursion issue:

1. Global puct_array Causes Invalid Selections #

Your puct_array is a global variable that never gets cleared. Every time find_best_path runs, it appends new PUCT values to the same array—so np.argmax will eventually pick from a mix of old and new node values, which completely breaks the selection logic.

Fix this by making puct_array a local variable inside find_best_path:

def find_best_path(parent):
    if parent == root or len(parent.nodes) == 0:
        return parent
    puct_array = []  # Reset array for each selection
    for N in parent.nodes:
        puct_array.append(N.puct)
    max_index = np.argmax(puct_array)
    child_node = parent.nodes[max_index]
    if len(child_node.nodes) == 0:
        return child_node
    return find_best_path(child_node)  # Recurse to find the actual leaf node

Note: I also fixed the end of this function—your original code returned the child node immediately without recursing further, so it would never reach deep leaf nodes.

2. compute_total_win_and_visits Fails to Accumulate Values #

This function uses value-based parameter passing, so the total_win and visits variables don't actually accumulate across recursive calls. You need to use return values to sum up child node stats:

def compute_total_win_and_visits(self):
    total_win = self.win
    visits = self.visit
    for n in self.nodes:
        child_win, child_visits = n.compute_total_win_and_visits()
        total_win += child_win
        visits += child_visits
    return total_win, visits

3. Backpropagation Termination & Logic Errors #

• Your root node check is wrong: the root has parent == 0, but you check if self.parent == root:—this will never trigger, so backpropagation will overshoot the root or loop infinitely.
• You call self.select() inside backpropagation, which is what causes the infinite cycle. Backpropagation should only update node stats, not trigger a new selection.
• The loss calculation uses bitwise ~ which doesn't do what you think (e.g., ~1 is -2 in Python). Use logical checks instead.

Here's a simplified fixed backpropagation method:

def backpropagation(self, win_result):
    # Update current node first
    self.visit += 1
    self.win += win_result
    
    # Recurse up to parent if not root
    if self.parent != 0:
        # Pass the result adjusted for player turn (if needed)
        self.parent.backpropagation(win_result)

The best way to avoid recursion limits is to run MCTS in an iterative loop for a fixed number of simulations, rather than letting stages recursively trigger each other. Here's how your main code should look:

root = Mcts(0)
num_simulations = 1000  # Adjust based on your needs

for _ in range(num_simulations):
    # 1. Select: Find the best leaf node
    leaf = find_best_path(root)
    
    # 2. Expand: Add child nodes to the leaf
    leaf.insert()
    
    # 3. Simulate: Run random playouts on new children
    for child in leaf.nodes:
        child.simulate()
    
    # 4. Backpropagate: Update stats from leaf to root
    # (Adjust your simulate/backprop logic to trigger this after simulation)

The RecursionError is a symptom of a broken call chain, not an expected behavior for MCTS. Once you fix the infinite recursion and the other logic bugs I outlined, your code should be able to run without hitting recursion limits.

内容的提问来源于stack exchange，提问作者kevin998x