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

Search Nedrilad ::

Custom Search