Game Development Reference
) as the problem to decide whether
k searchers have a monotone winning strategy on
We define Mon Vis Search Width(
The corresponding problems Invis Search Width(
) and Mon Invis
) 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, non-monotone strategies.
Let C be a class of graph searching games.
1 The visible graph searching game on
can be solved in exponential time.
2 The k-searcher visible graph searching game on
can be solved in polyno-
3 There are examples of visible graph searching games which are Exptime -
of the corresponding
reachability game as defined in Section 7.2.6 above. As
construct the game graph
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
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 , see Theorem 7.12.
If we are only interested in the existence of monotone strategies, then we
can prove slightly better complexity bounds.
Let C be a concise class of graph searching games.
1 The Searcher-monotone visible graph searching game on
can be solved
in polynomial space.
2 The Searcher-monotone k-searcher visible graph searching game on
be solved in polynomial time.
Proof In a Searcher-monotone strategy the Searcher can only make at most
polynomially many steps as he is never allowed to return to a vertex once
is concise, this means that a complete play can be kept in
polynomial space which immediately implies the result.