Der Alpha-Beta-Algorithmus

   Der Alpha-Beta-Algorithmus ist nicht mehr so einfach wie der Minimax, dafür untersucht er wesentlich weniger Varianten bei gleicher Leistung. Also los geht's:

   Bei genauerer Betrachtung der Abbildung beim Minimax, fällt vielleicht eine Kleinigkeit auf: der äußerst rechte Zug von Schwarz im Suchbaum ist eigentlich völlig unnötig. Das liegt daran, dass nach der Bewertung von -1 beim ersten Zug von Schwarz (auf den zweiten Zug von Weiß) klar ist, dass Weiß mit seinem zweiten Zug keine bessere Bewertung als 0 (der Wert seines ersten Zuges) erhalten wird, denn Schwarz wird die Bewertung höchstens weiter minimieren. Nach diesem ersten Zug von Schwarz steht also fest: Weiß wird seinen ersten Zug wählen.

   Das bedeutet also, dass in einer Rekursionsebene das Minimieren oder Maximieren abgebrochen werden kann, sobald das Maximum bzw. Minimum vom Gegner unter- bzw. überschritten wird (der Abbruch kann auch bei Gleichheit erfolgen; vergleiche Algorithmus).

   Der Alpha-Beta implementiert genau diese Vorgehensweise. In dem untenstehenden Pseudocode repräsentiert Alpha den besten Wert bezüglich der Farbe die gerade am Zug ist (gemäß Color) und Beta den besten Wert der gegnerischen Seite.

Konventionen: beim ersten Aufruf enthalten Depth, MaxDepth und Color Werte wie beim Minimax-Algorithmus. Außerdem erhalten Alpha und Beta die Werte:

  • Alpha=MinInteger und Beta=MaxInteger falls Color = White oder
  • Alpha=MaxInteger und Beta=MinInteger falls Color = Black

    Prozeduren: wie beim Minimax. Hinzu kommt Return (wie in C).

    Const White = 1; Black = -1; MaxInteger = 32767; MinInteger = -32768; Function AlphaBeta (Color, Alpha, Beta, Depth, MaxDepth : Integer) : Integer; var Value : Integer; begin if Depth = MaxDepth then AlphaBeta := EvaluatePosition (Color) end else begin GenerateMoves(Color, MoveList); For Each Move in MoveList do begin MoveForward (Move); Value := AlphaBeta (-Color, Beta, Alpha, Depth +1, MaxDepth); if Color = White then if Value > Alpha then Alpha := Value; if Color = Black then if Value < Alpha then Alpha := Value; MoveBack (Move); if Color = White then if Alpha >= Beta then Return Alpha; if Color = Black then if Alpha <= Beta then Return Alpha; end; AlphaBeta := Alpha; end; end;

       Die Analogie zum Minimax ist sehr groß. Im wesentlichen kommen nur zwei Bedingungen hinzu, die unter den oben geschilderten Bedingungen für einen Abbruch der Suche (man spricht von einem Schnitt) innerhalb einer Rekursionsebene sorgen.

       Die beiden Schranken Alpha und Beta können anschaulich auch als Suchfenster aufgefasst werden, wobei Alpha den Wert der eigenen bisher besten Variante enthält und Beta den Wert der bisher besten gegnerischen Variante. Das Suchfenster, das zunächst ganz offen ist, wird im Laufe der Suche immer kleiner.

    Beispiel: Der unten dargestellte Baum veranschaulicht die Funktionsweise des Alpha-Beta-Algorithmus. Die in eckigen Klammern angegebenen Werte sind die Schranken des Suchfensters, jeweils vor und nach einem Zug.

       Der Algorithmus lässt sich natürlich etwas kompakter darstellen. Werden beim rekursiven Aufruf statt Alpha und Beta -Alpha und -Beta übergeben, so ist keine Differenzierung zwischen Weiß und Schwarz nötig, d.h. es kann einfach stets maximiert werden. Dieses Prinzip wird mit Negamax-Rückbewertung bezeichnet.

    Anmerkung:

    • Die Behandlung von Schach, Patt und Matt wird i.d.R. aus Performance-Gründen vom Such-Algorithmus übernommen. Dies dem Zügegenerator und der Stellungsbewertung zu überlassen wäre weniger ratsam.

    © André Heuner, 1999