Game Development Reference
InDepth Information
Observe that the above series converges absolutely which is mathematically
convenient.
•
Weighted reachability
payoff assigns to every run
w
either 0 (if
w
does
not visit a target vertex) or the reward of the first target vertex visited
by
w
. Here, it is usually assumed that
r
is positive. One can also consider
a
discounted reachability
payoff which is a variant of discounted payoff
where
r
(
v
) is either 1 or 0 depending on whether
v
is a target vertex or
not.
•
limmax
and
limmin
payoffs, which assigns to each
w
Run
(
G
) ei
ther the maximal or the minimal reward which appears infinitely often
along
w
. More precisely, we assume that
r
takes only finitely many values,
and define
lim

max
(
w
) and
lim

min
(
w
)asthemax and min of the set
{
∈
x
∈
R

r
(
w
(
i
)) =
x
for infinitely many
i
≥
0
}
, respectively.
The presented list of Borel measurable payoffs contains only selected concep
tual representatives and it is surely not exhaustive.
The problems of interest
For a given class of turnbased stochastic games
and a given class of payoff
functions
F
, we are interested in answering the following basic questions:
G
(1)
Do optimal strategies exist for all G ∈Gand f ∈ F ?
(2)
What is the type of optimal and εoptimal strategies?
(3)
Can we compute/approximate val
f
(
v
)
?
(4)
Can we compute optimal and εoptimal strategies?
If the answer to Question (1) is negative, we also wonder whether the
existence of an optimal strategy in a given vertex is decidable and what is
the complexity of this problem.
Optimal strategies (if they exist) may require memory and/or randomisa
tion. A full answer to Question (2) should provide an optimal upper bound
on the size of the required memory. It can also happen that optimal strategies
require memory
or
randomisation, but not necessarily both.
Question (3) can also be reformulated as a decision problem. For a given
rational constant
, we ask whether
val
f
(
v
) is bounded by
(from above or
below). In particular, if
f
is a qualitative payoff, it is often important to know
whether
val
f
(
v
) is positive or equal to one, and this special
qualitative
variant
of the problem tends to be computationally easier. If
is a class of infinite
state games,
val
f
(
v
) can be irrational even if all transition probabilities
are rational and
f
is reachability payoff (a simple example is presented in
G
Search Nedrilad ::
Custom Search