Game Development Reference
In-Depth Information
Figure 7.5 Search tree for the strategy tree in Figure 7.4
free of the robber. Everything else is handed over to the robber and will be
searched later. However, the corresponding move from guard ( s )to guard ( t )
may not be possible in the cops and robber game in the sense that if the cops
were to make this move the robber might have the chance to run to vertices
inside clear ( t ). Intuitively, the move from guard ( s )to guard ( t ) corresponds
to a retreat move , where we allow the cops to retreat from a current position
to a new position inside their cleared area without allowing the robber to
change position during this move. See Ordyniak [2009] for a description
of search trees as strategy trees for the cops and robber game with retreat .
However, such a retreat move is not possible in the Cops and Robber game
and therefore not every search tree corresponds to a strategy tree. However,
if the search tree is monotone then it does not contain any retreat moves
and therefore monotone search trees have corresponding strategy trees.
The following lemma now follows immediately.
Lemma 7.18 If there is a strategy tree for k cops on a graph G then there
is a search tree of width k on G. Conversely, if there is a monotone search
tree on a graph G then there exists a monotone strategy tree of the same
width.
Essentially, our monotonicity proof for the cops and robber game now
 
Search Nedrilad ::




Custom Search