В теории игр Принцесса и Чудовище — это игра преследования[en], в которой два игрока играют в некоторой области. Разработана Айзеком Руфусом и опубликована в его книге Дифференциальные игры (1965) в следующем виде: «Монстр ищет принцессу, потраченное на поиск время является ценой игры. Оба находятся в совершенно тёмном помещении (любой формы), но оба знают его границы. Найти принцессу означает, что расстояние между принцессой и монстром оказывается в пределах радиуса захвата, который должен быть относительно мал по отношению к размерам помещения. Монстр достаточно разумен и движется с известной скоростью. Принцессе разрешается полная свобода движения»[1].
Эта игра оставалась хорошо известной открытой проблемой, пока не была решена Галом[en] в конце 1970-х годов[2][3]. Его оптимальная стратегия для принцессы следующая: принцесса переходит в случайную точку помещения и ждёт в этой точке некоторый интервал времени, не слишком короткий и не слишком длинный. Затем принцесса переходит в другую (независимую) случайную точку и так далее[3][4][5]. Для монстра предлагается оптимальная стратегия поиска, в которой всё пространство помещения делится на много мелких прямоугольников. Монстр выбирает прямоугольник случайно и ищет некоторым образом вокруг, затем выбирает случайно и независимо другой прямоугольник, и так далее.
Игру принцессы и монстра можно играть на заранее выбранном графе (возможным простым графом может служить окружность, которую Айзекс предложил как ступеньку для игр в произвольной области). Можно показать, что для любого конечного графа существует оптимальная смешанная стратегия, приводящая к постоянной цене игры. Игра решена Стивом Алперном[en] и, независимо, Михаилом Зеликиным только для очень простого графа, состоящего из единственной петли (окружности)[6][7]. Эта игра выглядит просто, но на самом деле достаточно сложна. К удивлению, очевидная стратегия начать с одного случайного конца и выметание отрезка настолько быстро, насколько возможно, не оптимальна. Эта стратегия гарантирует 0,75 ожидаемого времени захвата. Используя более сложную смешанную стратегию, можно сократить время примерно на 8,6 %. Фактически, это число может быть близко к цене игры, если кто-либо докажет оптимальность соответствующей стратегии для принцессы[8][9].
См. также
Примечания
- ↑ R. Isaacs. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. — New York: John Wiley & Sons, 1965. — С. 349—350.
- ↑ S. Gal. SEARCH GAMES. — New York: Academic Press, 1980.
- 1 2 Gal Shmuel. Search games with mobile and immobile hider // SIAM J. Control Optim. — 1979. — Т. 17, вып. 1. — С. 99–122. — DOI:10.1137/0317009.
- ↑ A. Garnaev. A Remark on the Princess and Monster Search Game // Int. J. Game Theory. — 1992. — Т. 20, вып. 3. — С. 269—276. — DOI:10.1007/BF01253781. (недоступная ссылка)
- ↑ 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.
- ↑ S. Alpern. The search game with mobile hiders on the circle // Proceedings of the Conference on Differential Games and Control Theory. — 1973.
- ↑ Зеликин М. И. Об одной дифференциальной игре с неполной информацией // Доклады Академии Наук СССР. — 1972. — Т. 202, вып. 5.
- ↑ 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.
- ↑ L. Geupel. The 'Princess and Monster' Game on an Interval.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .