Game Development Reference
In-Depth Information
this section we will introduce some of the main variants of the game and
attempt a classification of graph searching games.
Most variations do not fundamentally change the nature of the game. The
notable exception is between games with a visible fugitive and those where
the fugitive is invisible. Essentially, the game with a visible fugitive is a two-
player game of perfect information whereas games with an invisible fugitive
are more accurately described as one-player games on an (exponentially)
enlarged game graph or as two-player games of imperfect information. This
difference fundamentally changes the notion of strategies and we therefore
introduce the two types of games separately.
7.2.1 Abstract graph searching games
We find it useful to present graph searching games in their most abstract
form and then explain how some of the variants studied in the literature can
be derived from these abstract games. This will allow us to introduce abstract
notions of strategies which then apply to all graph searching games. We will
also derive general complexity results for variants of graph searching games.
Similar abstract definitions of graph searching games have very recently
be given by Amini et al. [2009], Adler [2009] and Lyaudet et al. [2009] for
proving very general monotonicity results. Our presentation here only serves
the purpose to present the games considered in this paper concisely and
in a uniform way and we therefore choose a presentation of abstract graph
searching games which is the most convenient for our purpose.
Definition 7.1
An abstract graph searching game is a tuple
G
:=
( V,
S
,
F
,c ) where
• V is a set
•S⊆ Pow( V ) × Pow( V ) is the Searcher admissibility relation , and
•F
: Pow( V ) 3
Pow( V ) is the Fugitive admissibility function , and
c : Pow( V )
N
is the complexity function .
In the following we will always assume that for every X
Pow( V ) there is
an X
Pow( V ) such that ( X, X )
. This is not essential but will avoid
certain notational complications in the definition of strategies below as they
otherwise would have to be defined as partial functions.
∈S
To give a first example, the Invisible Cops and Robber Game on a graph
G introduced in the introduction can be rephrased as an abstract graph
searching game
G
:= ( V,
S
,
F
,c ) as follows.