MMKI (SS08)
Übung zur Vorlesung "Moderne Methoden der Künstlichen Intelligenz" im SS 2008.
Ziel der Übung
In der Übung geht es um die praktische Anwendung von Methoden des Reinforcement Learning (RL) an einfachen spielerischen Beispielen.Als Anwendungsbeispiel werden klassische 2-player board games dienen, vor allem das Spiel "Tic-Tac-Toe".
Infrastruktur
Für die Bearbeitung der Aufgaben sind mitunter Programme (in C++) zu schreiben / zu vervollständigen. Der Quellcode diser Programme / Funktionen ist dann Teil der Abgabe. Die Programme müssen sich auf den Rechnern des Linux-Pools übersetzen und starten lassen. (Bei mehreren Quelldateien oder dazuzulinkenden Bibliotheken bitte ein entsprechendes shell-skript dazupacken.)Abgabeform
Die Aufgaben der Übung dürfen in Zweiergruppen bearbeitet und abgegeben werden. Dies ist durchaus auch erwünscht.Die Lösungen sind jeweils als pdf-Datei abzugeben.
Die Namen, und Matr.-Nr. der Gruppenmitglieder sowie ggf. der Gruppenname sind auf der Lösung anzugeben.
Gegebenenfalls sind zusätzlich Quellcode, Datensätze und Datenplots als Teil der Lösung mitabzugeben.
Die Abgabe erfolgt direkt über Goya.
Sollten dabei Probleme auftreten, senden Sie die Lösung bitte per email an berger@informatik.hu-berlin.de mit dem Betreff "MMKI08 Aufgabe N".
Aufgaben
- 1. Aufgabenblatt (Abgabe 22.05.08 00:00 / 24.05. 00:00)
- Quelltext zur 1. Aufgabe
- Musterlösung zur 1.b Aufgabe
- allg. Hinweise:
-
- Bei Aufgabe 1b war eine "optimale" Strategie zu finden. Optimal heisst hier z.B. nicht, dass sie suboptimale Gegenerstrategien erkennen und ausnutzen kann (perfekte Strategie). Optimal soll hier nur heissen, dass die Strategie nie ein Spiel verliert, d.h. gegen alle anderen "optimalen" Strategien das bestmögliche Ergebnis liefert.
- Die in der Übung vorgestellte Strategie mit 3 Regeln war nur optimal für den 1. Spieler. Sie muss also für den 2. Spieler noch um mindestens eine weitere Regel erweitert werden (siehe Musterlösung).
- 2. Aufgabenblatt (Abgabe 05.06.08 12:00)
- Musterlösung zur 2.a-c Aufgabe (optimale Strategie (aus der Musterlösung zu 1b))
- Musterlösung zur 2.a-c Aufgabe (perfekte Strategie)
- allg. Hinweise:
-
- die interessanten Funktionen der Musterlösung sind generateStateList und valueIteration, bei der "perfekten" sicher auch noch computerMove.
- die Generierung der Felder (Zustände) erfolgt in der Lösung so wie in der Übung vorgestellt, d.h. über dem Umweg der Repräsentation das Feldes als Zahl zur Basis 3 mit den Koeffizientenwerten (Alphabet) ' ', 'O' und 'X'.
- 3. Aufgabenblatt (Abgabe 19.06.08 12:00)
- Quelltext zur 3. Aufgabe
- Musterlösung zur 3. Aufgabe (c-e)
- allg. Hinweise:
-
- Machen Sie sich bis zur nächsten Übung am 12.06. mit den Aufgaben vertraut!
- Compileroptimierung bringt bei der Musterlösung einen speed-up von 150%! (g++ -Wall -O3 -o ttt_3l ttt_3l.cpp)
- 4. Aufgabenblatt (Abgabe 26.06.08 12:00)
- Quelltext zur 4. Aufgabe
- Musterlösung zur 4. Aufgabe
- allg. Hinweise:
- 5. Aufgabenblatt (Abgabe 20.07.08 12:00)
- Testprogramm zur 5. Aufgabe
- Quelltext zur 5. Aufgabe (d)
- Quelltext zur 5. Aufgabe (e)
- Zustandsliste
- vorberechnete Wertfunktion
- Musterlösung zur 5. Aufgabe (d)
- Musterlösung zur 5. Aufgabe (e)
- allg. Hinweise:
Literaturempfehlungen
- Tom Mitchell, Machine Learning
- Sutton / Barto, Reinforcement Learning: An Introduction
- http://www.cs.ualberta.ca/~sutton/RL-FAQ.html
FAQ
- Bei Problemen mit dem Herunterladen von Dateien, stellen Sie sicher, dass als Protokoll "https" und nicht "http" eingestellt ist. Die korrekte URL dieser Seite muss https://www.ki.informatik.hu-berlin.de/lehre/ss08/mmki/uebung sein.