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

Chapter 5
Open Problems on Search Games
Robbert Fokkink, Leonhard Geupel, and Kensaku Kikuta
Abstract We discuss two classic search games: Isaacs' princess and monster game,
and Dresher's high-low guessing game. Despite the fact that these games were in-
troduced decades ago, there are still numerous open problems around them.
5.1 Introduction
Rufus Isaacs' princess and monster game, which was discussed in the first chapter
by Shmuel Gal, is a classic search game. One could argue that this game, and its
solution by Gal in 1979, started Search Games as an independent area of research.
Gal essentially showed that the princess has the upper hand. From time to time
she quickly moves to a new position, nullifying any progress that the monster has
made in his search, so the time of capture becomes an exponential random variable.
One could take the area that has been searched by the monster as a state variable.
Every time the princess moves, she resets the state variable to zero. In Chap. 16 ,Rob
Arculus analyzes the princess and monster game from this point of view, and applies
it to predator-prey models in biology. It seems plausible that even if the princess is
noisy and the monster is aware of the fact that she has just moved, it does not help
him find the princess any more quickly.