Search Games: A Review - Search Theory: A Game Theoretic Perspective - page 7

1.1.4 Searching an Unknown Graph

Finding a hider in an unknown graph is equivalent to finding the exit of a maze.
Assume that you find yourself in a maze. What is the best way to exit it? This has
been a challenging problem since ancient times but the solution for it has been pub-
lished only in 1882 [ 39 ] by an algorithm of Tremaux. In 1895 Tarry [ 42 ] described
an algorithm which is now widely used in Computer Science as depth first search
(see Even [ 20 ]). This algorithm is based on numbering the passages out of every
node and using each passage by the order of this numbering, so that each passage is
not traversed more than once. It guarantees 2

search time which is the best possible
for a deterministic strategy. However, using random numbering of the passages out
of every node enables the searcher to exit the maze in expected time

μ

,asshown
in [ 27 ]. This is the best possible expected time which can be guaranteed for any
unknown graph.

μ

1.1.5 Searching a Two-Dimensional Region

Searching an immobile hider in a two dimensional region with area is equivalent

to searching an Eulerian graph. An optimal strategy for the searcher is to find a
minimal length closed curve that covers the entire region. Then flip an unbiased
coin and traverse either clockwise or anti-clockwise according to the toss-up result.
Since the searcher discovers a strip of width 2 r it follows that the length of a minimal
covering curve for the region is

μ

2 r . By encircling this curve equiprobably in
each direction the searcher can assure about

∼ μ /

4 r expected search time. Since the
rate of discovery of new points is about 2 r for each time unit, it follows that the area
discovered by time t is at most 2 rt . Thus, if the hider uses the natural strategy of
a uniform hiding distribution, then the probability of capture after time t is at least
1

μ /

2 rt

Since the expected search time is the integral of that probability it follows
that the hider can keep the expected search time above

−

μ .

μ / 4 r . Thus, v ∼ μ / 4 r as

expected. See [ 24 ] for more details.

1.1.6 Searching a Mixed Space

The case of a hider that hides in a node has been considered above. The search
space then is disconnected, consisting of a finite set of points, that are connected by
a set of paths. Suppose that the nodes are in the plane and that the paths are not yet
given. The searcher can choose the paths. This is a type of search game that has not
yet been studied and which can easily be generalized. By a mixed space is meant a
disconnected subset of Euclidean space. An example of such a mixed space is a set
of discrete points plus a region. For instance, houses and a grove. Each house can be
modeled as a point or as a small rectangle. Another example is a line segment plus
aset G of discrete nodes. To search the space, the searcher must connect the line