Game Development Reference
InDepth Information
An
abstract strategy tree
is a rooted directed tree
T
whose nodes
t
are
labelled by
cops
(
t
)
⊆
V
and whose edges
e
are labelled by
search
(
e
)
∈
V
as
follows.
1
search
(
e
)
∈
cops
(
s
) for all edges
e
:= (
s, t
)
∈
E
(
T
).
2 If
r
is the root of
T
then for all
v
∈
V
\
cops
(
r
) there is a successor
t
v
of
r
in
T
and
search
(
r, t
v
):=
v
.
3 If
t
is a node with predecessor
s
and
v
:=
search
((
s, t
)) then for each
u
∈
F
(
cops
(
s
)
,v,cops
(
t
)) there is a successor
t
u
of
t
in
T
so that
search
(
t, v
u
):=
u
.
Often this tree can be further simplified. Suppose for instance that there
is an edge (
s, t
)
∈
E
(
T
) and that there are vertices
u
1
,u
2
∈F
(
cops
(
s
)
,
v, cops
(
t
))
\
cops
(
t
) such that
F
(
cops
(
t
)
,u
1
,X
)=
F
(
cops
(
t
)
,u
2
,X
), for all
X
V
(
G
). In this case the two vertices
u
1
and
u
2
are equivalent in the
sense that it makes no sense for the Searcher to play differently depending
on whether the fugitive moves to
u
1
or
u
2
and likewise for the robber. We
therefore do not need to have separate subtrees corresponding to the two
different moves.
⊆
Example: The Visible Cops and Robber Game
Let us illustrate the definition of abstract graph searching games. In Seymour
and Thomas [1993], a graph searching game called the
Cops and Robber
Game
is considered, where searchers and the fugitive reside on vertices of a
graph
G
=(
V,E
). From a position (
X, v
), where
X
⊆
V
are the positions of
the searchers and
v
V
is the current fugitive position, the game proceeds
as follows. The searchers can move freely from position
X ⊆ V
to any other
position
X
⊆ V
. But they have to announce this move publicly and while
the searchers move from
X
to
X
the fugitive can choose his new position
from all vertices
v
such that there is a path in
G
from
v
to
v
not containing
a vertex from
X ∩ X
.
Formulated as an abstract graph searching game,
∈
G
:= (
V,
S
,
F
,c
)we
let
V
:=
V
(
G
) and
Pow(
V
), indicating that there is no
restriction on the moves of the searchers. The function
S
:= Pow(
V
)
×
F
is then defined as
,X
):=
X
) from
v
to
u
F
(
X,
{
v
}
{
u
∈
V
: there is a path in
G
\
(
X
∩
}
.
The complexity function
c
is defined as
c
(
X
):=
.
To illustrate the game we will show a winning strategy for three cops
in the visible Cops and Robber game played on the graph
G
depicted in
Figure 7.1. Initially the cops go on the vertices

X

{
3
,
4
}
. Now the robber has
a choice to go in one of the three components of
G
\{
3
,
4
}
. If he chooses
Search Nedrilad ::
Custom Search