HSLU DL4G HS20
Deeplearning 4 Games HS20; Special Thanks to: Cyrille Ulmi
Deeplearning 4 Games HS20; Special Thanks to: Cyrille Ulmi
Set of flashcards Details
| Flashcards | 124 |
|---|---|
| Language | Deutsch |
| Category | Computer Science |
| Level | University |
| Created / Updated | 22.01.2021 / 09.01.2023 |
| Weblink |
https://card2brain.ch/box/20210122_hslu_dl4g_hs20
|
| Embed |
<iframe src="https://card2brain.ch/box/20210122_hslu_dl4g_hs20/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Was sind die Eigenschaften von endlichen-sequenziellen Spielen?
- Eine endliche Anzahl Spieler mit einer endlichen Anzahl Aktionen
- Die Aktionen werden sequenziell ausgewählt
- Es wird eine endliche Anzahl Runden gespielt
- Spätere Spieler sehen die Aktionen vorheriger Spieler
Wieso werden Random Walks eingesetzt? (Tree Search)
- 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
Was ist ein Information Set?
- 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
Was ist die Idee hinter Monte Carlo Tree Search?
- 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
War wird unter Perfect Recall verstanden?
Perfekte Erinnerung an alle vorherigen Züge
Welche 4 Phasen gibt es bei Monte Carlo Tree Search?
- Selection
- Expansion
- Simulation
- Backpropagation
Was ist der Unterschied zwischen perfekter und imperfekter Information?
- Unterschiedliche Strategien werden gewählt
- Bei perfekter Information hat jeder Knoten exakt eine Option
Was passiert in der Selection Phase des Monte Carlo Tree Search
- 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
Was ist eine Strategie?
Sagt einem Spieler, welche Aktion im aktuellen Zug auszuführen ist
Was passiert in der Expansion Phase des Monte Carlo Tree Search
- 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
Was ist die Idee hinter Determinization?
- 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
Was passiert in der Simulation Phase des Monte Carlo Tree Search
- 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
Was ist ein Strategie-Profil?
Die ausgewählte Strategie eines Spielers
Was passiert in der Backpropagation Phase des Monte Carlo Tree Search
- Aktualisiere die gespeicherten Informationen in jedem Knoten von C zurück bis zu R
- MCTS erwartet einen Payoff in [0,1]
Was muss bei einer Implementation von Monte Carlo Tree-Search (MCTS) mit Information Sets beachtet werden?
- 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
Welche zwei Ansätze gibt es beim Auswählen eines neuen Knotens?
- Exploitation
- Exploration
Was ist eine Utility- oder Payoff-Function?
Sie berechnet das Resultat für jede Aktion
Was versteht man unter Exploration bei der Auswahl eines Knotens
- Etwas Neues wählen, versuchen möglichst viel zu erkunden
- Alle Maschinen spielen, um möglichst viel Informationen zu gewinnen
Wie muss die UCB1 (Upper Confidence Bound) angepasst werden für Information Sets?
- N_p = Anzahl Besuche des Vorgänger-Knotens und wie oft Knoten i verfügbar war
- Knotenliste ergänzen um „wie viel mal war jede Option verfügbar“
Was versteht man unter Exploitation bei der Auswahl eines Knotens
- Immer den besten Payoff wählen
- Anhand von Beobachtungen auf der besten Maschine spielen, um Gewinn zu maximieren
Was sind die Komplexitätsfaktoren bei einer Spielanalyse?
- Anzahl Spieler
- Grösse des Suchraums (Anzahl gespielte Züge & Anzahl mögliche Aktionen)
- Kompetitiv vs. Kooperativ
- Stochastische Spiele (mit Zufall) vs. Deterministisch
- Perfekte vs. imperfekte Information
Was ist die Idee hinter UCB1 (Upper Confidence Bound)?
- Die beste Strategie ist eine Mischung aus Exploitation und Exploration
- Ergibt ein statistisches Konfidenzintervall für jede Option
- Parameter c kontrolliert den Trade-Off zwischen Exploitation und Exploration
Was ist imperfekte Information?
- Das Spiel konnte nur teilweise beobachtet werden
- Man kennt bspw. nicht die Karten der anderen Spieler
Was ist sehr wichtig bei der Anwendung von UCB1 (Upper Confidence Bound)?
Immer die Vektor-Komponente des aktuellen Spielers für die Berechnung verwenden
Beispiele von Spielen mit perfekten / imperfekten Informationen?
Perfekt (Schach, Go) und imperfekt (Jass, Poker)
Was passiert bei MCTS, wenn die Zeit abgelaufen ist?
Spielt die Aktion mit der höchsten Anzahl an Besuchen
Was ist der Suchraum?
Anzahl gültige Brettpositionen und die untere Grenze des Suchbaums
Was sind die 6 wichtigsten Unterschiede zwischen Minimax und MCTS?
- Beide Algorithmen setzen perfekte Informationen voraus
- Minimax ist nur anwendbar auf Nullsummenspiele mit zwei Spielern
- MCTS funktioniert für jedes Spiel mit perfekter Information
- Minimax optimiert Payoffs, MCTS optimiert einen Exploitation-Exploration Trade-Off
- MCTS ist ein Anytime-Algorithmus, Minimax nicht
- Monte Carlo Bäume sind asymmetrisch, Minimax Bäume sind symmetrisch
Was ist ein Suchbaum?
- Knoten sind Spielpositionen / Spielzustände
- Kanten sind Aktionen / Spielzüge
- Blätter werden durch Payoff-Funktionen definiert
Was ist ein Anytime-Algorithmus?
- Er kann eine gültige Lösung zurückgeben, auch wenn die Ausführung vorzeitig abgebrochen wird.
- Es wird erwartet, dass er eine immer bessere Lösung findet, je länger er ausgeführt wird.
Wie funktioniert Backward Induction?
- Den Baum von unten nach oben durcharbeiten (bzw. von rechts nach links)
- Immer den besten Weg für den aktuellen Spieler markieren
- Geeignet für sequenzielle endliche Spiele mit perfekter Information
Wie sehen die Payoffs bei MCTS aus und was wird maximiert?
- Für ein Beispiel mit 2 Spielern nimmt der Payoff-Vektor die Form (W; N W) an
- Spieler 1 maximiert W, Spieler 2 maximiert N W (implizit minimiert Spieler 2 so auch W)
Was bedeutet Rationalität?
Dass der Spieler nicht die schlechtere Alternative wählt
Welche Arten von Lösungen werden bei endlich-sequenziellen Spielen unterschieden?
- Ultra-schwache Lösung
- Schwache Lösung
- Starke Lösung
Was versteht man unter Ultra-schwache Lösung bei endlich-sequenziellen Spielen
- Bestimmt, ob der erste Spieler einen Vorteil aus der Initialposition hat, ohne die genaue Strategie zu kennen
- Setzt perfektes Spielen des Gegners voraus
- Beispielsweise durch Existenzbeweise in der Mathematik
Was versteht man unter schwache Lösung bei endlich-sequenziellen Spielen
- Kann ein komplettes Spiel mit perfekten Zügen aus der Initialposition durchspielen
- Geht von einem perfekten Spiel des Gegners aus
Was versteht man unter Starke Lösung bei endlich-sequenziellen Spielen
- Kann aus jeder Position heraus perfekte Züge spielen
- Kann auch gewinnen, wenn vorherige Spieler einen Fehler gemacht haben
Was versteht man unter einem Zero-Sum Game (Nullsummenspiel)?
- Der Vorteil für einen Spieler ist zum Nachteil des anderen Spielers
- Die Punktesumme für zwei Strategien ist immer gleich Null
Was sind Charakteristiken des Minimax-Algorithmus?
- Gilt nur für ein Nullsummenspiel
- Zwei Möglichkeiten / Ziele
– den eigenen Gewinn maximieren
– den Gewinn des Gegners minimieren
Wie funktioniert der Minimax-Algorithmus?
- 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
