News
Currently, no news are available
Complexity of Games
Popular games hide computationally hard, sometimes even undecidable, algorithmic questions such as whether a player has a winning strategy – and some argue that this makes these games popular in the first place. In this seminar, we study (generalizations) of popular games, such as board, card and video games, for example: Hanabi, Chess, Minesweeper and Portal. They might be zero, one or multi-player games, and interesting problems to study range from whether there is a forced win, to simply whether there is a legal move. These problems often lead us to complexity classes beyond NP such as to PSPACE.
Organization
-
Kick-off meeting (possibly online) during the first or second week.
-
Each participant will give a presentation of an assigned recent paper, followed by a group discussion.
-
To help you with the preparation of the presentation, there are two one-to-one meetings for each participant: One meeting to discuss the outline of your presentation, and another meeting to discuss your more-or-less ready slides.
-
A written summary of the assigned paper has to be submitted during the semester.
Requirements
A solid background in algorithms and complexity. You should be familiar with NP and reductions to show hardness.