Game Development Reference

In-Depth Information

initially there are no searchers on the board and the Fugitive can reside on

any position in
V
.

Let
X
i
⊆

V
be the current position of the searchers and
R
i
⊆

V
be the

current fugitive space. If
R
i
=

then the Searcher has won and the game is

over. Otherwise, the Searcher chooses
X
i
+1
⊆

∅

V
such that (
X
i
,X
i
+1
)

∈S

.

Afterwards,
R
i
+1
:=

(
X
i
,R
i
,X
i
+1
) and the play continues at (
X
i
+1
,R
i
+1
).

If the fugitive can escape forever, then he wins.

Formally, a play in

F

G

:= (
V,

S

,

F

,c
) is a finite or infinite sequence

P

:=

(
X
0
,R
0
)
,...
such that, for all
i
,(
X
i
,X
i
+1
)

∈S

and
R
i
+1
:=

F

(
X
i
,R
i
,X
i
+1
).

Furthermore, if

P

is infinite then
R
i

=

∅

, for all
i

≥

0, and if

P

:=

(
X
0
,R
0
)
,...,
(
X
k
,R
k
) is finite then
R
k
=

for all
i<k
. Hence,

the Searcher wins all finite plays and the Fugitive wins the infinite plays.

Note that as
R
0
:=
V
and
R
i
+1
:=

∅

and
R
i

=

∅

(
X
i
,R
i
,X
i
+1
), the entire play is

determined by the actions of the Searcher and we can therefore represent

any play
P
:= (
X
0
,R
0
)
,...
by the sequence
X
0
,X
1
, ...
of searcher positions.

Hence, invisible graph searching games are essentially one-player games of

perfect information. Alternatively, we could have defined invisible graph

searching games as a game between two players where the fugitive also

chooses a particular vertex
v
i
∈

F

R
i
at each round but this information is

not revealed to the searchers. This would yield a two-player game of partial

information. For most applications, however, it is easier to think of these

games as one-player games.

We now formally define the concept of strategies and winning strategies.

As we are dealing with a one-player game, we will only define strategies for

the Searcher.

Definition 7.2

A
strategy
for the Searcher in an invisible abstract graph

searching game

G

:= (
V,

S

,

F

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

×

Pow(
V
)

→

Pow(
V
) such that (
X, f
(
X, R
))

∈S

for all
X, R

⊆

V
.

A finite or infinite play

P

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

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

The function
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, R
), i.e., the searchers are on the

vertices in
X
and the Fugitive space is
R
, 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 in Section 7.2.6 that

Search Nedrilad ::

Custom Search