Princess and monster game

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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Monster Manual —   Monster Manual for the D D 4th Edition Rules Genre(s) …   Wikipedia

  • Monster High — Type Fashion doll, Web series, Book series Company Mattel Country United States …   Wikipedia

  • Rufus Isaacs (game theorist) — Rufus Philip Isaacs (1914 1981) was a game theorist especially promenent in the 1950s and 1960s with his work on differential games. He worked for the RAND Corporation from 1948 until winter 1954/1955. His investigation stemmed from classic… …   Wikipedia

  • Chicken (game) — For other uses, see Chicken (disambiguation). The game of chicken, also known as the hawk dove or snowdrift[1] game, is an influential model of conflict for two players in game theory. The principle of the game is that while each player prefers… …   Wikipedia

  • Cooperative game — This article is about a part of game theory. For video gaming, see Cooperative gameplay. For the similar feature in some board games, see cooperative board game In game theory, a cooperative game is a game where groups of players ( coalitions )… …   Wikipedia

  • Dictator game — The dictator game is a game in experimental economics, similar to the ultimatum game. Experimental results offer evidence against the rationally self interested individual (sometimes called the homo economicus) concept of economic behavior,[1]… …   Wikipedia

  • Normal-form game — In game theory, normal form is a way of describing a game. Unlike extensive form, normal form representations are not graphical per se, but rather represent the game by way of a matrix. While this approach can be of greater use in identifying… …   Wikipedia

  • Zero–sum game — For other uses, see Zero sum (disambiguation). In game theory and economic theory, a zero sum game is a mathematical representation of a situation in which a participant s gain (or loss) of utility is exactly balanced by the losses (or gains) of… …   Wikipedia

  • Coordination game — In game theory, coordination games are a class of games with multiple pure strategy Nash equilibria in which players choose the same or corresponding strategies. Coordination games are a formalization of the idea of a coordination problem, which… …   Wikipedia

  • Strategy (game theory) — In game theory, a player s strategy in a game is a complete plan of action for whatever situation might arise; this fully determines the player s behaviour. A player s strategy will determine the action the player will take at any stage of the… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”