Princess and Monster game

Last updated

In game theory, a 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. [1]

This game remained a well-known open problem until it was solved by Shmuel Gal in the late 1970s. [2] [3] 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. [3] [4] [5] 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. 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 and independently by Mikhail Zelikin only for the very simple graph consisting of a single loop (a circle). [6] [7] 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 utilising 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. [8] [9]

See also

Related Research Articles

Game theory The study of mathematical models of strategic interaction between rational decision-makers

Game theory is the study of mathematical models of strategic interaction among rational decision-makers. It has applications in all fields of social science, as well as in logic, systems science and computer science. Originally, it addressed zero-sum games, in which each participant's gains or losses are exactly balanced by those of the other participants. Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers.

Search algorithm Any algorithm which solves the search problem

In computer science, a search algorithm is any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values. Specific applications of search algorithms include:

In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy.

The rendezvous dilemma is a logical dilemma, typically formulated in this way:

In game theory, the best response is the strategy which produces the most favorable outcome for a player, taking other players' strategies as given. The concept of a best response is central to John Nash's best-known contribution, the Nash equilibrium, the point at which each player in a game has selected the best response to the other players' strategies.

In game theory, a player's strategy is any of the options which he or she chooses in a setting where the outcome depends not only on their own actions but on the actions of others. A player's strategy will determine the action which the player will take at any stage of the game.

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of his or her current action on the future actions of other players; this impact is sometimes called his or her reputation. Single stage game or single shot game are names for non-repeated games.

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. In 1976, Torrence Parsons introduced a formulation whereby movement is constrained by a graph. The geometric formulation is sometimes called continuous pursuit-evasion, and the graph formulation discrete pursuit-evasion. Current research is typically limited to one of these two formulations.

Rufus Philip Isaacs was a game theorist especially prominent in the 1950s and 1960s with his work on differential games.

In game theory, a stochastic game, introduced by Lloyd Shapley in the early 1950s, is a dynamic game with probabilistic transitions played by one or more players. The game is played in a sequence of stages. At the beginning of each stage the game is in some state. The players select actions and each player receives a payoff that depends on the current state and the chosen actions. The game then moves to a new random state whose distribution depends on the previous state and the actions chosen by the players. The procedure is repeated at the new state and play continues for a finite or infinite number of stages. The total payoff to a player is often taken to be the discounted sum of the stage payoffs or the limit inferior of the averages of the stage payoffs.

In game theory, the homicidal chauffeur problem is a mathematical pursuit problem which pits a hypothetical runner, who can only move slowly, but is highly maneuverable, against the driver of a motor vehicle, which is much faster but far less maneuverable, who is attempting to run him down. Both runner and driver are assumed to never tire. The question to be solved is: under what circumstances, and with what strategy, can the driver of the car guarantee that he can always catch the pedestrian, or the pedestrian guarantee that he can indefinitely elude the car?

In game theory, differential games are a group of problems related to the modeling and analysis of conflict in the context of a dynamical system. More specifically, a state variable or variables evolve over time according to a differential equation. Early analyses reflected military interests, considering two actors—the pursuer and the evader—with diametrically opposed goals. More recent analyses have reflected engineering or economic considerations.

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 has any knowledge about the movement of the other player until their distance apart is less than or equal to the discovery radius and at this very moment capture occurs. As mathematical models, search games can be applied to areas such as hide-and-seek games that children play or representations of some tactical military situations. The area of search games was introduced in the last chapter of Rufus Isaacs' classic book "Differential Games" and has been developed further by Shmuel Gal and Steve Alpern. The princess and monster game deals with a moving target.

In computational complexity theory, the linear search problem is an optimal search problem introduced by Richard E. Bellman..

Shmuel Gal Israeli mathematician

Shmuel Gal is a mathematician and professor of statistics at the University of Haifa in Israel.

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 theory, but his more recent research has been concentrated in the fields of search games and rendezvous. He informally introduced the rendezvous problem as early as 1976. His collaborators include Shmuel Gal, Vic Baston and Robbert Fokkink.

Jean-François Mertens Belgian game theorist

Jean-François Mertens was a Belgian game theorist and mathematical economist.

Leon Petrosyan Game theorist

Leon Petrosjan is a professor of Applied Mathematics and the Head of the Department of Mathematical Game theory and Statistical Decision Theory at the St. Petersburg University, Russia.

Mikhail Il'ich Zelikin is a Russian mathematician, who works on differential equations, optimal control theory, differential games, the theory of fields of extremals for multiple integrals, the geometry of Grassmannians. He proposed an explanation of ball lightning based on the hypothesis of plasma superconductivity.

References

  1. R. Isaacs, Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization, John Wiley & Sons, New York (1965), PP 349350.
  2. S. Gal, SEARCH GAMES, Academic Press, New York (1980).
  3. 1 2 Gal Shmuel (1979). "Search games with mobile and immobile hider". SIAM J. Control Optim. 17 (1): 99–122. doi:10.1137/0317009. MR   0516859.
  4. A. Garnaev (1992). "A Remark on the Princess and Monster Search Game" (PDF). Int. J. Game Theory. 20 (3): 269–276. doi:10.1007/BF01253781.[ permanent dead link ]
  5. M. Chrobak (2004). "A princess swimming in the fog looking for a monster cow". ACM SIGACT News. 35 (2): 74–78. doi:10.1145/992287.992304.
  6. S. Alpern (1973). "The search game with mobile hiders on the circle". Proceedings of the Conference on Differential Games and Control Theory.
  7. M. I. Zelikin (1972). "On a differential game with incomplete information". Soviet Math. Dokl.
  8. S. Alpern, R. Fokkink, R. Lindelauf, and G. J. Olsder. Numerical Approaches to the 'Princess and Monster' Game on the Interval. SIAM J. control and optimization 2008.
  9. L. Geupel. The 'Princess and Monster' Game on an Interval.