Einführung Optimale Spiele

Backgammon: Zwei Spieler, was ist der beste Zug?

Quelle: "position-backgammon-decembre" by serialgamer_fr on Flickr.com (CC BY 2.0)

Zwei Spieler, ein Spielstand und ein Würfelergebnis: Was ist jetzt der beste Zug?!

Motivation: Unterschied zu Suche?!

=> Mehrere konkurrierende Agenten an Suche beteiligt!

=> (Re-) Aktion des Gegners unbekannt/nicht vorhersehbar.

Spiele und Umgebungen

=> Bis auf Roboterfußball in KI traditionell keine physischen Spiele!

Brettspiele sind interessant für KI

• Brettspiele gut abstrakt darstellbar:

  • Zustände einfach repräsentierbar
  • Aktionen wohldefiniert (und i.d.R. sehr einfach)
  • Realisierung als Suchproblem möglich

• Problem: Suchbäume werden in Praxis riesig

  Beispiel Schach:

  • Im Mittel 35 Aktionen (branching factor) von jeder Position
  • Oft mehr als 40 Züge pro Spieler => Suchbäume mit mehr als 80 Ebenen
  • $35^{80} \approx 10^{123}$ mögliche Knoten!
  • (Aber "nur" rund $10^{40}$ verschiedene Zustände)

  Quelle: [Russell2020, pp. 193-196]

Eigenschaften guter Spielalgorithmen

• Zeit begrenzt

  • Irgendeine gute Entscheidung treffen! => Bewertungsfunktion (auch für Zwischenzustände)

• Speicher begrenzt

  • Evaluierungsfunktion für Zwischenzustände
  • Löschen von irrelevanten Zweigen

• Strategien nötig

  • Vorausschauend spielen (Züge "vorhersehen")

Wrap-Up

• Spiele kann man als Suchproblem betrachten
• Merkmale:
  • Mehrere Agenten beteiligt
  • Beobachtbarkeit der Umgebung
  • Zufallskomponente
  • Spielstrategie
• Problem: Riesige Spielbäume
• Umgang mit begrenzten Ressourcen (Zeit, Speicher)

Minimax

Spiele als Suchproblem: Minimax

Terminologie

• Zwei abwechselnd spielende Spieler: MAX und MIN, wobei MAX beginnt

  • Beide Spieler spielen in jedem Zug optimal
  • Spielergebnis wird aus Sicht von MAX bewertet:
    • $+1$, wenn Spieler MAX gewinnt
    • $-1$, wenn Spieler MIN gewinnt
    • $0$, wenn unentschieden
  • Spieler MAX versucht, das Spielergebnis zu maximieren
  • Spieler MIN versucht, das Spielergebnis zu minimieren

• Startzustand: Initialer Zustand des Spielbrettes

• Aktionen: Legale Züge, abhängig vom Spielzustand

• Zieltest: Ist das Spiel vorbei?

  => Startzustand und anwendbare Aktionen definieren den Zustandsraum.

• Nutzenfunktion: $\operatorname{UTILITY}(s,p)$: Wert des Spiels für Spieler $p$ im Spielzustand $s$

• Strategie: Spieler benötigen Strategie, um zu gewünschtem Endzustand zu kommen (unabhängig von den Entscheidungen des Gegenspielers) => einfacher Pfad von Start zu Ziel reicht nicht

Hinweis: Nullsummenspiel! (Der Gewinn des einen Spielers ist der Verlust des anderen Spielers.)

Eine mit dem Minimax-Algorithmus berechnete Strategie wird auch Minimax-Strategie genannt. Sie sichert dem betreffenden Spieler den höchstmöglichen Gewinn, der unabhängig von der Spielweise des Gegners erreichbar ist.

Bei Nicht-Nullsummenspielen, bei denen die Niederlage des Gegners nicht zwangsläufig mit dem eigenen Gewinn zusammenfällt (d.h. Gewinn des einen Spielers $\ne$ Verlust des anderen Spielers), liefert der Minimax-Algorithmus nicht unbedingt eine optimale Strategie.

Spielbaum TTT

Minimax (Idee)

1. Erzeuge kompletten Suchbaum mit Tiefensuche
2. Wende Nutzenfunktion (Utility) auf jeden Endzustand an
3. Ausgehend von Endzuständen => Bewerte Vorgängerknoten:
   • Knoten ist Min-Knoten: Nutzen ist das Minimum der Kindknoten
   • Knoten ist Max-Knoten: Nutzen ist das Maximum der Kindknoten
4. Startknoten: Max wählt den Zug, der zum Nachfolger mit der höchsten Bewertung führt

Annahme: Beide spielen perfekt. Fehler verbessern das Resultat für den Gegner.

Minimax-Algorithmus: Funktionen für MAX- und MIN-Knoten

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

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

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

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

Hinweis I: Auf wikipedia.org/wiki/Minimax finden Sie eine Variante mit einem zusätzlichen Tiefenparameter, um bei einer bestimmten Suchtiefe abbrechen zu können. Dies ist bereits eine erweiterte Version, wo man beim Abbruch durch das Erreichen der Suchtiefe statt Utility() eine Eval()-Funktion braucht (vgl. Minimax: Heuristiken).

Wenn man ohne Suchtiefenbeschränkung arbeiten will, braucht man diesen Parameter nicht! Der Algorithmus terminiert auch ohne Suchtiefenbeschränkung!

Hinweis II: Im [Russell2020, S. 196, Abb. 6.3] findet sich eine Variante, die die auf der nächsten Folien gezeigte Startfunktion mit den hier gezeigten Min-Value()- und Max-Value()-Funktionen verschmilzt. Dabei wird in den beiden Hilfsfunktionen nicht nur der min- bzw. max-Wert optimiert, sondern auch der jeweils beste Zug gespeichert und als Rückgabe zurückgeliefert.

Minimax-Algorithmus: Sonderbehandlung Startknoten

def Minimax(state):
    (val, action) = (-INF, null)
    for (a, s) in Successors(state):
        v = Min-Value(s)
        if (val <= v):
            (val, action) = (v, a)
    return action

• Startknoten ist ein MAX-Knoten
• Nicht nur Kosten, sondern auch die zugehörige Aktion speichern

Minimax Beispiel

Aufwand Minimax

• maximale Tiefe des Spielbaums: $m$
• in jedem Zustand $b$ gültige Züge
• => Zeitkomplexität $O(b^m)$

Gedankenexperiment:

• erster Zug: $b$ Möglichkeiten,
• zweiter Zug: jeweils wieder $b$ Möglichkeiten $\rightarrow$ $b \star b = b^2$,
• dritter Zug: jeweils wieder $b$ Möglichkeiten $\rightarrow$ $b \star (b \star b) = b^3$,
• ...,
• $m$. Zug: jeweils wieder $b$ Möglichkeiten $\rightarrow$ $b^m$

Wrap-Up

• Minimax: Entwickelt Spielbaum, bewertet Zustände entsprechend Max und Min
  • Gewinn von Max: +1, Gewinn von Min: -1
  • Max wählt das Maximum der möglichen Züge von Min
  • Min wählt das Minimum der möglichen Züge von Max
  • Spielbaum wird bis zu den Blättern entwickelt, Bewertung mit Utility

Heuristiken

Wenn die Zeit nicht reicht: Suchtiefe begrenzen

• Einführung neuer Funktionen:

  1. Cutoff-Test statt Terminal-Test

     Beispielsweise bei erreichter Tiefe oder Zeitüberschreitung

  2. Eval statt Utility

     Bewertung der erreichten Position (statt nur Bewertung des Endzustandes)

• Bedingungen an Eval:

  1. Endknoten in selber Reihenfolge wie bei Utility
  2. Schnell zu berechnen (!)

Beispiel Schach

• Mögliche Evaluierungskriterien:

  • Materialwert: Bauer 1, Läufer/Springer 3, Turm 5, Dame 9
  • Stellungsbewertung: Sicherheit des Königs, Stellung der Bauern
  • Daumenregeln: 3 Punkte Vorteil => sicherer Sieg

• Nutzung gewichteter Features $f_i$: $\operatorname{Eval}(s) = w_1f_1(s) + w_2f_2(s) + \ldots$

  • Beispiel: $w_1 = 9$ und $f_1(s)$ = (# weiße Königinnen) - (# schwarze Königinnen)

• Alternativ: Speicherung von Positionen plus Bewertung in Datenbanken => Lookup mit $\operatorname{Eval}(s)$ (statt Berechnung zur Laufzeit)

Minimax mit mehreren Spielern

Hier maximiert jeder Spieler sein eigenes Ergebnis. Im Grunde müsste diese Variante dann besser "Maximax" heissen ...

Wenn es an einer Stelle im Suchbaum mehrere gleich gute (beste) Züge geben sollte, kann der Spieler Allianzen bilden: Er könnte dann einen Zug auswählen, der für einen der Mitspieler günstiger ist.

Zufallsspiele

Quelle: "position-backgammon-decembre" by serialgamer_fr on Flickr.com (CC BY 2.0)

Backgammon: Was ist in dieser Situation der optimale Zug?

Minimax mit Zufallsspielen: ZUFALLS-Knoten

Zusätzlich zu den MIN- und MAX-Knoten führt man noch Zufalls-Knoten ein, um das Würfelergebnis repräsentieren zu können. Je möglichem Würfelergebnis $i$ gibt es einen Ausgang, an dem die Wahrscheinlichkeit $P(i)$ dieses Ausgangs annotiert wird.

=> Für Zufallsknoten erwarteten Minimax-Wert (Expectimax) nutzen

Minimax mit Zufall: Expectimax

Expectimax-Wert für Zufallsknoten $C$:

• $i$ mögliches Würfelergebnis
• $P(i)$ Wahrscheinlichkeit für Würfelergebnis
• $s_i$ Nachfolgezustand von $C$ gegeben Würfelergebnis $i$

Für die normalen Min- und Max-Knoten liefert Expectimax() die üblichen Aufrufe von Min-Value() bwz. Max-Value().

Auf wikipedia.org/wiki/Expectiminimax finden Sie eine Variante mit einem zusätzlichen Tiefenparameter, um bei einer bestimmten Suchtiefe abbrechen zu können. Dies ist bereits eine erweiterte Version, wo man beim Abbruch durch das Erreichen der Suchtiefe statt Utility() eine Eval()-Funktion braucht. Zusätzlich kombiniert der dort gezeigte Algorithmus die Funktionen Expectimax(), Min-Value() und Max-Value() in eine einzige Funktion.

Eine ähnliche geschlossene Darstellung finden Sie im [Russell2020, S. 212].

Hinweis: Üblicherweise sind die Nachfolger der Zufallsknoten gleich wahrscheinlich. Dann kann man einfach mit dem Mittelwert der Bewertung der Nachfolger arbeiten.

Wrap-Up

• Minimax:
  • Kriterien zur Begrenzung der Suchtiefe, Bewertung Eval statt Utility
  • Erweiterung auf $>2$ Spieler
  • Erweiterung auf Spiele mit Zufall: Expectimax

Alpha-Beta-Pruning

Verbesserung Minimax-Algorithmus

=> Minimax-Baum: Verbesserungen möglich?

Alpha-beta-Pruning

Minimax-Algorithmus mit zusätzlichen Informationen:

• $\alpha$: bisher bester Wert für MAX (höchster Wert)
• $\beta$: bisher bester Wert für MIN (kleinster Wert)

=> Beobachtungen:

1. $\alpha$ für MAX-Knoten wird nie kleiner
2. $\beta$ für MIN-Knoten wird nie größer

Pruning-Regeln

1. Schneide (unter) MIN-Knoten ab, deren $\beta$ $\le$ dem $\alpha$ des MAX-Vorgängers ist.

2. Schneide (unter) MAX-Knoten ab, deren $\alpha$ $\ge$ dem $\beta$ des MIN-Vorgängers ist.

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 $\alpha = -\infty$ und $\beta = +\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

1. Pruning beeinflusst nicht das Endergebnis!

2. Sortierung der Nachfolger spielt große Rolle

3. 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: $\alpha$ und $\beta$
  • 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