Game Development Reference
In-Depth 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, non-monotone 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 k-searcher 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 Searcher-monotone visible graph searching game on
C
can be solved
in polynomial space.
2 The Searcher-monotone k-searcher visible graph searching game on
C
can
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
vacated. As
is concise, this means that a complete play can be kept in
polynomial space which immediately implies the result.
C