A melhor forma para implementar uma "MiniMax" recursão [fechado]

Question

Fechado. Esta questão é off-topic.Ele não está aceitando respostas.

---

Quer melhorar a esta questão? Atualização da pergunta por isso é sobre o tema, o para o Estouro de Pilha.

Fechado 5 anos atrás.

Eu estou usando o Mínmáx algoritmo para um jogo, e desde que há um monte de possibilidades a Mínmáx recursão leva demasiado tempo, mesmo com "alpha-beta poda"

Meu código é que alguns, como este:

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

Eu sei que às vezes você pode usar for loops em vez de recursividade mas eu não conseguia encontrar uma forma de convertê-lo.

Se alguém tem uma boa idéia, eu ficaria feliz em ouvir isso!

Obrigado,

Answer 1

Geralmente a recursão em mínmáx não pode ser substituído por um equivalente iterativa do algoritmo, e é por isso que existe são métodos de otimização, como a beta poda, que tenta melhorar as performances parando alguns ramos da árvore de recursão como o mais rapidamente possível.

É possível que para o seu jogo, mín-máx (ou, em geral, um algoritmo recursivo) não é necessário completamente, e pode haver outras maneiras de encontrar a solução ótima usando outras técnicas, mas sem um conjunto preciso de regras é impossível dizer.