Позиционные игры

3. Позиционные игры

3.1. Общие сведения

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

Позиционные игры должны включать следующие элементы описания:

         последовательность личных и случайных ходов игроков;

         выборы, которые могут делать игроки при каждом личном ходе;

         исходы случайных ходов и распределение вероятностей этих исходов;

         информацию, доступную игрокам при выполнении личного или случайного хода;

         правила окончания игры и подсчеты выигрыша игроков.

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

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

3.2.                  Задание позиционной игры в виде дерева

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

Рис.3.1.

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

         дерево содержит одну единственную начальную вершину (“корень” дерева), в который не входит ни одна ветвь;

         дерево имеет не менее одной вершины, из которой не выходит ни одна ветвь. Эти вершины называются конечными вершинами;

         из корня дерева имеется единственный путь к каждой из остальных вершин дерева.

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

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

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

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

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

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

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

Игрок всегда знает, какому классу информации соответствует состояние игры в данный момент, но не знает конкретной вершины этого класса.

Классы информации (информационные множества) должны удовлетворять следующим условиям:

1.   содержать вершины только одного игрока;

2.   каждая вершина может принадлежать только одному классу информации;

3.   вершины класса информации соответствуют только одному временному ходу;

4.   из всех вершин, составляющих класс информации, может выходить  только одинаковое количество ветвей.

Дерево, изображенное на рис.3.1., соответствует следующей игры:

Первый игрок выбирает одно из двух направлений (“налево” или “направо”). Ход “налево” оценивается двумя баллами, а “направо” - одним. Затем бросается жребий (монета) и, если выпадает герб, второму игроку сообщается предыдущий выбор первого игрока. Если выпадает решка, то второй игрок знает лишь, что он находится в классе информации V1, но не знает в какой из двух вершин этого класса он находится.

Второй игрок выбирает одно из двух направлений (“налево” или “направо”). Ход “налево” оценивается четырьмя баллами, а “направо” - тремя. Четвертый ход является опять случайным и состоит в выборе с равными вероятностями одного из направлений: “налево”, “прямо”, “направо”, которые оцениваются тремя, двумя и одним баллом соответственно. Поскольку вероятности выбора направления при случайном ходе одинаковы (равны ), то их можно на графическом изображении дерева игры и не указывать.

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

Пространства Ф1 и Ф2 всех возможных стратегий игроков 1 и 2 в рассматриваемом примере следующие:

Ф1=|(1), (2)|;

Ф2=|(1,3,3),(1,3,4),(1,4,3),(1,4,4),(2,3,3),(2,3,4),(2,4,3),(2,4,4)|

где первое число каждой стратегии в пространстве Ф2 соответствует выбору первого игрока, второе число - выпаданию герба или решки (“3” - выпал “герб”; “4” - выпала “решка”). Третья - выбору второго игрока тройки или четверки.

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

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

3.3. Нормализация позиционной игры

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

Рис. 3.2

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

В данной игре у первого игрока (игрока А) имеется две чистых стратегии: Ф1=/А1 А2/, где стратегия А1 - всегда выбирать левую ветвь; стратегия А2 - всегда выбирать правую ветвь. Второй игрок (игрок В) имеет больше стратегий:

Ф2=/В1,В2,В3,В4/,

где стратегия В1 - всегда выбирать левую ветвь;

      стратегия В2 - всегда выбирать правую ветвь;

      стратегия В3 - выбирать ветвь, которую выбрал игрок А;

      стратегия В4 - выбирать ветвь, противоположную той, которую выбрал игрок А.

Матрица игры в этом случае имеет вид

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

Действительно, так как

;

.

и, следовательно, .

Поэтому SA=||1,0| или SA=||0,1||, а  SB=||0,0,0,1||. Цена игры v=-2.

Допустим, что в рассматриваемом примере второму игроку не сообщается выбор, сделанный первым игроком. Тогда в дереве игры на втором ходе появляется класс информации V1, содержащей две вершины второго игрока (рис.3.3.)

Рис. 3.3

Количество чистых стратегий второго игрока по сравнению с первым случаем сократится до двух: Ф2=/В1,В2/,

где В1 - всегда выбирать левую ветвь;

      В2 - всегда выбирать правую ветвь.

Процесс нормализации приводит к следующей платежной матрице: