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.

Search Nedrilad ::

Custom Search