Theoretische Informatik und Grundlagen der KI

Praktikum "Game Playing" im Wintersemester 2005/06



Veranstalter: Prof. Markus Holzer, Markus Geipel, Florian Echtler

Art der Veranstaltung: Praktikum (6 SWS) im Bereich Informatik III (theoretische Informatik)

Einführung: Folien zur Vorbesprechung

Inhalt Voraussetzungen Durchführung Teilnehmer Literatur


Inhalt

In diesem Praktikum soll ein computergesteuerter Spieler für ein einfaches Brettspiel entwickelt werden. Ziel ist es, diese Aufgabe mit Mitteln der künstlichen Intelligenz wie z.B. Suchverfahren, Lernverfahren, etc. selbständig zu lösen. Darüber hinaus lernen Sie in einer Kleingruppe, effiziente Programme und Datenstrukturen für große Datenmengen zu entwerfen, die Zeiger und dynamische Speicheranforderungen verwenden, sie zu implementieren, zu testen und Fehler zu beseitigen. Am Ende des Praktikums soll jede Gruppe ihr individuelles Lösungkonzept vorstellen. In einem abschließenden Turnier gegen einen vorgegebenen Gegner moderater Spielstärke sowie gegen die Lösungen der anderen Teilnehmer soll die Leistungsfähigkeit Ihrer Implementierung unter Beweis gestellt werden.


Voraussetzungen

Das Praktikum richtet sich an Studierende mit abgeschlossenem Vordiplom in Informatik, und an Studierende des Masterstudienganges Informatik, mit Programmiererfahrung in C++, die Interesse an der Anwendung theoretischer Konzepte auf "praxisrelevante" Themen haben. Weitere Vorkenntnisse sind nicht erforderlich, diese sollen vor der Durchführung des eigentlichen Blockpraktikums selbständig erarbeitet werden (nähere Informationen hierzu bei der ersten Informationsveranstaltung).


Durchführung

Das Praktikum wird als Blockpraktikum nach folgendem Zeitplan durchgeführt:
13. bis 22. Februar 2006:
Blockpraktikum Teil 1 (Implementierung)
Beginn: 13.2.06, 10:00, Raum 00.09.02
3. April 2006:
Abgabe des Programms
6. und 7. April 2006:
Blockpraktikum Teil 2 (Lösungsvorstellung und Turnier mit Siegerehrung)

Teilnehmer

Eine vervollständigte Teilnehmerliste wird hier in Kürze veröffentlicht.


Literatur (kein Anspruch auf Vollständigkeit)

Künstliche Intelligenz
  1. Stuart Russell, Peter Norvig: Artificial Intelligence: A Modern Approach (Second Edition) (AIMA)
Spielbaumsuche
  1. "Adversarial Search" (Kapitel 6 von AIMA)
  2. Übersicht am Beispiel von Schach
  3. Programmierung strategischer Spiele
  4. Sammlung von Papieren
  5. Praktikum "Strategy and board game programming", UC Irvine
  6. Literaturliste für "two-person zero-sum games with perfect information"
Reinforcement Learning
  1. "Reinforcement Learning" (Kapitel 21 von AIMA)
  2. RL FAQ
  3. Richard Sutton, Andrew Barto: Reinforcement Learning: An Introduction (Volltext)
  4. UMich RL Group
  5. Erfolgreiche Anwendung von RL auf Spiele
  6. RL and AI, UAlberta