基于Minimax算法的回合制格斗游戏递归超限问题求助

问题描述 #

首次运行Minimax算法实现的回合制格斗游戏正常，第二次运行触发RecursionError: maximum recursion depth exceeded while calling a Python object，已应用Alpha-Beta剪枝但问题未解决。

核心问题排查 #

你的代码存在两个关键问题：

• 状态未回溯：递归调用时直接修改了实例变量self.attack和self.defend，但没有在递归返回后恢复原状态。第二次运行时，这些变量保留了上一次的修改，导致游戏状态异常，递归终止条件（is_winning/is_draw）无法触发，递归持续进行直到超出深度限制。
• 状态修改逻辑顺序：在未检查终止条件的情况下先修改状态，可能导致部分场景下终止条件判断基于已修改的错误状态，进一步加剧递归无法终止的问题。

修复方案 #

1. 实现状态回溯（核心修复） #

在递归调用前后保存并恢复实例变量，避免跨调用的状态污染：

def minimax(self, depth, is_maximizing, alpha, beta):
    # 先检查终止条件，确保无效递归提前终止
    if depth == 0 or self.is_winning(self.computer) or self.is_winning(self.player) or self.is_draw():
        if self.is_winning(self.computer):
            return self.computer_score - depth
        if self.is_winning(self.player):
            return -self.player_score + depth
        if self.is_draw():
            return 0

    if is_maximizing:
        best_value = float('-inf')
        # 保存原始攻击状态
        original_attack = self.attack
        for move in ["slash", "thrust"]:
            self.attack = move
            value = self.minimax(depth - 1, False, alpha, beta)
            best_value = max(best_value, value)
            alpha = max(alpha, best_value)
            if beta <= alpha:
                break
        # 恢复原始攻击状态
        self.attack = original_attack
        return best_value
    else:
        best_value = float('inf')
        # 保存原始防御状态
        original_defend = self.defend
        for move in ["block", "dodge"]:
            self.defend = move
            value = self.minimax(depth - 1, True, alpha, beta)
            best_value = min(best_value, value)
            beta = min(beta, best_value)
            if beta <= alpha:
                break
        # 恢复原始防御状态
        self.defend = original_defend
        return best_value

2. 优化终止条件验证 #

单独测试is_winning和is_draw函数，确保它们能准确识别游戏结束状态——如果这些函数逻辑错误，也会导致递归无法触发终止条件。

3. 临时调整递归深度（可选） #

如果游戏确实需要更深的递归层级，可以临时调整Python的递归深度限制，但这只是应急方案，优先修复状态回溯问题：

import sys
sys.setrecursionlimit(10000)  # 根据实际需求调整数值

额外建议 #

• 避免直接修改实例变量模拟游戏状态，建议使用不可变状态参数（如将状态作为参数传递而非修改self），从根源避免状态污染。
• 添加调试日志，在递归时输出当前深度、is_winning/is_draw的返回值，快速定位无法终止的分支。

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