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