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

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

Гру принцеси і монстра можна грати на заздалегідь вибраному графі (можливим простим графом може бути коло, яке Айзекс запропонував як сходинку для ігор у довільній області). Можна показати, що для будь-якого скінченного графа існує оптимальна змішана стратегія, яка веде до сталої за ціною гри. Гру розв'язав і, незалежно, тільки для дуже простого графа, що складається з єдиної петлі (кола). Ця гра виглядає просто, але насправді досить складна. Дивно, але очевидна стратегія почати з одного випадкового кінця і вимітання відрізка настільки швидко, наскільки можливо, не оптимальна. Ця стратегія гарантує 0,75 очікуваного часу захоплення. Використовуючи складнішу змішану стратегію, можна скоротити час приблизно на 8,6 %. Фактично, це число може бути близьким до ціни гри, якщо хтось доведе оптимальність відповідної стратегії для принцеси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.L. Geupel. The 'Princess and Monster' Game on an Interval. .

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

Примітки