Game Development Reference

In-Depth Information

Mazoit and Nisse [2008]. We will demonstrate the various constructions in

this part by the following example.

Figure 7.3 Example graph
G
for monotonicity proofs

Recall the representation of winning strategies for the Cop player in terms

of strategy trees in Definition 7.4. In this tree, a node
t
corresponds to

a cop position
cops
(
t
) and an out-going edge
e
:= (
t, s
) corresponds to a

robber move to a vertex
search
(
e
):=
v
. Clearly, if the cops are on vertices

X
:=
cops
(
t
) and
u, v
are in the same component of
G \ X
, then it makes no

difference for the game whether the robber moves to
u
or
v
, because whatever

the cops do next, the robber can move to exactly the same positions. We

therefore do not need to have two separate sub-trees for
u
and
v
and can

combine vertices in the same component. Thus, we can rephrase strategy

trees for the visible cops and robber game as follows. To distinguish from

search trees defined below we deviate from the notation of Definition 7.4 and

use
robber
(
e
) instead of
search
(
e
).

Definition 7.14
Let
G
be an undirected graph. A
strategy tree
is a

rooted directed tree
T
whose nodes
t
are labelled by
cops
(
t
)
⊆ V
(
G
) and

whose edges
e ∈ E
(
T
) are labelled by
robber
(
e
)
⊆ V
(
G
) as follows.

1 If
r
is the root of
T
then for all components
C
of
G

\

cops
(
r
) there is a

successor
t
C
of
r
in
T
and
robber
(
r, t
C
):=
V
(
C
).

2 If
t
is a node with predecessor
s
and
C
:=
robber
((
s, t
)) then for each

component
C
of
G

\

cops
(
t
) contained in the same component of
G

\

cops
(
t
)) as
C
there is an edge
e
C
:= (
t, t
C
)

(
cops
(
s
)

∩

∈

E
(
T
)that

robber
(
e
C
):=
V
(
C
).

A strategy tree is
monotone
if for all (
s, t
)
,
(
t, t
)

∈

E
(
T
)
robber
(
s, t
)

⊇

robber
(
t, t
).

Towards proving monotonicity of the game it turns out to be simpler to

think of the cops and the robber as controlling edges of the graph rather

than vertices. We therefore further reformulate strategy trees into what we

will call
search trees
. Here, a component housing a robber, or a robber space

in general, will be represented by the set of edges contained in the component

Search Nedrilad ::

Custom Search