Game Development Reference
In-Depth Information
1
2
1
2
1
2
1
2
1
2
v
1
2
1
2
1
2
1
2
1
2
d 1
d 2
d 3
d 4
d 5
e 1
e 2
e 3
e 4
e 5
v
s 1
s 2
s 3
s 4
s 5
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
Figure 5.4 An optimal maximising strategy may require infinite memory
branching) MDP G , then there is also an MD optimal maximising strategy
in v .
Claim (c) is not as trivial as it might seem. A naive idea of constructing
an optimal maximising MD strategy just by selecting some value-maximising
transition in every vertex does not work. To see this, consider the following
MDP, where t is the only target vertex:
v
u
t
Obviously, val ( v )= val ( u )= val ( t ) = 1, but the MD strategy which selects
the transitions v
v in the vertices v and u , respectively, is not
optimal maximising. Nevertheless, it is not hard to show that for every vertex
of v ∈ V there is a transition v → v such that the other outgoing transitions
of v can be safely removed without influencing the value in any vertex. This
result actually holds for all finitely branching stochastic games. Claim (c)
then follows immediately because if V is finite, then we can successively fix
such a transition in every v
u and u
V .
Proposition 5.8
, ( V ,V ,V ) , Prob ) be a finitely branching
stochastic game with a reachability objective associated to a set T
Let G =( V,
V .For
v such that the value of all u
every v
V there is a transition v
V