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

Search Nedrilad ::

Custom Search