Game Development Reference

In-Depth Information

Searcher strategies but we will come back to formalisations of Fugitive

strategies later in Section 7.5.

Definition 7.3

A
strategy
for the Searcher in a visible abstract graph

searching game

G

:= (
V,

S

,

F

,c
) is a function
f
: Pow(
V
)

×

V

→

Pow(
V
)

such that for all
X

⊆

V
and
v

∈

V
,(
X, f
(
X, v
))

∈S

.

A finite or infinite play

P

:= (
X
0
,v
0
)
, ...
is
consistent with
f
if
X
i
+1
:=

f
(
X
i
,v
i
), for all
i
.

f
is a
winning strategy
if every play

P

which is consistent with
f
is

winning for the Searcher.

If in a play the current position is (
X, v
), i.e., the Searchers are on the

vertices in
X
and the Fugitive is on
v
, then a strategy for the Searcher tells

the Searcher what to do next, i.e., to move the Searchers to the new position

X
.

Note that implicitly we have defined our strategies to be
positional strategies

in the sense that the action taken by a player depends only on the current

position in the play but not on the history. We will see below that this

is without loss of generality as graph searching games are special cases of

reachability games for which such positional strategies su
ce. Furthermore,

the determinacy of reachability games implies that in any visible graph

searching game exactly one of the two players has a winning strategy (see

Corollary 7.11).

It is worth pointing out the fundamental difference between strategies for

the visible and invisible case. In the invisible case, a strategy for the Searcher

uniquely defines a play. Therefore, as we have done above, we can represent a

strategy for the Searcher in an invisible graph searching game as a sequence

X
0
,X
1
,...
or Searcher positions.

In the visible case, however, the next searcher position may depend on

the choice of the fugitive. Therefore, a Searcher strategy
f
in the visible

case can be described by a rooted directed tree
T
as follows. The nodes

t ∈ V
(
T
) are labelled by
cops
(
t
)
⊆ V
and correspond to Searcher positions.

The individual edges correspond to the possible robber moves. More formally,

the root
r ∈ V
(
T
)of
T
is labelled by
cops
(
r
):=
X
0
the initial cop position.

For every
v ∈ V \X
0
there is a successor
t
v
such that
cops
(
t
v
):=
f
(
cops
(
t
)
,v
).

The edge (
t, t
v
) is labelled by
v
. Now, for every
u

(
X
0
,v,cops
(
t
v
)) there

is a successor
t
u
of
t
v
labelled by
cops
(
t
u
):=
f
(
cops
(
t
v
)
,u
). Continuing in

this way we can build up a strategy tree which is finite if, and only if,
f
is a

winning strategy. More formally, we define a strategy tree as follows.

∈F

Definition 7.4

Let (
V,

S

,

F

,c
) be an abstract visible graph searching game.

Search Nedrilad ::

Custom Search