wiki.neuro.tu-berlin.de

Alpha Beta Pruning

Alpha-Beta-Suche (Alpha-Beta Pruning)

Die Alpha-Beta-Suche (auch Alpha-Beta-Pruning) ist ein optimierter Suchalgorithmus für Zwei-Personen-Nullsummenspiele (wie Schach, Go, Tic-Tac-Toe oder Dame). Er ist eine Erweiterung des Minimax-Algorithmus, der darauf abzielt, die Anzahl der zu bewertenden Knoten im Suchbaum drastisch zu reduzieren, ohne das Ergebnis zu verändern.

Der Algorithmus ist heute das Standardverfahren in fast allen spielstarken Engines und ermöglicht es, bei gleicher Rechenzeit deutlich tiefere Suchbäume zu analysieren als mit dem naiven Minimax-Verfahren.

Funktionsweise

Das Grundprinzip des Algorithmus ist das "Abschneiden" (Pruning) von Ästen im Suchbaum, die für das Endergebnis irrelevant sind. Wenn der Algorithmus feststellt, dass ein Zweig zu einem Ergebnis führt, das schlechter ist als eine bereits gefundene Alternative, wird dieser Zweig sofort verworfen.

Dazu führt der Algorithmus zwei Werte (Schranken) mit sich, die während der Suche aktualisiert werden:

  1. Alpha (\alpha): Der bisher beste (höchste) Wert, den der maximierende Spieler (MAX) auf dem aktuellen Pfad oder einem vorherigen Pfad garantieren kann. Dies ist die untere Schranke für das Ergebnis von MAX.
  2. Beta (\beta): Der bisher beste (niedrigste) Wert, den der minimierende Spieler (MIN) auf dem aktuellen Pfad oder einem vorherigen Pfad garantieren kann. Dies ist die obere Schranke für das Ergebnis von MAX (da MIN versuchen wird, den Wert unter \beta zu drücken).

Die Cut-off-Bedingung

Ein Teilbaum wird nicht weiter durchsucht (abgeschnitten), sobald gilt:

\alpha \geq \beta

Logik dahinter:
Der Maximizer hat bereits eine Alternative gefunden (\alpha), die besser oder gleich gut ist wie das Beste, was der Minimizer in diesem aktuellen Zweig zulassen würde (\beta). Da der Minimizer (als optimaler Gegner) diesen Pfad niemals wählen würde, wenn er eine bessere Option hat, und der Maximizer diesen Pfad niemals betreten muss (da er schon ein besseres \alpha hat), ist das genaue Ergebnis dieses Zweigs irrelevant.

Algorithmus (Pseudocode)

Hier ist eine generische Implementierung, die sich leicht in Python übertragen lässt.

def alpha_beta_search(node, depth, alpha, beta, maximizing_player):
    # 1. Abbruchbedingung: Maximale Tiefe erreicht oder Spielende (Blattknoten)
    if depth == 0 or is_terminal(node):
        return heuristic_value(node)

    if maximizing_player:
        value = float('-inf')
        for child in generate_children(node):
            # Rekursiver Aufruf mit vertauschten Rollen
            value = max(value, alpha_beta_search(child, depth - 1, alpha, beta, False))
            
            alpha = max(alpha, value)
            if alpha >= beta:
                break
                
        return value

    else: # Minimizing Player
        value = float('inf')
        for child in generate_children(node):
            value = min(value, alpha_beta_search(child, depth - 1, alpha, beta, True))
            
            beta = min(beta, value)
            if alpha >= beta:
                break
                
        return value

Komplexität und Effizienz

Die Effizienz von Alpha-Beta hängt extrem stark von der Sortierung der Züge (Move Ordering) ab. Der Algorithmus arbeitet am besten, wenn er gute Züge früh untersucht, da er dann schnell enge Fenster (\alpha, \beta) etablieren und schlechte Zweige abschneiden kann.

Ein Suchbaum mit Verzweigungsgrad b (Anzahl der Züge pro Stellung) und Tiefe d hat im Worst Case b^d Knoten.

  1. Schlechtester Fall (Worst Case):
    Die Züge werden in der schlechtestmöglichen Reihenfolge geprüft (die besten Züge zuletzt). In diesem Szenario greift kein Cut-off, und der Algorithmus muss alle Knoten besuchen.

    • Aufwand: O(b^d) (identisch zu Minimax)

  2. Bester Fall (Best Case):
    Die besten Züge werden immer zuerst geprüft. Das maximiert die Anzahl der Cut-offs. In diesem Fall muss der Algorithmus nur etwa die Quadratwurzel der Knoten des Minimax-Baums untersuchen.

    • Aufwand: O(b^{d/2})

Praktische Bedeutung:
Im Idealfall kann Alpha-Beta bei gleicher Rechenzeit doppelt so tief suchen wie der naive Minimax-Algorithmus. In der Praxis erreichen starke Programme durch Heuristiken zur Zugsortierung (z.B. Killer Heuristic oder History Heuristic) Ergebnisse, die sehr nah am Best Case liegen.

Referenzen