Embed Size (px)
Citation preview
TD-Gammon
● Ein Backgammon-Spieler von Gerald Tesauro (Erste Version: 1991)
TD-Gammon
● Ein Neuronales Netz, das immer wieder gegen sich selbst spielt und dadurch lernt, eine gute Bewertungsfunktion für Backgammon-Positionen zu sein
● Eine Erfolgsgeschichte für Reinforcement Learning
● Der damals stärkste Computerspieler● Weltklassespieler haben von TD-Gammon
Eröffnungszüge übernommen.
Backgammon
● Ein uraltes Spiel für zwei Spieler● Wahrscheinlich 1000 Jahre älter als Schach
Backgammon
● Es wird gewürfelt. Beide Spieler müssen ihre Steine nach Hause bringen. Denkt an Mensch, ärgere Dich nicht.
● Die Strecke ist eindimensional und kein Kreis.● Die Spieler kommen einander entgegen.● Einzelne Steine können herausgeworfen werden.
Zusammen stehende Steine blockieren.● Es wird um Geld gespielt, oder um Punkte in
Matches aus vielen Runden.
Backgammon
Das Problem
● Komplexe Spiele haben riesige Zustandsmengen.– Für Backgammon: ca. 1020
– Spiel nach Wertetabelle ist daher unmöglich.● Hoher Verzweigungsfaktor
– Für Backgammon: etwa 420 ● 21 verschiedene Würfe● durchschnittlich 20 mögliche Züge pro Wurf
– zu viel, um tief im Spielbaum zu suchen– zum Vergleich:
● Schach 30-40● Dame 8-10
Die Lösung
● Heuristische Bewertung von Spielpositionen● Approximation der theoretischen Value-Function● Bisherige Ansätze:
– Design einer Bewertungsheuristik mit menschlichen Experten
– Überwachtes Lernen eines neuronalen Netzes anhand einer Spieldatenbank (Neurogammon, 1989)
● Neuheiten bei TD-Gammon:– keinerlei Vorwissen über das Spiel– keinerlei Beeinflussung durch die Auffassung
menschlicher Spieler
Das neuronale Netz
● approximiert beliebige stetige Funktionen● lernt durch Änderung der Kantengewichte
Das neuronale Netz in TD-Gammon
● Eingabe: Einfache Repräsentation des Spielfeldinhalts durch 198 Werte
● Ausgabe: Geschätzte Wahrscheinlichkeit für– einfachen Sieg– doppelten Sieg– einfachen Sieg des Gegners– doppelten Sieg des Gegners
● 40-80 Innere Knoten (hidden units)
Repräsentation einer Spielposition
● 4 Eingänge stehen für die Anzahl der weißen Steine auf einem Feld
● 4 Eingänge stehen für die Anzahl der schwarzen Steine auf einem Feld
● 2 Eingänge stehen für die weißen bzw. schwarzen Steine, die gerade herausgeworfen sind
● 4 Eingänge stehen für die weißen bzw. schwarzen Steine, die bereits zu Hause sind
● 2 Eingänge stehen dafür, ob weiß bzw. schwarz am Zuge ist
Ein Spielzug
● Würfle● Bewerte für jeden möglichen Zug die
resultierende Spielposition (after state)● optional: schaue für einige der am besten
bewerteten Positionen zwei oder drei Halbzüge in die Zukunft
● Wähle den besten Zug● Lerne
Lernen
● Das Netz wird mit kleinen, zufälligen Gewichten initialisiert. Es bewertet zunächst völlig zufällig.
● Nach jedem Zug wird der TD(λ)-Algorithmus angewendet, um die Gewichte zu verbessern.
wt1− wt=Y t1−Y t∑k=1
tt−k ∇ w Y k
Lernen
wt1− wt=Y t1−Y t∑k=1
tt−k ∇ w Y k
● w: Kantengewichte des Netzes● α: Lernparameter● Y
t+1: Bewertung der Spielposition S
t+1 durch das
Netz mit den Gewichten wt
● λ: Verfallsparameter
Gradientenabstiegsverfahren
● Bilde den Gradienten des TD-Fehlers bezüglich der Kantengewichte.
● Interpretiere ihn als Maß dafür, wie stark das jeweilige Gewicht am Fehler beteiligt ist.
➔ Je größer der Gradient in einer gewissen Koordinate, desto stärker verändere das entsprechende Gewicht.
−∇ wY t1−Y t2
TD(λ)
● Auch Gewichte, die für länger zurückliegende Züge ausschlaggebend waren, sollen in Erwägung der aktuelle Position verbessert werden.
● Und zwar nicht bis zu einer festen Anzahl n vergangener Schritte, sondern durchgängig in geringerem Maße, je länger der Zug her ist.
● λ heißt Verfalls-Parameter und gibt an, wie stark die Relevanz einer zurückliegenden Entscheidung nach jedem Zug abnimmt.
∈[0,1]
Eligibility Traces
● Konsequenz: Es wird ein Vektor aus sogenannten eligibility traces geführt.
● Sie geben an, in welchem Maße jedes Gewicht es gerade verdient (eligible), verändert zu werden, basierend auf aktueller und vergangener Relevanz.
Eligibility Traces
● Die eligibility traces werden nach jedem Zug mit dem Verfalls-Parameter multipliziert und verblassen etwas.
● Sodann kommen die Relevanzen für den aktuellen Fehler hinzu:
e e∇ w Y t
Nocheinmal: Die Lernformel
● Zusammengefasst:
et=∑k=1
tt−k ∇ w Y k
wt1− wt=Y t1−Y t et
et1=et∇ w Y t
Erfolge
Splittest du oder slottest du?
Seit einer Analyse durch TD-Gammon wird ein Eröffnungszug, der bis dahin als selbstverständlich galt, praktisch nicht mehr gespielt.
● Wurf: 4/1● weiß ist am Zug
Absolute und relative Genauigkeit
● TD-Gammons Einschätzungen liegen oft um mehr als einen zehntel Punkt daneben.
● Das macht aber nichts. Offenbar liegen die Einschätzungen benachbarter Züge hinreichend gleich daneben, so dass trotzdem sehr gute Entscheidungen getroffen werden.
Würfeln fördert den Lernprozess
● Weil gewürfelt wird, kommen automatisch sehr verschiedene Spielsituationen zustande.
● Das ist wichtig bei selbst lernenden Systemen. Sonst könnte es sein, dass bei schlechter Initialisierung große Teile des Positionsraums gar nicht besucht werden.– Bei selbst lernenden Dame- und Go-Spielern ist das
ein Problem.● TD-Gammon hat und braucht keinen weiteren
Mechanismus für erforschende Züge.
Würfeln fördert den Lernprozess
● Auch bei zwei dümmstmöglichen Spielern geht das Spiel immer auf sein Ende zu.
● Die theoretische Value-Funktion ist einigermaßen stetig und glatt. Kleine Veränderungen der Position bewirken kleine Veränderungen der Gewinnchancen.
● Bei deterministischen Spielen ist die theoretische Value-Funktion diskret. (Gewinne ich, verliere ich, unentschieden)
Lineare Eigenschaften
● TD-Gammon geht ohne den blassesten Dunst einer Ahnung von Backgammon an den Start
● ...und findet sehr schnell heraus, dass es Erfolg versprechend ist,– andere Steine zu schlagen– eigene Steine zu schützen– starke Positionen aufzubauen
● Diese Dinge nennt man linear features des Backgammon-Spiels, weil man sie durch lineare Funktionen der Position beschreiben kann.
Lineare Eigenschaften
● Man folgert: Neuronale Netze kombiniert mit TD-Learning entdecken sehr schnell den linearen Anteil einer Funktion
● Trotzdem werden in späteren Versionen von TD-Gammon wieder bestimmte Features per Hand kodiert und als zusätzliche Eingaben an das neuronale Netz gelegt.
Das wars!
