python - 极小极大递归超时

Question

我正在尝试为 pacman 游戏编写 minimax 算法。我的递归有问题 - 有时我的算法“有效”（它不会崩溃，但仍然返回错误的值），然后有时它会崩溃并给我一个递归错误，说超出了最大递归深度。有人可以阐明我在这里做错了什么吗？谢谢！

 def minimax(self, gamestate, depth, agent):
        if depth == self.depth or gamestate.isWin() or gamestate.isLose():
            return self.evaluationFunction(gamestate), Directions.STOP
        best_move = None

        if agent == 0: ## Pacman is max
            best_val = float('-inf')
        else: ## ghosties are min
            best_val = float('inf')

        actions = gamestate.getLegalActions(agent)
        for action in actions:
            next_agent = agent + 1  ## quit moving me! ## this goes here to set next_agent to be same as agent each iteration, because it also gets changed below
            successor = gamestate.generateSuccessor(agent, action) ## generate successors gamestate (ie new board)
            if next_agent == gamestate.getNumAgents():
                next_agent = 0  ## Once we reach the last agent, set back to 0
                depth += 1  ## increment depth

            v = self.minimax(successor, depth, next_agent)

            ## here is where we set the max and min values based on the agent
            if agent == 0: ## pacman - max
                if v > best_val:
                    best_val = v
                    best_move = action
            else: ## ghost - min
                if v < best_val:
                    best_val = v
                    best_move = action
        return best_move, best_val

标签： pythonalgorithmrecursionminimaxminmax