21-2. НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ИГР

Последние 10—15 лет быстро развивается специальная математическая дисциплина, получившая название теории игр [Л. 21-1]. В этой теории рассматриваются игры в широком смысле слова как последовательности подчиненных определенным правилам и статистическим зависимостям шагов сторон-игроков.

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

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

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

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

Так, например, для записи стратегии игрока в шахматы

Рис. 21-2. Множества стратегий игроков конечной игры с двумя сторонами.

потребовалось бы описать огромное количество вариантов, подавляющее большинство которых не встретится в каждой данной конкретной игре. Столь же велико и число возможных стратегий. Это обстоятельство, весьма существенное при построении Алгоритмов игровых управляющих машин (§ 21-4), не может, однако, служить препятствием успешному применению понятия стратегии или исчерпывающего алгоритма в общей математической теории игр.

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

Множество возможных стратегий игрока I обозначим игрока Если число сторон-игроков равно то всего будем иметь множеств возможных стратегий

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

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

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

Различные исходы игры для игроков неравноценны. Для описания

Рис. 21-3. Возможные стратегии игроков и значения функции выигрыша нормальной формы игры.

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

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

Если сумма функций выгоды игроков согласно правилам игры постоянна:

то игра называется игрой с постоянной суммой. Заменой

игра с постоянной суммой преобразуется в игру с нулевой суммой:

Для игры с двумя сторонами условие нулевой суммы имеет вид:

Функция

в играх с нулевой суммой называется функцией выигрыша. Эта функция совпадает с функцией выгоды I игрока и противоположна по знаку функции выгоды II игрока.

Все дальнейшие положения относятся к играм с двумя сторонами и нулевой суммой [см. 21-1]. Приведенные понятия и определения позволяют рассматривать в теории игр весьма простую и единую форму игры — так называемую нормальную форму игры.

Игра в нормальной форме состоит из пространства (множеств) возможных стратегий и функции выигрыша где Рис. 21-3 поясняет нормальную форму игры. Пронумерованные возможные стратегии I и II игроков

Рис. 21-4. К определению точной нижней и точной верхней цен игры.

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

Если игра конечна, то множество значений функции выигрыша также конечно, и удобно вместо этой функции рассматривать матрицу игры:

Элементы этой матрицы равны значениям функции выигрыша в точках, соответствующих номерам строк и столбцов:

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

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

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

Обратимся теперь к рис. 21-3, поясняющему нормальную форму игры. Первой игрок распоряжается лишь смещением вдоль оси т. е. заданием стратегии Второй игрок распоряжается координатой по оси т. е. заданием стратегии У.

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

Вместо пространственной картины и поверхностиможно рассматривать семейство сечений этой поверхности плоскостями или Соответствующие семейства сечений представлены на рис. 21-5 и 21-6.

На рис. 21-5 представлены сечения плоскостями Выбрав стратегию, первый игрок определяет тем самым график этого семейства. Там же указаны точные нижние границы при

Точная верхняя граница множества значений точных нижних границ функции выигрыша при называется нижней чистой ценой игры :

Рис. 21-5. Семейство сечений поверхности плоскостями и определение нижней чистой цены игры.

Для случая, представленного на рис. 21-5, нижняя чистая цена игры совпадает с т. е. с точной нижней границей при

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

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

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

Точная нижняя граница множества значений точных верхних границ функции выигрыша при называется верхней чистой ценой игры Я:

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

Нижняя и верхняя чистые цены игры обозначены также на рис. 21-3. Легко видеть, что в рассматриваемой игре они совпадают:

Величина носит название чистой цены игры.

Рис. 21-6. Семейство сечений поверхности плоскостями и определение верхней чистой цены игры.

Равенство (21-4) справедливо для широкого класса игр, именуемых играми, имеющими чистую цену.

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

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

Ввиду важности понятия оптимальных стратегий целесообразно дать дополнительные пояснения.

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

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

Если для наглядности принять, что значение функции выигрыша равное чистой цене X, соответствует ничейному результату (исходу) игры, то можно также формулировать: оптимальная стратегия

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

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

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

где элементы матрицы равны:

Элемент расположен в строке и столбце.

Элемент, минимальный (наименьший) в своей строке и максимальный (наибольший) в своем столбце называется седловым элементом матрицы.

Матрица конечной игры, имеющей чистую цену и имеющей, стало быть, оптимальные стратегии, всегда содержит седловой элемент. Седловой элемент матрицы конечной игры, имеющей чистую цену, равен этой чистой цене Я:

и индексы этого элемента соответствуют оптимальным стратегиям игроков.

Значительная часть теории игр посвящена математическому определению классов игр, имеющих оптимальные стратегии. В частности, вводится понятие игр с полной информацией. В играх с полной информацией игрок при каждом личном ходе знает выборы и исходы всех предыдущих личных и случайных ходов. Доказано [Л. 21-1], что всякая игра с полной информацией имеет чистую цену; матрица конечной игры с полной информацией всегда имеет седловой элемент.

Наряду с нормальной формой игры и понятием стратегии в теории игр вводится понятие усреднения игры смешанных стратегий. Ранее рассмотренные стратегии в отличие от смешанных называются чистыми стратегиями.

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

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