min max algorithm in python

Question

In the minmax algorithm,How to determine when your function reaches the end of the tree and break the recursive calls.

I have made a max function in which I am calling the min function. In the min function , what shud I do?? For max function, I am just returning the bestscore.

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

I could not understand how to proceed now?I not allowed to set the limit of depth of tree. it has to be arbitrary.

Answer 1

Usually you want to search until a certain recursion depth (e.g. n moves in advance, when playing chess). Therefore, you should pass the current recursion depth as a parameter. You may abort earlier when your results do not improve, if you can determine that with little effort.

Answer 2

This site has post of minimax, even though it is based on IronPython: http://blogs.microsoft.co.il/blogs/dhelper/archive/2009/07/13/getting-started-with-ironpython-part-4-minimax-algorithm.aspx

It says:

The Minimax algorithm is recursive by nature, and as such it requires a stop condition, in our case either the game has ended (no more moves) or the desired depth has been reached (lines 3-8).

You can avoid having two different functions by using Negamax http://en.wikipedia.org/wiki/Negamax

Answer 3

In the minmax algorithm,How to determine when your function reaches the end of the tree and break the recursive calls.

Basically, you're asking when you've reached a leaf node.

A leaf node occurs when you've reached the maximum depth for the search, or a terminal node (i.e. a position that ends the game).

Answer 4

I completely agree with relet. But you might want to consider this also:

There are times when you might also think that the current branch that you are exploring is worth exploring a little deeper. This will call for some further heuristics to be applied. I don't know how advanced the solution for your problem is required to be. This is because I don't know where the problem is coming from.

As suggested by Amber, try posting some code so we know how complex you want the solution to be. Further, if you explained how much you know/can_do, then we might be able to suggest more useful options - things that you might be able to realistically implement, rather than just amazing ideas that you may not know how to or have the time to implement