Why is My Minimax Not Expanding and Making Moves Correctly?
<p>I am implementing minimax in Python 2.7.11 in a basic game of Pacman. Pacman is the maximizing agent, and one or more ghosts (depending on the test layout) is/are the minimizing agent(s). </p>

<p>I must implement minimax so that there can be potentially <strong><em>more than one</em></strong> minimizing agent, and so that it can create a tree of <strong>n plies</strong> (depth). Ply 1, for example, would be each ghost taking a turn minimizing the terminal state utilities of their possible moves, as well as pacman taking his turn maximizing what the ghosts have already minimized. Graphically, ply 1 looks like this:</p>

<p><a href="https://i.stack.imgur.com/wEJ0N.png" rel="noreferrer"><img src="https://i.stack.imgur.com/wEJ0N.png" alt="Ply 1 depth of minimax"></a></p>

<p>If we had the following arbitrary utilities assigned to the green terminal states (left to right): </p>

<p><code>-10, 5, 8, 4, -4, 20, -7, 17</code> </p>

<p>Pacman should return <code>-4</code> and then move in that direction, creating an entirely new minimax tree based on that decision.
First, a list of variables and functions needed for my implementation to make sense:</p>

<pre><code># Stores everything about the current state of the game
gameState

# A globally defined depth that varies depending on the test cases.
#     It could be as little as 1 or arbitrarily large
self.depth

# A locally defined depth that keeps track of how many plies deep I've gone in the tree
self.myDepth

# A function that assigns a numeric value as a utility for the current state
#     How this is calculated is moot
self.evaluationFunction(gameState)

# Returns a list of legal actions for an agent
#     agentIndex = 0 means Pacman, ghosts are &gt;= 1
gameState.getLegalActions(agentIndex)

# Returns the successor game state after an agent takes an action
gameState.generateSuccessor(agentIndex, action)

# Returns the total number of agents in the game
gameState.getNumAgents()

# Returns whether or not the game state is a winning (terminal) state
gameState.isWin()

# Returns whether or not the game state is a losing (terminal) state
gameState.isLose()
</code></pre>

<p><strong>This is my implementation:</strong></p>

<pre><code>""" 
getAction takes a gameState and returns the optimal move for pacman,
assuming that the ghosts are optimal at minimizing his possibilities
"""
def getAction(self, gameState):
    self.myDepth = 0

    def miniMax(gameState):
        if gameState.isWin() or gameState.isLose() or self.myDepth == self.depth:
            return self.evaluationFunction(gameState)

        numAgents = gameState.getNumAgents()
        for i in range(0, numAgents, 1):
            legalMoves = gameState.getLegalActions(i)
            successors = [gameState.generateSuccessor(j, legalMoves[j]) for j, move 
                                                           in enumerate(legalMoves)]
            for successor in successors:
                if i == 0:
                    return maxValue(successor, i)
                else:
                    return minValue(successor, i)

    def minValue(gameState, agentIndex):
        minUtility = float('inf')
        legalMoves = gameState.getLegalActions(agentIndex)
        succesors = [gameState.generateSuccessor(i, legalMoves[i]) for i, move 
                                                      in enumerate(legalMoves)]
        for successor in successors:
            minUtility = min(minUtility, miniMax(successor))

        return minUtility

    def maxValue(gameState, agentIndex)
        self.myDepth += 1
        maxUtility = float('-inf')
        legalMoves = gameState.getLegalActions(agentIndex)
        successors = [gameState.generateSuccessor(i, legalMoves[i]) for i, move
                                                       in enumerate(legalMoves)]
        for successor in successors:
            maxUtility = max(maxUtility, miniMax(successor))

        return maxUtility

    return miniMax(gameState)
</code></pre>

<p>Does anyone have any ideas why my code is doing this? I'm hoping there are a few Minimax/Artificial Intelligence experts out there that can identify my issues.
Thanks in advance.</p>

<p><strong>UPDATE:</strong> by instantiating my <code>self.myDepth</code> value as <code>0</code> instead of <code>1</code>, I have irradicated the exception throwing issue. However, the overall incorrectness of my implementation still remains.</p>