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