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

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

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

Гру принцеси і монстра можна грати на заздалегідь вибраному графі (можливим простим графом може бути коло, яке Айзекс запропонував як сходинку для ігор у довільній області). Можна показати, що для будь-якого скінченного графа існує оптимальна змішана стратегія, яка веде до сталої за ціною гри. Гру розв'язав Стів Алперн і, незалежно, Михайло Зелікіним тільки для дуже простого графа, що складається з єдиної петлі (кола)[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 (9 листопада). — С. 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 (9 листопада). — С. 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 (9 листопада). — С. 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. — 9 листопада.
  7. Зеликин М. И. Об одной дифференциальной игре с неполной информацией // Доклады Академии Наук СССР. — 1972. — Т. 202, вип. 5 (9 листопада).
  8. S. Alpern, R. Fokkink, R. Lindelauf, and G. J. Olsder. Numerical Approaches to the 'Princess and Monster' Game on the Interval. SIAM J. control and optimization 2008.
  9. L. Geupel. The 'Princess and Monster' Game on an Interval.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.