Una mejor manera de implementar un "MiniMax" recursividad [cerrado]

Question

Cerrado. Esta pregunta es off-topic.Actualmente, no es la aceptación de respuestas.

---

Desea mejorar esta pregunta? Actualización de la pregunta por lo que es en el tema por Desbordamiento de Pila.

Cerrado Hace 5 años.

Estoy usando el mín-máx algoritmo para un juego, y ya hay muchas posibilidades de que el mín-máx recursividad toma demasiado tiempo, incluso con "alfa-beta de la poda"

Mi código es algo como esto:

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

Sé que a veces puede utilizar for bucles en lugar de la recursividad pero yo no podía encontrar una manera de convertir.

Si uno tiene una buena idea de la que me encantaría saber de ti!

Gracias,

Answer 1

Generalmente la recursividad en mín-máx, no puede ser sustituido por un equivalente algoritmo iterativo, y es por eso que hay métodos de optimización, como la beta de la poda, que tratan de mejorar las actuaciones por la detención de algunas ramas del árbol de recursión tan pronto como sea posible.

Es posible que por su juego, mín-máx (o, en general, un algoritmo recursivo) no es necesario del todo y podría haber otras maneras de encontrar la solución óptima utilizando otras técnicas, pero sin un preciso conjunto de reglas es imposible decir.