Fakultät für Informatik der Technischen Universität München,
Lehrstuhl für Theoretische Informatik und Grundlagen der KI


Proseminar im SS 2003

Komplexitätsanalyse von Spielen

(Brauer, Holzer, Römer)







Vorbesprechung: Mittwoch, den 05.02.2002, 14:00 Uhr c.t, Raum MI 03.09.014

Seminar-Termin: Dienstags 14:00-15:30 Uhr, Raum MI 03.09.014 (der erste Vortrag findet am 08.04.2003 statt).
                          

Kontaktperson: Markus Holzer


Inhalt

Viele Gesellschafts- und Solitaire-Spiele stellen aufgrund ihres Schwierigkeitsgrades eine Herausforderung für den menschlichen Intellekt dar. Oft kann die Schwierigkeit eines Spiels auch durch eine mathematische Analyse, in Form von komplexitätstheoretischen Resultaten untermauert werden. Jedes in der Klassifikation der Komplexitätstheorie als schwierig (NP-vollständig) eingestufte Problem kann als ein Puzzlespiel angesehen werden, und umgekehrt sind auch viele Einpersonenspiele in diesem Sinne schwierig. Zweipersonenspiele haben meist eine höhere Komplexität als Einpersonenspiele. In diesem Seminar sollen vor allem Einpersonenspiele, die im Handel erhältlich oder auf einer gängigen Rechnerplattform spielbar sind, komplexitätstheoretisch untersucht werden. Hierzu zählen z.B. Minesweeper, Atomix, Tantrix, etc.

Seminarablauf

Für das Verstehen der Spielanalysen sind grundlegende Kenntnisse der Komplexitätstheorie notwendig. Mit dem ersten Teil des Seminars sollen diese Kenntnisse vermittelt werden. Hierzu erarbeiten sich die Teilnehmenden während der Semesterferien einen einführenden Text in dieses Gebiet. Die erste Seminarsitzung im Wintersemester dient der Besprechung dieses Textes und dem gemeinsamen Lösen einfacher Übungsaufgaben. In der zweiten Seminarsitzung werden bis dahin zu lösende Übungsaufgaben besprochen. Die darauf folgenden Sitzungen werden durch die Referate der Teilnehmenden, die jeweils eines der unten aufgeführten Referatthemen übernommen haben, gestaltet. Neben dem Referat ist eine ca. fünfseitige Ausarbeitung zu erstellen, die an sämtliche Seminarteilnehmende verteilt wird. Bei der Erarbeitung des Stoffes und der Konzeption des Vortrags steht eine/r der MitarbeiterInnen hilfreich zur Seite. Da die Komplexitätstheorie eine Teildisziplin der theoretischen Informatik ist, sollten die Teilnehmenden dementsprechende Interessen mitbringen.

Vortragsthemen

Die den einzelnen Themen zugrundeliegende Literatur ist unten auf dieser Seite angegeben.

  Datum Thema Vortragende/r Betreuung
  1 08.04.2003 Einführung in die Komplexitätstheorie und Übungssitzung O. Ruepp M. Holzer
  2 15.04.2003 Übungssitzung --- ---
  3 22.04.2003 Clickomania --- M. Holzer
  4 29.04.2003 Solitaire Clobber E. Schweizer S. Römer
  5 06.05.2003 Minesweeper D. Birgel S. Römer
  6 13.05.2003 Peg Solitaire T. Freier S. Römer
  7 20.05.2003 Phutball F. Visintin M. Holzer
  8 27.05.2003 PushPush M. Yordanov M. Holzer
  9 03.06.2003 Sokoban+ R. Tashev S. Römer
 10 10.06.2003 Sokoban (Pfingstwoche) M. Pock S. Römer
 11 17.06.2003 Push-X S. Haspinger M. Holzer
 12 24.06.2003 Tantrix A. Smirnov M. Holzer
 13 01.07.2003 PushPush S. Yilmaz M. Holzer
 14 08.07.2003 Rush Hour und Co. V. Gontsharuk S. Römer


Hinweise

Literatur zu den einzelnen Themen



Markus Holzer (Last modification: 2003/01/14-12:00)