Game Development Reference
InDepth Information
into account the maximum priority
d
= max(
p
(
V
)) that occurs in the game
graph. Let
n
d
=
p
−
1
(
d
)


be the number of vertices with priority
d
.
Exercise 3.11
Observe that the maximum priority in the parity game
G
=
G
reach
j
(
p
−
1
(
d
)) is strictly smaller than
d
.
Assume that the procedure
paritywin
(
G
) makes its second recursive
call
paritywin
(
G
). Prove that if
reach
i
(
W
i
) does not contain a vertex of
priority
d
then
reach
i
(
W
i
)=
W
i
, and that the procedure
paritywin
(
G
)
does not make any recursive calls (because the condition in the second
if
statement obtains).
Argue that the worstcase running time of the procedure
paritywin
(
G
)
can be characterised by the recurrence:
\
T
(
n, d, n
d
)
≤
T
(
n, d
−
1
,n
d−
1
)+
T
(
n, d, n
d
−
1) +
O
(
m
)
,
T
(
n, d,
1)
≤
2
·
T
(
n, d
−
1
,n
d−
1
)+
O
(
m
)
,
T
(
n,
1
,n
d
)=
O
(
n
)
,
and hence also by the recurrence:
T
(
n, d
)
≤
(
n
d
+1)
·
T
(
n, d
−
1) +
O
(
n
d
m
)
,
T
(
n,
1) =
O
(
n
)
.
((
n
+
d
)
/d
)
d
)=
O
(
n
d
+
O
(1)
).
Prove that
T
(
n, d
)=
O
(
m
·
Theorem 3.7
(Emerson and Lei [1986], Emerson and Jutla [1991], Zielonka
[1998])
The winning sets of both players in parity games can be computed
in time O
(
m
((
n
+
d
)
/d
)
d
)=
O
(
n
d
+
O
(1)
)
.
·
3.3.2 Divide and conquer with dominion preprocessing
In this section we present a refinement of the divideandconquer algorithm
for solving parity games from Section 3.3.1. The purpose of the refinement
is to improve the worstcase running time of the algorithm for games with
many priorities. More specifically, we present an algorithm for solving parity
games that runs in time
n
O
(
√
n
)
, and hence has better worstcase running
time than the algorithm from Section 3.3.1 if
d
=Ω(
n
(1
/
2)+
ε
), i.e., if the
number of priorities in parity games asymptotically exceeds the square root
of the number of vertices.
In Figure 3.3 we present an algorithm for solving parity games that dovetails
the divideandconquer approach of Section 3.3.1 with preprocessing of parity
game graphs based on detecting and removing dominions of moderate size.
Search Nedrilad ::
Custom Search