Game Development Reference
In-Depth 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 parity-win ( G ) makes its second recursive
call parity-win ( 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 parity-win ( G )
does not make any recursive calls (because the condition in the second
if -statement obtains).
Argue that the worst-case running time of the procedure parity-win ( 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 divide-and-conquer algorithm
for solving parity games from Section 3.3.1. The purpose of the refinement
is to improve the worst-case 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 worst-case 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 divide-and-conquer approach of Section 3.3.1 with preprocessing of parity
game graphs based on detecting and removing dominions of moderate size.