Game Development Reference
In-Depth Information
v?' This problem can be decidable even if the existence of some (i.e., HR)
winning strategy in v is undecidable.
The existing results
Finite-state stochastic games with linear-time objectives are rarely studied
explicitly because most of the results can be deduced from the corresponding
results about stochastic games with ω -regular payoffs (see Section 5.2.1). For
infinite-state stochastic games, the relationship between linear-time objectives
and ω -regular payoffs is more subtle. For example, even for reachability
payoffs, the question of whether val ( v )=1is not the same as the question
of whether player
has a P =1 F t -winning strategy in v , where the atomic
proposition t is satisfied exactly in the target vertices (the details are given
in Section 5.3).
Finite-state turn-based stochastic games with branching-time objectives
were first considered by Baier et al. [2004], where it was shown that winning
strategies for PCTL objectives may require memory and/or randomisation.
Consider the following game, where ν ( u a )=
{
a
}
, ν ( u b )=
{
b
}
, and ν ( v )=
.
u a
u b
v
Let
( P =1 X a )
( P =1 F b )
ϕ 1
( P > 0 X a )
( P > 0 X b )
ϕ 2
( P > 0 X a )
( P > 0 X b )
( P =1 F ( P =1 G a )).
ϕ 3
, and
each such strategy must inevitably use memory for ϕ 1 , randomisation for
ϕ 2 , and both memory and randomisation for ϕ 3 .
In Baier et al. [2004], it was also shown that for PCTL objectives, the
problem of whether player hasaMD ϕ -winning strategy in a given vertex of
a given finite-state MDP is NP -complete. MR strategies for PCTL objectives
were considered by Kucera and Strazovsky [2008], where it was shown that
the existence of a ϕ -winning MR strategy in a given vertex is in EXPTIME
for finite-state turn-based stochastic games, and in PSPACE for finite-state
MDPs.
In Brazdil et al. [2006], it was noted that turn-based stochastic games with
PCTL objectives are not determined (for any strategy type). To see this,
consider the following game, where ν ( u a )=
Obviously, player
has a ϕ i -winning strategy for every i
∈{
1 , 2 , 3
}
{
a
}
, ν ( u b )=
{
b
}
, ν ( u c )=
{
c
}
,
ν ( u d )=
{
d
}
, and ν ( v )= ν ( v 1 )= ν ( v 2 )=
.
Search Nedrilad ::




Custom Search