Formal Definition
In his book ''Differential Games'' (1965), Rufus Isaacs (game theorist), 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. 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. 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 (discrete mathematics), graph. It can be demonstrated that for any finite graph an optimal Mixed strategy, 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). 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.L. GeupelSee also
*Search games *List of games in game theoryReferences