Как реализовать алгоритм MINIMAX для игр, слишком сложных для полного поиска - PullRequest
Новая
       76

Как реализовать алгоритм MINIMAX для игр, слишком сложных для полного поиска

0 голосов
/ 24 апреля 2020

Недавно я начал программировать некоторый ИИ для простых игр, но у меня возникают проблемы с пониманием концепции использования MINIMAX для игр, которые требуют досрочного завершения в пространстве поиска. 

time_start = time.clock()
minimax(initial_state, time_start)

def minimax(state, t):
    # Returns optimal child from current state with highest util
    (best_child, best_util) = maximise(state, -math.inf, math.inf, t)
    # Get all possible moves from current state
    moves = state.getMoves()
    for move in moves:
        # Return move that results in the child state with highest util
        if result(state, move) == best_child:
            return move

def maximise(state, a, b, t):

    # Check time and if execution of algorithm exceeds 0.5s, break immaturely
    time_end = time.clock()
    if time_end - t > 0.5:
        return state, heuristic(state)

    (max_child, max_util) = (None, -math.inf)

    # Get child state for all possible move of current state
    moves = state.getMoves()
    for move in moves:
        child_state = result(state, move)
        (child, util) = minimise(child_state, a, b, t)
        if util > max_util:
            (max_child, max_util) = (child, util)
        # Alpha-beta pruning
        if max_util >= b:
            break
        if max_util > a:
            a = max_util
    return max_child, max_util


def minimise(state, a, b, t):

    # Check time and if execution of algorithm exceeds 0.5s, break immaturely
    time_end = time.clock()
    if time_end - t > 0.5:
        return state, heuristic(state)

    (min_child, min_util) = (None, math.inf)
    # Get child state for all possible move of current state
    moves = state.getMoves()
    for move in moves:
        child_state = result(state, move)
        (child, util) = maximise(child_state, a, b, t)
        if util < min_util:
            (min_child, min_util) = (child, util)
        # Alpha-beta pruning
        if min_util <= a:
            break
        if min_util < b:
            b = min_util
    return min_child, min_util

Для воображаемой игры, скажем, например, моя цель - вернуть ход в течение 0,5 с. Этот код делает то, что иногда он возвращает оптимальный ход, но иногда, когда

если результат (состояние, перемещение) == best_child

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

Или моя логика c совершенно ошибочна, и я что-то пропустил? Спасибо за вашу помощь!

...