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