Игра на поиск

Игра на поиск — это игра с нулевой суммой двух лиц, которая происходит на множестве, называемым пространством поиска. Искатель может выбрать любую непрерывную траекторию, на которую накладывается ограничение на максимальную скорость. Всегда предполагается, что ни искатель, ни прячущийся не знают о передвижениях другого игрока, пока расстояние между ними не станет меньше (или равно) радиусу обнаружения и в этот самый момент осуществляется захват. В качестве математических моделей игры на поиск могут быть применены в таких областях, как игры в прятки, в которые играют дети, или в некоторых военных тактических обстоятельствах. Игры на поиск введены в последней главе классической книги Руфуса Айзекса «Дифференциальные игры» и позднее их развил Шмуэль Гал и Стив Альперн. Игра «Принцесса и Чудовище» имеет дело с движущейся целью.

Стратегия

Естественной стратегией поиска для неподвижной цели в графе является поиск минимальной замкнутой кривой L, которая проходит все дуги графа. (L называется маршрутом китайского почтальона). Тогда обходим L с вероятностью 1/2 для каждого направления. Эта стратегия работает хорошо, если граф эйлеров. В общем случае маршрут китайского почтальона является оптимальной стратегией тогда и только тогда, когда граф состоит из набора эйлеровых графов, соединённых подобной дереву структурой. Обманчиво простой пример графа не из этого семейства состоит из двух узлов, соединённых тремя дугами. Случайный обход китайского почтальона (эквивалентно проходу трёх дуг в случайном порядке) не оптимален, а оптимальный путь поиска этих трёх дуг сложен.

Неограниченные области

В общем случае неограниченной области для поиска, как в случае онлайнового алгоритма, приемлемой стратегией будет использование нормализованной функции потерь (называемой в литературе конкурентным соотношением).

Минимаксная траектория для задач такого типа всегда является геометрической последовательностью (или экспоненциальной функцией для непрерывных задач). Этот результат даёт простой метод нахождения минимаксной траектории путём минимизации единственного параметра (генератора этой последовательности) вместо поиска по всему пространству траекторий. Это средство используется в задаче линейного поиска, то есть задаче поиска цели на бесконечной прямой, которая привлекла много внимания в последнее время и анализировалась как игра на поиск. Оно использовалось также для поиска минимаксной траектории нахождения набора сходящихся в точке лучей. Оптимальный поиск на плоскости осуществляется с помощью экспоненциальных спиралей.

Поиск сходящихся лучей позднее был переоткрыт в научной литературе как «задача о коровьей тропе».

См. также

• Теория гарантированного поиска

Литература

• 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.
• Shmuel Gal. Search Games / Richard Bellman. — New York: Academic Press, 1980. — (Mathematics in science and engeneering). — ISBN 0-12-273850-0.
• 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). — ISBN 0-7923-7468-1. — ISBN 0-306-48212-6.
• Beck A., Newman D.J. Yet More on the linear search problem // Israel J. Math.. — 1970. — Т. 8, вып. 4. — С. 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.
• 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.