Seminar

Technische Universität Dresden Institut für Theoretische Informatik Lehrstuhl für Automatentheorie

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) .

Position in --> Curriculum

• Informatik (diploma) / master: INF-AQUA
• Computational Logic: [PCS (TCSL, PI)], 3 credit points

Prerequisites

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.
• Make sure the produced paper conforms to the usual standards of scientific writing. Advice (in German) for writing scientific papers can be found here.
• 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!

Contact

The seminar is coordinated by Anni-Yasmin Turhan.