Game Development Reference
In-Depth Information
If, in addition, the number of searchers is restricted to a fixed k ,wecan
use a straightforward alternating logarithmic space algorithm for it.
For Fugitive-monotone strategies we can obtain a similar result if the
searchers can move freely. In any Fugitive-monotone game the Fugitive
space can only decrease a linear number of times. However, a priori we
have no guarantee that in between two positions where the Fugitive space
does decrease, the searchers only need to make a linear number of steps. In
particular, in game variants where the cops can only move along an edge or
where their movement is restricted similar to the entanglement game, there
might be variants where they need a large number of steps before the robber
space shrinks again.
Games with an invisible fugitive
Lemma 7.48
Let
C
be a concise class of graph searching games.
1 The invisible graph searching game on
can be solved in polynomial space.
2 The k-searcher invisible graph searching game on
C
C
can be solved in poly-
nomial space.
3 There are examples of games which are Pspace -hard even in the case
where k is fixed.
Proof Recall that a winning strategy for the Searcher in an invisible graph
searching game can be described by the sequence X 0 ,...,X k of searcher
positions. As
is concise, any such position only consumes polynomial space.
We can therefore guess the individual moves of the searcher reusing space
as soon as a move has been made. In this way we only need to store at
most two Searcher positions and the fugitive space, which can all be done in
polynomial space.
Clearly, Part 1 implies Part 2. Kreutzer and Ordyniak [2009] show that
the invisible domination game is Pspace-complete even for two cops, which
shows Part 3.
C
Finally, we show that the complexity drops if we only consider monotone
strategies in invisible graph searching games.
Lemma 7.49
Let
C
be a concise class of graph searching games.
1 The Searcher-monotone invisible graph searching game on C can be solved
in NP.
2 The Searcher-monotone k-searcher visible graph searching game on
C
can
be solved in NP.