Pacman AI - Минимаксное приложение - Избежание повторяющихся состояний дерева игры - PullRequest
Новая
       37

Pacman AI - Минимаксное приложение - Избежание повторяющихся состояний дерева игры

1 голос
/ 31 октября 2019

В контексте проекта, следуя проекту UC Berkley pacman ai (его вторая часть), я хочу реализовать минимаксный алгоритм, без альфа-бета-отсечения, для агента соперника в достаточно малой компоновке, чтобы рекурсия непроблема.

Определив задачу как игру с 2 игроками (мы предполагаем, что у нее только 1 призрак), игра с нулевым результатом и идеальной информацией с применением рекурсии была бы довольно тривиальной. Тем не менее, поскольку многие разные стратегии могут оказаться в одном и том же игровом состоянии (определяемом как кортеж позиции Пакмана, позиции призрака, позиции еды и игрока, играющего в данный момент), я хотел найти способ избежать пересчета всех этих состояний.

Я искал и читал кое-что о таблицах транспонирования. Однако я не совсем уверен, как использовать такой метод, и я подумал, что должен реализовать следующее: каждый раз, когда состояние, еще не посещенное, расширяется, добавляйте его в набор «посещенных». Если состояние уже было расширено, то если это максимальный ход игрока (pacman), верните значение + inf (которое обычно никогда не будет выбрано минимальным игроком), если его ход за минутой вернет -inf соответственно.

Проблема с этой идеей, я думаю, и причина, по которой она работает для некоторых макетов, но не для других, заключается в том, что когда я нажимаю на узел, все дочерние элементы которого уже раскрыты, единственные значения, которые я должен выбрать, это+/- бесконечности. Это заставляет бесконечное значение распространяться вверх и выбираться, хотя на самом деле возможно, что это игровое состояние приведет к проигрышу. Я думаю, я понял проблему, но я не могу найти способ обойти ее.

Есть ли какой-нибудь другой метод, который я мог бы использовать, чтобы избежать вычисления повторяющихся состояний игры? Есть ли стандартный подход к этому, о котором я не знаю?

Вот какой-то псевдокод: 

 def maxPLayer(currentState, visitedSet):
     if not isTerminalState
         for nextState, action in currentState.generateMaxSuccessors()
             if nextState not in visitedSet
                mark nextState as visited
                scores = scores + [minPlayer(nextState, visitedSet)]
         if scores is not empty
            return bestScore = max(scores)
         else
            return +inf              #The problem is HERE!
     else
         return evalFnc(currentState)
 end MaxPlayer

def minPlayer(currenstState, visitedSet):
    if not isTerminal
        for nextState, action in generateMinSuccessors()
            if nextState not in visitedSet 
                mark nextState as visited
                scores = scores + [maxPLayer(nextState, visitedSet)]
        if scores is not empty
            return bestScore = min(scores)
        else
            return -inf            #The problem is also HERE!
    else
        return evalFnc(currentState)
   end MinPlayer

Обратите внимание, что первый игрок, который будет играть, это Макс, и я выбираю действие, которое имеетсамый высокий балл. Ничего не меняется, если я принимаю во внимание бесконечные значения или нет, все еще есть случаи, когда агент проигрывает или повторяет бесконечно.

1 Ответ

2 голосов
/ 31 октября 2019

Я думаю, что основным недостатком вашего подхода является то, что вы рассматриваете уже посещенные состояния как нежелательные цели, по которым противник может перейти. Вместо того, чтобы возвращать значение бесконечности, вы должны извлечь значение, которое было вычислено во время первого посещения этого состояния.

Практически это означает, что вы должны использовать карту (of state-> value) вместо набора(состояния).

Только в том случае, если значение первого посещения еще не рассчитано (поскольку рекурсивный вызов приводит к посещению состояния предка ), вам необходимо использоватьзарезервированное значение. Но пусть это значение будет undefined / null / None, чтобы оно не было обработано как другие числовые результаты, но было исключено из возможных путей, даже при возврате.

В качестве примечания я бы выполнилпоиск и маркировка состояний при начале функции - в текущем состоянии - вместо внутри цикла в соседних состояниях.

Вот как будет работать одна из двух функцийзатем посмотрите: 

def maxPLayer(currentState, evaluatedMap):
    if currentState in evaluatedMap
        return evaluatedMap.get(currentState)

    evaluatedMap.set(currentState, undefined)

    if not isTerminalState
        bestScore = undefined
        for nextState in currentState.generateMaxSuccessors()
            value = minPlayer(nextState, evaluatedMap)
            if value != undefined
                scores.append(value)
        if scores is not empty
            bestScore = max(scores)
    else
        bestScore = evalFnc(currentState)

    evaluatedMap.set(currentState, bestScore)
    return bestScore
end MaxPlayer

Значение undefined будет использоваться во время посещения состояния, но его значение еще не определено (из-за ожидающих рекурсивных вызовов). Если состояние таково, что текущий игрок не имеет действительных ходов («застрял»), то это состояние навсегда получит значение undefined, в других случаях значение undefined будет в конечном итоге заменено истинным счетом.

...