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

Search Nedrilad ::

Custom Search