3. Многошаговые игры

3.1. Основы теории

Рассмотрим многоходовую игру, например, шахматы или «крестики-нолики». Предположим, что, играя в «крестики-нолики», необходимо сосчитать число стратегий первого игрока. Заметим (пренебрегая симметрией), что при первом ходе игрок имеет девять альтернатив. Далее для любого из восьми возможных ответов на втором ходе у него будет семь альтернатив. Если рассмотреть только первые два хода первого игрока, то выяснится, что у него 9·7⁸=51 883 209 чистых стратегий. Естественно, что возможность перечислить их весьма сомнительна.

Вспомним определение чистой стратегии: это функция, определенная на совокупности информационных множеств одного игрока и приписывающая каждому информационному множеству число между 1 и k (где k – число альтернатив в данном информационном множестве). Таким образом, если у игрока N информационных множеств и в каждом из них k альтернатив, то общее число чистых стратегий равно k^N, а это число может быть очень большим. Если вернуться к примеру с «крестиками-ноликами», станет ясно, что никто не играет в эту игру, рассматривая все возможные чистые стратегии (т. е. все возможные последовательности ходов с первого до последнего). Скорее, в нее играют, рассматривая на каждом ходе все возможные альтернативы только для этого хода и выбирая из них наилучшую (исходя из собственного опыта или как-либо иначе). Итак, здесь сущность упрощения состоит в том, чтобы рассматривать ходы по одному за раз. Этот прием сводит один выбор из

k₁ k₂…k_N возможных стратегий к N выборам из k_i возможных альтернатив в каждом информационном множестве. Отсюда следует определение: стратегией поведения называется набор N вероятностных распределений, каждое из которых задано на множестве возможных альтернатив в каждом информационном множестве.

Определение 3.1. Деревом игры (древовидно упорядоченным множеством) называется конечное множество К, частично упорядоченное отношением <, в котором:

а) каковы бы ни были , из условий и следует, что либо , либо (условие предпочтения сверху);

б) существует такое , что для любого .

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

Дерево игры изображается графически с помощью диаграммы, состоящей из конечного числа вершин (рис. 3.1). Вершины являются позициями, а ребра соединяют позиции, непосредственно следующие друг за другом. Ребра, соединяющие некоторую позицию с непосредственно следующей за ней, называются альтернативами этой позиции. Альтернативы каждой позиции нумеруются натуральными числами. Если позиции и находятся в отношении , то позицию называют предыдущей, а позицию – последующей. Позиции, не имеющие последующих, называются окончательными, а остальные – неокончательными. Множество окончательных и неокончательных позиций будем обозначать соответственно через Т и Q. Очевидно, что и .

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

Каждая окончательная вершина определяет единственную цепь – последовательность идущих друг за другом дуг, ведущую от начальной вершины к данной. Эта цепь является партией игры. Число различных партий равно числу окончательных вершин. На множестве окончательных вершин определена функция М(t), которая указывает, сколько выигрывает первый игрок, если игра закончится в вершине .

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

Содержательный смысл информационного множества состоит в том, что игрок в каждый момент игры знает, в каком информационном множестве он находится, но не знает, в какой именно позиции данного множества. Очевидно, что если информационное множество состоит из одной позиции, то игроку известно, как протекала партия до этого момента, поэтому говорят, что игрок имеет полную информацию в игре, если каждое его информационное множество состоит из одного элемента. Семейство всех информационных множеств игрока i (i=0, 1, 2) будем обозначать через U_i, принимая, что каждое множество U₀ одноэлементно. Следовательно, динамика конфликта отражается в игре посредством множеств очередности, а информативность игроков определяется семействами информационных множеств.

Определение 3.2. Позиционной структурой С называется следующая система:

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

б) разбиение множества Q=K/T всех неокончательных позиций на множества очередности Q₀, Q₁, Q₂ (для каждого хода указывается, какой из игроков его делает);

в) подразбиение множеств очередности Q₁ и Q₂ на информационные множества U₁ и U₂ (подразбиение отражает информацию игрока i (i=1, 2) для каждого его хода на дереве игры);

г) вероятностные распределения на множествах альтернатив каждой позиции q из U₀;

д) нумерация альтернатив каждой позиции из одного информационного множества одними и теми же числами 1, 2, …, k (каждое число определяет по одной альтернативе в каждой позиции данного информационного множества).

Процесс игры с позиционной структурой С определяется следующим образом. Первый ход состоит в выборе альтернатив в начальной позиции q_1. Пусть n ходов уже произведены, в результате чего получена позиция . Тогда процесс считается законченным, а игрок i (i=1, 2) получает выигрыш M_i(t). Если позиция , то игра переводится из позиции q в одну из последующих позиций, которая определяется согласно распределению вероятностей на множестве альтернатив позиции q. Если же где - j-е информационное множество игрока i, i=1,…, s; s – число информационных множеств игрока i, то игрок i, зная, что находится в одной из позиций информационного множества , выбирает произвольно одну из альтернатив, и тем самым игра приходит в позицию g и т. д.

Определение 3.3. Чистой стратегией игрока будем называть заранее определенную последовательность ходов игрока в зависимости от информации о ходах другого игрока и ходах игрока 0 (природы).

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

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

Если игрок имеет r информационных множеств, причем любая позиция l-го (l=1, 2,…, r) множества обладает k_l альтернативами, то общее число чистых стратегий игрока равно

(3.1)

Определение 3.4. Будем говорить, что задана антагонистическая конечная позиционная игра Г, если заданы:

а) позиционная структура С;

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

В том случае, если в игре не участвует игрок 0 (природа, случай), выбор первым игроком чистой стратегии x, а вторым игроком – чистой стратегии y однозначно определяет исход игры, т. е. упорядоченная пара τ = (x, y) приводит к i-й окончательной вершине и первый игрок получает выигрыш M(t). Если в игре участвует игрок 0 (природа, случай), то пара τ определяет распределение вероятностей на множестве

T={t₁, t₂,…, t_s} окончательных вершин

P(τ, t) ≥ 0, , (3.2)

где P (τ, t) – вероятность того, что партия закончится в вершине .

Распределение вероятностей P (τ, t) естественным образом приводит к математическому ожиданию выигрыша первого игрока, которое определяется следующим образом:

, (3.3)

где - выигрыш первого игрока в окончательной позиции t_i , а |T| - число окончательных позиций.

На основе изложенного выше можно придти к заключению, что каждая пара чистых стратегий игроков 1 и 2 приводит к некоторой ситуации, в которой первый игрок получает определенный выигрыш или математическое ожидание выигрыша. На множестве пар чистых стратегий задана функция H, которая указывает выигрыш или математическое ожидание выигрыша первого игрока, если игроки будут применять данные чистые стратегии. Это функция выигрыша игрока 1 [9].