En teoría de juegos, La princesa y la bestia es un juego de persecución en el que dos jugadores juegan en un área. Desarrollado por Rufus Isaacs y publicado en su libro Juegos diferenciales (1965) de la siguiente manera: “El monstruo busca a la princesa, el tiempo dedicado a buscar es el precio del juego. Ambos están en una habitación completamente oscura (de cualquier forma), pero ambos conocen sus límites. Encontrar a la princesa significa que la distancia entre la princesa y el monstruo está dentro del radio de captura, que debería ser relativamente pequeño en relación con el tamaño de la habitación. El monstruo es lo suficientemente inteligente y se mueve a una velocidad conocida. A la princesa se le permite total libertad de movimiento .
Este juego siguió siendo un problema abierto bien conocido hasta que Gal lo resolvió a fines de la década de 1970 [2] [3] . Su estrategia óptima para la princesa es la siguiente: la princesa va a un punto aleatorio de la habitación y espera en ese punto durante un tiempo determinado, ni demasiado corto ni demasiado largo. Luego la princesa se mueve a otro punto aleatorio (independiente), y así sucesivamente [3] [4] [5] . Se propone una estrategia de búsqueda óptima para el monstruo, en la que todo el espacio de la habitación se divide en muchos rectángulos pequeños . El monstruo selecciona un rectángulo al azar y busca de alguna manera, luego selecciona otro rectángulo al azar e independientemente, y así sucesivamente.
El juego de la princesa y el monstruo se puede jugar en un gráfico preseleccionado (un posible gráfico simple es el círculo , que Isaacs propuso como trampolín para los juegos en un área arbitraria). Se puede demostrar que para cualquier gráfico finito existe una estrategia mixta óptima que conduce a un precio de juego constante. El juego fue resuelto por Steve Alpern e independientemente por Mikhail Zelikin solo para un gráfico muy simple que consiste en un solo bucle (círculo) [6] [7] . Este juego parece simple pero en realidad es bastante complejo. Sorprendentemente, la estrategia obvia de comenzar en un extremo aleatorio e hilvanar el corte lo más rápido posible no es óptima. Esta estrategia garantiza 0,75 del tiempo de captura esperado. Con una estrategia mixta más compleja, puede reducir el tiempo en aproximadamente un 8,6 %. De hecho, este número puede estar cerca del precio del juego, si alguien demuestra que la estrategia correspondiente es óptima para la princesa [8] [9] .