Princess and monster game
Encyclopedia
In game theory
, the princess and monster game is a pursuit-evasion
game played by two players in a region. The game was devised by Rufus Isaacs
and published in his book Differential Games (1965) as follows. "The monster searches for the princess, the time required being the payoff. They are both in a totally dark room (of any shape), but they are each cognizant of its boundary. Capture means that the distance between the princess and the monster is within the capture radius, which is assumed to be small in comparison with the dimension of the room. The monster, supposed highly intelligent, moves at a known speed. We permit the princess full freedom of locomotion."
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 especially interesting. Go to a random location in the room. Stay still for a time interval which is not too short but not too long, go to another (independent) random location and repeat the procedure. His proposed optimal search strategy 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, etc. The exact details of the search and evasion strategies are given in the references.
Princess and monster games can be played on a pre-selected graph
. (A possible simple graph is the circle, suggested by Isaacs as a stepping stone for the game in the region.) 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 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. This game looks simple but is quite complicated. Surprisingly, the 'obvious' search strategy of starting at one end (chosen at random) and 'sweeping' as fast as possible the whole interval is not optimal. This strategy guarantees 0.75 expected capture time. However, by utilising a more sophisticated mixed searcher and hider strategy, one can reduce the expected capture time by about 8.6%. Actually, this number would be quite close to the value of the game if someone was able to proof the optimality of the related strategy of the Princess.
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, the princess and monster game is a pursuit-evasion
Pursuit-evasion
Pursuit-evasion is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically...
game played by two players in a region. The game was devised by Rufus Isaacs
Rufus Isaacs (game theorist)
Rufus Philip Isaacs was a game theorist especially prominent in the 1950s and 1960s with his work on differential games.-Biography:...
and published in his book Differential Games (1965) as follows. "The monster searches for the princess, the time required being the payoff. They are both in a totally dark room (of any shape), but they are each cognizant of its boundary. Capture means that the distance between the princess and the monster is within the capture radius, which is assumed to be small in comparison with the dimension of the room. The monster, supposed highly intelligent, moves at a known speed. We permit the princess full freedom of locomotion."
This game remained a well known open problem until it was solved by Shmuel Gal
Shmuel Gal
Shmuel Gal is a professor of statistics at the University of Haifa in Israel.Gal received a Ph.D. in mathematics from the Hebrew University of Jerusalem....
in the late 1970s. His optimal strategy for the princess is especially interesting. Go to a random location in the room. Stay still for a time interval which is not too short but not too long, go to another (independent) random location and repeat the procedure. His proposed optimal search strategy 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, etc. The exact details of the search and evasion strategies are given in the references.
Princess and monster games can be played on a pre-selected graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
. (A possible simple graph is the circle, suggested by Isaacs as a stepping stone for the game in the region.) 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 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. This game looks simple but is quite complicated. Surprisingly, the 'obvious' search strategy of starting at one end (chosen at random) and 'sweeping' as fast as possible the whole interval is not optimal. This strategy guarantees 0.75 expected capture time. However, by utilising a more sophisticated mixed searcher and hider strategy, one can reduce the expected capture time by about 8.6%. Actually, this number would be quite close to the value of the game if someone was able to proof the optimality of the related strategy of the Princess.