Pacman，Alpha-Beta 剪枝扩展了太多节点

Question

更新2：在使用笔和纸检查测试用例并将其与自动评分器的测试进行比较，以及测试代码的其他部分以确保修剪正在发生之后，我相当确定自动评分器正在出问题，这代码实际上是 alpha-beta 修剪的一个正常工作的示例，这也许也是为什么尽管有近 30 次浏览却没有人发布答案的原因。不确定我现在要做什么，我想把它全部拆掉并构建一个全新的解决方案，并希望自动平地机这次让它滑行。我会保留这个，因为我很想知道自动评分器专门出于我自己的好奇心而叽叽喳喳地说了什么，或者万一我错了并且这段代码在某种程度上是不正确的。

更新：在对此进行了更多的困惑之后，我认为问题可能是我在检查 minVal() 和 maxVal() 函数之前生成了下一组状态，并且也许自动评分器将其读取为过多的状态生成。我修复了这个问题，如下所示：

def minVal(self, state, depth, agentIndex, alpha, beta):
    v = float('inf')
    #Keeping track of agents and depth.
    newAgent = agentIndex + 1
    if newAgent == state.getNumAgents():
        newAgent = 0
    newDepth = depth
    if newAgent == 0:
        newDepth = depth - 1
    #Generating new states
    for action in state.getLegalActions(agentIndex):
        v = min(v,self.minimax(state.generateSuccessor(agentIndex,action), newDepth, newAgent,alpha, beta))
        if v < alpha:
            return v
        beta = min(beta,v)
    return v

def maxVal(self, state, depth, agentIndex, alpha, beta):
    v = float('-inf')
    #Generating new states.
    for action in state.getLegalActions(agentIndex):
        v = max(v, self.minimax(state.generateSuccessor(agentIndex,action), depth, agentIndex+1, alpha, beta))
        if v > beta:
            return v
        alpha = max(alpha,v)
    return v

不幸的是，这没有导致任何改变，我仍然遇到同样的错误。

我正在尝试完成伯克利吃豆人项目的第二个吃豆人项目。第二个项目是在极小极大上。我的极小极大解决方案工作完美，并被自动评分器接受，但它声称我的 alpha-beta 剪枝算法扩展了太多节点，在对其进行了一番思考并对照在线资源进行检查后，我完全不知道为什么，对我来说这似乎是该算法的正确实现。

我的实现：

class AlphaBetaAgent(MultiAgentSearchAgent):
    """
    Your minimax agent with alpha-beta pruning (question 3)
    """
    def minimax(self, state, depth, agentIndex, alpha, beta):
        if depth == 0 or state.isWin() or state.isLose():
            return self.evaluationFunction(state)
        if agentIndex == 0:
            return self.maxVal(state, depth, agentIndex,alpha, beta)
        else:
            return self.minVal(state, depth, agentIndex, alpha, beta)
        
    def minVal(self, state, depth, agentIndex, alpha, beta):
        v = float('inf')
        #Keeping track of agents and depth.
        newAgent = agentIndex + 1
        if newAgent == state.getNumAgents():
            newAgent = 0
        newDepth = depth
        if newAgent == 0:
            newDepth = depth - 1
        #Generating new states
        newStates = []
        for action in state.getLegalActions(agentIndex):
            newStates.append(state.generateSuccessor(agentIndex,action))
        #Iterating over new states
        for newState in newStates:
            v = min(v,self.minimax(newState, newDepth, newAgent,alpha, beta))
            if v < alpha:
                return v
            beta = min(beta,v)
        return v

    def maxVal(self, state, depth, agentIndex, alpha, beta):
        v = float('-inf')
        #Generating new states.
        newStates = []
        for action in state.getLegalActions(agentIndex):
            newStates.append(state.generateSuccessor(agentIndex,action))
        #Iterating over new states.
        for newState in newStates:
            v = max(v, self.minimax(newState, depth, agentIndex+1, alpha, beta))
            if v > beta:
                return v
            alpha = max(alpha,v)
        return v
    
    def getAction(self, gameState):
        """
        Returns the minimax action using self.depth and self.evaluationFunction
        """
        "*** YOUR CODE HERE ***"
        alpha = float('-inf')
        beta = float('inf')
        legalActions = []
        for action in gameState.getLegalActions(0):
            legalActions.append(action)
        valuedStates = []
        for action in legalActions:
           valuedStates.append(self.minimax(gameState.generateSuccessor(0,action),self.depth,1,alpha,beta))
        ind = valuedStates.index(self.minimax(gameState,self.depth,0,alpha,beta))
        return legalActions[ind]

根据我所看到的情况，我认为这是一种有点不寻常的方法，特别是 getAction() 中的部分，我实际上是第二次调用 minimax 以检索操作本身。然而，这是有效的，因为自动评分器接受了我对上一个关于极小极大问题的解决方案。对第二个问题所做的唯一更改是那些直接与 alpha-beta 修剪相关的更改，在这里我完全遵循了该算法。

我在这里无计可施，不知道为什么这会扩大太多的州。我尝试过的一些事情：

1. 我尝试注释掉再次调用 minimax 的部分，以便找到要返回的操作。我希望这至少能查明扩展太多州的问题，但没有骰子，自动评分器仍然抱怨我扩展了太多州，并声称我正在扩展的州与之前的状态相同。
2. 尝试将 alpha / beta 比较更改为 >= 和 <= , based on the notion that only rejecting > 和 < was too lenient. Again no dice, exact same complaint from the autograder.

我想知道这里是否有人能够看到这个问题，我也向我的教授展示了代码，但他在查看代码时无法注意到任何问题，并说他需要更多时间来检查它。我真的很想了解为什么这不起作用，而不是我希望修复它。

Answer 1

经过一天的工作，我解决了自己的问题，我想为其他参与这些项目的学生回答我自己的问题，他们可能会找到此页面。

问题最终出在 getAction() 中第二次运行 minimax 并使用值索引来找到最佳操作的部分。原因是因为自动评分器出于某种原因对于代码调用generateSuccessor()的次数极其敏感。如果你这样做，它会指责你生成了太多状态。然而，由于两个原因，这个投诉变得更加令人困惑：

1. 自动评分器对此不一致。正如我在 OP 中所说，这种策略对于极小极大问题来说是没问题的，但突然间对 alpha-beta 剪枝产生了疑问。我想它也会对 Expectimax 产生争议。如果您的极小极大代码被接受，这种不一致可能会诱使您产生错误的安全感，使您合理地认为只需进行一些细微的更改就可以使其接受 alpha-beta 剪枝。不幸的是，情况并非如此。
2. 自动评分器将通过提出其他虚假投诉来掩盖此投诉。就我而言，它告诉我我正在生成节点，但事实并非如此。事实上，它真正的问题只是我调用了generateSuccessor()太多次，但是这个问题被自动评分器关于不存在的错误的抱怨所掩盖。

无论如何，修复方法是重新设计代码，以便调用generateSuccessor()的次数永远不会超过绝对最低必要次数。为此，我重新设计了最大化器，以便它也返回操作。这需要稍微重新设计所有函数，但最相关的两个是 getAction( ) 和最大化器，我将其称为 maxVal( )。这是重新设计的 getAction( ):

def getAction(self, gameState):
        """
        Returns the minimax action using self.depth and self.evaluationFunction
        """
        "*** YOUR CODE HERE ***"
        alpha = float('-inf')
        beta = float('inf')

        return self.minimax(gameState,0,0,alpha,beta)

这里是 maxVal( ):

def maxVal(self, state, depth, agentIndex, alpha, beta):
        v = float('-inf')
        #Generating new states.
        returnAct = Directions.STOP
        highestVal = float('-inf')
        for action in state.getLegalActions(agentIndex):
            v = self.minimax(state.generateSuccessor(agentIndex,action), depth, agentIndex+1, alpha, beta)
            if v > highestVal:
                highestVal = v
                returnAct = action
            if highestVal > beta:
                return highestVal
            alpha = max(alpha,v)
        if depth == 0:
            return returnAct
        else:
            return highestVal

我还对辅助函数（不是必需的，但我喜欢它）和最小化器做了一些小的更改。不过，发布这些内容会堵塞已经很长的帖子。

我希望这可以帮助将来遇到类似问题的人。