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.

Custom Search