Game Development Reference
In-Depth Information
algorithm parity-win-dominion ( G )
( D 0 ,D 1 )
progress-measure-lifting ( G, b )
D
reach 0 ( D 0 )
reach 1 ( D 1 )
G
D
G
\
D |
if |
<b/ 2
then ( W 0 ,W 1 )
parity-win ( G )
else ( W 0 ,W 1 )
parity-win-dominion ( G )
endif
( W 0 ,W 1 )
W 0 , reach 1 ( D 1 )
W 1 )
( reach 0 ( D 0 )
return ( W 0 ,W 1 )
Figure 3.5 A divide-and-conquer algorithm for parity games with dominion
preprocessing using modified progress measure lifting
For every integer b> 0, we define ξ ( b ) to be the game parity progress
measure computed by the procedure progress-measure-lifting ( G ) that uses
the set N b ∪{}
. We also write ζ ( b ) for the analogous
game parity progress measure for player 1 defined mutatis mutandis .In
what follows, we write progress-measure-lifting ( G, b ) for the procedure that
combines the above-described modified versions of the progress measure
lifting procedures for computing 0-dominions and 1-dominions, respectively,
and that returns the pair of sets ( dom ( ξ ( b ) ) , dom ( ζ ( b ) )).
An important property of procedure dominion ( G, ) used in Section 3.3.2
was that if it failed to produce a dominion of size at most then there
was no dominion of size at most in game G , and hence it followed that
the argument G of the call parity-win-dominion ( G ) in procedure parity-
win ( G ) had at most n
vertices. Unsurprisingly, a similar property holds
for the procedure progress-measure-lifting ( G, b ): if dom ( ξ ( b ) )=
then every
0-dominion in game G is of size strictly larger than b . However, in order to
achieve the improved O ( n d/ 3+ O (1) ) upper bound for the running time of the
algorithm parity-win-dominion ( G ), we need a stronger property that allows
us to carry out analysis similar to that used in Exercise 3.11. We formulate
this stronger property in the following exercise.
Exercise 3.22 Let b> 0 be even, and assume that |dom ( ξ ( b ) ) | <b/ 2. Argue
that then dom ( ξ ( b ) )= dom ( ξ ( b/ 2) ), and that reach 0 ( dom ( ξ ( b ) )) = dom ( ξ ( b ) ).
Prove that there is no 0-dominion of size at most b/ 2 in the game G
\
reach 0 ( dom ( ξ ( b ) )), using the property that the set of 0-dominions is closed
under union.