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