Game Development Reference

In-Depth Information

Lemma 7.10

1 Reachability games are positionally determined, i.e., in every reachability

game exactly one of the players has a winning strategy and this can be

chosen to be positional.

2 There is a linear time algorithm which, given a reachability game

(
A, V
0
,E,v
0
)
and a winning condition X ⊆ A, decides whether Player

0
has a winning strategy in the game.

Let
G
:= (
V,S,F,c
) be a visible graph searching game. We associate with

G
a game arena G := (
A, V
0
,E,v
0
) where

A
:=

Pow(
V
)

×

V

∪

(
X, v, X
)

V
:(
X, X
)

{

∈

Pow(
V
)

×

Pow(
V
)

×

∈S}

.

Nodes (
X, v
)
∈
Pow(
V
)
×V
correspond to positions in the graph searching

games. A node (
X, v, X
)
∈
Pow(
V
)
× V ×
Pow(
V
) will correspond to the

intermediate position where the searchers have announced that they move

from
X
to
X
and the fugitive can choose his new position
v
∈F

,X
).

There is an edge from (
X, v
)to(
X, v, X
) for all
X
such that (
X, X
)

(
X,

{

v

}

∈

. Furthermore, there is an edge from (
X, v, X
)to(
X
,v
) for all
v
∈

F

S

,X
).

All nodes of the form (
X, v
) belong to Player 0 and nodes (
X, v, X
) belong

to Player 1. Finally, the winning condition contains all nodes (
X, v
) for which

v ∈ X
.

Now, it is easily seen that from any position (
X, v
) in the graph searching

game, the Searcher has a winning strategy if, and only if, Player 0 has a

winning strategy in

(
X,

{

v

}

G

from the node (
X, v
). Lemma 7.10 implies the following

corollary.

Corollary 7.11
For every fixed k, in every visible graph searching game

exactly one of the two players has a winning strategy in the k-searcher game.

Similarly, for the invisible graph searching game, we define a game arena

G

as follows. The vertices are pairs (
X, R
) where
X, R

⊆

V
and there is an

edge between (
X, R
) and (
X
,R
)if(
X, X
)

(
X, R, X
). All

nodes belong to Player 0. Again it is easily seen that Player 0 has a winning

strategy from node (
X, R
)in

and
R
:=

∈S

F

if, and only if, the Searcher has a winning

strategy in the invisible graph searching game starting from (
X, R
).

G

Search Nedrilad ::

Custom Search