Game Development Reference
InDepth Information
vertex of one of the players has exactly one outgoing edge. A typical example
of a oneplayer 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 oneplayer game, and a strategy subgraph of a
positional strategy of player 1 is a player 0 oneplayer game.
Exercise 3.10
Consider a player 1 oneplayer 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 oneplayer
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 nondeterministic 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
coNP 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 coNP.
Now we are going to carry out a detailed analysis of the worstcase running
time of the algorithm
paritywin
(
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 worstcase 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 worstcase running time of the algorithm
paritywin
(
G
), that takes

V

and
m
=

E

Search Nedrilad ::
Custom Search