HSLU DL4G HS20

• Beginnen mit einer zufälligen Policy
• Berechnen der Value-Funktion v unter Berücksichtigung der aktuellen Policy
• Policy verbessern durch greedy-Auswahl der Aktionen aus v
• Wiederholen, bis sich die Policy nicht mehr verändert
   

• Den Baum von unten nach oben durcharbeiten (oder eben von rechts nach links)
• Immer den besten Weg (mit dem höchsten Payoff) für den aktuellen Spieler markieren
• Ist für sequenzielle endliche Spiele mit perfekter Information geeignet
   

• Wenn der Knoten mir gehört: Aktion wählen, die den Payoff maximiert
• Wenn der Knoten dem Gegner gehört: Aktion wählen, die den Payoff minimiert
• Wenn es ein Endknoten ist: Den Payoff berechnen

\(U_i ={W_i \over N_i} + c\sqrt{ln(N_p) \over N_i} \)

• W_i = Anzahl Gewinne mit der Maschine i
• N_i = Anzahl Versuche mit der Maschine i
• N_p = Anzahl Versuche insgesamt
• c = Verhältnis von wie viel Exploitation (tiefes C), bzw. Exploration (hohes C) verwendet werden solte. Erfahrungswert ist \(\sqrt2\)

• Deep Blue
  • 8000 handgefertigte Features
  • Evaluation des Bretts mit dem Skalarprodukt zwischen Features und Gewichten
  • Gewichte wurden vor allem von Hand angepasst durch menschliche Experten
  • High-Performance parallele Minimax mit Alpha-Beta Pruning
  • 480 spezialgefertige VLSI Schach-Prozessoren
  • Durchsucht 200 Millionen Positionen pro Sekunde
     

Knoten (Neuronen) mit Kanten (verbindungen), optional sind Neuronen in Layern gruppiert

• (Teilweis-)Linear
  • ReLU
• Nicht Linear
  • Softmax (Sigmoid),
  • tanh

Nicht-lineare Aktivierungsfunktionen machen das Netzwerk besonders mächtig

Greedy Algorithmen würden in lokalen Minima oder Maxima hängen bleiben d.h. ein globales Maximum oder Minimum wird nicht gefunden

Grid World ist ein rechteckiges 2D-Raster (Ny, Nx), bei dem ein Agent an einem Feld beginnt und versucht, zu einem anderen Feld zu wechseln, das sich an einer anderen Stelle befindet. Eine solche Umgebung ist eine natürliche Umgebung für die Anwendung von Reinforcement learning algorithmen, um optimale Pfade und Policies für Agenten auf dem Grids zu finden, um in möglichst wenigen Zügen die gewünschten Ziel-Felder zu erreichen.

minimax mit 8000 heuristiken

[Stochastic] Gradient descent -> Ableitung und dann iterativ in richtung Minimum

Gleich viele Daten beider Klassen (Negativ und Positiv)

Ist ein off policy, model freier reinforcement learning algorithm. Ähnlich zu SARSA

gradient descent: gradient berechnen um minimum zu finden 

• SGD: Stochastic gradient descent (Stochastisches Gradientenverfahren)
  • Das Ziel ist hier, die Kosten pro Iteration unabhängig von n werden zu lassen, um den hohen Rechenaufwand des normalen Gradientenverfahren zu minimieren

• Der Suchraum ist oft zu gross für eine vollständige Suche
• Die Idee, verglichen zu Minimax, ist, bei einer bestimmten Tiefe zu stoppen und zu raten
   

• Ein Information Set ist eine Menge von Knoten des gleichen Spielers
• Der Spieler kennt den vorherigen Zug nicht
• Alle Knoten müssen die gleichen Optionen bieten
• Sind immer aus der Sicht eines Spielers
   

• Macht einen Random Walk und spielt zufällige Simulationen
• Versucht, in einer fixen Zeit möglichst viel des Suchraums zu entdecken
• Am Schluss wird der vielversprechendste Spielzug ausgewählt
   

Perfekte Erinnerung an alle vorherigen Züge

1. Selection
2. Expansion
3. Simulation
4. Backpropagation
    

• Unterschiedliche Strategien werden gewählt
• Bei perfekter Information hat jeder Knoten exakt eine Option
   

• Starte beim Wurzelknoten R und wähle fortlaufend Kinderknoten
• Stoppe, wenn du einen Knoten erreichst, der noch nicht komplett erweitert/erforscht wurde
• Benötigt ein Kriterum für die Auswahl der Kinderknoten, sogennante tree policy
   

Sagt einem Spieler, welche Aktion im aktuellen Zug auszuführen ist

• Wenn das Zeitlimit L das Spiel beendet, gib die Payoffs zurück
• Sonst, wähle eine unerforschte Aktion und kreiere einen Knoten C für diese
   

• Unbekannte Karten zufällig auf die Gegner verteilen
• Danach das Anwenden der Regeln von perfekter Information (bspw. mit MCTS)
• Ergibt dann mehrere mögliche Suchbäume
• Schlussendlich über alle Bäume die Option wählen, die am meisten besucht wurde
• Manchmal werden Entscheidungen getroffen, welche gar nie eintreten können, was zu falschen Entscheidungen führen kann
   

• Simuliere ein Weiterspielen von Knoten C aus, mithilfe einer default policy
• Im simpelsten Fall, spiele einfach bis zu irgendeinem Ende mit zufälligen Zügen
   

Die ausgewählte Strategie eines Spielers

• Aktualisiere die gespeicherten Informationen in jedem Knoten von C zurück bis zu R
• MCTS erwartet einen Payoff in [0,1]
   

• Der Baum besteht aus Information Sets und nicht mehr aus Zuständen
• Knoten entsprechen Information Sets aus der Sicht des Wurzelspielers
• Karten werden zufällig verteilt und ungültige Varianten werden ausgeblendet
• Kanten entsprechen einer Aktion, welche in mindestens einem Zustand möglich ist
• Funktioniert danach wie ein Spiel mit perfekter Information