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