A princess and monster game is a pursuit–evasion game played by two players in a region.
In his book Differential Games (1965), Rufus Isaacs defined the game as:
This game remained a well-known open problem until it was solved by Shmuel Gal in the late 1970s.[1] [2] His optimal strategy for the princess is to move to a random location in the room and stay still for a time interval which is neither too short nor too long, before going to another (independent) random location and repeating the procedure.[2] [3] [4] The proposed optimal search strategy for the monster is based on subdividing the room into many narrow rectangles, picking a rectangle at random and searching it in some specific way, after some time picking another rectangle randomly and independently, and so on.
Princess and monster games can be played on a pre-selected graph. It can be demonstrated that for any finite graph an optimal mixed search strategy exists that results in a finite payoff. This game has been solved by Steve Alpern and independently by Mikhail Zelikin only for the very simple graph consisting of a single loop (a circle).[5] [6] The value of the game on the unit interval (a graph with two nodes with a link in-between) has been estimated approximatively.
The game appears simple but is quite complicated. The obvious search strategy of starting at a random end and "sweeping" the whole interval as fast as possible guarantees a 0.75 expected capture time, and is not optimal. By utilizing a more sophisticated mixed searcher and hider strategy, one can reduce the expected capture time by about 8.6%. This number would be quite close to the value of the game if someone was able to prove the optimality of the related strategy of the princess.[7] [8]