Game Development Reference
In-Depth 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 sub-trees 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