Как добиться значения в рекурсивной функции?

Question

Я пытался запрограммировать минимаксную игру NIM с Python. Я почти закончил с кодами. Однако я не смог решить проблему, которая так сложна. Я не смог достичь "лучшего движения" алгоритма. Я начал с позиции (5, Max), и вывод алгоритма должен быть (4, Min). Мой алгоритм решает целые деревья с полезными значениями, но не может вернуться к лучшему движению.

def startposition():
    return 5, 'max'


def terminalstate(state):
    if state == (0, 'min') or state == (0, 'max'):
        return True
    else:
        return False


def minimax(state):
    turn,heap=state
    if terminalstate(state):
        return utilitystatic(state)
    else:
        if heap == 'min':
            value = 250
            for x in successorsgenerator(state):
                value = min(value, minimax(x))
            result = state, value
        elif heap == 'max':
            value = -250
            for x in successorsgenerator(state):
                value = max(value, minimax(x))
            result = state, value

        print(result)
    return value


def utilitystatic(state):
    turn, heap = state
    assert terminalstate(state)
    if state[1] == 'max':
        return -100
    elif state[1] == 'min':
        return 100
    assert False


def successorsgenerator(state):
    successors = []
    state = toggle(state)
    newstate = decrease(state)
    i = 0
    while newstate[0] >= 0 and i < 3:
        successors.append(newstate)
        i += 1
        newstate = decrease(newstate)
    print('successors:', successors)
    return successors


def toggle(state):
    state = list(state)
    state[1] = 'min' if state[1] == 'max' else 'max'
    state = tuple(state)
    return state


def decrease(state):
    state = state[:0] + (state[0] - 1,) + state[1:2]
    return state


stick = startposition()
result = minimax(stick)
print('result:', result)

Answer 1

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

def minimax(state):
    turn,heap=state
    if terminalstate(state):
        return utilitystatic(state), _
    else:
        if heap == 'min':
            value = 250
            best_succ = None
            for x in successorsgenerator(state):
                val, _ = minimax(x)
                if val < value:
                    value = val
                    best_succ = x
            result = state, value
        elif heap == 'max':
            value = -250
            best_succ = None
            for x in successorsgenerator(state):
                val, _ = minimax(x)
                if val > value:
                    value = val
                    best_succ = x
            result = state, value

        print(result)
    return value, best_succ

С небольшими изменениями мы теперь сохраняем преемника x что привело к лучшей стоимости в best_succи, следовательно, также сможет точно сказать, какой преемник был лучшим (вместо того, чтобы только определить, какова его ценность)

Answer 2

Если вы не хотите хранить всю последовательность ходов в памяти (что часто / обычно не нужно), просто начните с создания возможных дочерних элементов вашего текущего игрового состояния. Не запускайте минимакс на вашем текущем состоянии, просто найдите возможные последующие шаги. Давайте представим, что есть 3 возможных хода оттуда, где вы находитесь (A, B, C). Теперь запустите алгоритм минимакса на A и сохраните результат вместе с описанием хода A. Повторите действия для B и C. Теперь у вас должно быть что-то вроде:

A: 3.5
B: 1.2
C: -7.1

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

В этом примере ход А является лучшим для максимизирующего игрока, а ход С является лучшим для минимизирующего игрока.