Game Development Reference

In-Depth Information

y
1

x
1

y
2

x
2

Figure 2.1 A game graph

Example 2.2
We can specify the following winning condition for Eva over

the game graph from Figure 2.1, where the colours are identified with the

vertices:
y
2
∈

Inf(
α
)

⇔{

x
1
,x
2
}⊆

Inf(
α
)
.
This means that
Win
contains all

those plays

•

in which
x
1
,
x
2
, and
y
2
appear infinitely often, or

•

in which
y
2
and at least one of
x
1
or
x
2
appear only finitely often.

Now let us think of a play being built up by the two players by moving a

token along the edges of the graph: Eva chooses the next move from vertices

in
V
E
and Adam from vertices of
V
A
. Then we are interested in the question

of whether Eva has a way to play such that she is sure to win, no matter

how Adam plays, i.e., we are interested in the question of whether Eva has a

winning strategy. This is formalised in the following definitions.

A
strategy
for Eva is a function
σ
:
V
∗
V
E
→

V
such that
σ
(
xv
)=
v

implies (
v, v
)

∈

E
. A play
v
0
v
1
v
2
···

is played according to
σ
if

∀

i
:
v
i
∈

V
E
→

σ
(
v
0
···

v
i
)=
v
i
+1
.

Strategies for Adam are defined similarly with
V
A
instead of
V
E
.

Given an initial vertex
v
0
and a strategy
σ
(for Eva or Adam), the set

Out
(
σ, v
0
) contains all plays starting in
v
0
that are played according to
σ

(the possible outcomes of
σ
).

A strategy
σ
for Eva in a game

=(
G, Win
) is a winning strategy from

vertex
v
0
if Eva wins all plays
α
that start in
v
0
and are played according to

σ
, i.e.,
c
(
α
)

G

∈

Win
for all
α

∈

Out
(
σ, v
0
). Similarly, a strategy
σ
for Adam

is winning from
v
0
if
c
(
α
)
/

∈

Win
for all
α

∈

Out
(
σ, v
0
).

Example 2.3
We continue Example 2.2 and define a winning strategy for

Eva. Note that the only choice that Eva can make is in
x
1
, where she can

choose to move to
y
1
or to
y
2
. If she always decides to move to
y
2
, then

Adam could win by never moving to
x
2
: the resulting play would contain

y
2
infinitely often but
x
2
only finitely often and thus would be winning for

Adam.

If Eva always decides to move to
y
1
, then Adam could win by alternating

Search Nedrilad ::

Custom Search