Game Development Reference

In-Depth Information

3.3.4 Divide and conquer with dominion preprocessing by

progress measure lifting

The algorithms in Sections 3.3.2 and 3.3.3 apply very distinct techniques to

e
ciently solve parity games with a large and small, respectively, number

of priorities relative to the number of vertices. In this section we show

that the two techniques can be successfully combined to improve the worst-

case running time from
O
(
dm

(
n/
(
d/
2))
d/
2
)=
O
(
n
d/
2+
O
(1)
) of the latter

algorithm to
O
(
n
d/
3+
O
(1)
), which is the best currently known for parity

games with
d
=
O
(
√
n
). The improvement requires a vital modification of

the progress measure lifting algorithm from Section 3.3.3.

In Section 3.3.3 we have introduced sets
M
D
of (
d/
2)-tuples of non-negative

integers (
x
d−
1
,...,x
3
,x
1
), where for each odd
q
the component
x
q
is bounded

by the number
n
q
of vertices of priority
q
in a set
D

·

V
. We argued that this

set was su
ciently large to express the values of the pointwise-lexicographic

least game parity progress measure, and the algorithm
progress-measure-

lifting
(
G
) computed the least progress measure by iterative application of

the
lift
(

⊆

,v
) operators.

In this section, for all integers
b>
0, we consider an alternative set
N
b

of (
d/
2)-tuples of non-negative integers (
x
d−
1
,...,x
3
,x
1
) that satisfy the

·

condition
odd
q
x
q
≤ b
. Note that for every
b>
0, the set
N
b
∪{}
is

totally ordered by the lexicographic order on (
d/
2)-tuples of numbers, and

the
lift
(
·,v
) operators can be appropriately modified to select only values in

the set
N
b
∪{}
.

We argue that using sets
N
b
, for appropriately chosen numbers
b
, instead

of using the set
M
V
, turns the algorithm
progress-measure-lifting
(
G
)into

an e
cient procedure for computing 0-dominions of moderate size, or estab-

lishing that no small 0-dominions exist. It is routine and straightforward to

adapt the algorithm
progress-measure-lifting
(
G
) to compute 1-dominions of

moderate size, or establishing lack thereof, too.

These combined procedures for computing 0-dominions and 1-dominions

of moderate size are then used in a modification of the dovetailing algorithm

parity-win-dominion
(
G
) from Section 3.3.2, instead of using the brute-force

search procedure
dominion
(
G,
). We will refer to this modification of pro-

cedure
parity-win-dominion
(
G
) as procedure
parity-win-dominion
†
(
G
), the

details of which are presented in Figure 3.5. Note that the procedure
parity-

win
‡
(
G
), that is used in procedure
parity-win-dominion
†
(
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.

Search Nedrilad ::

Custom Search