Game Development Reference
In-Depth Information
on v and the control state entered by M after reading the (unique) word ν ( wv )
obtained by replacing each vertex in wv with its associated colour. Infinite-
memory strategies are strategies which are not finite-memory. To sum up,
we consider the following six types of strategies: MD, MR, FD, FR, HD,
and HR, where XD
XR for every X
∈{
M , F , H
}
and MY
FY
HY for
every Y
are
denoted by Σ XY and Π XY , respectively (note that Σ = Σ HR and Π = Π HR ).
Every pair of strategies ( σ, π )
∈{
D , R
}
. The sets of all XY strategies of player
and player
Σ
×
Π and every initial probability
distribution μ : V
[0 , 1] determine a unique play of the game G , which
is a Markov chain G ( σ,π )
x
where V + is the set of states, and wu
wuu iff
μ
u , x> 0, and one of the following conditions holds:
u
u ;
u
V and σ ( wu ) assigns x to u
u ;
u
V and π ( wu ) assigns x to u
x
u .
u
V and u
The initial distribution of G ( σ,π μ assigns μ ( v ) to all v ∈ V , and zero to the
other states. Note that every run w in G ( σ,π μ naturally determines a unique
run w G in G , where w G ( i ) is the last vertex of w ( i ) for every i
0.
5.2 Winning objectives in stochastic games
In this section we give a taxonomy of winning objectives in turn-based
stochastic games and formulate the main problems of the associated algo-
rithmic analysis. For the rest of this section, we fix a turn-based stochastic
game G =( V,
, ( V ,V ,V ) , Prob ).
Let plays ( G ) be the set of all plays of G (i.e., plays ( G ) consists of all Markov
chains of the form G ( σ,π μ ). For every ∈{ , } , let yield : plays ( G ) R
be a function which to every play of G assigns the yield of player .
Remark In the standard terminology of game theory, the yield of a given
player under a given strategy profile is usually called a payoff . However, in
the context of turn-based stochastic games, the word 'payoff' usually refers
to a function f : Run ( G ) R whose expected value is to be maximised by
player
(see Section 5.2.1 for more details).
The objective of each player is to maximise his yield. For turn-based
stochastic games, most of the studied yield functions are zero-sum , i.e., for
every play G ( σ,π )
of G we have that
μ
yield ( G ( σ,π )
)+ yield ( G ( σ,π )
)=0 .
μ
μ
Search Nedrilad ::




Custom Search