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


Proseminar im WS 2001/02

Komplexitätsanalyse von Spielen

(Brauer, Holzer, Kiehn, König, Römer, Rossmanith)







Vorbesprechung: Montag, den 9.07.2001, 13:15 Uhr, Raum 1229 (Stammgelände)

Seminar-Termin: Dienstags 14:00-15:30 Uhr, Raum 0670 (der erste Vortrag findet am 16.10.2001 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 16.10.2001 Einführung in die Komplexitätstheorie - -
  2 23.10.2001 Übungssitzung I - -
  3 30.10.2001 Übungssitzung II - -
  4 06.11.2001 - - -
  5 13.11.2001 Instant Insanity Kreutz Martin P. Rossmanith
  6 20.11.2001 Minesweeper Nitsch Nils A. Kiehn
  7 27.11.2001 Peg Solitaire Bojczuk Luiza S. Römer
  8 04.12.2001 PushPush - -
  9 11.12.2001 Rush Hour - -
  10 18.12.2001 Phutball Bouillon Jan A. Kiehn
  11 08.01.2002 Sokoban+ Nagel Lars M. Holzer
  12 15.01.2002 Sokoban Sandner Matthias B. König
  13 22.01.2002 Push-X Gerges Christine P. Rossmanith
  14 29.01.2002 Tantrix Greiner-Mai Thomas M. Holzer
  15 05.02.2002 Clickomania Schiöberg Harald B. König


Hinweise

Literatur zu den einzelnen Themen



Markus Holzer (Last modification: 2001/01/17-15:25)