Game Development Reference

In-Depth Information

3.3.3 Value iteration: progress measure lifting

The divide-and-conquer algorithm from Section 3.3.1 solves parity games in

time
O
(
m

(
n/d
)
d
)=
O
(
n
d
+
O
(1)
), and if
d
=Ω(
n
(1
/
2)+
ε
) then the dovetail-

ing algorithm from Section 3.3.2 improves it to
n
O
(
√
n
)
. In this section we

present an altogether different algorithm, called the progress measure lifting

algorithm, that runs in time
O
(
dm

·

(
n/
(
d/
2))
d/
2
)=
O
(
n
d/
2+
O
(1)
), which is

·

better than either of the other two algorithms if
d
=
O
(
√
n
).

The design of the progress measure lifting algorithm is based on the

concept of a progress measure that is a labelling of vertices in a parity

game, which witnesses the existence of a positional dominion strategy in a

parity game. Let
p
:
V

be a priority function, and without

loss of generality, assume that
d
is even. In what follows we identify a

function
ξ
:
V →
N

→{

1
,
2
,...,d

}

d/
2
with a sequence of functions
ξ
d−
1
,...,ξ
3
,ξ
1
:
V →
N,

and hence
ξ
(
v
)=(
ξ
d−
1
(
v
)
,...,ξ
3
(
v
)
,ξ
1
(
v
)) for every
v ∈ V
. For a number

q ∈{
1
,
2
,...,d}
, we write
ξ
[
q
]
(
v
) for the tuple (
ξ
d−
1
(
v
)
,...,ξ
q
+2
(
v
)
,ξ
q
(
v
))

if
q
is odd, and for the tuple (
ξ
d−
1
(
v
)
,...,ξ
q
+3
(
v
)
,ξ
q
+1
(
v
)) if
q
is even. We

use the
lexicographic order
for comparisons between tuples of numbers,

e.g., (2
,
3
,
0)
>
(2
,
2
,
4) holds, but (4
,
0
,
2
,
1)

≤

(4
,
0
,
1
,
6) does not.

d/
2

We say that a function
ξ
:
V

→
N

is a
parity progress measure
if

ξ
[
p
(
v
)]
(
w
), and if
p
(
v
)is

odd then the inequality is strict. Observe that an equivalent definition of a

parity progress measure requires that for every vertex
v

E
, we have that
ξ
[
p
(
v
)]
(
v
)

for every edge (
v, w
)

∈

≥

∈

V
, we have that

ξ
[
p
(
v
)]
(
v
)

max
(
v,w
)
∈E
ξ
[
p
(
v
)]
(
w
), and if
p
(
v
) is odd then the inequality is

strict, where the maxima are taken with respect to the lexicographic order.

≥

d/
2

Exercise 3.16

Let
ξ
:
V

→
N

be a parity progress measure and let

q

∈{

1
,
3
,...,d

−

1

}

. Argue that on every infinite path, starting from an

arbitrary vertex
v

V
, the number of vertices of the odd priority
q
that

occur before an occurrence of a vertex of priority bigger than
q
is bounded

from above by
ξ
q
(
v
). Conclude that for every infinite path, the maximum

vertex priority that occurs infinitely many times is even.

∈

d/
2
is a
game parity progress measure

We say that a function
ξ
:
V

→
N

if for every vertex
v

∈

V
, the following conditions hold:

min
(
v,w
)
∈E
ξ
[
p
(
v
)]
(
w
)
,

and if
p
(
v
) is odd then the inequality is strict;

V
0
, then
ξ
[
p
(
v
)]
(
v
)

if
v

∈

≥

and

max
(
v,w
)
∈E
ξ
[
p
(
v
)]
(
w
)
,

and if
p
(
v
) is odd then the inequality is strict
.

V
1
, then
ξ
[
p
(
v
)]
(
v
)

if
v

∈

≥

Search Nedrilad ::

Custom Search