Knowledge Engineering und Lernen in Spielen

ACHTUNG:

Die Seminarnoten hängen an der Pinnwand neben Raum D202 aus.

Inhalt

Im Rahmen dieses Seminars werden wir klassische Arbeiten im Bereich der Künstlichen Intelligenz für den Einsatz im Bereich von Computer-Spielen betrachten. Hauptsächlich werden wir uns dabei auf die Artikel in folgendem Buch konzentrieren:

Jonathan Schaeffer, Jaap van den Herik: Chips Challenging Champions, Elsevier, 2002. Das Buch ist ein Nachdruck eines Special Issues des Journals Artificial Intelligence. Wir werden aber auch einige zusätzliche Artikel durcharbeiten.

Es wird erwartet, daß Studenten die ihnen zugeteilten Materialien (im Regelfall 2-4 Kapitel aus oben genannten Büchern) in einem ca. 45-minütigen Kurz-Vortrag (30 min Vortrag, 15 min Diskussion) vorstellen. Der Vortrag sollte jedoch inhaltlich über diese Materialien hinausgehen und eine selbständige Auseinandersetzung mit dem gewählten Thema demonstrieren.

Die Vergabe von Themen erfolgt am ersten Seminars-Termin (13.4.2010, 16.15), Sie können aber bereits davor Interesse an bestimmten Themen anmelden.

Vorkenntnisse

Es sind keine besonderen Vorkenntnisse aus dem Gebiet der künstlichen Intelligenz oder dem Maschinellen Lernen erforderlich. Im Prinzip kann das Seminar auch von Studenten des Grund- oder Bachelor-Studiums besucht werden.

Vorträge

Es wird erwartet, daß Sie die Vorträge mit Slides begleiten. Falls Sie keinen Laptop haben, bitte mir die Slides rechtzeitig zu senden, damit ich sie auf meinem Laptop einspielen bzw. testen kann. Die Vorträge und/oder Slides können wahlweise auf Deutsch oder Englisch gehalten werden.

Benotung

In die Gesamtnote fließen die Ausarbeitung des Vortrags (Folien), die Präsentation, die Beantwortung von Fragen zum Vortrag, sowie die aktive Teilnahme an der Diskussion bei den Vorträgen anderer ein. Eine schriftliche Ausarbeitung ist nicht notwendig.

Im Vordergrund der Gesamtbenotung steht jedoch die selbständige Auseinandersetzung mit den vorgestellten Methoden. Für eine sehr gute (1.x) Beurteilung muß Ihr Vortrag über eine blosse inhaltliche Wiedergabe der Techniken hinausgehen. Einfliessen lassen können Sie z.B. eigene Erfahrungen, Ideen, oder auch Demos. Eine exakte Wiedergabe des Inhalts der Papiere fhrt nur zu einer Beurteilung mit 2.x, auï¿œrordentlich schwache Leistungen in einem der genannten Punkte, insbesondere mangelnde Mitarbeit im Seminar, zu 3.x oder schlechter.

Ort und Zeit

jeweils Dienstag, 16:15 - 17:55, Raum S202|E302.

Themen und Termine

Wenn nicht anders angegeben, sind die Themen Kapitel aus obigem Buch.
Wichtig: Innerhalb des TUD-Netzes sollten alle Links funktionieren!

• Einführung für alle: Games, Computers and Artificial Intelligence (J. Schaeffer, H.J. van den Herik).
  

4.5. Squares, Cubes, and Boxes

• Rebekka Gohla: (Slides)
  Disjoint Pattern Database Heuristics (R.E. Korf, A. Felner).
  
• Mark Sollweck:  (Slides)
  Sokoban: Enhancing General Single-Agent Search Methods Using Domain Knowledge (A. Junghanns, J. Schaeffer).

11.5. Jigsaw and Crossword Puzzles

• Manuel Hiemenz: (Slides)
  Solving the Jigsaw Puzzle Problem in Linear Time (T. Altman), Applied Artificial Intelligence, 3(4):453-462, 1989.
  A global approach to automatic solution of jigsaw puzzles.  (Goldberg, D. ; Malon, C.; Bern, M. W.) Computational Geometry. 2004 June; 28 (2): 165-174.

• Fabian Walke: (Slides)
  A probabilistic Approach to Solving Crossword Puzzles (M.L. Littman, G.A. Keim, N. Shazeer).

18.5. Pac-Man and Super-Mario

• Michael Schmitt: (Slides)
  Learning to Play Using Low-Complexity Rule-Based Policies: Illustrations through Ms. Pac-Man. (Istvan Szita, András Lörincz),  Journal of Artificial Intelligence Research (2007)

• Christian Reuter: (Slides)
  Modeling Player Experience in Super Mario Bros (Christoffer Pedersen, Julian Togelius and Georgios Yannakakis), Proceedings IEEE Symposium on Computational Intellgience and Games, 2009
  Super Mario Evolution (Julian Togelius, Sergey Karakovskiy, Jan Koutnik and Jürgen Schmidhuber), Proceedings IEEE Symposium on Computational Intellgience and Games, 2009.

25.5.: Chess

• Olexandr Savchuk: (Slides)
  Deep Blue (M. Campbell, A.J. Hoane Jr, F.-h. Hsu).
  IBM's Deep Blue Chess Grandmaster Chips (F.-h. Hsu), IEEE Micro 19(2):70-81.
  
• Lavong Soysavanh: (Slides)
  B* Probability Based Search. (Hans J. Berliner, Chris McConnell), Artificial Intelligence 86 (1): 97–156, 1996

1.6.: Othello and Hex

• Malte Paskuda: (Slides)
  Improving Heuristic Min-Max Search by Supervised Learning (M. Buro).
  
• Robert Nitsch: (Slides)
  A Hierarchical Approach to Computer hex (V. Anshelevich). 

8.6.: Shogi and Go

• Nils Burmester:
  Computer shogi (H. Iida, M. Sakuta, J. Rollason). 
• Christian Brinker: (Slides)
  Modification of UCT with Patterns in Monte-Carlo Go (S. Gelly, Wang Y., Munos R., Teytaud O.), INRIA Technical Report #6062, 2006.
  Combining online and offline knowledge in UCT (S. Gelly, D. Silver), Proceedings of the 24th International Conference on Machine Learning (ICML-07), pp.273-280, 2007.

15.6.: Backgammon and Scrabble

• Tobias Krönke: (Slides)
  Programming Backgammon Using Self-Teaching Neural Nets (G. Tesauro).
  

29.6.: Bridge

• Tjark Vandommele: (Slides)
  GIB: Imperfect Information in a Computationally Challenging Game (M. Ginsberg), Journal of Artificial Intelligence Research 14:303-358
  
• Patrick Metzler: (Slides)
  Learning to bid in bridge (A. Amit, S. Markovitch)  Machine Learning 63(3): 287-327 (2006)

6.7.: Solved Games

• Florian Scheuring: (Slides)
  Games Solved: Now and in the future (H.J. van den Herik, J.W.H.M. Uiterwijk, J. van Rijswijck)
• Niklas Büscher: (Slides)
  Game Over: Black to Play and Draw in Checkers (J. Schaeffer) ICGA Journal 30(4): 187-197 (2007).
  Checkers Is Solved. (J. Schaeffer, N.  Burch, Y. Björnsson, A. Kishimoto, M. Müller, R. Lake, P. Lu, S. Sutphen) Science (4 September 2007: Vol. 317. no. 5844, pp. 1518 - 1522).

13.7.: Evolution of Game Strategies

• Christoph Thörle: (Slides)
  The Evolution of Cooperation, (Axelrod, Robert; Hamilton, William D.), Science 211: 1390–96, 1981.
  The Evolution of Strategies in the Iterated Prisoner's Dilemma (Robert Axelrod), in Lawrence Davis (ed.), Genetic Algorithms and Simulated Annealing, London: Pitman, and Los Altos, CA: Morgan Kaufman, 1987, pp. 32-41.
• Tobias Wieschnowsky: (Slides)
  Evolving and expert checkers playing program without using human expertise (K. Chellapilla, D. B. Fogel), IEEE Transactions on Evolutionary Computation 5(4):422-428, 2001.
  A self-learning evolutionary chess program (Fogel, D.B.; Hays, T.J.; Hahn, S.L.; Quon, J.) Proceedings of the IEEE 92(12):1947-1954, 2004.