Game Development Reference
In-Depth Information
the inequality
( σ,π )
v
μ Γ( v )
inf
π∈ Π
sup
σ∈ Σ P
( Reach ( T ))
(5.6)
cannot be strict.
Let us first assume that every vertex u
V has a locally optimal
a
→ u where μ Γ( u )= μ Γ( u ) (in particular, note that
if u has finitely many outgoing transitions, some of them must be locally
optimal because μ Γ is a fixed-point of Γ). Now consider a MD strategy π
which in every u ∈ V selects some (fixed) locally optimal outgoing transition
of u . One can easily show that μ Γ( v )=sup σ∈ Σ P
outgoing transition u
( σ,π )
v
( Reach ( T )) for every
v
V , which implies that Inequality (5.6) is an equality. Further, observe
that π is an optimal minimising strategy in every vertex of G . Thus, we
obtain the following:
Proposition 5.4
V has a locally optimal outgoing transition,
then there is a MD strategy of player
If every u
which is optimal minimising in every
vertex of G.
In the general case when the vertices of V do not necessarily have locally
optimal outgoing transitions (this can of course happen only if G is infinitely
branching), Inequality (5.6) is proven as follows. We show that for every
ε> 0 and every v
V there is a HD strategy π ε
Π such that
( σ,π ε )
v
σ∈ Σ P
sup
( Reach ( T ))
μ Γ( v )+ ε.
This implies that Inequality (5.6) cannot be strict. Intuitively, in a given
state wu
V V , the strategy π ε selects a transition u
u whose error
μ Γ( u ) is 'su ciently small'. Observe that the error can be made
arbitrarily small because μ Γ is a fixed point of Γ. The strategy π ε selects
transitions with progressively smaller and smaller error so that the 'total
error'
μ Γ( u )
( σ,π ε )
v
P
( Reach ( T ))
μ Γ( v ) stays bounded by ε no matter what player
does. A detailed proof can be found in, e.g., Brazdil et al. [2009a].
If G is finitely branching, then Γ is not only monotonic but also contin-
uous , i.e., Γ( i =0 y i )= i =0 Γ( y i ) for every infinite non-decreasing chain
y 1
in ([0 , 1] |V | ,
y 2
y 3
···
). By the Kleene fixed-point theorem, we
have that μ Γ= i =0 Γ i (0), where 0 is the vector of zeros. For every n
1,
let Reach n ( G ) be the set of all w
Run ( G ) such that w ( i )
T for some
0 ≤ i<n . A straightforward induction on n reveals that
Γ n (0)( v ) = sup
σ∈ Σ
( σ,π )
v
( Reach n ( T )) = inf
π∈ Π
( σ,π )
v
( Reach n ( T )) .
π∈ Π P
inf
σ∈ Σ P
sup