DA Einsatz von Reinforcement Learning für strategische Brettspiele am Beispiel von "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. G. 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.
• Aufbauend auf verschiedenen, an der FH Köln bereits durchgeführten Diplom und Bachelorarbeiten, insbes. [Rud03], aber auch [Wen03, Kla05], soll eine Java-Implementierung des Reinforcement-Learnings entwickelt werden und an praktischen Spielsituationen evaluiert werden.

Ziele

1. Erstellung eines Konzeptes für die Einbindung von Reinforcement Learning in strategische Brettspiele
2. Einbau eines Reinforcement-Learning-Agenten in die 4-Gewinnt-Entwicklungsumgebung [Rud03] oder Entwicklung eigener 4-Gewinnt-Umgebung
3. Anlernen des RL-Agenten (guided, self-play)
4. Design eines Benchmarking Systems und Evaluation des Reinforcement-Agenten

Schritte

• Einarbeitung: RL-Prinzipien [Sutton&Barto98], RL in Brettspielen [Gho04]
• [Evtl. als Vorbereitung zu 2.: einfaches Spiel „Gambler’s Problem“ (nach [Sutton&Barto98, Chap. 4.4]) mit einem RL-Agenten implementieren (RL-Methode kennenlernen)]
• Zu 2.: TD-Learning auf Basis des Pseudo Code in [SutBon93] in Java implementieren (Temporal Difference als Spezialfall einer RL-Methode kennenlernen)
• Zu 2.: Codierung Spielzustand, Überlegung zu günstigen Merkmalen (Features) bei 4-Gewinnt >> RL-Agent setzt auf diesen Merkmalen auf
• Zu 4.: Einbau der TD-Learning in die Get-Four-Java-Umgebung nach [Rud03] und deren Weiterentwicklung
• Testen
• Usability Tests, Verfeinerung

Voraussetzungen

• Grundkenntnisse Neuronale Netze, Java, Englisch

Literatur:

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.

• [Konen08a] W. Konen: Reinforcement Learning für Brettspiele:Der Temporal Difference Algorithmus, Technischer Report, Institut für Informatik, FH Köln, Okt. 2008. TR_TDlambda.pdf
• [Gho04] Imran Ghory: Reinforcement Learning in Board Games. CSTR-04-004, Department of Computer Science, University of Bristol. May 2004. Sehr guter Überblick zum Thema, enthält allerdings etliche Unklarheiten in den Gleichungen.
• [SutBon93] Richard Sutton and Allen Bonde Jr. (1992) Nonlinear TD/Backprop pseudo C-code, GTE Laboratories. Lokale Kopie hier. Ist eine „fast“ fertige TD(l)-Implementierung, erstaunlich kurz (!), es fehlt nur IO und Random Number Generator.
• [Kla05] A. Klassen: Evaluation der Einsetzbarkeit lernfähiger neuronaler Netze für das strategische Brettspiel „4-Gewinnt“, Bachelorarbeit, FH Köln, Feb 2005.
• [Wen03] T. Wende: Entwurf und Anwendung künstlicher neuronaler Netze zum Lernen strategischer Brettspiele, Diplomarbeit, FH Köln, Okt 2003.
• [Rud03] T. Rudolph: Konzeption einer Entwicklungsumgebung lernender KNN für strategische Spiele, Diplomarbeit, FH Köln, Sept 2003.

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.