Game Development Reference
In-Depth Information
Searcher strategies but we will come back to formalisations of Fugitive
strategies later in Section 7.5.
Definition 7.3
A strategy for the Searcher in a visible abstract graph
searching game
G
:= ( V,
S
,
F
,c ) is a function f : Pow( V )
×
V
Pow( V )
such that for all X
V and v
V ,( X, f ( X, v ))
∈S
.
A finite or infinite play
P
:= ( X 0 ,v 0 ) , ... is consistent with f if X i +1 :=
f ( X i ,v i ), for all i .
f is a winning strategy if every play
P
which is consistent with f is
winning for the Searcher.
If in a play the current position is ( X, v ), i.e., the Searchers are on the
vertices in X and the Fugitive is on v , then a strategy for the Searcher tells
the Searcher what to do next, i.e., to move the Searchers to the new position
X .
Note that implicitly we have defined our strategies to be positional strategies
in the sense that the action taken by a player depends only on the current
position in the play but not on the history. We will see below that this
is without loss of generality as graph searching games are special cases of
reachability games for which such positional strategies su ce. Furthermore,
the determinacy of reachability games implies that in any visible graph
searching game exactly one of the two players has a winning strategy (see
Corollary 7.11).
It is worth pointing out the fundamental difference between strategies for
the visible and invisible case. In the invisible case, a strategy for the Searcher
uniquely defines a play. Therefore, as we have done above, we can represent a
strategy for the Searcher in an invisible graph searching game as a sequence
X 0 ,X 1 ,... or Searcher positions.
In the visible case, however, the next searcher position may depend on
the choice of the fugitive. Therefore, a Searcher strategy f in the visible
case can be described by a rooted directed tree T as follows. The nodes
t ∈ V ( T ) are labelled by cops ( t ) ⊆ V and correspond to Searcher positions.
The individual edges correspond to the possible robber moves. More formally,
the root r ∈ V ( T )of T is labelled by cops ( r ):= X 0 the initial cop position.
For every v ∈ V \X 0 there is a successor t v such that cops ( t v ):= f ( cops ( t ) ,v ).
The edge ( t, t v ) is labelled by v . Now, for every u
( X 0 ,v,cops ( t v )) there
is a successor t u of t v labelled by cops ( t u ):= f ( cops ( t v ) ,u ). Continuing in
this way we can build up a strategy tree which is finite if, and only if, f is a
winning strategy. More formally, we define a strategy tree as follows.
∈F
Definition 7.4
Let ( V,
S
,
F
,c ) be an abstract visible graph searching game.