3.2. ОБЩАЯ ДИСКРЕТНАЯ ИГРА

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

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

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

(кликните для просмотра скана)

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

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

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

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

Упражнение 3.2.1. Завершить решение игры и показать, что здесь

Подведем итоги.

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

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

Аналогично в дифференциальных играх: есть цена игры, начинающейся из точки х.

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

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

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

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

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

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

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

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

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

С другой стороны, рассмотрим игру, диаграмма которой изображена на рис. 3.2.2. Правило ее построения очевидно. Формула ответа возникает сразу же в процессе построения решения. Действительно, легко можно доказать индукцией по что значения V для четырех верхних положений на рисунке таковы:

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

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

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

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

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