python中的min max算法

Question

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

我已经做了最大功能，在其中我打电话min功能。在min函数中，我做了什么？对于最大功能，我只是返回最佳分数。

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

这个网站有极小的职位，即使它是基于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

Answer 3

在最小最大算法， 如何确定当你的函数达到 的树的结束，打破 递归调用避免两个不同的功能。

基本上，你问的是你什么时候到达叶节点。

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

Answer 4

我完全同意relet。但是你也可以考虑这个：

有些时候你也许会认为你正在探索的当前分支值得探索一些。这将需要进一步的启发式应用。我不知道你的问题的解决方案需要多么先进。这是因为我不知道问题来自哪里。

正如Amber所建议的，尝试发布一些代码，以便我们知道您希望解决方案有多复杂。此外，如果您解释了多少/ can_do，那么我们可能会提出更多有用的选项 - 您可能能够切实执行的事情，而不仅仅是您可能不知道如何或有时间的惊人创意执行