Принцесса и Чудовище (игра)

Перейти к навигацииПерейти к поиску

В теории игр Принцесса и Чудовище — это игра преследования, в которой два игрока играют в некоторой области. Разработана Руфусом Айзексом и опубликована в его книге Дифференциальные игры (1965) в следующем виде: «Монстр ищет принцессу, потраченное на поиск время является ценой игры. Оба находятся в совершенно тёмном помещении (любой формы), но оба знают его границы. Найти принцессу означает, что расстояние между принцессой и монстром оказывается в пределах радиуса захвата, который должен быть относительно мал по отношению к размерам помещения. Монстр достаточно разумен и движется с известной скоростью. Принцессе разрешается полная свобода движения»[1].

Эта игра оставалась хорошо известной открытой проблемой, пока не была решена Галом[англ.] в конце 1970-х годов[2][3]. Его оптимальная стратегия для принцессы следующая: принцесса переходит в случайную точку помещения и ждёт в этой точке некоторый интервал времени, не слишком короткий и не слишком длинный. Затем принцесса переходит в другую (независимую) случайную точку и так далее[3][4][5]. Для монстра предлагается оптимальная стратегия поиска, в которой всё пространство помещения делится на много мелких прямоугольников. Монстр выбирает прямоугольник случайно и ищет некоторым образом вокруг, затем выбирает случайно и независимо другой прямоугольник, и так далее.

Игру принцессы и монстра можно играть на заранее выбранном графе (возможным простым графом может служить окружность, которую Айзекс предложил как ступеньку для игр в произвольной области). Можно показать, что для любого конечного графа существует оптимальная смешанная стратегия, приводящая к постоянной цене игры. Игра решена Стивом Алперном[англ.] и, независимо, Михаилом Зеликиным только для очень простого графа, состоящего из единственной петли (окружности)[6][7]. Эта игра выглядит просто, но на самом деле достаточно сложна. К удивлению, очевидная стратегия начать с одного случайного конца и выметание отрезка настолько быстро, насколько возможно, не оптимальна. Эта стратегия гарантирует 0,75 ожидаемого времени захвата. Используя более сложную смешанную стратегию, можно сократить время примерно на 8,6 %. Фактически, это число может быть близко к цене игры, если кто-либо докажет оптимальность соответствующей стратегии для принцессы[8][9].

См. также

Примечания

  1. ↑ R. Isaacs. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. — New York: John Wiley & Sons, 1965. — С. 349—350.
  2. ↑ S. Gal. SEARCH GAMES. — New York: Academic Press, 1980.
  3. ↑ 1 2 Gal Shmuel. Search games with mobile and immobile hider // SIAM J. Control Optim. — 1979. — Т. 17, вып. 1. — С. 99–122. — doi:10.1137/0317009.
  4. ↑ A. Garnaev. A Remark on the Princess and Monster Search Game // Int. J. Game Theory. — 1992. — Т. 20, вып. 3. — С. 269—276. — doi:10.1007/BF01253781. (недоступная ссылка)
  5. ↑ M. Chrobak. A princess swimming in the fog looking for a monster cow // ACM SIGACT News. — 2004. — Vol. 35. — Вып. 2. — С. 74—78. — doi:10.1145/992287.992304.
  6. ↑ S. Alpern. The search game with mobile hiders on the circle // Proceedings of the Conference on Differential Games and Control Theory. — 1973.
  7. ↑ Зеликин М. И. Об одной дифференциальной игре с неполной информацией // Доклады Академии Наук СССР. — 1972. — Т. 202, вып. 5.
  8. ↑ S. Alpern, R. Fokkink, R. Lindelauf, and G. J. Olsder. Numerical Approaches to the 'Princess and Monster' Game on the Interval. Архивная копия от 27 сентября 2020 на Wayback Machine SIAM J. control and optimization 2008.
  9. ↑ L. Geupel. The 'Princess and Monster' Game on an Interval. Архивная копия от 30 ноября 2020 на Wayback Machine