Игра принцесс и монстров - Princess and Monster game

В теория игры, а принцесса и монстр игра это преследование-уклонение игра, в которую играют два игрока в регионе. Игра была разработана Руфус Айзекс и опубликовал в своей книге Дифференциальные игры (1965) следующим образом:

Чудовище ищет принцессу, и расплата за это время. Они оба находятся в совершенно темной комнате (любой формы), но каждый осознает ее границы. Захват означает, что расстояние между принцессой и монстром находится в пределах радиуса захвата, который считается небольшим по сравнению с размером комнаты. Чудовище, считающееся очень умным, движется с известной скоростью. Мы даем принцессе полную свободу передвижения.[1]

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

В игры с принцессами и монстрами можно играть на предварительно выбранных график. Можно показать, что для любого конечного графа оптимальная смешанная стратегия поиска существует, что приводит к конечному результату. Эта игра была решена Стив Альперн и независимо Михаил Зеликин только для очень простого графа, состоящего из одной петли (круга).[6][7] Ценность игры на единичном интервале (граф с двумя узлами со связью между ними) была оценена приблизительно.

Игра кажется простой, но довольно сложной. Очевидная стратегия поиска, состоящая в том, чтобы начать со случайного конца и «развернуть» весь интервал как можно быстрее, гарантирует ожидаемое время захвата 0,75 и не является оптимальным. Используя более сложную стратегию смешанного поиска и укрытия, можно сократить ожидаемое время захвата примерно на 8,6%. Это число было бы довольно близко к значению игры, если бы кто-то смог доказать оптимальность соответствующей стратегии принцессы.[8][9]

Смотрите также

Рекомендации

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