我在Python 2.7.11中实现了极小化极大算法，用于一个基本的吃豆人游戏。吃豆人是最大化代理，而一个或多个鬼魂（取决于测试布局）是/是最小化代理。
我必须实现极小化极大算法，以便可能有多个最小化代理，并且能够创建一个n层（深度）的树。例如，第1层将是每个鬼魂轮流最小化它们可能移动的终端状态效用，以及吃豆人轮流最大化鬼魂已经最小化的内容。从图形上看，第1层看起来像这样：
如果我们为绿色终端状态（从左到右）分配以下任意效用值：
-10, 5, 8, 4, -4, 20, -7, 17
吃豆人应该返回-4，然后朝那个方向移动，基于该决定创建一个全新的极小化极大树。首先，这里是一些变量和函数的列表，这些是我实现的关键：
# 存储游戏当前状态的所有信息gameState# 全局定义的深度，根据测试用例变化。
# 它可以小到1，也可以任意大self.depth# 局部定义的深度，用于跟踪我在树中已经深入的层数self.myDepth# 一个函数，为当前状态分配一个数字值作为效用
# 如何计算这一点并不重要self.evaluationFunction(gameState)# 返回一个代理的合法动作列表
# agentIndex = 0 表示吃豆人，鬼魂是 >= 1gameState.getLegalActions(agentIndex)# 返回一个代理采取行动后的后续游戏状态gameState.generateSuccessor(agentIndex, action)# 返回游戏中代理的总数gameState.getNumAgents()# 返回游戏状态是否为赢（终端）状态gameState.isWin()# 返回游戏状态是否为输（终端）状态gameState.isLose()这是我的实现：
""" getAction 接受一个 gameState 并返回吃豆人的最优移动，
假设鬼魂在最小化他的可能性方面是最优的"""def getAction(self, gameState): self.myDepth = 0 def miniMax(gameState): if gameState.isWin() or gameState.isLose() or self.myDepth == self.depth: return self.evaluationFunction(gameState) numAgents = gameState.getNumAgents() for i in range(0, numAgents, 1): legalMoves = gameState.getLegalActions(i) successors = [gameState.generateSuccessor(j, legalMoves[j]) for j, move in enumerate(legalMoves)] for successor in successors: if i == 0: return maxValue(successor, i) else: return minValue(successor, i) def minValue(gameState, agentIndex): minUtility = float('inf') legalMoves = gameState.getLegalActions(agentIndex) succesors = [gameState.generateSuccessor(i, legalMoves[i]) for i, move in enumerate(legalMoves)] for successor in successors: minUtility = min(minUtility, miniMax(successor)) return minUtility def maxValue(gameState, agentIndex) self.myDepth += 1 maxUtility = float('-inf') legalMoves = gameState.getLegalActions(agentIndex) successors = [gameState.generateSuccessor(i, legalMoves[i]) for i, move in enumerate(legalMoves)] for successor in successors: maxUtility = max(maxUtility, miniMax(successor)) return maxUtility return miniMax(gameState)有谁知道为什么我的代码会这样做？我希望有一些极小化极大算法/人工智能专家能找出我的问题。提前感谢。
更新：通过将我的self.myDepth值实例化为0而不是1，我已经消除了异常抛出的问题。然而，我的实现总体上的不正确性仍然存在。
回答：
我终于找到了解决我的问题的方案。主要问题是我没有正确引用depth来跟踪层数。不是在maxValue方法中增加深度，而是应该将其作为参数传递给每个函数，并且仅在传递到maxValue时增加。还有其他几个逻辑错误，比如没有正确引用numAgents，以及我的miniMax方法没有返回动作。这里是我的解决方案，最终证明是有效的：
def getAction(self, gameState): self.numAgents = gameState.getNumAgents() self.myDepth = 0 self.action = Direction.STOP # 从定义5个方向的类中导入 def miniMax(gameState, index, depth, action): maxU = float('-inf') legalMoves = gameState.getLegalActions(index) for move in legalMoves: tempU = maxU successor = gameState.generateSuccessor(index, move) maxU = minValue(successor, index + 1, depth) if maxU > tempU: action = move return action def maxValue(gameState, index, depth): if gameState.isWin() or gameState.isLose() or depth == self.depth: return self.evaluationFunction(gameState) index %= (self.numAgents - 1) maxU = float('-inf') legalMoves = gameState.getLegalActions(index) for move in legalMoves: successor = gameState.generateSuccessor(index, move) maxU = max(maxU, minValue(successor, index + 1, depth) return maxU def minValue(gameState, index, depth): if gameState.isWin() or gameState.isLose() or depth == self.depth: return self.evaluationFunction(gameState) minU = float('inf') legalMoves = gameState.getLegalActions(index) if index + 1 == self.numAgents: for move in legalMoves: successor = gameState.generateSuccessor(index, move) # 增加深度的地方 minU = min(minU, maxValue(successor, index, depth + 1) else: for move in legalMoves: successor = gameState.generateSuccessor(index, move) minU = min(minU, minValue(successor, index + 1, depth) return minU return miniMax(gameState, self.index, self.myDepth, self.action)瞧！我们最终得到了一个有效的多代理极小化极大算法实现。
