A melhor forma para implementar uma "MiniMax" recursão [fechado]
-
21-12-2019 - |
Pergunta
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,
Solução
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.