Theoretische Informatik und Grundlagen der KI

Praktikum "Game Playing" im SS 2005



Veranstalter: Prof. Markus Holzer, Felix Fischer

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

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 bekannt gegeben. 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:
24. Mai 2005, 13:00-14: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.
18. bis 27. Juli 2005:
Blockpraktikum Teil 1 (Implementierung)
13. bis 14. Oktober 2005:
Blockpraktikum Teil 2 (Lösungsvorstellung und Turnier mit Siegerehrung)


Teilnehmer

Die Praktikumsteilnehmer wurden wie folgt in Zweiergruppen eingeteilt:
G01Markus DoerschmidtSebastian Grembowietz
G02Tobias SchmidbauerKorbinian Schwinger
G03Alexander GafrillerManuel Mayr
G04Uwe HermannDaniel Reutter
G05Bora EkmekciRaphael Geissler
G06Michael-Wilhelm MaurerTim Dutz
G07Andreas V. MeierTom Schreiber
G08Torge KummerowDaniel Saraci
G09Huy Hoang NguyenSimon Richter
G10Sebastian EschFelix Weyde
G11Christian KernNico Blodow
G12Thomas FriedlhuberKai Klimke
G13Thomas HrabeAlexander Scherer
G14Johannes HummelOliver Rahner
G15Alexander KieningTobias Reichl
G16Sebastian KortlerChristoph Meier
G17Oliver RueppFlorian Schneider
G18Michael SchmidtMatthias Frank
G19Stefan MisslingerFriedrich Kammerlander
G20Gregor MaierAxel Gerster
Es sind keine Plätze mehr frei. Das Praktikum Game Playing wird auch wieder im Wintersemester 2005/2006 veranstaltet - Anmeldungen per email an Markus Holzer.


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