Game Development Reference
In-Depth Information
literature and we will at various places below resort to this terminology. In
particular, we will refer to the game described above as the Invisible Cops
and Robber Game . The name 'Cops and Robber Game', however, has also
been used for a very different type of games. We will describe the differences
in Section 7.3.1.
Optimal strategies
Obviously, by using as many searchers as there are vertices we can always
guarantee to catch the fugitive. The main challenge with any graph searching
game therefore is to devise an optimal search strategy. There are various
possible optimisation goals. One is to minimise the number of searchers used
in the strategy. Using as few searchers as possible is clearly desirable in many
scenarios, as deploying searchers may be risky for them, or it may simply be
costly to hire the searchers. Closely related to this is the question of whether
with a given bound on the number of searches the graph can be searched at
all.
Another very common goal is to minimise the time it takes to search the
graph or the number of steps taken in the search. In particular, often one
would want to avoid searching parts of the graph multiple times. Think for
instance of the application where the task is to clean a system of tunnels of
some pollution which is spreading through the tunnels. Hence, every tunnel,
once cleaned, must be protected from recontamination which can only be
done by sealing off any exit of the tunnel facing a contaminated tunnel. As
cleaning is likely to be expensive, we would usually want to avoid having to
clean a tunnel twice. Search strategies which avoid having to clean any edge
or vertex twice are called monotone .
On the other hand, sealing off a tunnel might be problematic or costly
and we would therefore aim at minimising the number of tunnels that have
to be sealed off simultaneously. In the edge searching game described above,
sealing off a tunnel corresponds to putting a searcher on a vertex incident
to the edge modelling the tunnel. Hence, minimising this means using as
few searchers as possible. Ideally, therefore, we aim at a search strategy that
is monotone and at the same time minimises the number of searchers used.
This leads to one of the most studied problems with graph searching games,
the monotonicity problem , the question of whether for a particular type of
game the minimal number of searchers needed to catch the fugitive is the
same as the minimal number of searchers needed for a monotone winning
strategy. Monotonicity of a type of game also has close connections to the
complexity of deciding whether k searchers can catch a fugitive on a given
graph - monotone strategies are usually of length linear in the size of the
Search Nedrilad ::




Custom Search