3.4. ДВЕ ДИСКРЕТНЫЕ ИГРЫ ПРЕСЛЕДОВАНИЯ

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

Пример 3.4.1. Игра «полицейский автомобиль». Полицейский автомобиль гонится за автомобилем преступников по улицам города; эти улицы образуют идеальную прямоугольную решетку неограниченной протяженности. Скорость автомобиля вдвое превышает скорость однако обязан подчиняться правилам движения транспорта, которые запрещают левые и -образные повороты; преступники этими правилами пренебрегают.

В дискретном варианте этой игры, который сейчас рассматривается, игроки совершают перемещения поочередно. Если находится в точке решетки, как показано на рис. 3.4.1, то он, когда наступит его очередь передвигаться, может выбрать одну из четырех соседних точек решетки Предположим, что находится в точке О и что он переместился сюда предыдущим ходом из точки С. Далее он может или двигаться прямо вперед к точке А, или повернуть направо к Будем считать, что поимка преступников произошла, если совпадают либо оказываются в соседних точках решетки, если находится в точке О, то считается пойманным, если в это время он оказался в одной из девяти точек, отмеченных знаком Игра оканчивается ходом и платой является число его ходов от начала игры до поимки преступников.

Введем теперь редуцированное пространство. Примем точку О, положение автомобиля за начало координат, а ось

направим по направлению предыдущего перемещения Тогда позиция полностью определяется заданием вектора х=(х,у), где х, у — координаты в этой новой, связанной с системе координат. Ее можно представить себе как карту города, выполненную в полном масштабе и связанную с какой-либо плоскостью полицейской машины, скажем с ее крышей; тогда положение определяется вектором х на этой карте.

Рис. 3.4.1.

Рис. 3.4.2.

Недостатком редуцированного пространства является то, что движение в нем становится, как правило, более сложным. Предположим, что переместился на две единицы по направлению к А. Это эквивалентно перемещению х на две единицы в обратном направлении к точке А, как показано на рис. 3.4.1. Пусть теперь повернул направо к точке В. Направив ось у вдоль вектора мы видим, что х при этом оказывается левее В на четыре единицы и впереди на одну. В первоначальной (неподвижной) системе координат это эквивалентно перемещению х в точку В.

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

Начало координат и восемь его соседних точек, составляющих область захвата, сразу можно отметить значением 0, так как в этих точках совершает захват, не сделав ни одного хода. Принимая во внимание, что игра оканчивается ходом можно сразу найти и отметить точки, для которых на рис. 3.4.2 они отмечены цифрой 1.

Начиная с этого момента процесс приобретает общность. Следующий шаг состоит в отыскании таких узлов решетки, которые с точки зрения ограничены значениями или 1, а именно таких х, что если бы находился в х, то все четыре точки, куда он мог бы отсюда перемещаться, уже были бы отмечены, причем по крайней мере одна из них — значением 1. На рис. 3.4.2 все такие точки обведены пунктирной линий. Далее выделим из точек, для которых значение V еще пока не установлено, такие, что один ход может перевести их внутрь области, окруженной пунктирной линией. Легко видеть, что этому условию удовлетворяют четыре точки: две из них, отмеченные а, соответствуют случаю, когда движется прямо вперед, и две, отмеченные когда он сворачивает вправо. Следовательно, точкам отвечает значение

В самом деле, проверим это последнее утверждение. Если х находится в одной из точек а или то может перевести х в одну из точек, расположенных внутри выделенной пунктиром области, двигаясь прямо либо сворачивая (такие перемещения являются частью его оптимальной стратегии). Теперь наступает очередь для его оптимальная стратегия предписывает ему переместиться в точку с наибольшим значением V, которое здесь равно. Затем снова движется причем мы уже знаем (заметьте индукцию!), что он может из этого положения осуществить захват за один ход, сделав, таким образом, всего два хода.

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

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

Если игра начинается в какой либо из неотмеченных ючек, неизменно может избежать захвата Какова его стратегия

Проблема 3.4.1 Если мы увеличим скорость позволив ему перемещаться на 3 или более единицы за один ход (вместо 2), будут ли существовать начальные точки, позволяющие неизменно избегать захвата Разумеется, область захвата тогда должна быть соответственно увеличена, чтобы исключить случаи, когда проходит мимо не захватив его

Рис. 3.4.3

Рис. 3.4.4

Упражнение 3.4.2 Нарисовать несколько траектории оптимальной игры в естественном пространстве

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

Пусть находится в точке О (рис. 3.4.4 ), куда он предыдущим лодом переместился из точки С, тогда в качестве своего

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

Рис. 3.4.5

В то же время за один ход может перемещаться на одну единицу в любую из шести соседних точек

Захват осуществляется, если находится, скажем, в точке О, а занимает О или одну из соседних точек, все они отмечены значком X Как и в предыдущем примере, в качестве платы выбираем число ходов до захвата

Снова введем редуцированное пространство — подвижную систему координат, где начало координат О совпадает с вектор предыдущего перемещения принят за вертикальную ось, а х означает положение в этой системе координат Предоставляем

читателю самому определить, какие перемещения х отвечают каждому из допустимых ходов

Техника нахождения решения здесь та же, что и в предыдущем примере мы определяем V, начиная с области захвата (отмеченной значком X), и продолжаем процесс за ее пределы Точки, где или 1, можно найти сразу же Как и раньше, если мы знаем точки, где мы сперва находим множество таких х, что если находится в х, то для всех шести соседних точек Тогда множеством точек, где будут такие еще не обозначенные точки, которые одним ходом можно перевести в 5.

Рис. 3.4.6

В результате получим картину, изображенную на рис. 3.4.5. Здесь значение V уже определено для каждого узла треугольной решетки; всегда может осуществить захват Из-за симметрии левую сторону диаграммы мы не привели Обратите внимание на расположение последовательных значений На верхней части диаграммы точки с одинаковыми значениями V расположены рядами, параллельными сторонам шестиугольника — «области захвата»; каждый ряд искривляется вслед за предыдущим, и так происходит вплоть до Ряд со значением простирается через всю нижнюю часть диаграммы, оставляя свободной лишь область снизу от двойной стрелки со значениями от 10 до 13. Точкам этой области соответствуют оптимальные траектории с маневром разворота (см § 15).

Оптимальные траектории в естественном пространстве для начальной точки, где изображены на рис. 3.4.6. Заметьте, что должен сделать два шага влево, прежде чем развернется и начнет догонять заметьте также, что вначале следует за ним, стараясь заставить как можно больше маневрировать.

Картина не должна быть обязательно именно такой, ибо в этой игре оптимальная стратегия часто не единственна Нетрудно понять, что причина здесь просто в квантизации. Пусть,

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

Из-за некоторых причин, подобных этой, многие тонкости игры «шофер-убийца» затемняются в дискретном ее варианте. В дальнейших главах мы изучим кривую, называемую барьером, которая описывает начальные точки, ведущие к маневру разворота. На этой кривой V разрывна. Аналогию барьера можно усмотреть в дискретном случае, сравнивая на рис 3.4 5 пару соседних точек, в которых V отличается более чем на 1.