Game Development Reference
In-Depth 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 turn-based 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 surely-winning for an objective ϕ
in G if Outcome 1 ( G, α )
\
ϕ (resp. if Outcome 2 ( G, β )
ϕ ). We consider the
following objectives: