Game Development Reference
In-Depth Information
Graph Searching Games
Stephan Kreutzer
University of Oxford
This chapter provides an introduction to graph searching games, a form of
one- or two-player games on graphs that have been studied intensively in
algorithmic graph theory. The unifying idea of graph searching games is that
a number of searchers wants to find a fugitive on an arena defined by a graph
or hypergraph. Depending on the precise definition of moves allowed for the
searchers and the fugitive and on the type of graph the game is played on,
this yields a huge variety of graph searching games.
The objective of this chapter is to introduce and motivate the main concepts
studied in graph searching and to demonstrate some of the central ideas
developed in this area.
7.1 Introduction
Graph searching games are a form of two-player games where one player,
the Searcher or Cop , tries to catch a Fugitive or Robber . The study of graph
searching games dates back to the dawn of mankind: running after one
another or after an animal has been one of the earliest activities of mankind
and surely our hunter-gatherer ancestors thought about ways of optimising
their search strategies to maximise their success.
Depending on the type of games under consideration, more recent studies
of graph searching games can be traced back to the work of Pierre Bouger,
who studied the problem of a pirate ship pursuing a merchant vessel, or more
recently to a paper by Parsons [1978] which, according to Fomin and Thilikos
[2008], was inspired by a paper by Breisch in the Southwestern Cavers Journal
where a problem similar to the following problem was considered: suppose
Search Nedrilad ::

Custom Search