Implementierung von Alpha-Beta-Pruning in einem Minimax-Algorithmus

Nabla777

Hallo allerseits!

In meiner Verzweiflung, weil ich schon x Stunden an dieser Aufgabe sitze, habe ich mich dazu entschlossen, hier nach Hilfe zu suchen.

Folgendes ist das Ziel:

Ich soll einen Minimax-Algorithmus schreiben. Ich denke, das habe ich soweit geschafft.
Anna (purple/true) will maximieren, Raphi (black/false) will minimieren. Der Entscheidungsbaum besteht aus Nodes, die wiederum in sich einen Value (nur für Blätter relevant) und einen Left- sowie einen Right-Pointer auf ihre "Kinder" (falls existent, andernfalls jeweils nullptr)
Ich soll einen Alpha-Beta-Pruning-Algorithmus schreiben. Ich glaube, es hakt hier. Folgendes ist gegeben:

If it's a leaf: return its value
Else: evaluate the left child
If purple is playing, replace alpha by the maximum between alpha and the left child evaluation
If black is playing, replace beta by the minimum between beta and the left child evaluation
If beta is less or equal to alpha, prune the right child (that is remove the child, and pay attention to possible memory leaks!)
Else: evaluate the right child
Return the best evaluation

Ich soll einen Dekonstruktor schreiben, der für einen "geprunten" Ast den ganzen Subtree löscht.

Mein Alpha-Beta-Pruning-Algorithmus sieht wie folgt aus:

int alpha_beta_pruning(Node* position, int alpha, int beta, bool colour) 
{
    //base case, leaf
    if(position->left == nullptr && position->right == nullptr)
    {
      return position->value;
    }
    
    //Anna's turn
    if(colour)
    {
      //left child exists
      if(position->left != nullptr)
      {
      int evall = alpha_beta_pruning(position->left, alpha, beta, !colour);
      int evalr = INT_MIN;
      alpha = maximum(evall, alpha);
      
      //only delete right child if existent
      if(beta<=alpha && position->right != nullptr)
      {
        delete position->right;
      }
      
      //evaluate right child if alpha<beta and existent
      else
      {
        if(position->right != nullptr)
        {
        evalr = alpha_beta_pruning(position->right, alpha, beta, !colour);
        alpha = maximum(evalr, alpha);
        }
      }
      
      //return maximum
      return maximum(evalr, evall);
      }
      
      //if left child doesn't exist only evaluate right child
      else
      {
        return alpha_beta_pruning(position->right, alpha, beta, !colour);
      }
    }
    
    //Raphi's turn
    else
    {
      //left child exists
      if(position->left != nullptr)
      {
      int evall = alpha_beta_pruning(position->left, alpha, beta, !colour);
      int evalr = INT_MAX;
      beta = minimum(evall, beta);
      
      //only delete right child if existent
      if(beta<=alpha && position->right != nullptr)
      {
        delete position->right;
      }
      
      //evaluate right child if alpha<beta and existent
      else
      {
        if(position->right != nullptr)
        {
        evalr = alpha_beta_pruning(position->right, alpha, beta, !colour);
        beta = minimum(beta, evalr);
        }
      }
      
      //return minimum
      return minimum(evalr, evall);
      }
      
      //if left child doesn't exist only evaluate right child
      else
      {
        return alpha_beta_pruning(position->right, alpha, beta, !colour);
      }
    }
    
}

Mein Dekonstruktor:

Node::~Node(){
    delete this->right;
    delete this->left;
    this->right = nullptr;
    this->left = nullptr;
}

Ich verstehe ganz grundsätzlich die Idee hinter dem Pruning. Aber ich verstehe nicht:

Wo es hakt in meinem Code, da ich meiner Meinung nach die gegebenen Punkte von oben implementiert habe. Die Fehlermeldungen enthalten alle "INVALID READ" bzw. "INVALID WRITE". Es scheint, als würde versucht werden, auf nicht alloziierten Speicher zuzugreifen.
Warum diese gegebenen Punkte genau zur richtigen Durchlaufsreihenfolge für Alpha-Beta-Pruning führen. Ich finde die ganze Weitergabe von den Alphas und Betas schwierig nachzuvollziehen, wenn es dazwischen noch Rekursion hat und dann auch noch die verschiedenen Fälle: Muss ich Alpha/Beta auch aktualisieren/vergleichen, wenn nur ein Ast von einem Knoten weg existiert? Muss ich sie auch vergleichen, falls ich den rechten Ast gecheckt habe (ergo der rechte nicht geprunt wurde)? Muss ich Alpha auch anpassen/vergleichen, falls Raphi dran ist? Und Beta auch, falls Anna dran ist?

Ich hoffe, dass alles notwendige enthalten ist, und nun alles den Post-Kriterien entspricht.

Danke schonmal im Voraus für eure Hilfe!

Leon0402

Hi,

ich versuche mal auf ein paar Punkte einzugehen. Erstmal kann man den Algorithmus für viele verschiedene Spiele verwenden. Interessant wäre welches Spiel du genau implementierst und was bei dir left node und right node sind.
z.B. in Schach hat jeder Knoten beliebig viele child nodes, eben ein child für jeden Zug den der Gegner als nächstes machen kann.

Ich denke es hilft erstmal den Algorithmus für den allgemeinen Fall zu verstehen und vlt. kannst du dein Problem dann auch selber lösen. Zum Beispiel mit Schach:

Wir haben 2 Spieler (Schwarz und Weiß) und es handelt sich um ein Nullsummenspiel
Eine hohe positive Spielbewertung (z.B. +9) ist gut für Weiß, eine sehr niedrige Spielbewertung (z.B. -10) ist gut für Schwarz
Der weiße Spieler versucht also immer den Zug zu machen, der den Wert maximiert, während der schwarze Spieler einen zug versucht zu machen, der den Wert minimiert
Wir starten in einer gegeben Spielsituation, indem z.B. der weiße Spieler am Zug ist. Das ist unser Root Knoten. Die Children von diesem sind nun alle Positionen, die aus allen möglichen Zügen von dem weißen Spieler entstehen. In diesen ist dann Schwarz am Zug, sodass jeder dieser Nodes dann widerum child nodes mit allen Positionen hat, die enstehen können durch einen schwarzen Zug.
Die Leaf Knoten haben keine childs mehr. Hier ist einer der Spieler Schachmatt oder die maximale Suchtiefe ist erreicht
Bei Minimax wird von den Leaf Knoten gestartet und die Bewertung der Position zurückgegeben (z.B. Weiß hat Schachmatt gesetzt). Dann wird rekursiv auf jeder Ebene des Baums immer der max bzw. min Wert zurückgegeben von allen child nodes je nachdem ob Weiß oder Schwarz dort dran ist. Dies entspricht dem Verhalten, dass Weiß natürlich den Zug (child node) wählt bei dem die Stellung für ihn am besten ist (maximaler Wert) und Schwarz ebenfalls (minimaler Wert)

Soweit der Minimax Algorithmus, der letzendes einfach für die aktuelle und alle möglichen zukünftigen Stellungen einen Score berechnet, der darauf basiert, dass beide Spieler jeweils für sich optimale Züge machen. Die Idee von Alpha Beta Pruning basiert darauf, dass man sich gewisse Teilbäume gar nicht mehr anschauen muss.

Der Algorithmus oben ist eine Tiefensuche, daher er folgt vom root Knoten aus einem Pfad bis zum Ende (meist dem ganz linken) und arbeitet sich dann schrittweise zurück.
Angenommen der komplette linke Teilbaum wurde evaluiert und der weiße Spieler weiß somit mit dem Zug A erreicht er einen Wer von 10
Nun wird der rechte Teilbaum sich angeschaut mit dem Zug B. Schwarz ist jetzt am Zug und hat auch mehrere Züge zur Auswahl. Der komplette Teilbaum für seinen ersten Zug wird evaluiert und es kommt ein Score von 5 zurück. Da der schwarze Spieler minimiert wird er niemals einen Zug spielen, der einen höheren Score von 5 hat. Ohne die restlichen Züge anzuschauen wissen wir also, dass der rechte Teilbaum einen Score von 5 oder niedriger zurückgibt.
Der weiße Spieler maximiert und hat einen Zug bei dem er 10 erreicht hat, er wird also niemals Zug B spielen, der ihm einen Score von 5 oder niedriger einbringt. Hier kann er also direkt Zug A spielen.
In diesem Beispiel bei dem weiß 2 Züge hat A und B musste also der komplette Teilbaum für A angeschaut werden. Für B musste aber nur ein einziger Zug von Schwarz angeschaut werden, alle anderen Züge können ignoriert werden. Daher kann dieser ganze Teil des Baums "gepruned" werden.

Um Alpha Beta zu implementieren müssen wir stets wissen: Was ist der beste Score, den weiß oder Schwarz eine Ebene weiter oben bereits jetzt erreichen kann. Hierzug gibt es die 2 Variablen alpha und beta.

Alpha: Dies ist der beste Score den Weiß bisher erreichen kann. Er wird also am Ende einen Zug auswählen, der mindestens diesen Score aufweist, sofern er nicht noch einen besseren findet
Beta: Dies ist der beste Score den Schwarz bisher erreichen kann. Analog wird er einen Zug auswählen, welcher höchstens diesen Score hat

Am Anfang des Algorithmus ist alpha in der Regel negativ unendlich und beta positiv unendlich. Das heißt letzendes wir wissen: Weiß erreicht garantiert einen score von negativ unendlich (schlechter geht es für weiß nicht) und schwarz einen score von positiv unendlich (schlechter geht es für schwarz nicht). Folgende Regeln sind dann zu beachten:

Alpha und Beta werden grundsätzlich immer an child nodes weitergegeben (nicht an parents!)
Weiß ist am Zug: Er geht nacheinander durch seine Züge. Wenn einer der Züge einen höheren score als alpha hat, wird alpha auf diesen Wert gesetzt. Sobald alpha >= beta wird die Suche abgebrochen. Denn das bedeutet Schwarz würde eine Ebene höher einen anderen Zug wählen, indem er einen niedrigen score als hier erreicht
Schwarz ist im Zug: Er geht nacheinander durch seine Züge. Wenn einer der Züge einen niedrigeren score als beta hat, wird beta auf diesen Wert gesetzt. Sobald beta <= alpha wird die Suche abgebrochen. Denn das bedeutet Weiß würde eine Ebene höher einen einen anderen Zug wählen, indem er einen höheren score als hier erreicht.

Hier eine Python implementierung:

def _value(self, board: chess.Board, depth: int, alpha: Score, beta: Score) -> PovScore:
    if (score := self.evaluator.evaluate(board)) is not None:
        return score
    if depth == 0:
        return self.evaluator.heuristic(board)

    if board.turn is chess.WHITE:
        for move in board.legal_moves:
            board.push(move)
            value = self._value(board, depth - 1, alpha, beta)
            board.pop()
            if value.white() >= beta:
                return value
            alpha = max(alpha, value.white())

        return PovScore(alpha, chess.WHITE)
    else:
        for move in board.legal_moves:
            board.push(move)
            value = self._value(board, depth - 1, alpha, beta)
            board.pop()
            if alpha >= value.white():
                return value
            beta = min(beta, value.white())

        return PovScore(beta, chess.WHITE)

Du siehst die Sachen wie oben beschrieben

Beide iterieren durch die möglichen Züge (child nodes)
Weiß vergleicht den aktuellen Wert mit beta und Schwarz mit alpha, um ggf. vorzeitig abzubrechen
Weiß setzt den alpha Wert und Schwart den Beta wert

Wenn du auf deinen Code nun schaust, fallen dir vlt. 2 Sachen auf:

Erstens ist die Implementierung ein bisschen kompliziert. Z.B. speichert alpha bzw. beta jeweils immer schon den besten Zug. Es gibt also keine notwendigkeit evall und evalr zu speichern und am Ende nochmal ein maximum bzw. minimum zu bilden
Zweitens nochmal die Konditionen überprüfen. Daher ob alpha >= beta oder alpha <= beta sein muss

Hint: Die gegebenen Punkte sind falsch If beta is less or equal to alpha, prune the right child stimmt nur für einen der Spieler.

Nabla777

Hallo Leon

Danke schonmal für deine sehr ausführliche Antwort!
Den grundsätzlichen Algorithmus verstehe ich, danke. Ich glaube, den habe ich auch richtig implementiert:

int minimax(Node* position, bool colour) {
  
  //base case
  if(position->left == nullptr && position->right == nullptr)
  {
    return position->value;
  }
  
  //Anna's turn
  if(colour)
  {
    //only right child exists
    if(position->left == nullptr && position->right != nullptr)
    {
      return minimax(position->right, !colour);
    }
    
    //only left child exists
    if(position->right == nullptr && position->left != nullptr)
    {
      return minimax(position->left, !colour);
    }
    
    //both children exist
    return maximum(minimax(position->left, !colour), minimax(position->right, !colour));
  }
  
  //Raphi's turn
  
  else
  {
    //only right child exists
    if(position->left == nullptr && position->right != nullptr)
    {
      return minimax(position->right, !colour);
    }
    
    //only left child exists
    if(position->right == nullptr && position->left != nullptr)
    {
      return minimax(position->left, !colour);
    }
    
    //both children exist
    return minimum(minimax(position->left, !colour), minimax(position->right, !colour));
  }
  
  return 0;
}

So sehr ich deinen Aufwand schätze, mit dem Python-Code kann ich leider nicht allzu viel anfangen, da meine jetztige Programmiererfahrung einzig und allein aus einer Vorlesung C++ besteht...

Deinen ersten Punkt verstehe ich nicht ganz. Ich brauche doch separate Variablen evall und evalr, um diese dann mit alpha und untereinander zu vergleichen, oder nicht?

Der zweite Punkt macht Sinn. Ich habe das einfach aus den gegebenen Punkten übernommen... Ich denke bei Raphi/Minimizer müsste beta >= alpha stehen.
EDIT:EDIT: Ich denke doch nicht. Du schreibst in deinem Text:
" Weiss ist am Zug: ist alpha>=beta --> Abbruch"
"Schwarz ist am Zug: ist beta<=alpha -->Abbruch"
Das ist doch beides dieselbe Relation.
Wenn ich das richtig sehe, wird in deinem Code ein geprunter Subtree nicht gelöscht. Das ist in meiner Aufgabe jedoch explizit verlangt.

Vielleicht täusche ich mich auch, aber für mich hören sich die Fehler "INVALID READ" und "INVALID WRITE" mehr danach an, also ob deallozierter Speicher aufgerufen würde. Denn müsste doch nicht an den Bedingungen des Löschvorgangs, sondern am Löschvorgang selbst was nicht stimmen, oder etwa nicht?

EDIT: Wenn ich bei Raphi nun aber beta >= alpha setze, dann bestehe ich noch 1/10 Testcases, nicht mehr 4/10...
Was ich ebenfalls bei beiden angepasst habe ist ganz am Schluss, falls nur das rechte Kind besteht:

      //if left child doesn't exist only evaluate right child
      else
      {
        int evalr = alpha_beta_pruning(position->right, alpha, beta, !colour);
        alpha = maximum(alpha, evalr);
        return evalr;
      }

Ein Node ist übrigens ein Element dieses Baums. Und jeder Node enthält einen Value und zwei Pointer, left und right, die auf die Kinder dieses Nodes zeigen und auf nullptr gesetzt sind, falls diese nicht exisitieren, also insbesondere bei den Blättern des Baums.

Ich bin jetzt mit meinem Code jeden einzelnen Schritt des Beispielbaums durchgegangen mit den Blättern:
-1 3 5 1
Minimizer startet -> Maximizer wählt 3, nicht 1 -> Minimizer kann also sicherlich 3 vergeben --> Maximizer deckt 5 auf --> rechter Ast (1) wird gepruned, weil alpha auf 5, beta auf 3 ist. --> Ergebnis ist 3.

Das ausgegebene Endergebnis stimmt, es wird vor und nach Pruning 3 ausgegeben. Aber (es gibt eine Baumprinting-Fkt.) der ganze Baum ist noch da und es erscheinen die Fehler wieder.
Ich bin aber jeden einzelnen Schritt durchgegangen in meinem Code und es müsste eigentlich wirklich stimmen. Ich habe das Gefühl, das Deallozieren funktioniert nicht....

Ich wäre wirklich froh um rasche Hilfe, da das eine zeitlich beschränkte Abgabe für die Klausur ist und ich hier immer noch verzweifle....

Leon0402

@Nabla777 Ja, ich glaube tatsächlich das ich mich geirrt habe. Die Bedingung müsste doch so stimmen wie du sie hast, ich bin kurz durcheinander gekommen

Für den Fehler müsstest du vlt. mal ein minimal working Example geben. Z.B. in einem online Editor direkt, um es einfach zu machen. Ich sehe auf Anhieb zumindest kein Problem in dem Code. Bzw. auch mal die genauen Fehlermeldungen würden sicher helfen.

Th69

Hallo @Nabla777,

du löschst ja in Zeile 22 und 59 mit

delete position->right;

jeweils den rechten Knoten. Wenn nun aber wieder auf position->right zugegriffen wird (z.B. im Destruktor) so hast du dort einen Zugriff auf ungültigen Speicher.
Setze mal jeweils dort noch

position->right = nullptr;

Nabla777

Hallo Th69

Nach langem Debuggen (Ausgabe in Konsole) bin ich genau auf das gekommen und habe das versucht und es hat geklappt!
Es wurden leider nur die "right" und "left" der folgenden Elemente des Subtrees auf nullptr gesetzt, aber nicht vom letzten gültigen/notwendigen Element...

Danke euch!