Algorithms for 2-Player-Games
From PUMA Graduiertenkolleg
We consider algorithms for solving positionally determined two-player-games, in particular parity, mean payoff, and discounted payoff games. These are perfect information games played on directed graphs with integer-labeled nodes. The winner of a play in such a game is determined by a predicate referring to all numbers occurring infinitely often.
Solving these games can be seen as the algorithmic essence of numerous problems originating from omega-automata-theory as well as program verification: solving parity games for instance is equivalent to the model-checking problem of the modal mu-calculus, and a vital part of deciding validity for this logic.
We particularly investigate the strategy improvement method, being a very general class of solving algorithms, with regards to the following issues: we try to find lower bounds on the number of strategy improvement iterations, inspect possible improvements to this solving class, and pursue the extension of the strategy iteration to other problem classes.
Additionally, we study practical aspects of solving algorithms: we develop a software package for the automatic description, analysis and solution of games. Our main focus will be put on the efficient and optimised implementation of the cutting-edge solving algorithms as well as on comparative inquiries regarding the actual running times on selected game families.