En teoría de juegos , un juego de princesas y monstruos es un juego de persecución y evasión jugado por dos jugadores en una región. El juego fue ideado por Rufus Isaacs y publicado en su libro Differential Games (1965) de la siguiente manera:
El monstruo busca a la princesa, el tiempo necesario es la recompensa. Ambos están en una habitación totalmente oscura (de cualquier forma), pero cada uno es consciente de su límite. Capturar significa que la distancia entre la princesa y el monstruo está dentro del radio de captura, que se supone que es pequeño en comparación con la dimensión de la habitación. El monstruo, supuestamente muy inteligente, se mueve a una velocidad conocida. Permitimos a la princesa total libertad de locomoción. [1]
Este juego siguió siendo un problema abierto bien conocido hasta que Shmuel Gal lo resolvió a fines 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 sea 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, luego 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 gráfico preseleccionado . Se puede demostrar que para cualquier gráfico finito existe una estrategia de búsqueda mixta óptima que da como resultado un pago finito. Este juego ha sido resuelto por Steve Alpern e independientemente por Mikhail Zelikin solo para el gráfico muy simple que consiste en un solo bucle (un círculo). [6] [7] El valor del juego en el intervalo de la unidad (un gráfico con dos nodos con un vínculo en el medio) se ha estimado de forma aproximada.
El juego parece simple pero bastante complicado. La estrategia de búsqueda obvia de comenzar en un extremo aleatorio y "barrer" todo el intervalo lo más rápido posible garantiza un tiempo de captura esperado de 0,75, y no es óptimo. Al utilizar una estrategia mixta de búsqueda y ocultación más sofisticada, se puede reducir el tiempo de captura esperado en aproximadamente un 8,6%. Este número estaría bastante cerca del valor del juego si alguien pudiera demostrar la optimización de la estrategia relacionada de la princesa. [8] [9]
Ver también
Referencias
- ^ R. Isaacs, Juegos diferenciales: una teoría matemática con aplicaciones a la guerra y persecución, control y optimización, John Wiley & Sons, Nueva York (1965), PP 349-350.
- ^ S. Gal, BÚSQUEDA DE JUEGOS, Academic Press, Nueva York (1980).
- ↑ a b Gal Shmuel (1979). "Buscar juegos con ocultador móvil e inmóvil". SIAM J. Control Optim . 17 (1): 99-122. doi : 10.1137 / 0317009 . Señor 0516859 .
- ^ A. Garnaev (1992). "Un comentario sobre el juego de búsqueda de princesas y monstruos" (PDF) . En t. J. Teoría de juegos . 20 (3): 269-276. doi : 10.1007 / BF01253781 .[ enlace muerto permanente ]
- ^ M. Chrobak (2004). "Una princesa nadando en la niebla en busca de una vaca monstruosa". Noticias ACM SIGACT . 35 (2): 74–78. doi : 10.1145 / 992287.992304 .
- ^ S. Alpern (1973). "El juego de búsqueda con escondites móviles en el círculo". Actas de la Conferencia sobre Juegos Diferenciales y Teoría del Control .
- ^ MI Zelikin (1972). "Sobre un juego diferencial con información incompleta". Matemáticas soviéticas. Dokl .
- ^ S. Alpern, R. Fokkink, R. Lindelauf y GJ Olsder. Enfoques numéricos del juego 'Princesa y monstruo' en el intervalo. SIAM J. control y optimización 2008.
- ^ L. Geupel. El juego 'Princesa y monstruo' en un intervalo.