Game Development Reference
In-Depth 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.
lim-max and lim-min 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 turn-based 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