Game Development Reference

In-Depth Information

v

u

s
1

s
2

s
3

s
4

s
i

t

t

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

1

1

2

1

2

1

2

1

2

1

2

1

Figure 5.2 An optimal minimising strategy does not necessarily exist.

Proposition 5.6
Let G be a stochastic game with a reachability objective

associated to a set of target vertices T .Letv be a vertex of G. Then

(a) an optimal minimising strategy in v does not necessarily exist; and if it

exists, it may require infinite memory;

(b) an ε-optimal minimising strategy in v may require infinite memory for

every fixed ε

(0
,
1)
;

(c) if G is finitely branching, then there is a MD strategy which is optimal

minimising in every vertex of G.

∈

A counterexample for claims (a) and (b) is given in Figure 5.2, where
t, t

are the only target vertices. Observe that
val
(
u
) = 0, but there is no optimal

minimising strategy in
u
. Further, observe that for each fixed
ε

(0
,
1),

every
ε
-optimal minimising strategy
π
in
u
must employ infinitely many

transitions of the form
u

∈

s
i
(otherwise, the target vertex
t
would be

inevitably reached with probability 1). Hence,
π
requires infinite memory.

Finally, note that
val
(
v
)=
2
and there is an optimal minimising strategy
π

in
v
which requires infinite memory (the strategy
π
must ensure that the

probability of reaching a target vertex from
u
is at most

→

1

2
, because then

u
; hence,
π

requires infinite memory). Claim (c) follows directly from Proposition 5.4.

The properties of optimal maximising strategies are remarkably different

from those of optimal minimising strategies. The most notable (and perhaps

somewhat surprising) difference is that an optimal maximising strategy may

require
infinite memory
, even in finitely branching games.

player

does not gain anything if she uses the transition
v

→

Proposition 5.7
Let G be a stochastic game with a reachability objective

associated to a set of target vertices T .Letv be a vertex of G. Then

(a) an optimal maximising strategy in v does not necessarily exist even if G

is finitely branching;

Search Nedrilad ::

Custom Search