Game Development Reference
In-Depth Information
Hence, every vertex v
V has its f -value , denoted by val f ( v, G ) (or just
by val f ( v )if G is understood), which is defined by Equality (5.1). Note that
this result holds without any additional assumptions about the game G .In
particular, G may have infinitely many vertices and some (or all) of them
may have infinitely many outgoing transitions.
Remark It is worth noting that the result presented by Maitra and Sud-
derth [1998] is even more general and holds also for concurrent stochastic
games (where both players make their choice simultaneously) with an arbi-
trary (not necessarily countable) action and state spaces. The only require-
ment is that f is a bounded B -measurable function and both players choose
their actions at random according to finitely additive probability measures on
the power sets of their respective action sets. This can be used, e.g., to show
that vertices in various types of timed stochastic games have an f -value.
An important subclass of payoff functions are qualitative payoffs which
simply classify each run as good or bad according to some criteria. The good
runs are assigned 1, and the bad ones are assigned 0. General (not necessarily
qualitative) payoffs are also called quantitative payoffs.
Note that a qualitative payoff f is just a characteristic function of some
Borel set B f
Run ( G ). For every pair of strategies ( σ, π )
Σ
×
Π and every
initial distribution μ we have that
( f σ,π
Run ( G ( σ,π )
E
)=
P μ (
{
w
)
|
w G
B f }
) .
μ
μ
Hence, player
in fact try to maximise and minimise the
probability of all runs in B f , respectively.
Observe that Equality (5.1) does not guarantee the existence of optimal
strategies for player
and player
which would achieve the yield val f ( v )
or better against every strategy of the opponent. As we shall see, optimal
strategies do not exist in general, but they may exist in some restricted cases.
On the other hand, Equality (5.1) does imply the existence of ε -optimal
strategies for an arbitrarily small ε> 0.
and player
Definition 5.3 Let ε ≥ 0. A strategy σ ∈ Σisan ε -optimal maximising
strategy in a vertex v ∈ V if inf π∈ Π E( f σ, v ) ≥ val f ( v ) − ε . Similarly, a
strategy π ∈ Πisan ε -optimal minimising strategy in a vertex v ∈ V if
sup σ∈ Σ
E( f σ,π
) ≤ val f ( v )+ ε . Strategies that are 0-optimal are optimal .
v
Qualitative payoffs
2 C a valuation .
An important and well-studied class of qualitative payoffs are characteristic
Let C =
{
c 1 ,...,c n }
be a finite set of colours , and ν : V