dl4g

• das Spiel konnte nur teilweise beobachtet werden
• z.B. kennt man nicht die Karten der anderen Spieler
 

• Perfekt (Schach)
• Nicht perfekt (Jass)
 

• Anzahl gültige Brettpositionen
• untere Grenze für Suchbaum
 

• Knoten sind Spielpositionen / Spielzustände
• Kanten sind Aktionen / Spielzüge
• Blätter werden durch payoff functions definiert
 

• Baum von unten nach oben durcharbeiten
• immer bester Weg für den aktuellen Spieler markieren
• für sequenzielle endliche Spiele mit perfekter Information geeignet
 

Spieler nimmt nicht die schlechtere Alternative
 

• ultraschwach
– hat der erste Spieler ein Vorteil
– beispielsweise durch Existenzbeweise in Mathe
– Wissen das erste Personen einen Vorteil hat
– ohne genaue Strategie zu kennen
• schwache Lösung
– kann ein komplettes Spiel durchspielen
– Annahme dass der Gegner sich rational verhält
• starke Lösung
– immer durchsetzbar auch wenn nicht erster Spieler
– kann von jeder Position aus gewinnen
 

• Vorteil für einen Spieler ist zum Nachteil des anderen Spielers
• Punktesumme für zwei Strategien ist immer 0
 

• gilt nur für einen Nullsummenspiel
• zwei Möglichkeiten / Ziele
– eigenen Gewinn maximieren
– Gewinn des Gegners minimieren

• 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 einen Endknoten ist: payoff berechnen
 

• nicht relevante Teilbäume weglassen
• Reduzierung des Rechenaufwands
 

• α ist der grösste Wert aller MAX Vorfahren eines MIN Knoten
• β ist der kleinste Wert aller MIN Vorfahren eines MAX Knoten
• Teilbaum abschneiden, falls grösser als α oder kleiner als β
 

• b = Anzahl Kanten pro Knoten
• m = Tiefe des Baumes
• von O(bˆm) nach O(bˆ(m/2))
• halbieren der Tiefe des Suchbaume

• Suchraum ist oft zu grosse für eine vollständige Suche
• die Idee bei minimax ist bei einer bestimmten Tiefe zu stoppen und zu raten
• eine alternative ist der Monte Carlo Tree Search
 

• macht einen Random Walk und spielt zufällige Simulationen
• versucht in einer fixen Zeit möglich viel des Suchraumes zu entdecken
• am Schluss wird der vielversprechenste Spielzug ausgewählt
 

1. Selection:
• Start from root node R and select successive child nodes
• Stop when you reach a leaf or a node that has not yet been fully expanded
• Needs a criterion for selecting child nodes called tree policy
2. Expansion:
• If L ends the game, return payoffs
• Otherwise, choose an unexplored action and create a node C for it
3. Simulation:
• Simulate a playout from node C using a default policy
• In the simplest case, just play the game to an end with random moves
4. Backpropagation:
• Update the information stored in each node from C back to the root node R
• Monte Carlo Tree Search expects payoffs in [0,1]
 

• Exploitation:
– immer bestes payoff wählen
– Anhand der Beobachtungen auf der besten Maschine spielen um Gewinn zu maximieren
• Exploration:
– etwas neues wählen, versuchen möglichst viel zu erkunden
– alle Maschinen spielen um möglichst viel Informationen zu gewinnen
 

• steht für Upper Confidence Bound
• beste Strategie ist Mischung aus Exploitation und Exploration
• ergibt ein statistischen Konfidenzintervall für jede Option
• Parameter c kontrolliert trade-off zwischen Exploitation und Exploration
 

immer die Vektor-Komponente des aktuellen Spieler für die Berechnung verwenden
 

Aktion spielen mit der höchsten Anzahl an Besuchen
 

• beide Algorithem setzen perfekte Information voraus
• Minimax ist nur anwendbar auf Nullsummenspiele mit zwei Spieler
• Monte Carlo Tree Search funktioniert für jedes Spiel mit perfekter Information
• Minimax optimiert payoffs; MCTS optimizes an exploitation-exploration tradeoff
• MCTS ist ein Anytime-Algorithmus, Minimax nicht
• Monte Carlo Bäume sind asymetrisch; Minimax Bäume sind symterisch
 

Kann eine gültige Lösung zurückgeben, auch wenn die Ausführung abgebrochen wird
 

• für ein Beispiel mit zwei Spieler nimmt der payoff Vektor die Form [W, N - W] an
• Spieler 1 maximiert W, Spieler 2 maximiert N - W
• ebenso kann Spieler 2 -W minimieren
 

• ist eine Menge von Knoten des gleichen Spielers
• Spieler kennt vorherigen Zug nicht
• alle Knoten müssen gleiche Optionen bieten
• immer aus Sicht eines Spielers
 

• unterschiedliche Strategien werden gewählt
• bei perfekter Information hat jeder Knoten exakt eine Option
 

• unbekannte Karten zufällig auf die Gegner verteilen
• danach anwenden der Regeln von vollständiger Information (beispielsweise mit MCTS)
• ergibt dann mehrere mögliche Spielbäume
• schlussendlich über alle Bäume die Option welche am meisten besucht wurde
• manchmal werden Entscheidung getroffen, welche gar nie eintreten können
• kann zu falschen Entscheidungen führen

• Baum besteht aus Information Sets und nicht mehr aus Zuständen
• Knoten entsprechen Information Sets aus 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
• Danach funktioniert es wie ein Spiel mit perfekter Information
 

• Np = wie oft wurde der Vorgänger Knoten gespielt und i war verfügbar
• dazu muss die Knotenliste ergänzt werden mit wie viel Mal jede Option verfügbar war
 

1. Supervised Learning
• dem Algorithmus werden gelabelte Trainingsdaten gegeben
• der Algorithmus lernt Labels von unbekannten Daten vorherzusagen
2. Unsupervised Learning
• dem Algorithmus werden nicht gelabelte Trainingsdaten gegeben
• der Algorithmus entdeckt selbständig die Struktur der Daten
3. Semi-Supervised Learning
• eine Mischung zwischen Supervised und Unsupervised Learning
• wird meistens benutzt wenn eine kleine Anzahl an gelabelten Daten zur Verfügung stehen
4. Reinforcement Learning
• Keine Daten stehen zur Verfügung
• der Algorithmus wird durch eine Reward Funktion geleitet
• das ideale Verhalten wird gesucht um die Reward Funktion zu maximieren
 

• schlecht designet, mangelhafte oder inkonsistente Datenformate
• Programmierfehler oder technische Probleme
• Alter der Daten (z.B. ungültige E-Mail Adressen)
• schlechte Dateneingabemasken (fehlende Validierung)
• menschliche Fehler bei der Daten Exportierung
• ungültige oder falsche Informationen
 

• Datenquellen und deren Zuverlässigkeit überprüfen
• Statistische Kennzahlen interpretieren und überprüfen
• Visuelles überprüfen eines Datenauszug
• manuell Datenbereiche überprüfen (z.B. negative Löhne)
• Plausibilität von Zusammenhänge überprüfen
• Redundanz der Daten messe
• Abweichungen in Syntax und Semantik der Daten
• NULL-Werte und doppelte Daten untersuchen
 

• Daten in Testdaten und Trainingsdaten aufteilen
• Klassifikator auf den Trainingsdaten trainieren
• Klassifikator anhand der Testdaten bewerten
 

=> funktioniert nur mit vielen Daten und wenn die Hyperparameter festgelegt sind
 

• ca. 70% - 80% Trainingdaten
• ca. 20% - 30% Testdaten
 

• Daten zufällig mischen
• Daten aufteilen in Training und Test
• Training und Testdaten müssen disjunkt sein