Seminar Theoretical Computer Science: "Complexity of board games"

Course Description

Classical board games such as Chess, Checkers or Go are not only popular among players, but they were also studied with respect to their computational complexity. In this seminar we will take a look at several board games and see how they differ in computational complexity.

Prerequisites: Basic knowledge in complexity theory. For computer scientist students: Pflichtvorlesung Formale Systeme

SWS/Modules

SWS: 0/2/0

This course can be used in the following modules:

• Master Computational Logic: MCL-PS
• Master Informatik, Diplom Informatik: INF-04-HS, INF-AQUA, INF-D-940

Organisation

Available topics are sketched and assigned to interested students in an initial meeting on Friday 25th of October 14:50–16:20, in room APB/3027. Further organisational matters are covered there as well. Students who cannot attend the initial meeting, but want to participate in the seminar, should contact Anni-Yasmin Turhan.

Each participant must get acquainted with the respective topic, write a report (ca. 12 pages) about it, and give a presentation (ca. 30 minutes) at the end of the semester (more specifically, in the two weeks before the lecture-free period). During the semester, every student gets individual help and guidance by a tutor (Prof. Dr.-Ing. Franz Baader) or (Anni-Yasmin Turhan. Furthermore, each student is expected to participate in the discussions after the talks given by her/his fellow students.

The students are expected to stick to the following schedule.

• October: mandatory meeting with the tutor
• end of November: first complete version of the report
• middle of December: first complete version of the presentation slides
• end of January: presentation and discussion

Topics

• "GO is Polynominal-Space Hard". David Lichtenstein and Michael Sipser, 1978
• "The Othello game on an N*n board is PSpace-complete". Shigeki Iwata, Takumi Kasai; Theor. Comput. Sci. 123(2): 329-340 (1994)
• "Gobang ist PSpace-vollständig". Stefan Reisch, 1980
• "The Complexity of Graph Ramsey Games". Wolfgang Slany, 2002
• "Implementing a Computer Player for Abalone using Alpha-Beta and Monte-Carlo Search". Pascal Chorus, M.Sc. thesis, 2009
• "Combinatorics of Go". John Tromp and Gunnar Farnebäck (2007).

Participants are welcome to add papers to the pool of papers!