Game Development Reference
In-Depth Information
7.3.2 Node and edge searching with an invisible fugitive
We have already formally described the rules of the (non turn-based) Invisible
Cops and Robber Game in Section 7.2.2. This game has been introduced as
node-searching by Kirousis and Papadimitriou [1986] who showed that it is
essentially equivalent to pebbling games used to analyse the complexity of
sequential computation.
Pebble games are played on an acyclic directed graph. In each step of
a play we can remove a pebble from a vertex or place a new pebble on a
vertex provided that all its predecessors carry pebbles. The motivation for
pebble games comes from the analysis of register allocation for sequential
computation, for instance for computing arithmetical expressions. The ver-
tices of a directed acyclic graph corresponds to sub-terms that have to be
computed. Hence, to compute the value of a term represented by a node t
we first need to compute the value of its immediate sub-terms represented by
the predecessors of t . A pebble on a node means that the value of this node
is currently contained in a register of the processor. To compute a value of
a term in a register the values of its sub-terms must also be contained in
registers and this motivates the rule that a pebble can only be placed if its
predecessors have been pebbled.
Initially the graph is pebble free and the play stops once all vertices have
been pebbled at least once. The minimal number of pebbles needed for a
directed graph representing an expression t is the minimal number of registers
that have to be used for computing t . Kirousis and Papadimitriou [1986]
show that pebble games can be reformulated as graph searching games with
an invisible fugitive and therefore register analysis as described above can be
done within the framework of graph searching games.
In the same paper they show that edge searching and node searching are
closely related. Recall from the introduction that the edge searching game
is a game where the robber resides on edges of the graph. The searchers
occupy vertices. In each move, the searchers can clear an edge by sliding
along it, i.e., if a searcher occupies an endpoint of an edge then he can move
to the other endpoint and thereby clears the edge. As shown by Kirousis and
Papadimitriou [1986], if G is a graph and G is the graph obtained from G by
sub-dividing each edge twice, then the minimal number of cops required to
catch the fugitive in the node searching game on G , called the node search
number of G , is one more than the minimal number of searchers required
in the edge searching game on G , called the edge search number of G .
Conversely, if G is a graph and G is obtained from G by replacing each edge