Alpha-Beta-Pruning

TL;DR

Minimax entwickelt den gesamten Spielbaum. Wenn man dabei die bisher besten Werte für MAX und MIN als $α$ und $β$ mitführt, beobachtet man, dass ein $α$ -Wert nie kleiner wird und ein $β$ -Wert nie größer wird. Dies kann man ausnutzen und das Entwickeln von Pfaden abbrechen, wenn in einem MIN-Knoten der $β$ -Wert kleiner wird als der $α$ -Wert des MAX-Vorgängers: (a) kann der $β$ -Wert bei der weiteren Untersuchung der verbleibenden Nachfolger im MIN-Knoten nur noch kleiner werden, und (b) würde der MAX-Vorgänger diesen MIN-Knoten nie als Nachfolger in Betracht ziehen, da er bereits einen besseren Zug gesehen hat (da sein $α$ größer ist als das $β$ im Nachfolger). Deshalb kann man hier sofort die Untersuchung der verbleibenden Nachfolger im MIN-Knoten abbrechen ("Pruning"). Eine analoge Überlegung gilt für einen MAX-Nachfolger unter einem MIN-Knoten.

Dabei bleibt das Endergebnis erhalten. Man schneidet nur Suchpfade weg, die das Ergebnis von Minimax nicht verändern.

Die mögliche Effizienzsteigerung ist sehr stark abhängig von Sortierung der Nachfolger! Deshalb stellt man häufig Heuristiken zur "richtigen" Sortierung der Nachfolger auf ("Killer-Moves").

Zusätzlich kann man wie bei Minimax auch die Suchtiefe begrenzen und eine Bewertungsfunktion (statt der Nutzenfunktion) einsetzen. Auch hier kann die Bewertungsfunktion wieder gewichtete Features nutzen und/oder Positionen mit in Datenbanken gespeicherten Positionen und Bewertungen abgleichen.

Videos (YouTube)

VL Alpha-Beta-Pruning

Videos (HSBI-Medienportal)

VL Alpha-Beta-Pruning

Lernziele

(K2) Optimierungsmöglichkeit: Sortierung der Nachfolger => Heuristik
(K2) Optimierungsmöglichkeit: Suchtiefe beschränken => Übergang zu Bewertungsfunktion
(K2) Optimierungsmöglichkeit: Bewertung über Spieldatenbanken
(K3) alpha-beta-Pruning

Verbesserung Minimax-Algorithmus

=> Minimax-Baum: Verbesserungen möglich?

Alpha-beta-Pruning

Minimax-Algorithmus mit zusätzlichen Informationen:

$α$ : bisher bester Wert für MAX (höchster Wert)
$β$ : bisher bester Wert für MIN (kleinster Wert)

=> Beobachtungen:

$α$ für MAX-Knoten wird nie kleiner
$β$ für MIN-Knoten wird nie größer

Pruning-Regeln

Schneide (unter) MIN-Knoten ab, deren $β$ $\leq$ dem $α$ des MAX-Vorgängers ist.
Schneide (unter) MAX-Knoten ab, deren $α$ $\geq$ dem $β$ des MIN-Vorgängers ist.

Abbruch, wenn kein Platz mehr zwischen Alpha und Beta

Alpha-beta-Pruning -- Der Algorithmus (Skizze)

def Max-Value(state, alpha, beta):
    if Terminal-Test(state): return Utility(state)

    v = -INF
    for (a, s) in Successors(state):
        v = MAX(v, Min-Value(s, alpha, beta))
        if (v >= beta): return v
        alpha = MAX(alpha, v)
    return v

def Min-Value(state, alpha, beta):
    if Terminal-Test(state): return Utility(state)

    v = +INF
    for (a, s) in Successors(state):
        v = MIN(v, Max-Value(s, alpha, beta))
        if (v <= alpha): return v
        beta = MIN(beta, v)
    return v

Initialer Aufruf von Max-Value() mit $α = - \infty$ und $β = + \infty$

Achtung: Es kursieren Varianten von diesem Algorithmus, bei denen auf die Hilfsvariable v verzichtet wird und stattdessen alpha bzw. beta direkt modifiziert werden und als Rückgabewert dienen. Das kann zu anderen oder falschen Ergebnissen führen! Sie können das in der Aufgabe auf Blatt 03 gut beobachten.

Alpha-beta-Pruning -- Eigenschaften

Pruning beeinflusst nicht das Endergebnis!
Sortierung der Nachfolger spielt große Rolle
Perfekte Sortierung: $O (b^{d / 2})$ => Verdopplung der Suchtiefe möglich

Für Schach immer noch zu aufwändig ...

Verbesserungen für Alpha-beta-Pruning

"Killer-Move": Maximale Effizienz nur wenn optimaler Zug immer zuerst untersucht => Zu untersuchende Züge sortieren/priorisieren, zb. Schach: a) Figuren schlagen b) Drohen c) Vorwärts ziehen d) Rückwärts ziehen
Verändern der Suchtiefe nach Spielsituation
Bewertungsfunktion Eval:
- Datenbanken mit Spielsituationen und Expertenbewertung:
  - Eröffnungsspiele (besonders viele Verzweigungen)
  - Endspiele
- Lernen der optimalen Gewichte für Eval-Funktion
- Berücksichtigung von Symmetrien

Beispiel DeepBlue (IBM, 1997)

Alpha-beta-Pruning mit Tiefenbeschränkung: ca. 14 Halbzüge
Dynamische Tiefenbeschränkung (stellungsabhängig, max. ca. 40 Züge)
Heuristische Stellungsbewertung Eval:
- mehr als 8.000 Features
- ca. 4.000 Eröffnungsstellungen
- ca. 700.000 Spielsituationen (von Experten bewertet)
- Endspiel-Datenbank: alle Spiele mit 5 Steinen, viele mit 6 Steinen

Quelle: [Russell2014, p. 185]

Beispiel AlphaGo (Google, 2016)

Beschränkung der Suchtiefe: Bewertung der Stellung durch "Value Network"
Beschränkung der Verzweigungsbreite: Bestimmung von Zugkandidaten durch "Policy Network"
Training dieser "Deep Neural Networks":
- Überwachtes Lernen: "Analyse" von Spiel-Datenbanken
- Reinforcement-Lernen: Self-Play, Bewertung am Ende
  - Züge mit Monte-Carlo-Baumsuche ausgewählt

Quelle: [Silver2016], siehe auch deepmind.com/research/alphago/

Wrap-Up

Alpha-beta-Pruning:
- Mitführen der bisher besten Werte für MAX und MIN: $α$ und $β$
- Abschneiden von Pfaden, die Verschlechterung bewirken würden
- Endergebnis bleibt erhalten
- Effizienzsteigerung abhängig von Sortierung der Nachfolger
Viele Verbesserungen denkbar:
- Zu untersuchende Züge "richtig" sortieren (Heuristik)
- Suchtiefe begrenzen und Bewertungsfunktion (statt Nutzenfunktion)
- Positionen mit Datenbank abgleichen

Quizzes

Selbsttest Alpha-Beta-Pruning (ILIAS)

Challenges

Optimale Spiele und MiniMax

Auf einem Tisch liegen nebeneinander 5 Streichhölzer. Es gibt zwei Spieler - Weiß und Schwarz - die abwechselnd ein oder zwei Streichhölzer wegnehmen dürfen (es muss mind. ein Streichholz genommen werden). Wer das letzte Streichholz nehmen muss, hat verloren. Zu Beginn ist Weiß am Zug.

Spielbaum

Zeichnen Sie den kompletten Spielbaum auf. Geben Sie an den Kanten jeweils die Zahl der genommenen und der verbleibenden Hölzer an.

Beispiel: Wenn in einem Zug ein Holz genommen wird und 3 Hölzer verbleiben, steht an der entsprechenden Kante "1/3". Geben Sie jeweils an, welcher Spieler am Zug ist.

Minimax

Geben Sie die Bewertung aller Spielzustände mit Hilfe des Minimax-Algorithmus an. Bewerten Sie die Endzustände mit +1, wenn Spieler Weiß gewonnen hat, mit -1, falls Schwarz gewonnen hat.

Alpha-Beta-Pruning

Wenden Sie Alpha-Beta-Pruning auf den Spielbaum an. Werden damit mehr oder weniger oder gleich viele Spielzüge wie mit Minimax entwickelt? Begründen Sie Ihre Antwort.

Übungsblätter/Aufgaben

Übungsblatt: Spiele

Quellen

[Ertel2017] Introduction to Artificial Intelligence
Ertel, W., Springer, 2017. ISBN 978-3-319-58487-4. DOI 10.1007/978-3-319-58487-4.
[Russell2014] Artificial Intelligence: A Modern Approach
Russell, S. und Norvig, P., Pearson, 2014. ISBN 978-1-292-02420-2.
[Russell2020] Artificial Intelligence: A Modern Approach
Russell, S. und Norvig, P., Pearson, 2020. ISBN 978-0134610993.
Alpha-beta-Pruning: Abschnitt 6.2.3, Erweiterungen: Abschnitt 6.3
[Silver2016] Mastering the game of Go with deep neural networks and tree search
Silver, D. und Huang, A. und Maddison, C. und Guez, A. und Sifre, L. und Van Den Driessche, G. und Schrittwieser, I., J. Schrittwieser und Panneershelvam, V. und Lanctot, M. und others, Nature Publishing Group, 2016. DOI 10.1038/nature16961.