Game Development Reference
InDepth Information
algorithm
paritywindominion
(
G
)
n
←
√
2
n
←
V

;
(
D, i
)
←
dominion
(
G,
);
j
←
1
−
i
G
∗
←
G
\
reach
i
(
D
)
if
D
=
∅
then
(
W
0
,W
1
)
paritywin
†
(
G
∗
)
←
else
(
W
0
,W
1
)
←
paritywindominion
(
G
∗
)
(
W
i
,W
j
)
←
(
V
\
W
j
,W
j
)
endif
return
(
W
0
,W
1
)
Figure 3.3 A divideandconquer algorithm for parity games with dominion
preprocessing
The procedure
paritywindominion
(
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 0dominion or 1dominion exists, and it returns (
)
otherwise. Moreover, the procedure
paritywin
†
(
G
) is a copy of the procedure
paritywin
(
G
) from Section 3.3.1 in which both recursive calls
paritywin
(
G
)
and
paritywin
(
G
) have been replaced by calls
paritywindominion
(
G
)
and
paritywindominion
(
G
), respectively.
∅
,
⊥
Exercise 3.12
Prove that the algorithm
paritywindominion
(
G
) is correct.
Note that the procedures
paritywindominion
(
G
) and
paritywin
†
(
G
) are
mutually recursive, and then use an inductive argument similar to that
for the algorithm
paritywin
(
G
) in Section 3.3.1. In particular, in order to
justify the
else
case in procedure
paritywindominion
(
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 divideandconquer approach and prepro
cessing based on detection and removal of dominions is that, if an appropriate
tradeoff is chosen between the size of dominions detected and removed, and
the cost of detecting them, then the analysis of the worstcase running time
of the divideandconquer algorithm carried out in Exercise 3.11 can be
improved.
Exercise 3.13
Argue that procedure
dominion
(
G,
) can be implemented
Search Nedrilad ::
Custom Search