Game Development Reference
InDepth Information
algorithm
paritywindominion
†
(
G
)
(
D
0
,D
1
)
progressmeasurelifting
†
(
G, b
)
←
D
∗
←
reach
0
(
D
0
)
∪
reach
1
(
D
1
)
G
∗
←
D
∗
G
\
D
∗

if

<b/
2
then
(
W
0
,W
1
)
paritywin
‡
(
G
∗
)
←
else
(
W
0
,W
1
)
←
paritywindominion
†
(
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 divideandconquer 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
progressmeasurelifting
(
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
progressmeasurelifting
†
(
G, b
) for the procedure that
combines the abovedescribed modified versions of the progress measure
lifting procedures for computing 0dominions and 1dominions, 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
paritywindominion
(
G
) in procedure
parity
win
†
(
G
) had at most
n
instead of
M
V
∪{}
vertices. Unsurprisingly, a similar property holds
for the procedure
progressmeasurelifting
†
(
G, b
): if
dom
(
ξ
(
b
)
)=
−
then every
0dominion 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
paritywindominion
†
(
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 0dominion of size at most
b/
2 in the game
G
\
reach
0
(
dom
(
ξ
(
b
)
)), using the property that the set of 0dominions is closed
under union.
Search Nedrilad ::
Custom Search