Hauptseminar Theoretische Informatik:
"Complexity of Board Games"
Topic of
seminar
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.
Preliminary schedule
The seminar starts on Friday, April 12, at
3:00pm in room 3027 of the computer science
building with an introductory meeting. In this meeting all students
will be assigned a research paper and a tutor.
Students who would still like to join the seminar, write an email Anni-Yasmin Turhan. We
accept students for the seminar until 30th of April.
Presentations will take place during the last weeks of the
teaching period (i.e. in July) .
Basic knowledge in computational complexity is helpful.
For computer science students: “Grundlagen der
Theoretischen Informatik” or “Formale Systeme”
Language
The language of the seminar is English — unless attended by
native German speakers only.
Goal of the Hauptseminar
Apart from learning about the main topic, students should learn
how to get acquainted with a relevant body of literature, how to
produce a well-structured paper, and how to give an understandable
scientific talk.
Duties of Participants
Classical — for the AQUA and PCS modules
In the initial meeting, students choose a topic to work on and
are assigned a tutor.
During the seminar, the student has to understand the relevant
literature and writes a paper about the chosen topic (~12 pages).
Finally, each student presents his/her work in a talk to the
other participants. In
doing this, he/she receives individual support by the tutor. The students
should present
a first full version of their paper at least 5 weeks
before their talk,
a first version of all the slides for their talk at least
2 weeks before the talk, and
a 20-25 minute presentation followed by 5-10 minutes of discussion.
Oral exam — for the PI and TCSL modules
Chose 3 papers from thepool of papers
and make appointment for the
exam. Ideally attend the seminar talks.
Additionally, students must meet the following requirements.
Refrain from any form of plagiarism in the preparation of your report.
If you are unsure what is considered plagiarism in academia please consult
this helpful guide
by the University of Oxford.
Reserve enough time for the seminar.
Make appointments with your tutor. It is customary to have a first
consultation within one or two weeks after the initial session.
Remember that your tutor may not always be available because of travelling
obligations. If possible, try to arrange meetings well ahead of time.
If possible use LaTeX for typesetting your report. If you absolutely have
to use a different software you must make sure that all formulas are typeset
using a formula editor.
If you choose to use LaTeX use either the document class article or
scrartcl. Do not change fonts, font sizes, margins, headers or
footers.
Prepare a question for the discussion of your partner paper. This
will be explained in more detail during the introductory meeting.
Pool of papers
"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
(Will be presented by A. Abdrahmanov)
"Combinatorics of Go".
John Tromp and Gunnar Farnebäck (2007).
Participants are welcome to add papers to the pool of papers!