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

segment to the nodes, and the problem is to do this in the most efficient way. The
simplest example of a disconnected search space is a unit interval, with the starting
point O in the middle, plus a point A above O (Fig. 1.3 ).

Fig. 1.3 A simple mixed space

It seems natural to connect A to O and search it as a tree. However, a better way
is to construct the triangle with A as a vertex and search it as an Eulerian network,
i.e., starting from O and encircling it clockwise or anti-clockwise, each with prob-
ability 1 2. Using the triangle inequality it is easy to demonstrate the superiority

of the latter strategy. This strategy, based on the triangle, is probably optimal but
the problem is more complicated than it seems at first sight. We should take into
consideration some other mixed strategies based on trajectories that visit either A
first, or part of the interval then A and finally the remaining parts of the interval. The
searching of disconnected spaces seems to be an interesting and challenging topic
for further research. For example, in some cases a possible solution is the minimal
value weakly Eulerian graph that spans the line segment plus the set G

/

. It would be

interesting to find some sort of characterization of these cases.

1.2 Search Games for a Mobile Hider

Search games with a mobile hider are more difficult to solve than those with an
immobile hider. These games are also known as princess and monster games.

1.2.1 Isaacs' Princess and Monster Game

The princess and monster was a well known open problem during the 1960s and
1970s. It was introduced by Rufus Isaacs in his classical topic Differential Games
[ 30 ] as follows:

The monster P searches for the princess E , the time required being the pay-
off. They are both in a totally dark room Q (of any shape) but they are each
cognizant of its boundary (possibly through small light admitting perforations
high in the walls). Capture means that the distance PE

≤ r , a quantity small in

.

comparison with the dimension of Q The monster, supposed highly intelligent,

moves at a known speed. We permit the princess full freedom of locomotion.