Game Development Reference
In-Depth Information
algorithm parity-win-dominion ( G )
n
2 n
←|
V
|
;
( D, i )
dominion ( G, ); j
1
i
G
G
\
reach i ( D )
if D =
then ( W 0 ,W 1 )
parity-win ( G )
else
( W 0 ,W 1 )
parity-win-dominion ( G )
( W i ,W j )
( V
\
W j ,W j )
endif
return ( W 0 ,W 1 )
Figure 3.3 A divide-and-conquer algorithm for parity games with dominion
preprocessing
The procedure parity-win-dominion ( G ) takes a parity game G as input, and
it returns the pair ( win 0 ( G ) , win 1 ( G )) of the winning sets of both players.
Assume that the procedure dominion ( G, ) takes a parity game G and a
number as input, and it returns a pair ( D, i ) such that D is an i -dominion of
size at most if any such 0-dominion or 1-dominion exists, and it returns (
)
otherwise. Moreover, the procedure parity-win ( G ) is a copy of the procedure
parity-win ( G ) from Section 3.3.1 in which both recursive calls parity-win ( G )
and parity-win ( G ) have been replaced by calls parity-win-dominion ( G )
and parity-win-dominion ( G ), respectively.
,
Exercise 3.12 Prove that the algorithm parity-win-dominion ( G ) is correct.
Note that the procedures parity-win-dominion ( G ) and parity-win ( G ) are
mutually recursive, and then use an inductive argument similar to that
for the algorithm parity-win ( G ) in Section 3.3.1. In particular, in order to
justify the else -case in procedure parity-win-dominion ( G ), the arguments
similar to those applied to game G in Exercise 3.9 may be applied to
game G = G
\
reach i ( D ).
The rationale for dovetailing the divide-and-conquer approach and prepro-
cessing based on detection and removal of dominions is that, if an appropriate
trade-off is chosen between the size of dominions detected and removed, and
the cost of detecting them, then the analysis of the worst-case running time
of the divide-and-conquer algorithm carried out in Exercise 3.11 can be
improved.
Exercise 3.13
Argue that procedure dominion ( G, ) can be implemented