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

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

- Shilpa

---

你可能想展示一些实际的代码。 - Amber

你应该分享你目前所拥有的。 - Hamish Grubijan

仅仅是风格上的建议：在你有 else: finalstage = False 的代码行处，你确实需要使用一个 else 子句，因为整个函数的剩余部分都在 else 里面。我通常会写一些类似于 #else ... 的注释，然后继续而不需要额外增加一个缩进级别。 - Hamish Grubijan

这个else不是问题。我需要知道如何实现最小值函数。 - Shilpa

Answer 1

通常您希望搜索到特定的递归深度（例如，在下棋时向前n步）。因此，您应将当前递归深度作为参数传递。如果您能轻松确定结果不会改善，可以更早地中止搜索。

- relet

---

但我需要通过评估函数找到最后一阶段的分数。我该怎么做？我不允许设置任何深度限制。 - Shilpa

我认为我可以对Alpha-Beta剪枝算法进行修改，但这并不是那么高级的算法。 - Shilpa

Answer 2

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

基本上，您是在询问何时已经到达了一个叶子节点。

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

- Shaggy Frog

Answer 3

我完全同意relet的观点。但你可能也想考虑以下内容：

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

正如Amber建议的那样，尝试发布一些代码，以便我们知道你需要多复杂的解决方案。此外，如果你解释了你知道/能做多少，那么我们可能能够提供更有用的选项——那些你可能真正能够实现的东西，而不仅仅是你可能不知道如何或没有时间实现的惊人想法。

- inspectorG4dget

Answer 4

这个网站有极小化算法的文章，尽管它是基于IronPython: http://blogs.microsoft.co.il/blogs/dhelper/archive/2009/07/13/getting-started-with-ironpython-part-4-minimax-algorithm.aspx

文章中说:

极小化算法本质上是递归的，因此它需要一个停止条件，在我们的情况下，要么游戏结束(没有更多的移动)，要么达到了所需的深度(第3-8行)。

您可以使用Negamax http://en.wikipedia.org/wiki/Negamax 来避免拥有两个不同的函数

- Tony Veijalainen

---

我们可以把negamax函数用于简单的minmax算法吗？我之后需要做alpha-beta剪枝。 - Shilpa