Theoretische Informatik und Grundlagen der KI

Praktikum "Game Playing" im WS 2004/05



Veranstalter: Prof. Markus Holzer, Felix Fischer

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

Ankündigung (pdf)

Folien zur Informationsveranstaltung (pdf)


Inhalt Voraussetzungen Durchführung Teilnehmer Literatur


Inhalt

In diesem Praktikum soll ein computergesteuerter Spieler für ein einfaches Brettspiel entwickelt werden - genauere Informationen werden im Rahmen einer ersten Kurzveranstaltung Anfang Januar bekanntgegeben. 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:
18. Januar 2005, 10:00-11:00 Uhr, Raum MI 03.09.014:
Informationsveranstaltung mit Einteilung der Gruppen und Diskussion möglicher Lösungsansätze
Aus organisatorischen Gründen ist eine persönliche Anwesenheit bei dieser Informationsveranstaltung zwingend erforderlich, andernfalls verfällt die Anmeldung.
14. bis 23. Februar 2005:
Blockpraktikum Teil 1 (Implementierung)
6. bis 8. April 2005:
Blockpraktikum Teil 2 (Lösungsvorstellung und Turnier mit Siegerehrung)

Teilnehmer

Die Praktikumsteilnehmer wurden wie folgt in Zweiergruppen eingeteilt:
Alexander KieningTobias Reichl
Kevin TunstallSebastian Pätzold
Benjamin GuflerDaniel Weber
Marc BachmannMiriam Wiegand
Bernhard AmannBenedikt Fraunhofer
Daniel J. PhilippMoritz Köhler
Moritz BartlAndreas Holzer
Stefan FoersterHeike Lupold
Jakob ReinehrFlorian Sollinger
Robert WestRoland Can Aydin
Aufgrund der großen Anzahl an Anmeldungen konnte leider nicht allen Interessierten ein Platz im Praktikum zugeteilt werden. Die Betroffenen erhalten aber eine Voranmeldung zum Praktikum "Game Playing" im SS2005.

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