Лучший способ реализовать рекурсию «MiniMax» [закрыто]

Question

Закрыто. Этот вопрос не по теме.В настоящее время он не принимает ответы.

---

Хотите улучшить этот вопрос? Обновить вопрос так что это по теме для переполнения стека.

Закрыто 5 лет назад.

Я использую алгоритм MinMax для игры, и, поскольку возможностей много, рекурсия MinMax занимает слишком много времени, даже с «альфа-бета-обрезкой».

Мой код выглядит примерно так:

min(state,depth,alpha,beta):
    if stopingCond: 
        return value

    for moves in allmoves:
        state.do(move)
        beta = min(beta, max(state,depth,alpha,beta) )
        if alpha >= beta: return beta
    return beta

max(state,depth,alpha,beta):
    if stopingCond: 
        return value

    for moves in allmoves:
        state.do(move)
        alpha = max(beta, min(state,depth,alpha,beta) )
        if alpha >= beta: return alpha
    return beta

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

Если у кого-то есть хорошая идея, я буду рад ее услышать!

Спасибо,

Answer 1

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

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