Game Development Reference
In-Depth Information
7.3 Variants of graph searching games
In this section we present some of the main variants of games studied in the
literature.
7.3.1 A different Cops and Robber game
Nowakowski and Winkler [1983] study a graph searching game, also called a
Cops and Robber game , where the two players take turns and both players
are restricted to move along an edge. More formally, starting from a position
( X, r ), first the Searcher moves and can choose a new position X obtained
from X by moving some searchers to neighbours of their current position.
Once the searchers have moved the fugitive can then choose a neighbour of
his current position, provided he has not already been caught. See Alspach
[2006] for a survey of this type of game.
In our framework of graph searching games, this game, played on a graph
G , can be formalised as G := ( V,S,F,c ) where
V := V ( G ).
A pair ( X, X )isin
X (these are the searchers
that move) and a set Y which contains for each v ∈ Y a successor v of v ,
i.e., a vertex with ( v, v ) ∈ E ( G ), and X ⊆ Y ∪ X \ Y .
S
if there is a subset Y
For a triple ( X, v, X ) we define
( X, v, X ) to be empty if v
X and
F
X and ( v, u )
otherwise the set of vertices u s.t. u
E ( G ).
Finally, c ( X ):= |X| for all X ⊆ V .
We will refer to this type of game as turn-based . Goldstein and Reingold
[1995] study turn-based Cops and Robber games on directed graphs and
establish a range of complexity results for variations of this game ranging from
Logspace-completeness to Exptime-completeness. Among other results
they show the following theorem.
Theorem 7.12 (Goldstein and Reingold [1995]) The turn-based Cops and
Robber game on a strongly connected digraph is Exptime -complete.
The study of this type of game forms a rich and somewhat independent
branch of graph searching games. To keep the presentation concise, we
will mostly be focusing on games where the two players (essentially) move
simultaneously and are not restricted to moves of distance one. See Alspach
[2006] and Fomin and Thilikos [2008] and references therein for a guide to
the rich literature on turn-based games.