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，那麼我們可能會提出更多有用的選項 - 您可能能夠切實執行的事情，而不僅僅是您可能不知道如何或有時間的驚人創意執行