Hispanopedia WikiUn juego de princesas y monstruos es un juego de persecución y evasión que se juega entre dos jugadores en una región.
Definición formal
En su libro Juegos diferenciales (1965), Rufus Isaacs definió el juego como:
El monstruo busca a la princesa, y el tiempo que tarda en encontrarla es su recompensa. Ambos se encuentran en una habitación totalmente oscura (de cualquier forma), pero cada uno es consciente de sus límites. La captura implica que la distancia entre la princesa y el monstruo se encuentra dentro del radio de captura, que se supone pequeño en comparación con las dimensiones de la habitación. El monstruo, presumiblemente muy inteligente, se mueve a una velocidad conocida. Se le concede a la princesa total libertad de movimiento. [ 1 ]
Este juego siguió siendo un problema abierto bien conocido hasta que fue resuelto por Shmuel Gal a finales de la década de 1970. [ 2 ] [ 3 ] Su estrategia óptima para la princesa es moverse a una ubicación aleatoria en la habitación y permanecer quieta durante un intervalo de tiempo que no es ni demasiado corto ni demasiado largo, antes de ir a otra ubicación aleatoria (independiente) y repetir el procedimiento. [ 3 ] [ 4 ] [ 5 ] La estrategia de búsqueda óptima propuesta para el monstruo se basa en subdividir la habitación en muchos rectángulos estrechos, elegir un rectángulo al azar y buscarlo de alguna manera específica, después de un tiempo elegir otro rectángulo al azar e independientemente, y así sucesivamente.
Los juegos de princesas y monstruos se pueden jugar en un grafo preseleccionado . Se puede demostrar que para cualquier grafo finito existe una estrategia de búsqueda mixta óptima que produce una recompensa finita. Este juego ha sido resuelto por Steve Alpern e independientemente por Mikhail Zelikin solo para el grafo muy simple que consiste en un solo bucle (un círculo). [ 6 ] [ 7 ] El valor del juego en el intervalo unitario (un grafo con dos nodos con un enlace entre ellos) se ha estimado de forma aproximada.
El juego parece sencillo, pero es bastante complejo. La estrategia de búsqueda obvia, que consiste en comenzar en un extremo aleatorio y recorrer todo el intervalo lo más rápido posible, garantiza un tiempo de captura esperado de 0,75, y no es óptima. Al utilizar una estrategia mixta más sofisticada de búsqueda y ocultación, se puede reducir el tiempo de captura esperado en aproximadamente un 8,6 %. Este valor sería muy cercano al del juego si alguien pudiera demostrar la optimalidad de la estrategia relacionada de la princesa. [ 8 ] [ 9 ]
Véase también
Referencias
- ↑ R. Isaacs, Juegos diferenciales: una teoría matemática con aplicaciones a la guerra y la persecución, el control y la optimización, John Wiley & Sons, Nueva York (1965), págs. 349-350 .
- ↑ S. Gal, JUEGOS DE BÚSQUEDA, Academic Press, Nueva York (1980).
- 1 2 Gal Shmuel (1979). "Juegos de búsqueda con ocultadores móviles e inmóviles". SIAM J. Control Optim . 17 (1): 99– 122. doi : 10.1137/0317009 . MR 0516859 .
- ↑ A. Garnaev (1992). "Una observación sobre el juego de búsqueda de la princesa y el monstruo" (PDF) . Int. J. Game Theory . 20 (3): 269– 276. doi : 10.1007/BF01253781 . S2CID 122335218 .
- ↑ M. Chrobak (2004). "Una princesa nadando en la niebla buscando una vaca monstruosa". ACM SIGACT News . 35 (2): 74– 78. doi : 10.1145/992287.992304 . S2CID 8687739 .
- ↑ S. Alpern (1973). "El juego de búsqueda con agentes móviles que se esconden en el círculo". Actas de la Conferencia sobre Juegos Diferenciales y Teoría de Control .
- ↑ MI Zelikin (1972). "Sobre un juego diferencial con información incompleta". Soviet Math. Dokl .
- ↑ S. Alpern, R. Fokkink, R. Lindelauf y G.J. Olsder. Enfoques numéricos para el juego de la "Princesa y el Monstruo" en el intervalo. SIAM J. control and optimization 2008.
- ↑ L. Geupel. El juego de la 'Princesa y el Monstruo' en un intermedio.
- Persecución-evasión
- Juegos no cooperativos