TD-Gammon ist ein Computerprogramm für Backgammon, das in den 1990er Jahren von Gerald Tesauro am Thomas J. Watson Research Center von IBM entwickelt wurde. Sein Name leitet sich von seiner Verwendung eines künstlichen neuronalen Netzes ab, das durch Temporal-Difference-Lernen, insbesondere TD-Lambda, trainiert wurde. Es erkundete Strategien, die Menschen nicht verfolgt hatten, und führte zu Fortschritten in der Theorie des korrekten Backgammonspiels. Im Jahr 1993 wurde TD-Gammon (Version 2.1) mit 1,5 Millionen Spielen des Selbstspiels trainiert und erreichte ein Spielniveau, das nur geringfügig unter dem der damaligen besten menschlichen Backgammonspieler lag. Im Jahr 1998 wurde es während einer Serie von 100 Spielen vom Weltmeister mit einem knappen Vorsprung von lediglich 8 Punkten besiegt. Seine unkonventionelle Bewertung einiger Eröffnungsstrategien wurde von Experten akzeptiert und übernommen. TD-Gammon wird häufig als früher Erfolg des bestärkenden Lernens und neuronaler Netze angeführt und wurde in Arbeiten zu Deep Q-Learning und AlphaGo referenziert.
Algorithmus für Spiel und Lernen
Während des Spiels untersucht TD-Gammon bei jedem Zug alle möglichen legalen Züge und alle ihre möglichen Antworten (Lookahead-Suche), führt jede resultierende Brettposition in seine Bewertungsfunktion ein und wählt den Zug, der zu der Brettposition mit der höchsten Punktzahl führt. In dieser Hinsicht unterscheidet sich TD-Gammon nicht von fast jedem anderen Computerprogramm für Brettspiele. Die Innovation von TD-Gammon lag darin, wie es seine Bewertungsfunktion lernte.
Der Lernalgorithmus von TD-Gammon besteht darin, nach jedem Zug die Gewichte in seinem neuronalen Netz zu aktualisieren, um die Differenz zwischen seiner Bewertung der Brettpositionen früherer Züge und seiner Bewertung der Brettposition des aktuellen Zuges zu verringern - daher "Temporal-Difference-Lernen". Die Punktzahl jeder Brettposition ist eine Menge von vier Zahlen, die die Schätzung des Programms über die Wahrscheinlichkeit jedes möglichen Spielergebnisses widerspiegelt: Weiß gewinnt normal, Schwarz gewinnt normal, Weiß gewinnt ein Gammon, Schwarz gewinnt ein Gammon. Für die endgültige Brettposition des Spiels vergleicht der Algorithmus mit dem tatsächlichen Ergebnis des Spiels und nicht mit seiner eigenen Bewertung der Brettposition.
Der Kern von TD-Gammon ist ein neuronales Netz mit 3 Schichten. Die Eingabeschicht hat zwei Arten von Neuronen. Eine Art kodiert die Brettposition: nicht-negative ganze Zahlen von 0 bis 15, die die Anzahl der weißen oder schwarzen Steine an jeder Brettposition angeben, mit 99 Eingabeneuronen für jede, insgesamt 198 Neuronen. Eine andere Art kodiert handgefertigte Merkmale, die zuvor in Neurogammon verwendet wurden, und kodiert Standardkonzepte, die von menschlichen Experten verwendet werden, wie "fortgeschrittener Anker", "Blockadestärke", "Stärke des Heimatbretts" und die Wahrscheinlichkeit, dass ein "Blot" (einzelner Stein) geschlagen wird. Die verborgene Schicht enthält verborgene Neuronen, wobei spätere Versionen mehr haben. Die Ausgabeschicht enthält 4 Neuronen, die die Schätzung des Netzes über die Wahrscheinlichkeit ("Equity") darstellen, dass das aktuelle Brett zu Folgendem führt: Weiß gewinnt normal, Weiß gewinnt ein Gammon, Schwarz gewinnt normal, Schwarz gewinnt ein Gammon. Ein Backgammon-Gewinn ist so selten, dass Tesauro sich entschied, ihn nicht darzustellen.
Nach jedem Zug aktualisiert der Lernalgorithmus jedes Gewicht gemäß der Regel: w_{t+1} - w_t = alpha (Y_{t+1} - Y_t) sum_{k=1}^{t} lambda^{t-k} grad_w Y_k, wobei alpha die Lernrate ist, Y_t die Bewertung bei Zug t und lambda der Abklingparameter ist. Es wurde festgestellt, dass die Wahl eines kleinen lambda eine etwa gleich gute Leistung bot und ein großes lambda die Leistung verschlechterte. Aus diesem Grund wurde TD-Gammon nach 1992 mit lambda = 0 trainiert, was zu einem Standard-TD-Lernen degenerierte und Rechenleistung um den Faktor 2 sparte.
Entwicklungsgeschichte
Version 1.0 verwendete eine einfache 1-Ply-Suche: Jeder nächste Zug wird vom neuronalen Netz bewertet, und der Zug mit der höchsten Punktzahl wird ausgewählt. Die Versionen 2.0 und 2.1 verwendeten eine 2-Ply-Suche: Zuerst eine 1-Ply-Analyse, um unwahrscheinliche Züge zu entfernen ("Vorwärtsbeschneidung"), dann eine 2-Ply-Minimax-Analyse nur für die wahrscheinlichen Züge, wobei der beste Zug wahrscheinlichkeitsgewichtet nach jedem der 21 möglichen Würfelwürfe des Gegners ausgewählt wird (Nicht-Doppel doppelt so stark gewichtet wie Doppel). Die Versionen 3.0 und 3.1 verwendeten eine 3-Ply-Suche mit 21^2 = 441 möglichen Würfelwürfen anstelle von 21. Die letzte Version, 3.1, wurde speziell für ein Ausstellungsspiel gegen Malcolm Davis bei der AAAI Hall of Champions 1998 trainiert. Es verlor mit -8 Punkten, hauptsächlich aufgrund eines Patzers, bei dem TD-Gammon sich für ein Verdoppeln entschied und mit -32 Punkten ein Gammon kassierte.
Experimente und Trainingsphasen
Im Gegensatz zu früheren neuronalen Netz-Backgammonprogrammen wie Neurogammon (ebenfalls von Tesauro geschrieben), bei denen ein Experte das Programm trainierte, indem er die "korrekte" Bewertung jeder Position lieferte, wurde TD-Gammon zunächst "wissensfrei" programmiert. In frühen Experimenten, die nur eine rohe Brettkodierung ohne menschlich gestaltete Merkmale verwendeten, erreichte TD-Gammon ein Spielniveau, das mit Neurogammon vergleichbar war: das eines fortgeschrittenen menschlichen Backgammonspielers.
Obwohl TD-Gammon von sich aus aufschlussreiche Merkmale entdeckte, fragte sich Tesauro, ob sein Spiel durch die Verwendung handgestalteter Merkmale wie bei Neurogammon verbessert werden könnte. Tatsächlich übertraf das selbsttrainierende TD-Gammon mit expertenentworfenen Merkmalen bald alle früheren Computer-Backgammonprogramme. Es hörte auf, sich nach etwa 1.500.000 Spielen (Selbstspiel) zu verbessern, wobei es ein dreischichtiges neuronales Netz mit 198 Eingabeeinheiten verwendete, die expertenentworfene Merkmale kodierten, 80 verborgenen Einheiten und einer Ausgabeeinheit, die die vorhergesagte Gewinnwahrscheinlichkeit darstellte.
Fortschritte in der Backgammon-Theorie
Das ausschließliche Training von TD-Gammon durch Selbstspiel (anstelle von Nachahmungslernen) ermöglichte es, Strategien zu erkunden, die Menschen zuvor nicht in Betracht gezogen oder fälschlicherweise ausgeschlossen hatten. Sein Erfolg mit unorthodoxen Strategien hatte einen bedeutenden Einfluss auf die Backgammon-Gemeinschaft. Ende 1991 wurden Bill Robertie, Paul Magriel und Malcolm Davis eingeladen, gegen TD-Gammon (Version 1.0) zu spielen. Insgesamt wurden 51 Spiele gespielt, wobei TD-Gammon mit -0,25 ppg verlor. Robertie fand, dass TD-Gammon auf dem Niveau eines starken menschlichen Spielers war, und seine unkonventionellen Züge wurden später von Experten übernommen, was das Verständnis der Eröffnungsstrategie veränderte.
Vermächtnis und Einfluss
TD-Gammon wird weithin als Meilenstein im maschinellen Lernen und der künstlichen Intelligenz anerkannt, da es zeigte, dass ein neuronales Netz komplexe strategische Spiele durch Selbstspiel und Temporal-Difference-Lernen erlernen konnte. Sein Erfolg inspirierte spätere Arbeiten im bestärkenden Lernen, einschließlich der Entwicklung von Deep Q-Netzwerken und AlphaGo. Die Fähigkeit des Programms, neuartige Strategien zu entdecken, die Menschen übersehen hatten, hob das Potenzial neuronaler Netze hervor, die menschliche Intuition im Spiel zu übertreffen, und es bleibt ein klassisches Beispiel in der Geschichte der KI-Forschung.