Game Development Reference

In-Depth Information

7 are clear but then there are not enough cops left to clear the rest of the

graph.

To formally prove that we cannot search the graph with only three cops we

will exhibit structural properties of graphs, called
blockages
, which guarantee

the existence of a winning strategy for the robber. This leads to the concept

of
obstructions
and corresponding duality theorems which we will study in

more detail in Section 7.5.

7.2.3 Visible abstract graph searching games

In this section we describe a variant of graph searching games where the

fugitive is visible to the searchers. This fundamentally changes the nature of

the game as now the searchers can adapt their strategy to the move of the

fugitive. Such graph searching games are now truly two-player games which

necessitates some changes to the concepts of strategies.

In particular, it no longer makes sense to represent the position of the

fugitive as a fugitive space. Instead we will have to consider individual

positions of the fugitive.

Given an abstract game
G
:= (
V,S,F,c
), the rules of the
visible abstract

graph searching game on
G

are defined as follows. Initially, the board is

empty.
1
In the first round the Searcher first chooses a set
X
0
⊆

V
and then

the Fugitive chooses a vertex
v
0
∈

V
.

Let
X
i
⊆ V
and
v
i
∈ V
be the current positions of the searchers and the

Fugitive respectively. If
v
i
∈ X
i
then the Searcher has won and the game is

over. Otherwise, the Searcher chooses
X
i
+1
⊆ V
such that (
X
i
,X
i
+1
)
∈S
.

Afterwards, the Fugitive can choose any vertex
v
i
+1
∈F

(
X
i
,

{

v
i
}

,X
i
+1
). If

there is none or if

X
i
+1
, then again the Searcher wins.

Otherwise, the play continues at (
X
i
+1
,v
i
+1
). If the Fugitive can escape

forever, then he wins.

Formally, a
play
in
G
is a finite or infinite sequence
P
:= (
X
0
,v
0
)
,...
such

that (
X
i
,X
i
+1
)
∈S
and
v
i
+1
∈F
(
X
i
,{v
i
},X
i
+1
), for all
i ≥
0. Furthermore,

if

F

(
X
i
,

{

v
i
}

,X
i
+1
)

⊆

P

is infinite then
v
i
∈

X
i
, for all
i

≥

0, and if

P

:= (
X
0
,v
0
)
,...,
(
X
k
,v
k
)

is finite then
v
k
∈

X
i
for all
i<k
. Hence, the Searcher wins all

finite plays and the Fugitive wins the infinite plays.

We now define strategies and winning strategies for the Searcher. In

contrast to the invisible case, there is now also a meaningful concept of

strategies for the Fugitive. However, here we are primarily interested in

X
k
and
v
i
∈

1
There are some variants of games where the robber chooses his position first, but this is not

relevant for our presentation.

Search Nedrilad ::

Custom Search