Принцеса і Чудовисько (гра)

У теорії ігор Принцеса і Чудовисько — це гра переслідування, в якій двоє гравців грають на деякій ділянці. Розробив Руфус Айзекс і опублікував у книзі Диференціальні ігри (1965) в такому вигляді: «Монстр шукає принцесу, витрачений на пошук час є ціною гри. Обидва перебувають в абсолютно темному приміщенні (будь-якої форми), але обидва знають його межі. Знайти принцесу означає, що відстань між принцесою і монстром виявляється в межах радіуса захоплення, який має бути відносно малим порівняно з розмірами приміщення. Монстр досить розумний і рухається з відомою швидкістю. Принцесі дозволена повна свобода руху»[1].

Ця гра залишалася добре відомою відкритою проблемою, поки її не розв'язав Гал^[en] у кінці 1970-х років[2][3]. Його оптимальна стратегія для принцеси така: принцеса переходить у випадкову точку приміщення і чекає в цій точці деякий проміжок часу, не дуже короткий і не дуже довгий. Потім принцеса переходить в іншу (незалежну) випадкову точку і так далі[4][5]. Для монстра пропонується оптимальна стратегія пошуку, в якій весь простір приміщення ділиться на багато дрібних прямокутників. Монстр вибирає прямокутник випадково і шукає певним чином навколо, потім вибирає випадково і незалежно інший прямокутник, і так далі.

Гру принцеси і монстра можна грати на заздалегідь вибраному графі (можливим простим графом може бути коло, яке Айзекс запропонував як сходинку для ігор у довільній області). Можна показати, що для будь-якого скінченного графа існує оптимальна змішана стратегія, яка веде до сталої за ціною гри. Гру розв'язав Стів Алперн^[en] і, незалежно, Михайло Зелікіним^[ru] тільки для дуже простого графа, що складається з єдиної петлі (кола)[6][7]. Ця гра виглядає просто, але насправді досить складна. Дивно, але очевидна стратегія почати з одного випадкового кінця і вимітання відрізка настільки швидко, наскільки можливо, не оптимальна. Ця стратегія гарантує 0,75 очікуваного часу захоплення. Використовуючи складнішу змішану стратегію, можна скоротити час приблизно на 8,6 %. Фактично, це число може бути близьким до ціни гри, якщо хтось доведе оптимальність відповідної стратегії для принцеси[8][9].

Див. також

• Пошукова гра
• Список ігор у теорії ігор

Примітки

1. R. Isaacs. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. — New York : John Wiley & Sons, 1965. — С. 349—350.
2. S. Gal. SEARCH GAMES. — New York : Academic Press, 1980.
3. Gal Shmuel. Search games with mobile and immobile hider // SIAM J. Control Optim. — 1979. — Т. 17, вип. 1 (21 січня). — С. 99–122. — DOI:10.1137/0317009.
4. A. Garnaev. A Remark on the Princess and Monster Search Game // Int. J. Game Theory. — 1992. — Т. 20, вип. 3 (21 січня). — С. 269—276. — DOI:10.1007/BF01253781.^[недоступне посилання з Март 2018]
5. M. Chrobak. A princess swimming in the fog looking for a monster cow // ACM SIGACT News. — 2004. — Т. 35, вип. 2 (21 січня). — С. 74—78. — DOI:10.1145/992287.992304.
6. S. Alpern. The search game with mobile hiders on the circle // Proceedings of the Conference on Differential Games and Control Theory. — 1973. — 21 січня.
7. Зеликин М. И. Об одной дифференциальной игре с неполной информацией // Доклады Академии Наук СССР. — 1972. — Т. 202, вип. 5 (21 січня).
8. S. Alpern, R. Fokkink, R. Lindelauf, and G. J. Olsder. Numerical Approaches to the 'Princess and Monster' Game on the Interval. [Архівовано 27 вересня 2020 у Wayback Machine.] SIAM J. control and optimization 2008.
9. L. Geupel. The 'Princess and Monster' Game on an Interval. [Архівовано 30 листопада 2020 у Wayback Machine.]