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