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.

Search Nedrilad ::

Custom Search