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

The game is now commonly called Ulam's game or the Rényi-Ulam game, after
Stanislaw Ulam popularized a similar problem in his autobiography [ 16 ]. Since the
hider may give faulty feedback, the Rényi-Ulam game presents a more versatile
problem than Dresher's guessing game, and the literature on the topic is extensive.

5.2 The Princess and Monster Game on Graphs

. The max-
imum speed of the monster M is 1 and the maximum speed of the princess P is
unbounded. If M moves at maximum speed, then we say that he runs. The positions
of the players m

We consider the princess and monster game on the interval [ − 1 , 1 ]

is Lipschitz of con-
stant 1. The time that the monster finds the princess is min t 0 = {

( t ) and p ( t ) vary continuously with t and m ( t )

,
and the payoff to the princess is t 0 in this case. As a first attempt to solve this game,
the following strategy is an obvious candidate solution: the monster flips a coin and
start at either end of the interval equiprobably, and runs to the opposite end. We
say that an M that moves like that is a sweeper. Against this sweeper strategy, it is
optimal for the princess to initially hide in 0, wait until time 1

t : m ( t )= p ( t ) }

− ε

, flip a coin, and
move to one of the end points equiprobably. The expected time that M finds P is 2
in this case. This is not the solution of the game. P 's strategy is optimal againt M 's,
but M 's strategy is not optimal against P 's. In [ 2 ] it has been conjectured that an
optimal mixed strategy for M can be based upon the following pure strategies:

M 1 Choose an arbitrary initial point and an arbitrary direction. M runs in that di-
rection until the end, and then back until the other end.

M

2 Again choose an arbitrary initial point and an arbitrary direction. But now M
runs until he meets the sweeper coming from that direction, then turns around
and runs until the end, joining the sweeper, and then back until the other end.

If the strategy space of the monster is restricted to these pure strategies, then the
optimal mixed strategy of the princess is based upon the following pure strategies:

P Choose an infinitesimal 0. Either hide at an end-point and remaind immo-

bile, or choose an arbitrary initial point in

ε >

[ − 1 + ε ,− ε ] ∪ [ ε , 1 − ε ] and remain