Игра Принцесса и монстр
Игра «Принцесса и монстр» — это игра преследования и уклонения, в которую играют два игрока в одном регионе.
Формальное определение [ править ]
В своей книге «Дифференциальные игры» (1965) Руфус Айзекс определил игру как:
Монстр ищет принцессу, и платой за это является время, потраченное на поиски. Они оба находятся в совершенно темной комнате (любой формы), но каждый осознает ее границы. Захват означает, что расстояние между принцессой и монстром находится в пределах радиуса захвата, который считается небольшим по сравнению с размером комнаты. Монстр, предположительно очень умный, движется с известной скоростью. Мы предоставляем принцессе полную свободу передвижения. [1]
Эта игра оставалась широко известной открытой задачей, пока ее не решил Шмуэль Гал в конце 1970-х годов. [2] [3] Его оптимальная стратегия для принцессы — переместиться в случайное место в комнате и оставаться на месте в течение интервала времени, который не является ни слишком коротким, ни слишком длинным, прежде чем перейти в другое (независимое) случайное место и повторить процедуру. [3] [4] [5] Предлагаемая оптимальная стратегия поиска монстра основана на разбиении комнаты на множество узких прямоугольников, выборе случайного прямоугольника и поиске его каким-то определенным образом, через некоторое время случайном и независимом выборе другого прямоугольника и так далее.
В игры с принцессами и монстрами можно играть на заранее выбранном графике . Можно продемонстрировать, что для любого конечного графа существует оптимальная стратегия смешанного поиска , приводящая к конечному выигрышу. Эта игра была решена Стивом Альперном и независимо Михаилом Зеликином только для очень простого графа, состоящего из одной петли (круга). [6] [7] Приблизительно оценена ценность игры на единичном интервале (граф с двумя узлами со связью между ними).
Игра кажется простой, но на самом деле она довольно сложна. Очевидная стратегия поиска, заключающаяся в том, чтобы начать со случайного конца и как можно быстрее «охватить» весь интервал, гарантирует ожидаемое время захвата 0,75 и не является оптимальной. Используя более сложную стратегию смешанного поиска и скрытия, можно сократить ожидаемое время захвата примерно на 8,6%. Это число было бы весьма близко к ценности игры, если бы кто-то смог доказать оптимальность соответствующей стратегии принцессы. [8] [9]
См. также [ править ]
Ссылки [ править ]
- ^ Р. Айзекс, Дифференциальные игры: математическая теория с приложениями к войне и преследованию, контролю и оптимизации, John Wiley & Sons, Нью-Йорк (1965), стр. 349–350.
- ^ С. Гал, ПОИСКОВЫЕ ИГРЫ, Academic Press, Нью-Йорк (1980).
- ↑ Перейти обратно: Перейти обратно: а б Галь Шмуэль (1979). «Поиск игр с мобильным и неподвижным хидером». СИАМ Дж. Оптимальное управление . 17 (1): 99–122. дои : 10.1137/0317009 . МР 0516859 .
- ^ А. Гарнаев (1992). «Замечание об игре «Поиск принцесс и монстров»» (PDF) . Межд. Дж. Теория игр . 20 (3): 269–276. дои : 10.1007/BF01253781 . S2CID 122335218 . [ постоянная мертвая ссылка ]
- ^ М. Хробак (2004). «Принцесса, плавающая в тумане в поисках коровы-монстра». Новости ACM SIGACT . 35 (2): 74–78. дои : 10.1145/992287.992304 . S2CID 8687739 .
- ^ С. Альперн (1973). «Поисковая игра с мобильными укрытиями на круге». Материалы конференции по дифференциальным играм и теории управления .
- ^ М. И. Зеликин (1972). «О дифференциальной игре с неполной информацией». Советская математика. Докл .
- ^ С. Альперн, Р. Фоккинк, Р. Линделауф и Г. Дж. Олсдер. Численные подходы к игре «Принцесса и чудовище» на интервале. СИАМ Дж. Контроль и оптимизация 2008.
- ^ Л. Геупель. Игра «Принцесса и чудовище» в перерыве.