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
}

Custom Search