https://commons.wikimedia.org/wiki/File:World_Chess_Championship_2021,_game_11,_Ian_Nepomniachtchi_and_Magnus_Carlsen_(cropped).jpg

Beispiel: Bucket Spiel

• Du suchst dir einen der drei Töpfe aus
• Ich wähle eine der 2 Zahlen aus dem Topf
• Dein Ziel ist, die gewählte Zahl zu maximieren

Game Tree

Game Tree

Jeder Knoten ist eine Entscheidung für einen der Spieler

Jeder Pfad von der Wurzel zu einem Blatt ist ein mögliches Ergebnis

Einschränkungen für den Start:

• 2 Spieler
• Abwechselnd Zugbasiert
• Full observation
• Deterministisch
• Zero-sum

• $\text{Players} = \{\text{agent}, \text{opp}\}$
• $s_\text{start}$: Start Zustand
• $\operatorname{Actions}(s)$: Mögliche Aktionen aus $s$
• $\operatorname{Succ}(s,a)$: Ergebnis, wenn man $a$ in Zustand $s$ macht
• $\operatorname{IsEnd}(s)$: Ob das Spiel in $s$ endet
• $\operatorname{Utility}(s)$: Utility von $\text{agent}$ (wir) im End-Zustand $s$.
• $\operatorname{Player}(s) \in \text{Players}$: Aktiver Spieler in $s$.

Schach

• $\text{Players} = \{\text{white}, \text{black}\}$
• $s_\text{start}$:
• $\operatorname{Actions}(s)$: Legale Schach Züge von $\operatorname{Player}(s)$
• $\operatorname{IsEnd}(s)$: Ist $s$ Schachmatt oder Patt?
• $\operatorname{Utility}(s)$: $+\infty$ wenn $\text{white}$ gewinnt, $0$ bei Unentschieden, $-\infty$, wenn $\text{black}$ gewinnt.

Das Halbierungsspiel

• Start mit Zahl $N$
• Spieler können abwechselnd die Zahl entweder
  • um eins verringern
  • halbieren (abgerundet)
• Der Spieler zu dessen Zug die Zahl $0$ ist gewinnt

Jupyter

          class HalvingGame:
          def __init__(self, N):
              self.N = N

          #state = (player, number)

          def start_state(self):
              return (+1, self.N)

          def is_end(self, state):
              player, number = state
              return number == 0

          def utility(self, state):
              player, number = state
              assert number == 0
              return player * float('inf')

          def action(self, state):
              return ['-', '/']

          def player(self, state):
              player, number = state
              return player

          def succ(self, state, action):
              player, number = state
              if action == "-":
                  return (-player, number - 1)
              elif action == "/":
                  return (-player, number // 2)
        

Policies

• Deterministische Policy $\pi_p(s) \in \operatorname{Actions}(s)$:
  Aktion, die Spieler $p$ in Zustand $s$ nimmt.
• Stochastische Policy $\pi(s,a)\in [0, 1]$:
  Wahrscheinlichkeit, dass Spieler $p$ Aktion $a$ in Zustand $s$ wählt.

Jupyter

Beispiel: Game evaluation

• $\pi_\text{agent}(s) = A$
• $\pi_\text{opp}(s, a) = \frac{1}{2} \text{ for } a \in \operatorname{Actions}(s)$

$V_\text{eval}(s_\text{start}) = 0$

Value eines Zustands:

\[ V_\text{eval}(s) = \begin{cases} \operatorname{Utility}(s) && \operatorname{IsEnd}(s) \\ \sum_{a \in \operatorname{Actions}(s)} \pi_\text{agent}(s, a) V_\text{eval}(\operatorname{Succ}(s,a)) && \operatorname{Player}(s) = \text{agent} \\ \sum_{a \in \operatorname{Actions}(s)} \pi_\text{opp}(s, a) V_\text{eval}(\operatorname{Succ}(s,a)) && \operatorname{Player}(s) = \text{opp} \end{cases} \]

Wenn wir die Policy unseres Gegners kennen, können wir einfach unseren Value maximieren → Expectimax

• $\pi_\text{opp}(s, a) = \frac{1}{2} \text{ for } a \in \operatorname{Actions}(s)$

$V_\text{exptmax}(s_\text{start}) = 5$

Analog zur value iteration bei MDPs:

\[ V_{\color{red} \text{exptmax}}(s) = \begin{cases} \operatorname{Utility}(s) && \operatorname{IsEnd}(s) \\ {\color{red} \max_{a \in \operatorname{Actions}(s)}} V_{\color{red} \text{exptmax}}(\operatorname{Succ}(s,a)) && \operatorname{Player}(s) = \text{agent} \\ \sum_{a \in \operatorname{Actions}(s)} \pi_\text{opp}(s, a) V_{\color{red} \text{exptmax}}(\operatorname{Succ}(s,a)) && \operatorname{Player}(s) = \text{opp} \end{cases} \]

Problem: Wir kennen $\pi_\text{opp}$ nicht!

Ansatz: Wir gehen vom Worst-Case aus.

Minimax

$V_\text{minimax}(s_\text{start}) = 1$

Policies \[ {\color{red} \pi_\text{max}} = \operatornamewithlimits{arg\,max}_{a \in \operatorname{Actions}(s)} V_\text{minimax}(\operatorname{Succ}(s,a)) \] \[ {\color{blue} \pi_\text{min}} = \operatornamewithlimits{arg\,min}_{a \in \operatorname{Actions}(s)} V_\text{minimax}(\operatorname{Succ}(s,a)) \]

Jupyter

• Expectimax: Gegner verwendet feste Policy $\color{blue} \pi_\text{x}$ und ich nehme $\color{red} \pi_\text{expmax(x)}$
• Minimax: Gegner minimiert mit $\color{blue} \pi_\text{min}$, ich maximiere mit $\color{red} \pi_\text{max}$

Was, wenn wir Expectimax gegen Minimax spielen lassen?

Beispiel: Bucket Game

Beispiel: Bucket Game, $\pi_x$ ist Münzwurf

Eigenschaft 1: Minimax ist beste Policy gegen Minimax

\[ V({\color{red}\pi_\text{max}}, {\color{blue}\pi_\text{min}}) \geq V({\color{red}\pi_\text{agent}}, {\color{blue}\pi_\text{min}}) \] für jede Policy $\color{red}\pi_\text{agent}$

Eigenschaft 2: Untere Schranke für jeden Gegner

\[ V({\color{red}\pi_\text{max}}, {\color{blue}\pi_\text{min}}) \leq V({\color{red}\pi_\text{max}}, {\color{blue}\pi_\text{opp}}) \] für jede Policy $\color{blue}\pi_\text{opp}$

Eigenschaft 3: Minimax ist nicht optimal gegen bekannte Gegner

\[ V({\color{red}\pi_\text{max}}, {\color{blue}\pi_\text{x}}) \leq V({\color{red}\pi_\text{exptmax(x)}}, {\color{blue}\pi_\text{x}}) \] für bekannte Policy $\color{blue}\pi_\text{x}$

Beispiel: Bucket Spiel 2

• Du suchst dir einen der drei Töpfe aus
• Wir werfen eine Münze und bei Kopf gehen wir einen Topf nach Links (und von A nach C)
• Ich wähle eine der 2 Zahlen aus dem Topf
• Dein Ziel ist, die gewählte Zahl zu maximieren

Im Prinzip haben wir jetzt einen neuen Spieler dazubekommen mit Policy: \[ {\color{green} \pi_\text{coin}(s,a)} = \frac{1}{2} \text{ für } a \in \{0, 1\} \]

$V_\text{exptminmax}(s_\text{start}) = -2$

$\text{Players} = \{\text{agent}, \text{opp}, {\color{green} \text{coin}}\}$

\[ V_{\text{exptminimax}}(s) = \begin{cases} \operatorname{Utility}(s) && \operatorname{IsEnd}(s) \\ {\color{red} \max_{a \in \operatorname{Actions}(s)}} V_{\text{exptminimax}}(\operatorname{Succ}(s,a)) && \operatorname{Player}(s) = \text{agent} \\ {\color{blue} \min_{a \in \operatorname{Actions}(s)}} V_{\text{exptminimax}}(\operatorname{Succ}(s,a)) && \operatorname{Player}(s) = \text{opp} \\ {\color{green} \sum_{a \in \operatorname{Actions}(s)} \pi_\text{coin}(s,a)} V_{\text{exptminimax}}(\operatorname{Succ}(s,a)) && \operatorname{Player}(s) = \text{coin} \\ \end{cases} \]

Bausteine: Max-Nodes, Chance-Nodes, Min-Nodes

Weitere Szenarien:

• Mehrere Gegner / Partner
• Komplexere Zugfolge (z.B. extra Züge)

Ansatz: Tree Search

Wie machen wir minimax schneller?

• Evaluation function: Approximiere $V$ durch Extra Wissen über das Spiel
• Alpha-beta pruning: Lasse irrelevante Teile des Suchbaums aus

Im Zustand $s$ berechnen wir $V_{\text{minimax}}(s, d_\text{max})$

Die Evaluation Function $\operatorname{Eval}(s)$ ist eine Abschätzung des wahren Wertes $V_\text{minmax}(s)$.

Ähnlich zur Heuristik $h$, die im A* die $\operatorname{FutureCost}$ abschätzt.

Beispiel Schach

$\operatorname{Eval}(s) = \text{material} + \text{mobility} + \text{king-safety} + \text{center-control}$

$\text{material} = 9(Q-Q') + 5(R-R') + 3(B-B') + 3(N-N') + 1(P-P')$

$\text{mobility} = 0.1(\text{num-legal-moves} - \text{num-legal-moves}')$

...

Im Gegensatz zu A* haben wir hier keine Garantien, wie gut unsere Approximation ist.

Wähle A oder B mit maximalem Wert

Idee: branch and bound
Wir merken uns eine untere / obere Schranke für die Value Function und ignorieren Abzweige, die außerhalb davon liegen.

Sobald wir die 2 sehen, wissen wir, dass der rechte Knoten einen Value $\leq 2$ haben muss. Daher können wir dort aufhören.

Algorithmus: Alpha-beta pruning

• Setze $[\alpha_{s_\text{start}}, \beta_{s_\text{start}}] = [-\infty, +\infty]$
• Expandieren wir $s \to s'$, dann setze
  $[\alpha_{s'}, \beta_{s'}] \gets [\alpha_s, \beta_s]$
• Hat ein Kind von $s$ den Value $v$, dann update
  • $\alpha_s \gets \max(\alpha_s, v)$ wenn $s$ ein Max-Node
  • $\beta_s \gets \min(\beta_s, v)$ wenn $s$ ein Min-Node
• Wenn $\alpha_s > \beta_s$, dann prune $s$.

Move ordering

Wieviel wir prunen hängt von der Reihenfolge ab

• Schlechteste Reihenfolge: $O(b^{2 \cdot {\color{red} d}})$ Rechenzeit
• Beste Reihenfolge: $O(b^{2 \cdot {\color{red} 0.5 d}})$ Rechenzeit
• Zufällige Reihenfolge: $O(b^{2 \cdot {\color{red} 0.75 d}})$ Rechenzeit (wenn $b = 2$)

Wir können $\operatorname{Eval}(s)$ nutzen um die Reihenfolge zu bestimmen

• Max Node: Starte mit größtem $\operatorname{Eval}(s)$ und dann absteigend
• Min Node: Starte mit kleinstem $\operatorname{Eval}(s)$ und dann aufsteigend

Lookup tables

Idee: Speichere vorberechnete Values $V$ für geläufige Zustände $s$.

Beispiel (Schach): Datenbank mit Eröffnungen und Endgame Positionen

Forward pruning

Idee: Branches abschneiden, die wahrscheinlich schlecht sind

• Von jedem Node nur die besten $n$ Kinder expandieren
• Node $s$ prunen, wenn zum Beispiel $\operatorname{Eval(s)}$ zu weit außerhalb von $[\alpha_s, \beta_s]$ liegt

Late move reduction

Idee: Für Züge, die spät in der Move Ordering kommen, reduzieren wir die Suchtiefe

Monte Carlo Tree Search

Idee: Wir simulieren komplette Spielverläufe und bewerten Knoten daran, wie oft sie zum Sieg geführt haben.

Fokus mehr auf Tiefe im Suchbaum, als auf Breite

Wie sieht $V(s,w)$ aus?

Woher kommen meine Trainingsdaten?

• Linear:
  $V(s, w) = w \cdot \phi(s)$
• Neuronales Netzwerk:
  $V(s, w, W) = w \cdot \sigma(W \phi(s))$

Beispiel: Backgammon

Daten generieren wir, indem wir basierend auf unserem aktuellen $V(s,w)$ spielen:

• $$\pi_\text{agent}(s,w) = \operatornamewithlimits{arg\,max}_{a \in \operatorname{Actions}(s)} V(\operatorname{Succ}(s,a), w)$$
• $$\pi_\text{opp}(s,w) = \operatornamewithlimits{arg\,min}_{a \in \operatorname{Actions}(s)} V(\operatorname{Succ}(s,a), w)$$

Achtung: Im allgemeinen sollten wir eine randomisierte Policy nehmen (z.B. $\epsilon$-greedy). Hier haben wir durch die Würfel schon etwas Zufall und explorieren in jedem Fall.

Jedes Spiel generiert eine Episode:
${\color{red} s_0}; a_1, r_1, {\color{red} s_1}; a_2, r_2, {\color{red} s_2}; a_3, r_3, {\color{red} s_3}; \ldots; a_n, r_n, s_n$

Wir generieren Lerndaten aus den einzelnen Stücken $(s_{t-1}, a_t, r_t, s_t)$

Prediction: $V(s_{t-1}, w)$

Target: $r_t + \gamma V(s_t,w)$

Achtung: Ein Reward von $+\infty$ oder $-\infty$ macht uns hier natürlich echt Probleme. Stattdessen nehmen wir lieber zum Beispiel $+1$ und $-1$.

Beispiel ($\eta = 0.5, \gamma = 1, \nabla V = \phi(s_{t-1})$)

Episode = $(s_0; a_1, 0, s_1; a_2, 0, s_2; a_3, 1, s_3)$

$\phi(s_0) = [0,1], \phi(s_1) = [1, 0], \phi(s_2) = [1, 2], \phi(s_3) = [1, 0]$

Beispiel Fortsetzung ($\eta = 0.5, \gamma = 1, \nabla V = \phi(s_{t-1})$)

Episode = $(s_0'; a_1', 0, s_1'; a_2', 0, s_2'; a_3', -1, s_3')$

$\phi(s_0') = [0,1], \phi(s_1') = [1, 0], \phi(s_2') = [-1, 2], \phi(s_3) = [1, 0]$

Dank Bootstrapping machen wir auch schon Updates während der Reward noch 0 ist.

Sollten alle Fehler 0 werden, gilt
$V(s_0, w) = V(s_1, w) = V(s_2, w) = \ldots = V(s_n, w) = \text{Utility}$
Wir hätten also ein ideales $V$.

TD Learning

• Abschätzen von $V_\pi(s)$
• On-policy (Values sind abhängig von aktueller Policy)
• Nicht Model-free (Wir müssen das Spiel und $\operatorname{Succ}$ kennen.

Mit geschätztem $V$ könnten wir auch immer die Aktion nehmen, die maximales $V$ im nächsten Zustand hat.

Warum brauchen wir MiniMax Suche überhaupt noch?

Welcher Spieler liegt vorne?

Nach 3 weiteren Zügen

Spätere Zustände lassen sich oft einfacher bewerten. Durch MiniMax bekommen wir mehr Leistung aus der Evaluierungsfunktion.

Dame

Arthur Samuels Dame Programm (1959)

• Lineare Evaluation Funktion mit cleveren Features
• Self-Play, Intermediate Rewards
• Alpha-Beta Pruning und Such Heuristiken
• Menschlicher Amateur Level

Backgammon

TD-Gammon von Gerald Tesauro (1992)

• Neuronales Netzwerk, "dumme" Features
• Self-Play (1 Million Spiele), keine intermediate Rewards
Verfeinerte Variante von TD Learning
• Menschlicher Experten Level

Schach

Deep Blue von IBM (1996)

• Hand designte Evaluation Function mit gelernten Parametern
• Trainiert auf Großmeister Partien
• Umfangreiche Positionsdatenbank
• Parallelisiertes Alpha-Beta Pruning auf spezieller Hardware
• Sieg gegen Weltmeister Garry Kasparov (1997)

Go

AlphaGo Zero von DeepMind (2017)

• Neuronales Netzwerk, "dumme" Features
• Self-Play (4.9 Millionen Spiele), keine intermediate Rewards
• Monte Carlo Tree Search
• 2017 Sieg gegen Vorgänger AlphaGo (2015)
• Fand komplett neue Strategien; gab neue Einsichten in das Spiel

https://en.wikipedia.org/wiki/File:13_by_13_game_finished.jpg

Schere, Stein, Papier

Hier kommen wir mit Game Trees nicht weiter.

https://en.wikipedia.org/wiki/File:Rps2010_2.jpg

Two-finger Morra

• Spieler A und B zeigen jeder 1 oder 2 Finger
• Der Gewinner erhält die Anzahl gezeigte Finger als Punkte
• Wenn die Anzahl gerade ist gewinnt A, ansonsten B

Single Move Simultaneous Game

• $\text{Players} = \{A, B\}$
• $\text{Actions}$: Eine Menge an möglichen Aktionen
• $V(a,b)$: Die Utility von A, wenn A Aktion a und B Aktion b macht

$V$ ist die Payoff Matrix

Beispiel Strategien für Two-finger Morra:

• Immer 1: $\pi = [1, 0]$
• Immer 2: $\pi = [0, 1]$
• Gleichverteilt zufällig: $\pi = [\frac{1}{2}, \frac{1}{2}]$

Wir ermitteln den Value von einem Paar von Strategien als \[ V(\pi_A, \pi_B) = \sum_{\substack{a \in \text{Actions}\\ b \in \text{Actions}}} \pi_A(a) \pi_B(b) V(a,b) \]

• Spieler A nimmt immer 1: $\pi_A = [1, 0]$
• Spieler B spielt zufällig: $\pi_B = [\frac{1}{2}, \frac{1}{2}]$

$V(\pi_A, \pi_B) = 1 \cdot \frac{1}{2} \cdot 2 + 1 \cdot \frac{1}{2} \cdot -3 = - \frac{1}{2}$

Wie optimieren wir die Strategy?

A will $V(\pi_A, \pi_B)$ maximieren,
B will $V(\pi_A, \pi_B)$ minimieren

Angenommen, wie spielen abwechselnd

Spieler A zuerst

Spieler B zuerst

$${\color{red} \max_{a}}\,{\color{blue}\min_{b}} V(a,b) \leq {\color{blue}\min_{b}}\, {\color{red} \max_{a}} V(a,b)$$

Was passiert, wenn wir unserem Gegner verraten, welche Mixed Strategy wir verwenden?

Spieler A verrät, dass er $\pi_A = [\frac{1}{2}, \frac{1}{2}]$ spielt.

\[ V(\pi_A, \pi_B) = \frac{1}{2} \pi_B(1)\cdot 2 + \frac{1}{2} \pi_B(1)\cdot (-3) + \frac{1}{2} \pi_B(2) \cdot (-3) + \frac{1}{2} \pi_B(2) \cdot 4\\ = - \frac{1}{2} \pi_B(1) + \frac{1}{2} \pi_B(2) \]

Optimale Strategie für B ist $\pi_B = [1, 0]$
mit Value $-\frac{1}{2}$.

Strategie von Spieler A ist $\pi_A = [p, 1-p]$.

\[ V(\pi_A, [1,0]) = p \cdot (2) + (1-p) \cdot (-3) = 5p - 3 \]

\[ V(\pi_A, [0,1]) = p \cdot (-3) + (1-p) \cdot (4) = -7p + 4 \]

\[ \pi_B = \begin{cases} [1,0] && \text{if } 5p-3 \leq -7p + 4 \\ [0,1] && \text{else} \end{cases} \]

Spieler B optimiert Strategie: \[ {\color{blue}\min}(5p - 3, -7p + 4) \]

Folgerichtig will Spieler A seine Strategie optimieren: \[ {\color{red} \max_{0 \leq p \leq 1}}\, {\color{blue}\min}(5p - 3, -7p + 4) \]

Das Ergebnis ist der Schnitt der beiden Geraden: \[ 5p - 3 = -7p + 4 \Rightarrow p = \frac{7}{12}, V = - \frac{1}{12} \]

Was, wenn B seine Strategie $\pi_B = [p, 1-p]$ verraten muss?

\[ V([1,0], \pi_B) = p \cdot (2) + (1-p) \cdot (-3) = 5p - 3 \]

\[ V([0,1], \pi_B) = p \cdot (-3) + (1-p) \cdot (4) = -7p + 4 \]

\[ {\color{blue} \min_{0 \leq p \leq 1}}\,{\color{red} \max}(5p - 3, -7p + 4) = - \frac{1}{12} \text{ mit } p = \frac{7}{12} \]

Ausblick (nicht Teil dieser Vorlesung):

• Wie berechnet man die optimale Strategie allgemein? (Linear Programming)
• Erweiterung auf mehrere Züge
• Incomplete Information Games

Sei $V_{\color{red} p}(\pi_A, \pi_B)$ die Utility von Spieler $\color{red} p$.

Von Neumanns Minimax Theorem gilt nicht (nicht Zero-Sum). Wir brauchen daher etwas anderes.

Beispiele

• Two-finger Morra:
  Beide spielen $\pi = [\frac{7}{12}, \frac{5}{12}]$
• Kooperatives two-finger Morra:
  
  • Beide spielen immer 1
  • Beide spielen immer 2
• Prisoner's Dilemma:
  Beide sagen gegeneinander aus

Poker

Cepheus (University of Alberta) (2015)

• Weakly solved heads-up limit Texas hold 'em
• Findet Strategie sehr nah am Nash Equilibrium
• Counterfactual Regret Minimization zum Lösen der Linearen Programme
• Hat den Poker Stil auf Profi Niveau komplett geändert

https://commons.wikimedia.org/wiki/File:Holdem.jpg

Andere "Spiele"

• Personalverteilung im Sicherheitsbereich am Flughafen
• Patrouillenrouten der Küstenwache
• Design von Marktplätzen und Vergabesystemen