Game Development Reference
In-Depth Information
combined with an appropriately modified progress measure lifting algorithm
to achieve running time O ( n d/ 3+ O (1) ), which is the best currently known
running time bound for solving parity games with d = O ( n ).
3.3.1 Divide and conquer
In Figure 3.2 we present a divide-and-conquer algorithm for solving parity
games that generalises the algorithm for solving repeated reachability and
eventual safety games from Section 3.2. The algorithm takes a parity game G
with the priority function p : V
as input, and it returns the
pair ( win 0 ( G ) , win 1 ( G )) of the winning sets of both players. Without loss
of generality, we assume that the set p 1 ( d ), of the vertices with highest
priority d , is not empty.
Similarly to the algorithm for solving repeated reachability games, a
solution of the parity game is obtained from solutions of subgames that are
also parity games, and that have strictly smaller size. In contrast to the case of
repeated reachability games, the divide-and-conquer procedure parity-win ( G )
may make two recursive calls, one on the subgame G = G
→{
1 , 2 ,...,d
}
reach j ( p 1 ( d ))
\
and the other on the subgame G = G
reach i ( W i ), where the identity of
player j is determined by the parity of the highest priority d , player i is the
opponent of player j , and W i is the winning set of player i in subgame G .
\
algorithm parity-win ( G )
j
d mod 2 ; i
1
j
if reach j ( p 1 ( d )) = V
then ( W i ,W j )
(
,V )
else
G
reach j ( p 1 ( d ))
G
\
( W 0
,W 1
parity-win ( G )
)
if W i
then ( W i ,W j )
=
(
,V )
else
G
reach i ( W i )
G
\
( W 0
,W 1
parity-win ( G )
)
W j ,W j )
( W i ,W j )
( V
\
endif
endif
return ( W 0 ,W 1 )
Figure 3.2 A divide-and-conquer algorithm for parity games
In a series of exercises similar to, and generalising, Exercises 3.4-3.6 we

Custom Search