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