3.3. ИГРЫ НА УНИЧТОЖЕНИЕ

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

Примем за первый квадрант плоскости х, у, тогда состоит из положительных полуосей х и у. Если у соответствует максимизирующему игроку то на полуоси х и на полуоси у.

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

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

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

Пример 3.3.1. Простейшая игра на уничтожение. Пространство игры есть множество узлов прямоугольной решетки, изображенной на рис. 3.3.1, с обычными координатами х, у. Левые и нижние граничные точки решетки образуют здесь силы одного из противников обращаются в нуль. Возможные значения отмечены на рисунке. Слева и внизу нарисованы вектограммы для и для Например, если у принимает значения 0, 1, 2 или 3, то может выбирать один из двух ходов, изображенных на его нижней вектограмме; для или 7 он уже имеет возможность выбрать любой из трех ходов средней вектограммы, а при 8 он использует верхнюю вектограмму.

Противники ходят поочередно. Можно представлять себе фишку х, расположенную в начале игры в некотором узле решетки (как и в непрерывном случае, каждая точка может служить начальным положением). Игроки движутся попеременно,

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

Рис. 3.3.1.

Будем считать, что середине отрезка между двумя узлами решетки соответствует величина платы, большая по модулю.

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

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

в распоряжении хода приводят его либо к достижению в точке (3,0), либо к пересечению в точке при этом плата равна соответственно 3 и 1; выбирает максимум, равный 3, что и записываем справа и сверху от точки (1, —1). В то же время имеющиеся в распоряжении два хода позволяют ему, отправляясь из этой точки, окончить игру с платой —1 и —2; последнее значение, как минимальное, записываем слева и снизу от точки Мы пока ничего не можем написать в тех точках, где оба допустимых хода не позволяют игрокам достичь (например, точка

Рис. 3.3.2

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

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

Повторное применение этого правила полностью определяет V для обоих игроков. Например, если движется из точки он может оказаться либо в (3,0), где либо в где V для равна 6; минимальная величина 3 есть значение V для в точке (5, —1). Теперь известны оба исхода для находящегося в точке (3. —2), и для него можно аналогично определить V в этой точке. Продолжение этой процедуры дает диаграмму, изображенную на рис. 3.3.3

Теперь оптимальные стратегии известны сразу для двух игроков; игрок выбирает решение в соответствии с нашим правилом.

На рис. 3.3.4 изображены оптимальные траектории для двух соседних начальных точек (11, —14) и (10, —14), в которых V (для равна 4 и —3. Сплошные стрелки означают движение пунктирные — движение

Рис. 3.3.3 (см. скан)

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

Укажем одну трудность, незначительную для рассмотренного случая, но которая может оказаться серьезной в других вариантах. Сформулируем ее в виде задачи

Задача 3.3.1. Заметим, что на нижней вектограмме для (рис. 3.3.1) и на крайней справа для имеется пара равных и противоположно направленных векторов, составляющие которых по горизонтали и вертикали равны соответственно 1 и 2 Для некоторых точек пространства где допустимы оба эти

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

Рис. 3.3.4. (см. скан)

Показать теперь, что при оптимальном ходе игры партия всегда оканчивается, и указать, как находить V для пары критических точек.

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

Задача 3.3.2. Заметим, что на рис. 3.3.4 при движении из точки (11, —14) (верхняя картинка) часто есть выбор из нескольких оптимальных ходов, в то время как оптимальная

траектория единственна. В то же время на нижней картинке большей свободой действий обладает

Выяснить, хотя бы приближенно, какие факторы определяют количество ходов игрока, допускаемых оптимальной стратегией.

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

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

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

Пример 3.3.2. Игра на уничтожение (игра качества). Описанная выше игра на уничтожение, рассматриваемая как игра качества, имеет решение, показанное на рис. 3.3.5, где отмеченные узлы решетки образуют барьер.

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

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

Рис. 3.3.5.

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

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

прошедшая такую проверку, будет новой точкой барьера. Это построение, разумеется, можно начинать с нулевой точки.

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

Упражнение 3.3.1. Построить барьер для случая, когда начинает игру.