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.

Search Nedrilad ::

Custom Search