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


Proseminar im SS 2004

Komplexitätsanalyse von Spielen

(Brauer, Holzer)







Vorbesprechung: ist am Dienstag, 3.02.2004, 14.00 Uhr, Raum MI 03.09.014

Seminar-Termin: Dienstags 14:00-15:30 Uhr, Raum MI 03.09.014 (der erste Vortrag findet am 27.04.2004 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.



Hinweise

Literatur zu den einzelnen Themen



Markus Holzer (Last modification: 2004/01/15-17:00)