Game Development Reference
In-Depth Information
vertex of one of the players has exactly one outgoing edge. A typical example
of a one-player parity game of the latter kind is the strategy subgraph of a
positional strategy: given a positional strategy μ : V 0
V of player 0, its
strategy subgraph is obtained by removing all edges ( v, w )
V 0 ×
V , such
that w
= μ ( v ); strategy subgraphs of positional strategies of player 1 are
defined analogously. Naturally, a strategy subgraph of a positional strategy
of player 0 is a player 1 one-player game, and a strategy subgraph of a
positional strategy of player 1 is a player 0 one-player game.
Exercise 3.10 Consider a player 1 one-player parity game with a starting
vertex v . We say that a cycle in the game graph of a parity game is odd if the
highest priority of a vertex on that cycle is odd; the cycle is even otherwise.
Argue that player 1 is the winner in the game if and only if an odd cycle is
reachable from v in the game graph.
Design a polynomial time algorithm for deciding the winner in one-player
parity games.
It is now easy to establish that deciding the winner in parity games is
in NP: by positional determinacy it su ces to guess a positional strategy χ
for player 1, and that can be done in non-deterministic polynomial time,
and then to run the polynomial time algorithm from Exercise 3.10 on the
strategy subgraph of χ to verify that χ is a winning strategy for player 1. A
co-NP procedure for parity games is analogous: it su ces to swap players 1
and 0 in the above argument, mutatis mutandis .
Corollary 3.6 (Emerson et al. [1993])
The problem of deciding the winner
in parity games is in NP and in co-NP.
Now we are going to carry out a detailed analysis of the worst-case running
time of the algorithm parity-win ( G ). Note that the algorithm solves two
reachability games by computing sets reach j ( p 1 ( d )) and reach i ( W i ), and
it makes two recursive calls on parity games G = G
reach j ( p 1 ( d )) and
\
G = G
reach i ( W i ), whose numbers of vertices are strictly smaller than
that of parity game G . It follows that its worst-case running time can be
characterised by the recurrence
\
T ( n ) 2 · T ( n − 1) + O ( m ) ,
T (1) = O (1) ,
where n =
are the numbers of vertices and edges, respectively,
of the game graph, and hence T ( n )= O (2 n ).
In the following exercise we ask the reader to carry out a better analysis
of the worst-case running time of the algorithm parity-win ( G ), that takes
|
V
|
and m =
|
E
|