Game Development Reference
In-Depth Information
3
Algorithms for Solving Parity Games
Marcin Jurdzinski
University of Warwick
Abstract
This is a selective survey of algorithms for solving parity games, which are
infinite games played on finite graphs. Parity games are an important class of
omega-regular games, i.e., games whose payoff functions are computable by a
finite automaton on infinite words. The games considered here are zero-sum,
perfect-information, and non-stochastic. Several state-of-the-art algorithms
for solving parity games are presented, exhibiting disparate algorithmic
techniques, such as divide-and-conquer and value iteration, as well as hybrid
approaches that dovetail the two. While the problem of solving parity games
is in NP and co-NP, and also in PLS and PPAD, and hence unlikely to
be complete for any of the four complexity classes, no polynomial time
algorithms are known for solving it.
3.1 Games on graphs
A game graph ( V,E,V 0 ,V 1 ) consists of a directed graph ( V,E ), with a set
of vertices V and a set of edges E , and a partition V 0 V 1 = V of the set
of vertices. For technical convenience, and without loss of generality, we
assume that every vertex has at least one outgoing edge. An infinite game
on the game graph is played by two players, called player 0 and player 1,
player Even and player Odd, or player Min and player Max, etc., depending
on the context. A play of the game is started by placing a token on a starting
vertex v 0
V , after which infinitely many rounds follow. In every round, if
the token is on a vertex v
E going
out of vertex v and places the token on w , and if the token is on a vertex
V 0 then player 0 chooses an edge ( v, w )