Game Development Reference
In-Depth Information
after an accident in a mine some workers are lost in the system of tunnels
constituting the mine and a search party is sent into the mine to find them.
The problem is to devise a strategy for the searchers which guarantees that
the lost workers are found but tries to minimise the number of searchers
that need to be sent into the mine. Graph-theoretically, this leads to the
following formulation in terms of a game played on a graph which is due to
Golovach [1989]. The game is played on a graph which models the system of
tunnels, where an edge corresponds to a tunnel and a vertex corresponds to
a crossing between two tunnels. The two players are the Fugitive and the
Searcher. The Fugitive, modelling the lost worker, hides in an edge of the
graph. The Searcher controls a number of searchers which occupy vertices of
the graph. The Searcher knows the graph, i.e., the layout of the tunnels, but
the current position of the fugitive is unknown to the Searcher. In the course
of the game the searchers search edges by moving along an edge from one
endpoint to another trying to find the fugitive.
This formulation of the game is known as edge searching . More popular
in current research on graph searching is a variant of the game called node
searching which we will describe now in more detail.
Node searching
In node searching, both the fugitive and the searchers occupy vertices of
the graph. Initially, the fugitive can reside on any vertex and there are no
searchers on the graph. In each round of the play, the Searcher can lift some
searchers up or place new searchers on vertices of the graph. This can happen
within one move, so in one step the searcher can lift some searchers up and
place them somewhere else. However, after the searchers are lifted from the
graph but before they are placed again the fugitive can move. He can move
to any vertex in the graph reachable from his current position by a path
of arbitrary length without going through a vertex occupied by a searcher
remaining on the board. In choosing his new position, the fugitive knows
where the searchers want to move. This is necessary to prevent 'lucky' moves
by the searchers where they accidentally land on a fugitive. The fugitive's
goal is to avoid capture by the searchers. In our example above, the fugitive
or lost miner would normally not try to avoid capture. But recall that we
want the search strategy to succeed independent of how the lost miner moves,
and this is modelled by the fugitive trying to escape. If at some point of the
game the searchers occupy the same vertex as the fugitive then they have
won. Otherwise, i.e., if the fugitive can escape forever, then he wins. The
fact that the fugitive tries to avoid capture by a number of searchers has
led to these kinds of games being known as Cops and Robber games in the