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

Search Nedrilad ::

Custom Search