Game Development Reference

In-Depth Information

can never move back to a position they left previously, they can only take a

linear number of steps.

Almost all games considered in this chapter have the property that no

player is forced to move and therefore, if the searchers do not move, the

fugitive space does not decrease. An exception is the game of entanglement

studied by Berwanger and Gradel [2004] where the fugitive has to move at

every step and therefore it can be beneficial for the searchers not to move.

A similar lemma as before can often be shown for robber monotone

strategies as the robber space is non-increasing. However, this would require

the game to be such that there is a bound on the number of steps the cops

have to make to ensure that the robber space actually becomes smaller. In

almost all games such a bound can easily be found, but formalising this in

an abstract setting does not lead to any new insights.

7.2.6 Connection to reachability games

In this section we rephrase graph searching games as reachability games

and derive some consequences of this. A
reachability game
is a game played

on an arena

G

:= (
A, V
0
,E,v
0
) where (
A, E
) is a directed graph,
V
0
⊆

A

and
v
0
∈

V
0
. The game is played by two players,

Player 0 and Player 1, who push a token along edges of the digraph. Initially

the token is on the vertex
v
0
. In each round of the game, if the token is

on a vertex
v
i
∈

A
. We define
V
1
:=
A

\

V
0
then Player 0 can choose a successor
v
i
+1
of
v
i
,i.e.,

(
v
i
,v
i
+1
)

E
, and push the token along the edge to
v
i
+1
where the play

continues. If the token is on a vertex in
V
1
then Player 1 can choose the

successor. The winning condition is given by a set
X

∈

A
. Player 0 wins if

at some point the token is on a vertex in
X
or if the token is on a vertex in

V
1
which has no successors. If the token never reaches a vertex in
X
or if at

some point Player 0 cannot move anymore, then Player 1 wins. See [Gradel

et al., 2002, Chapter 2] for details of reachability games.

A positional strategy for Player
i
in a reachability game can be described

as a function
f
i
:
V
i
→ A
assigning to each vertex
v
where the player moves a

successor
f
(
v
)suchthat(
v, f
(
v
))
∈ E
.
f
i
is a winning strategy if the player

wins every play consistent with this strategy. For our purposes we need two

results on reachability games,
positional determinacy
and the fact that the

winning region for a player in a reachability game can be computed in linear

time.

⊆

Search Nedrilad ::

Custom Search