Минимаксный AI в python - PullRequest
Новая
       103

Минимаксный AI в python

0 голосов
/ 16 марта 2020

Я пытаюсь создать минимаксный ИИ типа, который бы go проходил через 4 слоя ходов, и пытался выбрать наилучший возможный ход, основанный на определенном heuristi c. Дело в моей машине состояний, если я когда-либо достигну узла, который является недопустимым перемещением, тогда я возвращаю значение None вместо нормального значения точки, которое дала бы моя функция heuristi c. Имея дело с этим в моей минимаксной функции, я не совсем уверен, как лучше всего об этом go. Пока это выглядит примерно так и было интересно, имеет ли это смысл. 

def ai_min_max(board, ai_mancala, player_mancala, ai_choices, player_choices, target_depth, cur_depth, maxTurn, position):
    #base case where we call our heuristic function to tell us what the value of this state is
    if cur_depth == target_depth :
        #return the heuristic value for this state
        return first_heuristic(board, ai_mancala, player_mancala, ai_choices, player_choices, position)

    #if we are currently on a level where we are maximizing our function
    if maxTurn :
        #set the value to negative infinity
        max_eval = float("-inf")
        #go through the 10 possible choices you can make
        for x in range(len(ai_choices)) :
            new_position = position + [x]
            my_eval = ai_min_max(board, ai_mancala, player_mancala, ai_choices, player_choices, target_depth, cur_depth +1, False, new_position)
            #update the current max only if we have a valid movement, if not then do not update
            if my_eval is not None:
                max_eval = max(max_eval, my_eval)
        if max_eval == float("-inf") :
            return float("inf")
        return max_eval

    #if it is the minimizing player's turn
    else :
        min_eval = float("inf")
        for x in range(len(player_choices)) :
            new_position = position + [x]
            my_eval = ai_min_max(board, ai_mancala, player_mancala, ai_choices, player_choices, target_depth, cur_depth +1, True, new_position)
            if my_eval is not None:
                min_eval = min(min_eval, my_eval)
        #if there were no valid moves
        if min_eval == float("inf") :
            return float("-inf")
        return min_eval

1 Ответ

1 голос
/ 16 марта 2020

Как правило, в минимаксной реализации вы фактически никогда не делаете рекурсивный вызов недопустимых перемещений - они никогда не создаются в первую очередь. Но в некоторых случаях может быть проще (или дешевле) фактически применить этот шаг, чтобы выяснить, законный он или нет. Например, если вам нужно применить сложное вычисление, чтобы выяснить, является ли ход допустимым, то вам не нужно делать это дважды (один раз, когда вы генерируете потенциальные шаги, и один раз, когда вы ищите их). Итак, я буду предполагать, что это именно тот случай.

Учитывая это, имеет ли смысл возвращать специальное значение, как в приведенном выше коде.

Нет, есть лучший подход. На узле min вы можете вернуть -inf родителю, когда перемещение недопустимо, а на узле max вы можете вернуть inf родителю. Таким образом, незаконные перемещения имеют худшее возможное значение и будут обрабатываться естественным образом остальной частью поиска без каких-либо других особых случаев. Это значительно упрощает основной минимакс / альфа-бета l oop.

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

...