Game Development Reference
In-Depth Information
Reachability and safety objectives. Given a set
T⊆
L of target locations,
the reachability objective Reach(
T
)=
{
0 1 ...
|∃
k
0: k ∈T}
requires that an observation in
T
is visited at least once. Dually, the
safety objective Safe(
T
)=
{
0 1 ...
|∀
k
0: k ∈T}
requires that
are visited.
• Buchi and co-Buchi objectives. Given a set T⊆L of target locations,
the Buchi objective Buchi( T )= {π | Inf( π ) ∩T = ∅ } requires that at
least one location in T is visited infinitely often. Dually, the co-Buchi
objective coBuchi(
only locations in
T
T
)=
{
π
| Inf( π )
⊆T}
requires that only locations in
T
are visited infinitely often.
be a priority
function that maps each location to a non-negative integer priority.
The parity objective Parity( pr )=
Parity objectives. For d
N
, let pr : L
→{
0 , 1 ,...,d
}
{
π
|
min
{
pr ( )
|
Inf( π )
}
is even
}
requires that the minimal priority occurring infinitely often is even.
Given a location ˆ , we also say that Player i ( i =1 , 2) is surely-winning
from ˆ (or that ˆ is surely-winning) for an objective ϕ in G if Player i has
a surely-winning strategy in for ϕ in the game
where ˆ is
the initial location. A game is determined if when player i does not have a
surely-winning strategy from a location for an objective ϕ , then Player 3
G =
L, ˆ , Σ , Δ
i
has a surely-winning strategy from for the complement objective ϕ .
Exercise 6.1
Prove the following:
(a) Buchi and co-Buchi objectives are special cases of parity objectives.
(b) The complement of a parity objective is again a parity objective.
The following result shows that ( i ) parity games are determined and ( ii )
memoryless strategies are su cient to win parity games.
Theorem 6.1 (Memoryless determinacy, Emerson and Jutla [1991])
In all
game graphs G with parity objective ϕ, the following hold:
either Player 1 has a surely-winning strategy in
G, ϕ
, or Player 2 has a
;
• Player 1 has a surely-winning strategy in G, ϕ if and only if she has a
memoryless surely-winning strategy in G, ϕ;
surely-winning strategy in
G, ϕ
Player 2 has a surely-winning strategy in
G, ϕ
if and only if he has a
memoryless surely-winning strategy in
G, ϕ
.
which is not total,
and assume that we modify the rules of the game as follows: if in a round
where the current location is , Player 1 chooses an action σ
Exercise 6.2
Consider a game graph G =
L, l I , Σ , Δ
Σ such that