Game Development Reference
InDepth 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 coBuchi 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
coBuchi
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 nonnegative 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 surelywinning
from
ˆ
(or that
ˆ
is surelywinning) for an objective
ϕ
in
G
if Player
i
has
a surelywinning strategy in for
ϕ
in the game
where
ˆ
is
the initial location. A game is
determined
if when player
i
does not have a
surelywinning strategy from a location
for an objective
ϕ
, then Player 3
G
=
L,
ˆ
,
Σ
,
Δ
−
i
has a surelywinning strategy from
for the complement objective
ϕ
.
Exercise 6.1
Prove the following:
(a) Buchi and coBuchi 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 surelywinning strategy in
G, ϕ
, or Player
2
has a
;
• Player
1
has a surelywinning strategy in G, ϕ if and only if she has a
memoryless surelywinning strategy in G, ϕ;
surelywinning strategy in
G, ϕ
•
Player
2
has a surelywinning strategy in
G, ϕ
if and only if he has a
memoryless surelywinning 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
Search Nedrilad ::
Custom Search