Une meilleure façon d'implémenter une récursion "MiniMax" [fermé]

Question

Fermé. Cette question est hors sujet.Il n’accepte actuellement pas de réponses.

---

Vous souhaitez améliorer cette question ? Mettre à jour la question alors c'est sur le sujet pour le débordement de pile.

Fermé il y a 5 ans.

J'utilise l'algorithme MinMax pour un jeu, et comme il y a beaucoup de possibilités, la récursion MinMax prend beaucoup trop de temps, même avec "l'élagage alpha-bêta".

Mon code ressemble à ceci :

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

Je sais que parfois tu peux utiliser for boucles au lieu de la récursivité mais je n'ai pas pu trouver de moyen de le convertir.

Si quelqu'un a une bonne idée, je serais ravi de l'entendre !

Merci,

Answer 1

Généralement la récursivité dans minmax ne peut pas être remplacée par un algorithme itératif équivalent, et c'est pourquoi il existe des méthodes d'optimisation, comme l'élagage bêta, qui tentent d'améliorer les performances en arrêtant au plus vite certaines branches de l'arbre de récursion.

Il est possible que pour votre jeu, minmax (ou, généralement, un algorithme récursif) ne soit pas complètement nécessaire et qu'il puisse exister d'autres moyens de trouver la solution optimale en utilisant d'autres techniques, mais sans un ensemble précis de règles, il est impossible de le dire.