Game Development Reference
In-Depth Information
decision problem to decide, given an abstract graph searching game
G
:=
( V,
for the Searcher of
complexity at most k . We will usually restrict this problem to certain classes
of graph searching games, such as Visible Cops and Robber Games. In these
cases we will simply say 'the Visible Cops and Robber Game has complexity
C
S
,
F
,c ) and k
N
, if there is a winning strategy in
G
'. Furthermore, often this problem is further restricted to games with a
fixed number of Searchers.
Definition 7.7 Let k ∈ N. The k-searcher game on G := ( V,S,F,c )is
defined as the graph searching game G := ( V,S ,F,c ) on the restriction of
G to S := { ( X, X ):( X, X ) ∈S and c ( X ) ,c ( X ) ≤ k} .
7.2.5 Monotonicity
In this section we formally define the concept of monotone strategies. Let
G := ( V,S,F,c ) be an abstract graph searching game.
Definition 7.8
A play
P
:= ( X 0 ,R 0 ) ,... , where R i :=
{
v i }
in case of
visible graph searching games, is cop-monotone if for all v
V and
i
l
j :if v
X i and v
X j then v
X l .
P
is robber-monotone if
F
( X i ,R i ,X i +1 )
⊇F
( X i +1 ,R i +1 ,X i +2 ), for all
i
0.
A strategy is cop- or robber-monotone if any play consistent with the
strategy is cop- or robber-monotone.
As outlined above, monotone winning strategies have the advantage of
being e cient in the sense that no part of the graph is searched more than
once. In most games, this also means that the strategies are short, in the
sense that they take at most a linear number of steps.
,c ) be an abstract graph searching game with
the property that the robber space does not decrease if the cops do not move.
Then every play consistent with a cop-monotone winning strategy f will end
after at most
Lemma 7.9
Let
G
:= ( V,
S
,
F
|
V
|
steps.
Proof Note that by definition of Searcher strategies the move of the searchers
only depends on the current searcher position and the fugitive space or
position. Hence, from the assumption that no part of the graph is cleared
if the searchers do not move, we can conclude that if at some point the
searchers do not move and the fugitive stands still, the play would be infinite
and hence losing for the searchers.
Therefore, the cops have to move at every step of the game and as they