DA Reinforcement Learning mit
N-Tupel-Systemen für das Brettspiel "4-Gewinnt"
Ausgangspunkt
- Reinforcement
Learning (RL) in Verbindung mit
Neuronalen Netzen ist eine clevere Strategie, wie man allein aus Belohnungen
"gut – schlecht" am Spielende eine komplexe Spielstrategie
erlernen kann. Gerald Tesauro hat gezeigt, wie man auf diese Weise ein auf
Weltklasseniveau spielendes Backgammon-Programm erzeugen kann. Ziel der
Arbeit ist es, diese Lernstrategie erstmals auf das strategische
Brettspiel "4-Gewinnt" anzuwenden.
- Die
Diplomarbeit von Jan Schwenck [Schwenck08] hat, aufbauend auf weiteren, an
der FH Köln bereits durchgeführten Diplom- und Bachelorarbeiten zu
4-Gewinnt [Rud03, Wen03, Kla05], eine Java-Implementierung des
Reinforcement-Learnings entwickelt, die bestimmte 4-Gewinnt-Endspiele
erlernen kann. Allerdings sind die Ergebnisse noch nicht
zufriedenstellend, weil der RL-Agent bisher nur sehr einfache Endspiele
von 4-Gewint erlernen kann und gegen den Minimax-Agenten meist verliert.
- Dies
ist auch nicht sehr verwunderlich, weil bisher nur mit den "nackten"
Spielfeldern als Input gearbeitet wurde. Man weiß jedoch, dass die
Erkennung und Verwendung von Mustern oder Merkmalen große Bedeutung
für einen guten Spiel-Agenten hat. (Merkmale können z.B. aus der Spielsituation
abgeleitete Kennzahlen oder Prädikate sein.)
- Mit
N-Tupel-Systemen [Rohwer95, Lucas97, Lucas08] gibt es nun eine sehr gute
Möglichkeit, eine große Zahl von Features zu erstellen. N-Tupel-Systeme
bilden für zufällige Zusammensetzungen von N Spielfeldern und kodieren
alle möglichen Belegungen dieser Spielfelder als Merkmale.
- Existierende
Java-Implementierungen für die Spiele Nimm-3, TicTacToe und 4-Gewinnt [Konen08,
Schwenck08].
Ziele
- Erstellung
eines Konzeptes für die Einbindung von N-Tupel-Systemen in das Reinforcement
Learning für strategische Brettspiele
- Einbau
der N-Tupel-Systeme in das RL-System und erstmalige Anwendung der
N-Tupel-Systeme auf das Spiel 4-Gewinnt
- Anlernen
des N-Tupel-RL-Agenten (guided, self-play), Evaluation der Verbesserung
- Entwicklung
einer 4-Gewinnt-GUI für das RL-Training und -Testen
Schritte
- Einarbeitung:
RL-Prinzipien [Sutton&Barto98], N-Tupel-Systeme [Rohwer95, Lucas97, Lucas08]
- Zu
2.: N-Tupel-Coding implementieren
- Zu
3., 4.: Testen auf 4-Gewinnt-Endspielen, Vgl. mit RL-Agent und
MinMax-Agent, Testen auf 4-Gewinnt-Gesamtspielen
- Zu
4.: Usability Tests, Verfeinerung
Voraussetzungen
- Grundkenntnisse
Neuronale Netze, gute Java-Kenntnisse, Englisch
Literatur:
zentral:
o
[Rohwer95]
Richard Rohwer: The
n-tuple classifier: Too good to ignore, Tech. Report Aston University,
Birmingham, 1995.
o
[Lucas97]
Simon Lucas: Face
recognition with the continuous n-tuple classifier, Proc. British Machine
Vision Conference, p. 222-231, 1997.
o
[Lucas08]
Simon Lucas: Learning
to play Games, Tutorial PPSN (Parallel Problem Solving from Nature),
Dortmund, 2008. Hier relevant: Folien 41-50.
weiterführend:
- [Konen08] W. Konen, T.
Bartz-Beielstein: Reinforcement Learning: Insights from
Interesting Failures in Parameter Selection. In: G. Rudolph (ed.), 10th International
Conference on Parallel Problem Solving From Nature (PPSN2008), Dortmund,
September 2008, p. 478-487, Lecture Notes in Computer
Science, LNCS
5199, Springer, Berlin, 2008. (PDF)
o
[Sutton&Barto98]
Richard S.
Sutton, Andrew G. Barto: Reinforcement Learning. MIT Press,
Cambridge, 1998. Hervorragende Einführung ins Thema. TD-Gammon und andere
Spiele. Als HTML-Book verfügbar unter: http://www.cs.ualberta.ca/~sutton/book/the-book.html.
o
[Tesauro95]
Gerald
Tesauro: Temporal Difference Learning and TD-Gammon, Communications of
the ACM, March 1995 / Vol. 38, No. 3. Sehr guter Übersichtsartikel über
Tesauro's Arbeiten von 1992.
o
[Tesauro92]
Gerald Tesauro: Practical issues in temporal
difference learning. Mach. Learning 8, (1992), 257-277.