Русская Википедия:Принцесса и Чудовище (игра)
В теории игр Принцесса и Чудовище — это игра преследования, в которой два игрока играют в некоторой области. Разработана Руфусом Айзексом и опубликована в его книге Дифференциальные игры (1965) в следующем виде: «Монстр ищет принцессу, потраченное на поиск время является ценой игры. Оба находятся в совершенно тёмном помещении (любой формы), но оба знают его границы. Найти принцессу означает, что расстояние между принцессой и монстром оказывается в пределах радиуса захвата, который должен быть относительно мал по отношению к размерам помещения. Монстр достаточно разумен и движется с известной скоростью. Принцессе разрешается полная свобода движения»[1].
Эта игра оставалась хорошо известной открытой проблемой, пока не была решена Шаблон:Не переведено 5 в конце 1970-х годов[2][3]. Его оптимальная стратегия для принцессы следующая: принцесса переходит в случайную точку помещения и ждёт в этой точке некоторый интервал времени, не слишком короткий и не слишком длинный. Затем принцесса переходит в другую (независимую) случайную точку и так далее[3][4][5]. Для монстра предлагается оптимальная стратегия поиска, в которой всё пространство помещения делится на много мелких прямоугольников. Монстр выбирает прямоугольник случайно и ищет некоторым образом вокруг, затем выбирает случайно и независимо другой прямоугольник, и так далее.
Игру принцессы и монстра можно играть на заранее выбранном графе (возможным простым графом может служить окружность, которую Айзекс предложил как ступеньку для игр в произвольной области). Можно показать, что для любого конечного графа существует оптимальная смешанная стратегия, приводящая к постоянной цене игры. Игра решена Шаблон:Не переведено 5 и, независимо, Михаилом Зеликиным только для очень простого графа, состоящего из единственной петли (окружности)[6][7]. Эта игра выглядит просто, но на самом деле достаточно сложна. К удивлению, очевидная стратегия начать с одного случайного конца и выметание отрезка настолько быстро, насколько возможно, не оптимальна. Эта стратегия гарантирует 0,75 ожидаемого времени захвата. Используя более сложную смешанную стратегию, можно сократить время примерно на 8,6 %. Фактически, это число может быть близко к цене игры, если кто-либо докажет оптимальность соответствующей стратегии для принцессы[8][9].
См. также
Примечания
- ↑ Шаблон:Книга
- ↑ Шаблон:Книга
- ↑ 3,0 3,1 Шаблон:Статья
- ↑ Шаблон:СтатьяШаблон:Недоступная ссылка
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ S. Alpern, R. Fokkink, R. Lindelauf, and G. J. Olsder. Numerical Approaches to the 'Princess and Monster' Game on the Interval. Шаблон:Wayback SIAM J. control and optimization 2008.
- ↑ L. Geupel. The 'Princess and Monster' Game on an Interval. Шаблон:Wayback
