Eine bessere Möglichkeit, eine „MiniMax“-Rekursion zu implementieren [geschlossen]

Question

Geschlossen. Diese Frage ist Off-Topic.Derzeit werden keine Antworten akzeptiert.

---

Möchten Sie diese Frage verbessern? Aktualisieren Sie die Frage so ist es zum Thema für Stack Overflow.

Geschlossen vor 5 Jahren.

Ich verwende den MinMax-Algorithmus für ein Spiel, und da es viele Möglichkeiten gibt, dauert die MinMax-Rekursion viel zu lange, selbst mit „Alpha-Beta-Bereinigung“.

Mein Code sieht ungefähr so ​​aus:

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

Ich weiß, dass man es manchmal gebrauchen kann for Loops statt Rekursion, aber ich konnte keinen Weg finden, es umzuwandeln.

Wenn jemand eine gute Idee hat, würde ich mich freuen, sie zu hören!

Danke,

Answer 1

Im Allgemeinen kann die Rekursion in Minmax nicht durch einen gleichwertigen iterativen Algorithmus ersetzt werden. Deshalb gibt es Optimierungsmethoden wie Beta Pruning, die versuchen, die Leistung zu verbessern, indem sie einige Zweige des Rekursionsbaums so schnell wie möglich stoppen.

Es ist möglich, dass für Ihr Spiel Minmax (oder allgemein ein rekursiver Algorithmus) überhaupt nicht benötigt wird und es andere Möglichkeiten gibt, mit anderen Techniken die optimale Lösung zu finden, aber ohne einen genauen Satz von Regeln ist das unmöglich zu sagen.