«Чистые» стратегии. Игра в чистых стратегиях

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

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

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

ν = α = β. ν > 0, то игрок А будет в выигрыше, если ν < 0, то в выигрыше игрок В. Если ν = 0, в этом случае игра справедлива для обоих игроков. Не все матричные игры имеют седловые точки.

Теорема: каждая игра с полной информацией имеет седловую точку и следовательно решает в чистых стратегиях, т.е. имеется пара устойчивых стратегий, дающих устойчивый выигрыш равный ν.Если матрица не имеет седловую точку, то цена игры лежит α<ν<β. Это означает, что первый игрок, используя максиминный принцип, обеспечит себе выигрыш не менее, чем α. А второй игрок придерживаясь минимаксного подхода обеспечит себе проигрыш не больше верхней цены игры. Игра будет оптимальна, если оба игрока будут применять смешанные стратегии.Случайная величина, значениями которой являются чистые стратегии, называется смешанной стратегией для этого игрока.

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

S A = || p 1 , p 2 …. p m || ,S B = || q1, q2 …. q m || , A: ∑ pi = 1 ,B: ∑ qi = 1

Игра может повторяться несколько раз, но в каждой партии игрок придерживается смешанной стратегии, где чистые стратегии придерживаются вероятности p i и q j .

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

Предположим что и игрок А и игрок В придерживаются смешанной стратегии. Необходимо определить А: ∑∑ a ij p i q j

Для игрока В ожидаемый проигрыш равен ожидаемому выигрышу игрока А. Выигрыш первого игрока и средний проигрыш второго игрока равны друг другу.

18.Методы решения конечной игры двух лиц порядка m*n.

Предположим, что все элементы платёжной матрицы 0≤aij. Тогда α≤ν≤β. Согласно основной теореме матричных игр, любая матричная игра имеет 2 оптимальные смешанные стратегии.

S A = (p 1 , p 2 , … , p n)

S B = (p 1 , p 2 , … , p n)

Решаем игру для игрока А, при этом предполагая что игрок В использует только чистые стратегии. Тогда

a 11 p 1 + a 21 p 2 + … + a m1 p m ≥ ν: B 1

a 12 p 1 + a 22 p 2 + … + a m2 p m ≥ ν: B 2 (1)

a 1n p 1 + a 2n p 2 + … + a mn p m ≥ ν: B n

X 1 = P 1 /ν , X 2 = P 2 /ν … X m = P m /ν

a 11 X 1 … + a m1 p m ≥ 1

a 1n X 1 … + a m1 p m ≥ 1 (2)

p 1 +p 2 +…+p m =1

X 1 +X 2 +…+X m = 1/ν (3)

L(x) = X 1 +X 2 +…+X m -> min (4)

Определим задачу линейного программирования.

ν = 1/(X 1 0 +X 2 0 …X m 0) (5)

P1 = X 1 0 *ν опт

p2 = X 2 0 *ν опт (6)

min L(x) = ∑x i

∑a ij: 1≤x i (7) (прямая задача)

0≤x i (i=1,2..)

a 11 q 1 + a 21 q 2 + … + a m1 q m < ν: A 1

a 21 q 1 + a 22 q 2 + … + a m2 q m < ν: A 2 (8)

a m1 q 1 + a m2 q 2 + … + a mn q m < ν: A m

Y 1 = q 1 /ν , Y 2 = q 2 /ν … Y m = q m /ν

q 1 +q 2 +…+q n =1

y 1 +y 2 +…+y n =1/ν

L(y)=∑y j -> max

∑a ij , y i ≤1 (i=1,2…) (9) (двойственная задача)

y 1 0 +y 2 0 …y m 0 = 1/ν опт

ν опт = 1/∑y m 0

Q1 = y 1 0 *ν опт

q2 = y 2 0 *ν опт

ν=1/∑x i = 1/∑y i = 1/min L(x) = 1/ max L(y) (11)

1) α = 1, β = 3

2) Нет упрощений.

L(x)=x 1 +x 2 +x 3 => min

x 1 +3x 2 +x 3 >= 1

2x 1 +x 2 +x 3 >=1

3x 1 +x 2 +x 3 >=1

x 1 =2/9, x 2 =2/9, x 3 =1/9

ν=1/(2/9+2/9+1/9)=9/5

p 1 =x 1 *ν=2/5

S A =(2/5, 2/5, 1/5)

двойственная задача

L(y) = y 1 +y 2 +y 3 => max

y 1 +2y 2 +3y 3 ≤ 1 y 1 =2/9

3y 1 +y 2 +y 3 ≤1 => y 2 =2/9 max L(y) = 5/9

y 1 +3y 2 +y 3 ≤1 y 3 =1/9

ν=1/(2/9+2/9+1/9)=9/5

q 1 =y 2 *ν=(2/9)*(9/5)=2/5

q 2 =(2/9)*(9/5)=2/5

q 3 =(1/9)*(9/5)=1/5

S B =(2/5, 2/5, 1/5)

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

Приближённый метод решения матричных игр mxn (Браун-Робинсон).

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

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

Определение. В антагонистической игре пара стратегий (А i , В j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.

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

Рассмотрим матричную игру G (3х4)

В этом примере нижняя цена игры равна верхней: ==9, т.е. игра имеет седловую точку.

Оказывается, что в этом случае максиминные стратегии А 2 и В 2 будут устойчивыми по отношению к информации о поведении противника.

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

Пара стратегий А 2 и В 2 обладает свойством устойчивости, а выигрыш (в рассматриваемом примере он равен 9), достигаемый при этой паре стратегий, оказывается седловой точкой платежной матрицы.

Признак устойчивости (равновесности) пары стратегии - это равенство нижней и верхней цены игры.

Стратегии А i и В j (в рассматриваемом примере А 2 , В 2), при котором выполняется равенство нижней и верхней цены игры, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях.

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

Если 0, то игра выгодна для игрока А, если 0 - для игрока В; при =0 игра справедлива, т.е. является одинаково выгодной для обоих участников.

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

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

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

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

Возникает вопрос: как найти решение игры, платежная матрица которой не имеет седловой точки? Применение максиминного принципа каждым из игроков обеспечивает игроку А выигрыш не менее, игроку - проигрыш не больше. Учитывая что, естественно для игрока А желание увеличить выигрыш, а для игрока В - уменьшить проигрыш. Поиск такого решения производит к необходимости применять смешанные стратегии: чередовать чистые стратегии с какими-то частотами.

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

Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его чистые стратегии.

Будем обозначать смешанные стратегии игроков А и В соответственно

S A =||p 1 , p 2 , ..., p m ||,

S B =||q 1 , q 2 , ..., q n ||,

где p i - вероятность применения игроком А чистой с тратегии А і ; ; q j - вероятность применения игроком В чистой стратегии B j ; .

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

Применение смешанных стратегий осуществляется, например, таким образом: игра повторяется много раз, но в каждой партии игрок применяет различные чистые стратегии с относительными частотами их применения, равными p i и q j .

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

Если игрок А применяет смешанную стратегию S A =||p 1 , p 2 , ..., p m ||, а игрок В смешанную стратегию S B =||q 1 , q 2 , ..., q n ||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением

Естественно, что ожидаемый проигрыш игрока В равен такой же величине.

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

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

Оптимальные чистые стратегии игроков отличаются от смешанных наличием обязательного единичного p i = 1, q i = 1. Например: P(1,0), Q(1,0). Здесь p 1 = 1, q 1 = 1.

Задача 1
По платёжной матрице найти оптимальные чистые стратегии, используя принцип строгого доминирования. В качестве ответа записать векторы P*, Q*.

Все задачи решаем с помощью калькулятора Матричная игра .

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

p 1 = 1
p 2 = 0
Цена игры, y = 1
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений
q 1 = 1
q 1 +q 2 = 1
Решая эту систему, находим:
q 1 = 1.
Ответ:
Цена игры: y = 1, векторы стратегии игроков:
Q(1, 0), P(1, 0)

∑a ij q j ≤ v
∑a ij p i ≥ v
M(P 1 ;Q) = (1 1) + (2 0) = 1 = v
M(P 2 ;Q) = (-2 1) + (-2 0) = -2 ≤ v
M(P;Q 1) = (1 1) + (-2 0) = 1 = v
M(P;Q 2) = (2 1) + (-2 0) = 2 ≥ v

Поскольку из исходной матрицы были удалены строки и столбцы, то найденные векторы вероятности можно записать в виде:
P(1,0,0,0)
Q(0,1,0,0)

Задача 2
По платёжной матрице найти нижнюю и верхнюю цену игры. При наличии седловой точки записать векторы оптимальных чистых стратегий P*, Q*.

Задача 3
По платёжной матрице найти векторы оптимальных стратегий P*, Q*и цену игры. Кто из игроков оказывается в выигрыше?

Максиминной оптимальной стратегии игрока A соответствует точка N, для которой можно записать следующую систему уравнений:
p 1 = 0
p 2 = 1
Цена игры, y = -2
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B 1 ,B 3 ,B 4 , которая дает явно больший проигрыш игроку B, и, следовательно, q 1 = 0,q 3 = 0,q 4 = 0.
-2q 2 = -2
q 2 = 1
Решая эту систему, находим:
q 2 = 1.
Ответ:
Цена игры: y = -2, векторы стратегии игроков:
Q(0, 1, 0, 0), P(0, 1)
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑a ij q j ≤ v
∑a ij p i ≥ v
M(P 1 ;Q) = (-6 0) + (-6 1) + (2 0) + (4 0) = -6 ≤ v
M(P 2 ;Q) = (2 0) + (-2 1) + (7 0) + (-1 0) = -2 = v
M(P;Q 1) = (-6 0) + (2 1) = 2 ≥ v
M(P;Q 2) = (-6 0) + (-2 1) = -2 = v
M(P;Q 3) = (2 0) + (7 1) = 7 ≥ v
M(P;Q 4) = (4 0) + (-1 1) = -1 ≥ v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.

Задача 4
Дайте развернутый ответ на вопрос