Game Development Reference

In-Depth Information

v

V
1
then player 1 moves the token in the same fashion. The outcome of

such a play is then an infinite path

∈

in the game graph.

An infinite game on a graph consists of a game graph a
n
d a payoff function

π
:
V
ω

v
0
,v
1
,v
2
,...

.A
pa
y
off function
assigns a payoff
π
(
v
) to every infinite

sequence of vertices
v
=

→
R

in the game graph. In this chapter we

c
onsider only zero-sum games, i.e., if the outcome
o
f a play is the infinite path

v

v
0
,v
1
,v
2
,...

V
ω
then player 0 (player Min) has to pay
π
(
v
) to player 1 (player Max).

We call a game on a graph a
qualitative game
if the payoff function

is Boolea
n
, i.e., if
π
(
V
ω
)

∈

. In
q
ualitative games, we say that an

outcome
v
is winning for player 0 if
π
(
v
) = 0, and it is losing for player 0

otherwise; and vice versa for player 1. An alternative, and popular, way

of formalising qualitative games is to specify a set
W

⊆{

0
,
1

}

V
ω
of outcomes

that are winning for player 1, which in our formalisation is
π
−
1
(1), i.e., the

indicator set of the Boolean payoff function
π
.

A
strategy
for player 0 is a function
μ
:
V
+

⊆

→ V
, such that if
v ∈

V
∗
and
w ∈ V
0
then (
w, μ
(
vw
))
∈ E
. Strategies for player 1 are defined

analogously. Both players follow their strategies
μ
and
χ
, respectively, to

produce an
outcome
Outcome(
v
0
,μ,χ
)=
v
0
,v
1
,v
2
,...
if for all
i ≥
0, we

have that
v
i
∈

V
1
implies
v
i
+1
=
μ
(
v
0
v
1
···

v
i
), and that
v
i
∈

V
2
implies

v
i
). A strategy
μ
:
V
ω

v
i
+1
=
χ
(
v
0
v
1
···

→

V
for player 0 is a
positional

V
∗
and
v

strategy
if for all
w, u

V
0
,wehave
μ
(
wv
)=
μ
(
uv
), i.e., the

values of
μ
are uniquely determined by the last element of its argument. It

follows that a function
μ
:
V
0
→

∈

∈

V
uniquely determines a positional strategy

for player 0, and we often do not distinguish between the two. Positional

strategies for player 1 are defined analogously.

We say that a game, with a game graph (
V,E,V
0
,V
1
) and a payoff function

π
:
V
ω

→
R

, is determined if:

su
χ

in
μ

π
(Outcome(
v, μ, χ
)) = in
μ

su
χ

π
(Outcome(
v, μ, χ
))
,

(3.1)

for all
v

V
, where
μ
and
χ
range over the sets of strategies for player 0

and player 1, respectively. Note that the inequality

∈

su
χ

in
μ

π
(Outcome(
v, μ, χ
))

≤

in
μ

su
χ

π
(Outcome(
v, μ, χ
))

(3.2)

always, and trivially, holds. One interpretation of
determinacy
, i.e., when

the converse of inequality (3.2) holds, is that player 0 (player Min) does

not undermine her objective of minimising the payoff if she announces her

strategy to player 1 (player Max) before the play begins, rather than keeping

it secret and acting 'by surprise' in every round. An analogous interpretation

holds for player 1.

Search Nedrilad ::

Custom Search