Игра про принцессу и монстра
-
Определение игры «Принцесса и монстр»
- Игра представляет собой погоню и уклонение, в которой участвуют два игрока в одном регионе.
- Монстр ищет принцессу, а платой за это является затраченное время.
- Оба игрока находятся в темной комнате, но осознают ее границы.
- Захват принцессы монстром происходит, когда расстояние между ними меньше радиуса захвата.
-
Решение Шмуэля Галя
- Галь предложил оптимальную стратегию для принцессы, которая заключается в перемещении в случайное место и неподвижности в течение определенного времени.
- Стратегия основана на разделении комнаты на узкие прямоугольники и поиске в них.
-
Игра как открытая задача
- Игра была известна как открытая задача до ее решения Галем в конце 1970-х.
- Существуют оптимальные стратегии смешанного поиска для различных графов, но они не были доказаны для всех случаев.
-
Сложность игры
- Очевидная стратегия поиска не является оптимальной и может привести к ожидаемому времени захвата в 0,75 секунды.
- Использование более сложной комбинированной стратегии поиска и скрытия может сократить ожидаемое время захвата на 8,6%.
-
Рекомендации и библиография
- В статье приведены ссылки на книги и статьи, связанные с игрой «Принцесса и монстр».
- Ссылки на игры в теории игр и поисковые игры также включены в список.
Полный текст статьи: