Методы и модели игры

Впрочем, возможны и иные подходы  к разбиению игр.

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

Часть II ПОЗИЦИОННЫЕ ИГРЫ

 

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

1. Структура  позиционной игры

 

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

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

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

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

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

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

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

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

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

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

Рис. 2

В каждой окончательной позиции  задан числовой выигрыш игрока А.

Замечание. Мы будем рассматривать здесь только антагонистические позиционные игры.

В шахматах функция выигрышей игрока А (белых) определяется так:

+1 на выигрываемых партиях,

0 на ничейных партиях, 

-1 на проигрываемых партиях.

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

Различают позиционные  игры с полной информацией и позиционные игры с неполной информацией.

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

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

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

Позиции, принадлежащие  одному и тому же информационному  множеству, объединяются пунктирными  линиями.

Рассмотрим примеры двух игр, состоящих из двух ходов, которые последовательно делают участвующие в ней игроки А и В. Начинает игрок А: он выбирает одну из двух возможных альтернатив — число х, равное либо 1 (первая альтернатива), либо 2 (вторая альтернатива). На ход игрока А игрок В отвечает своим ходом, выбирая одну из двух возможных альтернатив — число у, равное либо 1 (первая альтернатива), либо 2 (вторая альтернатива).

И в результате игрок А получает вознаграждение или вынужден платить штраф.

Пример 13.

1-й ход. Игрок А выбирает число х из множества двух чисел {1, 2}.

2-й ход. Игрок В выбирает число у из множества двух чисел {1,2}, зная выбор числа х игроком А.

Функция W(x, у) выплат игроку А за счет игрока В задается так

W(l, l) =   1,      W(2, l) = -2,

W(l, 2) = -l,       W(2, 2)=   2.

На рис. 3 показаны дерево игры и  информационные множества.

Рис. 3 Рис.4

Пример 14. В случав, вели выполнены все условия предыдущего примера, кроме одного — хода игрока В.

2-й ход — игрок В выбирает число у из множества двух чисел {1, 2}, не зная выбора числа х игроком А, информационные множества выглядят так, как показано на рис. 4.

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

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

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

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

Покажем на нескольких примерах, как  это делается.

Пример 13 (продолжение). Опишем стратегии игроков.

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

Тем самым, у игрока А две чистых стратегии:

А₁ —выбрать х = 1,   А₂ — выбрать х = 2.

Стратегию игрока В, принимая во внимание, что выбор игрока А на 1-м ходе ему известен, удобно описывать упорядоченной парой

[y₁, y₂].

Здесь y₁ (y₁ = 1, 2) — альтернатива, выбираемая игроком В при условии, что игрок А выбрал первую альтернативу, х = 1, a y₂ (y₂ = 1, 2) — альтернатива, выбираемая игроком В при условии, что игрок А выбрал вторую альтернативу, х = 2.

Например, выбор  игроком В стратегии [2, 1] означает, что если на 1-м ходе игрок А выбрал х = 1, то игрок В на своем ходе должен выбрать у = 2. Если же на 1-м xoде игрок А выбрал х = 2, то согласно этой стратегии игрок В на своем ходе должен выбрать у = 1.

Таким образом, у игрока В четыре чистых стратегии:

В₁ — [1,1], у = 1 при любом выборе х;

В₂ — [1, 2], у = х при любом выборе х;

В₃ — [2,1], у ≠ х при любом выборе х;

В₄ — [2, 2], у = 2 при любом выборе х.

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

Пусть, например, игрок А выбрал стратегию А₁ — (1), а игрок В — стратегию В₂ — [1, 2]. Тогда х = 1, а из стратегии [1, 2] вытекает, что у = 1. Отсюда

W(х, y) = W(1, 1) = 1.

Остальные выигрыши рассчитываются совершенно аналогично.

Результаты расчетов записывается обычно или в виде таблицы выигрышей  игрока А

		В1	В2	В3	В4
		[1, 1]	[1, 2]	[2, 1]	[2, 2]
А1	х = 1	W(1, 1)	W(1, 1)	W(1, 2)	W(1, 2)
А2	х = 2	W(2, 1)	W(2, 2)	W(2, 1)	W(2, 2)

или в вида матрицы игры

,

где, как обычно, строки соответствуют  стратегиям игрока А, а столбцы — стратегиям игрока В,

Полученная матрица имеет седловую точку. Оптимальные стратегии игроков: А₁ — (1) и В₃ — [2, 1]. Тем самым, игрок А на 1-м ходе выбирает х = 1, а игрок В на 2-м ходе выбирает у = 2. Цена игры v =  -1.

Пример 14 (продолжение). Опишем стратегии игроков.

У игрока А они те же, что и в предыдущем примере

А₁ – выбрать х = 1,   А₂ — выбрать х = 2.

Так как игроку В выбор игрока А неизвестен, то есть игрок В не знает, в какой именно из двух позиций он находится (см. рис. 4), то у него те же две стратегии:

В₁ — выбрать у = 1,   В₂ — выбрать у = 2.

Соответствующие таблица выигрышей  игрока А и матрица игры имеют следующий вид

 

		В1	В2
		Y = 1	y = 2
А1	х = 1	W(1, 1)	W(1, 2)
А2	х = 2	W(2, 1)	W(2, 2)

Полученная  матрица седловой точки не имеет. Оптимальные смешанные стратегии игроков: Р = {2/3, 1/3} и Q = {1/2, 1/2}. Цена игры v = 0.

Замечание 1. На этих двух примерах хорошо видно, что результат сведения позиционной игры к матричной напрямую зависит от степени информированности игроков. В частности, отсутствие у игрока В сведений о выборе, сделанном игроком А приводит к уменьшению количества его возможных стратегий. Сравнивая, ответы, полученные в примерах 13 и 14, замечаем, что, снижение уровня информированности игрока (в данном случае — игрока В) делает для него исход игры менее, благоприятными.

 

Замечание 2. Приведенные выше примеры не исчерпывают всех возможных вариантов даже в этом, самом простом, случае двухходовых позиционных игр.

 

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

Пример 15.

1-й ход делает игрок А: он выбирает число х из множества двух чисел {1, 2}.

2-й ход делает игрок В: зная выбранное игроком А число х, он выбирает число у из множества двух чисел {1, 2}.

3-й ход делает игрок А: не зная о выбранном игроке В числе у на 2-м ходе и забыв выбранное им самим на 1-м ходе число х, он выбирает число z из множества двух чисел {1, 2}.

После этого игрок А получает вознаграждение W(x, у, z) за счет игрока В, например, такое:

W(1, 1, 1) = -2  W(2, 1, 1) =  3

W(1, 1, 2) =  4  W(2, 1, 2) =  0

W(1, 2, 1) =  1  W(2, 2, 1) = -3

W(1, 2, 2) = -4  W(2, 2, 2) =  5

На рис.5 показаны дерево игры и информационные множества.

Рис. 5

 

Нормализуем эту игру.

Поскольку игроку В выбор игрока А на 1-м ходе известен, то у игрока В те же четыре стратегии, что и в примере 13:

В₁ – [1, 1], В₂ – [1, 2], В₃ – [2, 1], В₄ – [2, 2].

Игрок А на 3-м ходе не знает предыдущих выборов — ни значения х, ни значения у. Поэтому каждая его стратегия состоит просто из пары чисел (х, z), где x (х = 1, 2) — альтернатива, выбираемая игроком А на 1-м ходе, а z (z = 1, 2) — альтернатива, выбираемая игроком А на 3-м ходе.

Например, выбор игроком А стратегии (2, 1) означает, что на 1-м ходе он выбирает x = 2, а на 3-м ходе — z = 1.

Таким образом, у игрока А четыре стратегии:

A₁ – [1, 1], A₂ – [1, 2], A₃ – [2, 1], A₄ – [2, 2].

Покажем теперь, как рассчитываются выигрыши игрока А в зависимости от стратегий, применяемых в данной игре. Пусть, например, игрок А выбрал стратегию A₂ — (1, 2), а игрок В — стратегию В₃ — (2, 1]• Тогда х = 1, откуда вытекает, что у = 2. Значение z = 2 выбрано игроком А независимо от выбора игрока В. Вычисляя значение функции выигрышей для этого набора, получаем

W(x, y, z) = W(1, 2, 2) = -4.

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

 

		В1	В2	В3	В4
		[1, 1]	[1, 2]	[2, 1]	[2, 2]
А1	(1, 1)	W(1, 1, 1)	W(1, 1, 1)	W(1, 2, 1)	W(1, 2, 1)
А2	(1, 2)	W(1, 1, 2)	W(1, 1, 2)	W(1, 2, 2)	W(1, 2, 2)
А3	(2, 1)	W(2, 1, 1)	W(2, 2, 1)	W(2, 1, 1)	W(2, 2, 1)
А4	(2, 2)	W(2, 1, 2)	W(2, 2, 2)	W(2, 1, 2)	W(2, 2, 2)