Game Development Reference
In-Depth Information
Further, for every n
1 we define HD strategies σ n
Σ and π n
Πas
follows:
The strategies σ 1 and π 1 are defined arbitrarily.
V V such that len ( wv ) <n , the strategy σ n
selects a transition v → v such that Γ k (0)( v )=max { Γ k (0)( v ) | v → v }
where k = n − len ( wv ).
For all n
2 and wv
V V such that len ( wv ) <n , the strategy π n
For all n
2 and wv
v such that Γ k (0)( v )=min
Γ k (0)( v )
v }
selects a transition v
{
|
v
where k = n
len ( wv ).
It is easy to prove that for every n
1
Γ n (0)( v ) = inf
( σ n )
v
( Reach n ( T )) = sup
( σ,π n )
v
( Reach n ( T )) .
π∈ Π P
σ∈ Σ P
A direct corollary to these observations is the following:
Proposition 5.5
If G is finitely branching, then for all v
V and ε> 0
( σ,π )
v
( Reach n ( T ))
there are n
0 and a HD strategy σ
Σ such that
P
val ( v )
ε for every π
Π .
Finally, let us note that the values in infinite-state games can be irrational,
even if all transition probabilities are equal to
1
2 . To see this, consider the
following Markov chain
M
, where t is the only target vertex.
1
2
1
2
1
2
t
v
1
1
2
1
2
1
2
1
2
Obviously, val ( v ) is equal to the probability of all w
Run ( v ) which visit t ,
where μ v is the initial probability distribution. By inspecting the structure
of
, it is easy to see that val ( v ) has to satisfy the equation x = 2 + 2 x 3 .
Actually, va l ( v )isthe least solution of this equation in the interval [0 , 1],
which is 5 1
2
M
(the 'golden ratio').
5.3.2 Optimal strategies and determinacy
In this section we classify the conditions under which optimal strategies exist,
analyse the type of optimal strategies, and resolve the determinacy of games
with P F t objectives.
The properties of optimal minimising strategies are summarised in the
next proposition.