A princess and monster game is a
pursuit–evasion
Pursuit–evasion (variants of which are referred to as cops and robbers and graph searching) 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 ...
game played by two players in a region.
Formal definition
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
Shmuel Gal (; born 1940) is a mathematician and professor of statistics at the University of Haifa in Israel.
He devised the Gal's accurate tables method for the computer evaluation of elementary functions. With Zvi Yehudai he developed in 1993 ...
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
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
. 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
Steve Alpern is a professor of Operational Research at the University of Warwick, where he recently moved after working for many years at the London School of Economics. His early work was mainly in the area of dynamical systems and ergodic the ...
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. Geupel]
The 'Princess and Monster' Game on an Interval.
/ref>
See also
*Search games
A search game is a two-person zero-sum game which takes place in a set called the search space. The searcher can choose any continuous trajectory subject to a maximal velocity constraint. It is always assumed that neither the searcher nor the hider ...
*List of games in game theory
Game theory studies strategic interaction between individuals in situations called games. Classes of these games have been given names. This is a list of the most commonly studied games
Explanation of features
Games can have several features ...
References
{{Game theory
Pursuit–evasion
Non-cooperative games