Game Development Reference

In-Depth Information

Figure 7.2 A visible directed reachability game

admissibility function
F
is defined as
F
(
X, R, X
):=
{v ∈ V
: there is an

u ∈ R
such that
u
and
v
are in the same strongly connected component of

G \
(
X ∩ X
)
}
.

To demonstrate the games and the fundamental difference between games

on undirected and directed graphs, we give an example of a directed visible

reachability game.

Consider the directed graph depicted in Figure 7.3.5. An undirected edge

indicates a directed edge in both directions. The graph consists of two cliques

of three vertices each which we will call
C
L
:=

.

An edge connecting a clique to a specific vertex means that every vertex

of the clique is connected to this vertex. That is, every vertex of
C
l
has

a directed edge to 4 and 5 and every vertex of
C
R
has a directed edge to

every vertex in
C
L
and also an undirected edge (two directed edges in either

direction) to the vertices 4
,
5
,
6 in the middle.

On this graph, five cops have a winning strategies against the robber as

follows. As every vertex in
C
R
has an edge to every other vertex, the cops

must first occupy all vertices in
C
R
, which takes three cops. In addition they

put two cops on 4 and 5. Now the robber has a choice to either move to 6 or

to a vertex in the clique
C
L
.Ifhegoesto
C
L
we lift all cops from
C
R
and

place them on
C
L
capturing the robber, as the only escape route from
C
L
is

through the vertices 4 and 5 which are both blocked.

If on the other hand the robber decides to move to 6 then we lift the two

cops from 4 and 5 and place one of them on 6. Now the robber can move to

one of 4 or 5 but whatever he does we can then place the space cop on the

chosen vertex capturing the robber.

Note that this strategy is non-monotone as the robber can reach the

vertices 4 and 5 after they have already been occupied by a cop. Kreutzer

and Ordyniak [2008] show that there is no monotone strategy with five cops

on this graph, showing that the directed reachability game is non-monotone.

This example also demonstrates the crucial difference between games

{

1
,
2
,
3

}

and
C
R
:=

{

7
,
8
,
9

}

Search Nedrilad ::

Custom Search