Open Problems on Search Games - Search Theory: A Game Theoretic Perspective - page 72

The original problem posed by Isaacs, was to solve the game for a relatively small
radius of detection. If the radius of detection is larger, and has an order of magnitude
that is comparable to the size of the search space, then it is more convenient to
model the game on a graph. The searcher then finds the hider once they are in the
same place. This version of the princess and monster game was also proposed by
Isaacs [ 11 , p 349-350]. The game on a graph has only been solved for the circle (see
Sect. 1.2 of this topic), but it remains open for all other graphs. Even if the graph
is an interval, although there is a conjectured solution in this case, which we will
discuss below.
The princess and monster game is related to the game between the lion and a
Christian, which was invented by Richard Rado: a lion and a Christian in a closed
circular arena have equal maximum speeds. Can the lion catch the Christian in finite
time? Surprisingly, the answer turns out to be NO [ 3 , p 46], provided that the players
are both represented by points, and the radius of detection is zero. So the lion only
catches the Christian if the two points coincide and not any earlier, which in real life
would require some divine intervention. This game was popularized by Littlewood
in his Miscellany [ 14 ], and he added the following problem: can two lions catch a
man in a bounded area with rectifiable lakes? According to Béla Bollobás [ 3 ], this
problem remains unsolved. If there are two lions, then we have a multi-agent game
that is similar to the game of cops and robbers [ 4 ], which has recently received
a lot of attention. These are pursuit-evasion games: the players have visual contact.
Contrary to search games, in which the players are blind. It is the difference between
catching and finding.
Gal's 1980 topic [ 9 ] is the first monograph on Search Games. Selmer Johnson's
1964 paper [ 13 ], which is aptly called 'A Search Game', may be the first serious
publication on the topic, predating Isaacs' classic on Differential Games which is
generally recognized as the work that initiated the field (see Gal's review in Chap. 1 ).
Johnson writes:
The following game was first suggested to the author by Melvin Dresher several
years ago. Blue chooses h , an integer from the set 1 to n (a region to hide). Red
guesses an integer from 1 to n , is told whether he is too high or too low, and
repeats until he guesses h . The payoff to Blue is one unit for each guess.
This game had appeared earlier as an example in Dresher's monograph on Game
Theory [ 5 ]. In that same year Rényi proposed to study a similar game. It is inspired
by the parlor game 20 Questions, so it is a win-lose game with an upper bound
on the number of questions. The original text is in Hungarian, and the following
translation is taken from [ 15 ]:
A thinks of something and B must guess it. B can ask questions which can be
answered by 'yes' or 'no' and he must find out of what A had thought of [...] it
is better to suppose that a given percentage of the answers are wrong (because
A misunderstands the question or does not know certain facts).