Game Development Reference
In-Depth Information
While the algorithm is simple and e cient, its design provides a blueprint
for a divide-and-conquer 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 1-reachability 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 0-reachability 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 1-closed set U to a successor in U is called
a U -trapping strategy . Sets that are 0-closed , and positional trapping
strategies for player 1, are defined analogously.
A set U
V is said to be a 1-closed set if for every vertex u
Exercise 3.2 Argue that the set S = V \ reach 1 ( T ) is 1-closed, 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
|