- Princess and monster game
The princess and monster game is a pursuit-evasion game played by two players on a graph. The game was devised by Rufus Isaacs and published in his book "Differential games". [R. Isaacs, Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization, John Wiley & Sons, New York (1965).]
Princess and monster games are played on a pre-selected graph. A searcher (the monster) moves along a pre-chosen path on the graph at a speed not exceeding unit speed. The hider (the princess), not aware of the searcher's selected strategy and not receiving any information about the position of the searcher, is allowed to move at any desirable speed along any continuous path. The payoff for the hider in this
zero-sum game is the capture time. It can be demonstrated that for any finite graph an optimal mixed search strategy exists that results in a finite payoff.Actually, in the proposed game by Isaacs the monster searches for the princess in a totally dark room with a small radius of capture (the game on the circle was a suggested stepping stone). This problem remained open until it was solved by Shmuel Gal in the late 1970's. [S. Gal, SEARCH GAMES, Academic Press, New York (1980).] [S. Gal, Search games with mobile and immobile hider, SIAM J. Control Optim, 17, 99-122 (1979).] The presented 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 (the exact formula is given in the references) go to another random location and repeat the procedure. The princess and monster game has been solved only for the very simple graph consisting of a single loop (a circle). [S. Alpern: The search game with mobile hiders on the circle, Proceedings of the conference on differential games and control theory, July 1973.] The game on an interval (a graph with two nodes with a link in-between) has been solved approximatively. The optimal search strategy on an interval is "not" to start at one end (chosen at random) and 'sweep' as fast as possible tho whole interval. Rather, by utilising a mixed search strategy, one can reduce the expected capture time by 8.5%. [ [http://www.cdam.lse.ac.uk/Reports/Files/cdam-2006-18.pdf S. Alpern, R. Fokkink, R. Lindelauf and GJ Olsder: Numerical approaches to the 'Princess and monster' game on the interval.]
]
References
Wikimedia Foundation. 2010.