Пошукова гра

Пошукова гра — це гра з нульовою сумою для двох осіб, яка відбувається на множині, званій простором пошуку. Шукач може вибрати будь-яку неперервну траєкторію, на яку накладається обмеження на максимальну швидкість. Завжди передбачається, що ні шукач, ні той, що ховається, не знають про пересування іншого гравця, поки відстань між ними не стане меншою (або рівною) радіусу виявлення і в цей самий момент здійснюється захоплення. Як математичні моделі пошукові ігри можна застосувати в таких галузях, як ігри в хованки, в які грають діти, або за деяких військових тактичних обставин. Ігри на пошук уведені в останньому розділі класичної книги ^[ru] «Диференціальні ігри» і пізніше їх розвинув Шмуель Гал і Стів Альперн. Гра «Принцеса і Чудовисько» має справу з рухомою ціллю.

Стратегія

Природною стратегією пошуку для нерухомої цілі в графі є пошук мінімальної замкнутої кривої L, яка проходить всі дуги графу. (L називається маршрутом китайського листоноші). Тоді обходимо L з імовірністю 1/2 для кожного напрямку. Ця стратегія працює добре, якщо граф ейлерів. У загальному випадку маршрут китайського листоноші є оптимальною стратегією тоді й лише тоді, коли граф складається з набору ейлерових графів, з'єднаних деревоподібною структурою. Оманливо простий приклад графу не з цього сімейства складається з двох вузлів, з'єднаних трьома дугами. Випадковий обхід китайського листоноші (еквівалентний проходу трьох дуг у випадковому порядку) не оптимальний, а оптимальний шлях пошуку цих трьох дуг складний.

Необмежені області

У загальному випадку необмеженої області для пошуку, як у разі онлайнового алгоритму, прийнятною стратегією буде використання нормалізованої функції втрат (званої в літературі конкурентним співвідношенням).

Мінімаксна траєкторія для задач такого типу завжди є геометричною послідовністю (або експоненційною функцією для неперервних задач). Цей результат дає простий метод знаходження мінімаксної траєкторії шляхом мінімізації єдиного параметра (генератора цієї послідовності) замість пошуку по всьому простору траєкторій. Цей засіб використовується в ^[en], тобто задачі пошуку цілі на нескінченній прямій, яка привернула багато уваги останнім часом і аналізувалася як пошукова гра. Він використовувався також для пошуку мінімаксної траєкторії знаходження набору променів, що сходяться в точці. Оптимальний пошук на площині здійснюється за допомогою експоненційних спіралей.

Пошук променів, що сходяться, пізніше перевідкрито в науковій літературі як «задача про коров'ячу стежку».

Примітки

1. Isaacs, 1965.
2. Gal, 1980.
3. Alpern, Gal, 2003.
4. Gal, 2000.
5. Beck, Newman, 1970, с. 419—429.
6. Chrobak2004, с. 74–78.
7. Kao, Reif, Tate, 1993.

Література

• Rufus Isaacs. Differential Games. — John Wiley and Sons. — 1965.
• Gal S. On the optimality of a simple strategy for searching graphs // Int. J. Game Theory. — 2000. — 17 червня.
• Shmuel Gal. Search Games / Richard Bellman. — New York : Academic Press, 1980. — (Mathematics in science and engeneering) — .
• Alpern S., Gal S. The Theory of Search Games and Rendezvous. — New York, Boston, London, Moscow : Kluwer Academic Publishers, 2003. — (International series in operations research & management science) — .
• Beck A., Newman D.J. Yet More on the linear search problem // Israel J. Math.. — 1970. — Т. 8, вип. 4 (17 червня). — С. 419—429. — DOI:10.1007/BF02798690.
• Chrobak M. A princess swimming in the fog looking for a monster cow // ACM Sigact news. — 2004. — Т. 35, вип. 2 (17 червня).
• Kao M.Y., Reif J.H., Tate S.R. Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem // SODA. — 1993.