Game Development Reference
InDepth Information
While the algorithm is simple and e
cient, its design provides a blueprint
for a divideandconquer algorithm for solving parity games discussed in
Section 3.3.
Before we present the algorithm for solving repeated reachability games
we establish positional determinacy of reachability and safety games, and we
describe the structure of the winning sets in reachability and safety games.
For a set
T
⊆
V
of target vertices, we define the
1reachability set
by
reach
1
(
T
)=
i
=0
reach
1
(
T
), where:
reach
1
(
T
)=
T
reach
i
+1
(
T
)=
reach
1
(
T
)
∪{
1
reach
1
(
T
)
v
∈
V
1
: there is (
v, w
)
∈
E,
such that
w
∈
}
reach
1
(
T
)
∪{
v
∈
V
0
: for all (
v, w
)
∈
E,
we have
w
∈
}
.
A positional strategy for player 1 that maps each of his vertices in a set
reach
i
+
1
(
T
)
\reach
1
(
T
) to its successor in
reach
1
(
T
) will be referred to as a
T

reachability strategy
. The
0reachability set
reach
0
(
T
), and positional
T
reachability strategies for player 0, are defined in an analogous way.
Exercise 3.1
Argue that if player 1 follows a
T
reachability strategy from
a vertex in
reach
1
(
T
) then a vertex in
T
is reached in at most
i
rounds.
Conclude that if
G
is a reachability game with a target set
T
⊆
V
, then
reach
1
(
T
)
⊆
win
1
(
G
).
U
,
if
u
belongs to player 0 then it has a successor in
U
, and if
u
belongs to
player 1 then all its successors are in
U
. A positional strategy for player 0
that maps each of her vertices in a 1closed set
U
to a successor in
U
is called
a
U
trapping strategy
. Sets that are
0closed
, and positional trapping
strategies for player 1, are defined analogously.
A set
U
⊆
V
is said to be a
1closed set
if for every vertex
u
∈
Exercise 3.2
Argue that the set
S
=
V \ reach
1
(
T
) is 1closed, and that
if player 0 follows an
S
trapping strategy from a vertex in
S
then no vertex
in
T
is ever reached. Conclude that if
G
is a reachability game with a target
set
T ⊆ V
, then
V \ reach
1
(
T
)
⊆ win
0
(
G
), and that reachability and safety
games are positionally determined.
In the following exercise the reader is asked to provide vital implementation
details of an e
cient algorithm for solving reachability and safety games.
Exercise 3.3
Give a detailed description of an algorithm for computing
the set
reach
1
(
T
) that runs in time
O
(
m
), where
m
=
is the number of
edges in the game graph. Devise an appropriate data structure for directed

E

Search Nedrilad ::
Custom Search