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

Search Nedrilad ::

Custom Search