Game Development Reference
In-Depth Information
can never move back to a position they left previously, they can only take a
linear number of steps.
Almost all games considered in this chapter have the property that no
player is forced to move and therefore, if the searchers do not move, the
fugitive space does not decrease. An exception is the game of entanglement
studied by Berwanger and Gradel [2004] where the fugitive has to move at
every step and therefore it can be beneficial for the searchers not to move.
A similar lemma as before can often be shown for robber monotone
strategies as the robber space is non-increasing. However, this would require
the game to be such that there is a bound on the number of steps the cops
have to make to ensure that the robber space actually becomes smaller. In
almost all games such a bound can easily be found, but formalising this in
an abstract setting does not lead to any new insights.
7.2.6 Connection to reachability games
In this section we rephrase graph searching games as reachability games
and derive some consequences of this. A reachability game is a game played
on an arena
G
:= ( A, V 0 ,E,v 0 ) where ( A, E ) is a directed graph, V 0
A
and v 0
V 0 . The game is played by two players,
Player 0 and Player 1, who push a token along edges of the digraph. Initially
the token is on the vertex v 0 . In each round of the game, if the token is
on a vertex v i
A . We define V 1 := A
\
V 0 then Player 0 can choose a successor v i +1 of v i ,i.e.,
( v i ,v i +1 )
E , and push the token along the edge to v i +1 where the play
continues. If the token is on a vertex in V 1 then Player 1 can choose the
successor. The winning condition is given by a set X
A . Player 0 wins if
at some point the token is on a vertex in X or if the token is on a vertex in
V 1 which has no successors. If the token never reaches a vertex in X or if at
some point Player 0 cannot move anymore, then Player 1 wins. See [Gradel
et al., 2002, Chapter 2] for details of reachability games.
A positional strategy for Player i in a reachability game can be described
as a function f i : V i → A assigning to each vertex v where the player moves a
successor f ( v )suchthat( v, f ( v )) ∈ E . f i is a winning strategy if the player
wins every play consistent with this strategy. For our purposes we need two
results on reachability games, positional determinacy and the fact that the
winning region for a player in a reachability game can be computed in linear
time.