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