Почему My Minimax не расширяется и делает правильные движения?

Question

Я реализую минимакс в Python 2.7.11 в основной игре Pacman. Pacman - агент максимизации, и один или несколько призраков (в зависимости от тестового макета) являются/являются минимизирующим агентом (агентами).

я должен реализовать минимакса, так что может быть потенциально более чем один минимизируя агента, и таким образом, что он может создать дерево п курсирует (глубина). Например, Ply 1 был бы каждым призраком, который делал бы поворот, сводя к минимуму утилиты терминального состояния их возможных ходов, а также pacman, делающий свою очередь, максимизируя то, что призраки уже свернули. Графически слойные 1 выглядит следующим образом:

Если мы следующие произвольные утилиты, назначенные на зеленые терминальные состояния (слева направо):

-10, 5, 8, 4, -4, 20, -7, 17

Pacman должен вернуть -4 и затем двигайтесь в этом направлении, создавая совершенно новое минимаксное дерево, основанное на этом решении. Во-первых, список переменных и функций, необходимых для моей реализации, чтобы понять:

# 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 >= 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() 

Это моя реализация:

""" 
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) 

Кто-нибудь есть какие-либо идеи, почему мой код делает это? Я надеюсь, что есть несколько экспертов Minimax/Artificial Intelligence, которые могут идентифицировать мои проблемы. Спасибо заранее.

UPDATE: по инстанцированию моего self.myDepth значения, как 0 вместо 1, я irradicated вопроса исключения метания. Однако общая некорректность моей реализации все еще остается.

Answer 1

Я, наконец, выяснил решение моей проблемы. Основная проблема заключалась в том, что я неправильно ссылался на depth, чтобы отслеживать слои. Вместо увеличения глубины в методе maxValue он должен быть передан как параметр каждой функции и только увеличивается при передаче в maxValue. Было также несколько других логических ошибок, таких как неверное обращение numAgents, а также тот факт, что мой метод miniMax не возвращал действие. Вот мое решение, которое оказалось для работы:

def getAction(self, gameState): 

    self.numAgents = gameState.getNumAgents() 
    self.myDepth = 0 
    self.action = Direction.STOP # Imported from a class that defines 5 directions 

    def miniMax(gameState, index, depth, action): 
     maxU = float('-inf') 
     legalMoves = gameState.getLegalActions(index) 
     for move in legalMoves: 
      tempU = maxU 
      successor = gameState.generateSuccessor(index, move) 
      maxU = minValue(successor, index + 1, depth) 
      if maxU > tempU: 
       action = move 
     return action 

    def maxValue(gameState, index, depth): 
     if gameState.isWin() or gameState.isLose() or depth == self.depth: 
      return self.evaluationFunction(gameState) 

     index %= (self.numAgents - 1) 
     maxU = float('-inf') 
     legalMoves = gameState.getLegalActions(index) 
     for move in legalMoves: 
      successor = gameState.generateSuccessor(index, move) 
      maxU = max(maxU, minValue(successor, index + 1, depth) 
     return maxU 

    def minValue(gameState, index, depth): 
     if gameState.isWin() or gameState.isLose() or depth == self.depth: 
      return self.evaluationFunction(gameState) 

     minU = float('inf') 
     legalMoves = gameState.getLegalActions(index) 
     if index + 1 == self.numAgents: 
      for move in legalMoves: 
       successor = gameState.generateSuccessor(index, move) 
       # Where depth is increased 
       minU = min(minU, maxValue(successor, index, depth + 1) 
     else: 
      for move in legalMoves: 
       successor = gameState.generateSuccessor(index, move) 
       minU = min(minU, minValue(successor, index + 1, depth) 
     return minU 

    return miniMax(gameState, self.index, self.myDepth, self.action) 

И presto! Наша окончательная работа с минимальным внедрением нескольких агентов.