Game Development Reference
In-Depth Information
a vertex in
. As the cop 3
remains on the board the robber cannot escape and is trapped. Analogously,
if the robber chooses a vertex in
{
1 , 2
}
then the next cop move is to play
{
3 , 1 , 2
}
{
5 , 6
}
then the cops go to
{
4 , 5 , 6
}
. Finally,
suppose the robber chooses a vertex in
. Now the cops have to be a
little more careful. If they were to lift up a cop on the board, say the cop
on vertex 3 to place it on 7, then the robber could escape through a path
from his current vertex over the vertex 3 to the component
{
7 , 8 , 9
}
.Sothe
cop on 3 has to remain on the board and the same for 4. To continue with
the winning strategy for the cops we place the third cop on the vertex 7.
Now the robber can only move to one of 8 , 9. We can now lift the cop from 3
and place it on 8, as the cops remaining on 7 and 4 block all exits from the
component containing the robber. Putting the cop on 7 leaves only vertex 9
for the robber and in the next move he will be caught by moving the cop
from 4 to 9.
Recall that in the invisible graph searching game we needed 4 cops to
catch the invisible robber whereas here, knowing the robber position, allows
us to save one cop. This example also shows that strategies for the cops are
trees rather than just simple sequences of cop positions.
{
1 , 2 , 3
}
7.2.4 Complexity of strategies
We now define the complexity of a strategy for the Searcher.
Definition 7.5
Let
P
:= ( X 0 ,R 0 ) ,... , where R i :=
{
v i }
in case of visible
games, be a finite or infinite play in a graph searching game
G
:= ( V,
S
,
F
,c ).
The complexity of
P
is defined as
comp (
P
):=max
{
c ( X i ):( X i ,R i )
∈P}
.
The complexity of a winning strategy f for the Searcher is
comp ( f ):=max
{
comp (
P
):
P
is an f -consistent play
}
.
As outlined in the introduction, the computational problem associated
with a graph searching game is to determine a winning strategy for the
Searcher that uses as few searchers as possible, i.e., is of lowest complexity.
Definition 7.6
Let
G
:= ( V,
S
,
F
,c ) be an abstract graph searching game.
The search-width of
G
is the minimal complexity of all winning strategies
for the Searcher, or
if the Searcher does not have any winning strategies.
A natural computational problem, therefore, is to compute the search-width
of a graph searching game. More often we are interested in the corresponding