Game Development Reference
InDepth Information
) as the problem to decide whether
k
searchers have a monotone winning strategy on
We define Mon Vis Search Width(
C
.
The corresponding problems Invis Search Width(
G
C
) and Mon Invis
Search Width(
C
) for the invisible variant are defined analogously.
To simplify presentation we will refer to this problem simply as 'the visible
graph searching game on
C
' and likewise for the invisible variant.
Games with a visible fugitive
We first consider the case of arbitrary, nonmonotone strategies.
Lemma 7.46
Let C be a class of graph searching games.
1 The visible graph searching game on
can be solved in exponential time.
2 The ksearcher visible graph searching game on
C
C
can be solved in polyno
mial time.
3 There are examples of visible graph searching games which are
Exptime

complete.
Proof
of the corresponding
reachability game as defined in Section 7.2.6 above. As
Given
G∈C
construct the game graph
G
is concise, this
graph is of exponential size and can be constructed in exponential time.
We can then use Lemma 7.10 to decide whether or not the Searcher has a
winning strategy.
If the complexity is restricted to some fixed
k
, then the game graph is of
polynomial size and therefore the game can be decided in polynomial time.
An example of a visible graph searching game which is complete for
Exptime has been given by Goldstein and Reingold [1995], see Theorem 7.12.
C
If we are only interested in the existence of monotone strategies, then we
can prove slightly better complexity bounds.
Lemma 7.47
Let C be a concise class of graph searching games.
1 The Searchermonotone visible graph searching game on
C
can be solved
in polynomial space.
2 The Searchermonotone ksearcher visible graph searching game on
C
can
be solved in polynomial time.
Proof
In a Searchermonotone strategy the Searcher can only make at most
polynomially many steps as he is never allowed to return to a vertex once
vacated. As
is concise, this means that a complete play can be kept in
polynomial space which immediately implies the result.
C
Search Nedrilad ::
Custom Search