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