Game Development Reference
InDepth Information
6.2 Games with perfect information
Game graphs
A
game graph
is a tuple
G
=
L, l
I
,
Σ
,
Δ
, where
L
is a
finite set of states,
l
I
∈
L
is the initial state, Σ is a finite alphabet of actions,
and Δ
L
is a set of labelled transitions. We require the game
graph
G
to be
total
, i.e., for all
⊆
L
×
Σ
×
Σ, there exists
∈
∈
L
and all
σ
∈
L
such
that (
, σ,
)
Δ.
The turnbased game on
G
is played by two players for infinitely many
rounds. The first round starts in the initial location
l
I
of the game graph. In
each round, if the current location is
, Player 1 chooses an action
σ
∈
∈
Σ,
and then Player 2 chooses a location
such that (
, σ,
)
∈
Δ. The next
round starts in
.
Plays and strategies
A
play
in
G
is an infinite sequence
π
=
0
1
...
such
that
0
=
l
I
, and for all
i ≥
0, there exists
σ
i
∈
Σ such that (
i
,σ
i
,
i
+1
)
∈
Δ.
We denote by Inf(
π
) the set of locations that occur infinitely often in
π
.A
history
is a finite prefix
π
(
i
)=
0
...
i
of a play, and its
length
is

π
(
i
)

=
i
.
We denote by Last(
π
(
i
)) =
i
the last location in
π
(
i
).
A
deterministic strategy
in
G
for Player 1 is a function
α
:
L
+
→
Σ that
maps histories to actions, and for Player 2 it is a function
β
:
L
+
×
Σ
→
L
L
+
such that for all
π
∈
and all
σ
∈
Σ, we have (Last(
π
)
,σ,β
(
π, σ
))
∈
Δ.
We denote by
B
G
the set of all Player 1 and Player 2 strategies in
G
, respectively. A strategy
α
A
G
and
∈A
G
is
memoryless
if Last(
π
)=Last(
π
)
implies
α
(
π
)=
α
(
π
) for all
π, π
∈
L
+
, that is the strategy only depends on
the last location of the history. We define memoryless strategies for Player 2
analogously.
The
outcome
of deterministic strategies
α
(for Player 1) and
β
(for
Player2)in
G
is the play
π
=
0
1
...
such that
σ
i
=
α
(
π
(
i
)) and
i
+1
=
β
(
π
(
i
)
,σ
i
) for all
i
0. This play is denoted outcome(
G, α, β
). A play
π
is
consistent
with a deterministic strategy
α
for Player 1 if
π
= outcome(
G, α, β
)
for some deterministic strategy
β
for Player 2. We denote by Outcome
1
(
G, α
)
the set of plays that are consistent with
α
. Plays that are consistent with a
deterministic strategy for Player 2 and the set Outcome
2
(
G, β
) are defined
analogously.
≥
L
ω
.
Objectives
An
objective
for a game graph
G
=
L, l
I
,
Σ
,
Δ
isaset
ϕ
⊆
We denote by
ϕ
=
L
ω
ϕ
the complement of
ϕ
. A deterministic strategy
α
for Player 1 (resp.
β
for Player 2) is
surelywinning
for an objective
ϕ
in
G
if Outcome
1
(
G, α
)
\
⊆
ϕ
(resp. if Outcome
2
(
G, β
)
⊆
ϕ
). We consider the
following objectives:
Search Nedrilad ::
Custom Search