Game Development Reference
InDepth 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 infinitestate 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.
Search Nedrilad ::
Custom Search