Game Development Reference

In-Depth Information

this is without loss of generality as graph searching games are special cases

of reachability games for which such positional strategies su
ce.

Example: The Invisible Cops and Robber Game

We have already seen how the Invisible Cops and Robber Game on a graph

G
described in the introduction can be formulated as an abstract Invisible

Cops and Robber Game (
V,

,c
) where
V
:=
V
(
G
) is the set of positions,

S
:= Pow(
V
)
×
Pow(
V
) says that the cops can move freely from one position

to another and
F
(
X, R, X
):=
{v ∈ V
: there is a path in
G\
(
X ∩X
) from

some
u ∈ R
to
v }
. This game was first described as
node searching
by

Kirousis and Papadimitriou [1986]. Here the searchers try to systematically

search the vertices of the graph in a way that the space available to the

fugitive shrinks until it becomes empty.

S

,

F

9

7

8

1

3

4

6

2

5

Figure 7.1 Example for an Invisible Cops and Robber Game

To give an example, consider the graph depicted in Figure 7.1. We will

describe a winning strategy for four cops in the Invisible Cops and Robber

Game. The first row contains the cop positions and the second row the

corresponding robber space.

X
i
:

{

1
,
2
,
3

}

{

3
,
4

}

{

3
,
4
,
5
,
6

}{

3
,
4
,
7

}{

4
,
7
,
8

}{

7
,
8
,
9

}

R
i
:

}
{

7
,
8
,
9

}{

8
,
9

}

{

9

}

∅

{

4
,
5
,
6
,
7
,
8
,
9

}{

5
,
6
,
7
,
8
,
9

Note that we have used all four cops only once, at position
{
3
,
4
,
5
,
6
}
.Itis

not too di
cult to see that we cannot win with three cops. For, consider the

edge 3
,
4 and assume that cops are placed on it. The graph
G\{
3
,
4
}
contains

three components,

. Each of these requires at least

three cops for clearing but as soon as one of them is cleared the vertices of

the edge

{

1
,
2

}

,

{

5
,
6

}

and

{

7
,
8
,
9

}

adjacent to a vertex in the component must be guarded until

at least a second component of
G

{

3
,
4

}

\{

3
,
4

}

is cleared. For instance, if we first

clear the triangle

{

1
,
2
,
3

}

then the vertex 3 needs to be guarded until 4 and

Search Nedrilad ::

Custom Search