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