python中的最小最大算法

Question

在 minmax 算法中，如何确定函数何时到达树的末尾并中断递归调用。

我创建了一个 max 函数，在其中调用 min 函数。在 min 函数中，我应该做什么？对于 max 函数，我只是返回最好成绩。

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

通常你想要搜索直到某个递归深度（例如，下棋时提前 n 步）。因此，您应该将当前递归深度作为参数传递。当您的结果没有改善时，如果您可以毫不费力地确定这一点，您可以提前终止。

Answer 2

在minmax算法中，如何
确定你的函数何时达到
树的末端并打破
递归调用。

基本上，您是在询问何时到达叶节点。

当您达到搜索的最大深度时，就会出现叶节点，或者出现终端节点（即结束游戏的位置）。

Answer 3

我完全同意转租。但您可能还想考虑这一点：

有时您可能还认为您正在探索的当前分支值得更深入地探索。这将需要应用一些进一步的启发式方法。我不知道您的问题的解决方案需要多先进。这是因为我不知道问题出在哪里。

按照 Amber 的建议，尝试发布一些代码，以便我们知道您希望解决方案的复杂程度。此外，如果您解释了您知道/可以做多少，那么我们也许能够建议更有用的选项 - 您可能能够实际实现的事情，而不仅仅是您可能不知道如何或没有时间实现的惊人想法实施

Answer 4

这个网站有 minimax 的帖子，尽管它是基于 IronPython 的：
http://blogs.microsoft.co.il/blogs/dhelper/archive/2009/07/13/getting-started-with-ironpython-part-4-minimax-algorithm.aspx

nofollow 说：

Minimax 算法本质上是递归的，因此它需要一个停止条件，在我们的例子中，要么游戏已经结束（不再移动），要么已经达到所需的深度（第 3-8 行）。

您可以通过使用 Negamax http://en.wikipedia.org/wiki/Negamax< /a>