Python中的最小最大算法

Question

在最小最大算法中，如何判断你的函数何时到达树的末端，并停止递归调用。

我写了一个最大值函数，在这个函数里我调用了最小值函数。那么在最小值函数中，我该怎么做呢？对于最大值函数，我只是返回了最佳分数。

def maxAgent(gameState, depth):
      if (gameState.isWin()):
        return gameState.getScore()
      actions = gameState.getLegalActions(0);
      bestScore = -99999
      bestAction = Directions.STOP

      for action in actions:
        if (action != Directions.STOP):
          score = minAgent(gameState.generateSuccessor(0, action), depth, 1)
          if (score > bestScore):
            bestScore = score
            bestAction = action
      return bestScore

def minvalue(gameState,depth,agentIndex):
       if (gameState.isLose()):
         return gameState.getScore()
       else:
         finalstage = False
         number = gameState.getNumAgents()
         if (agentIndex == number-1):
           finalstage = True
           bestScore = 9999
           for action in gameState.getLegalActions(agentIndex):
             if(action != Directions.STOP

我现在不知道该怎么继续了？我不能设置树的深度限制，这个深度必须是任意的。

Answer 1

我完全同意relet的看法。不过你可能还想考虑以下几点：

有时候，你可能会觉得当前正在研究的分支值得更深入地探索。这时候就需要应用一些额外的经验法则。我不太清楚你问题的解决方案需要多复杂，因为我不知道问题的来源是什么。

正如Amber所建议的，试着发一些代码，这样我们就能知道你希望解决方案有多复杂。此外，如果你能解释一下你知道多少或者能做到什么，我们可能能给出更有用的建议——那些你实际上能够实现的选项，而不是一些你可能不知道怎么做或者没有时间去实现的炫酷想法。

Answer 2

在最小最大算法中，如何判断你的函数何时到达树的末端，并停止递归调用。

其实，你是在问什么时候到达了叶子节点。

叶子节点就是你已经达到搜索的最大深度，或者是一个终止节点（也就是游戏结束的位置）。

Answer 3

通常情况下，当你在进行某种搜索时，比如下棋时，你可能只想搜索到一定的深度（比如提前考虑n步）。所以，你应该把当前的搜索深度作为一个参数传递。这样，如果你发现结果没有改善，且判断这个情况不需要太多努力，你可以提前停止搜索。