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