12. ИГРЫ ПОИСКА С ДВИЖУЩИМИСЯ ОБЪЕКТАМИ

Насколько мы знаем, о решении таких игр не известно, по существу, ничего. Следующие примеры приведены для того, чтобы выявить квинтэссенцию задачи.

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

Мы не знаем, как решить эту задачу, но кажется весьма вероятным, что оптимальные стратегии должны в значительной мере использовать случайные движения. Мы думаем, что не важно, как именно игроки используют свою возможность выбора траекторий; наверное, один случайный изгиб траектории так же хорош, как и любой другой.

По-видимому, единственное важное решение остается за принцессой — насколько быстро она должна бежать? Одна крайность — полная неподвижность — не слишком обещающая стратегия. Действительно, сделав тур по будет иметь определенную плату, не превышающую фиксированной величины. В то же время любой другой вид движения оставляет по крайней мере возможность того, что до момента поимки пройдет произвольно большой отрезок времени. Другой крайний случай — очень высокая скорость (в сравнении с -вряд ли желателен для поскольку вероятность поимки за короткое время станет очень близка к единице; принцесса сама набежит на чудовище.

Оптимальная скорость принцессы должна лежать где-то между этими крайностями. Где именно?

Этот пример является типичной задачей для чистых игр типа поиска. Следующий пример также не решен, но кажется проще и, возможно, послужит опорным камнем для предыдущего.

Пример 12.4.2. Упрощенный вариант игры «принцесса и чудовище». Единственное нововведение состоит в том, что теперь как так и должны двигаться по фиксированной замкнутой кривой. Возьмем в качестве такой кривой окружность.

Упрощение состоит в том, что при фиксированных скоростях игроков в каждый момент времени каждый игрок имеет лишь два различных выбора.

Теперь у нас есть основание для догадки, что оптимальная скорость движения должна быть равна скорости движения Шаткое основание для этой догадки состоит в том, что лишь равные скорости сохраняют неизменным расстояние если оба игрока используют одну и ту же чистую стратегию.

Проблема 12.4.1. Решить дискретный вариант этой игры. Каждый игрок занимает одну из точек, распределенных по границе круга. Они ходят по очереди в одну из двух соседних точек. Поимка считается состоявшейся, если оба игрока попадают в одну и ту же точку. Платой является число ходов, например, игрока до момента поимки. По-видимому, для начала надо разобрать случай равномерного распределения.