Приближенные методы решения игр

⇐ ПредыдущаяСтр 3 из 3

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

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

Идея метода итераций сводится к следующему. Разыгрывается "мысленный эксперимент", в котором противники А и В применяют друг против друга свои стратегии. Эксперимент состоит из последовательности элементарных игр, каждая из которых имеет матрицу заданной игры. Начинается с того, что мы (игрок А) выбираем произвольно одну из своих стратегий, например A_i. Противник на это отвечает той своей стратегией B_j, которая наименее выгодна для нас, т.е. обращает выигрыш при стратегии А_i в минимум. На этот ход мы отвечаем той своей стратегией А_k, которая дает максимальный средний выигрыш при применении противником стратегии B_j. Далее - снова очередь противника. Он отвечает на нашу пару ходов A_i и A_k той своей стратегией B_s, которая дает нам наименьший средний выигрыш при этих двух стратегиях (A_i, А_k), и так далее. На каждом шаге итерационного процесса каждый игрок отвечает на любой ход другого игрока той стратегией, которая является оптимальной относительно всех его предыдущих ходов, рассматриваемых как некоторая смешанная стратегия.

Если такой процесс продолжать достаточно долго, то средний выигрыш, приходящийся на одну пару ходов (элементарную игру), будет стремиться к цене игры, а частоты p₁,...,p_n; q₁,...,q_m, с которыми встречаются стратегии игроков в этом розыгрыше, будут приближаться к частотам, определяющим оптимальные стратегии.

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

Проиллюстрируем применение метода на примере игры 3×3, с матрицей:

В А	В₁	В₂	В₃
А₁	8	2	4
А₂	4	5	6
А₃	1	7	3

В таблице 3.5 приведены первые 18 шагов итерационного процесса.

В первом столбце дан номер элементарной игры (пары ходов) n; во втором - номер i выбранной стратегии игрока A; в последующих трех - "накопленный выигрыш" за первые n игр при стратегиях противника В₁, В₂,В₃. Минимальное из этих значений отмечено значком *.

Таблица 3.5

n	i	B₁	B₂	B₃	j	A₁	A₂	A₃	V'	V"	V*
1	3	1*	7	3	1	8*	4	1	1	8	4,50
2	1	9	9	7*	1	12*	10	4	3,5	6	4,45
3	1	17	11*	11	2	14	15*	11	3,67	5,00	4,33
4	2	21	16*	17	2	16	20*	18	4,00	5,00	4,50
5	2	25	21*	23	2	18	25*	25	4,20	5,00	4,60
6	2	29	26*	29	2	20	30	32*	4,33	5,33	4,82
7	3	30*	33	32	1	28	34*	33	4,29	4,86	4,57
8	2	34*	38	38	1	36	38*	34	4,25	4,75	4,50
9	2	38*	43	44	1	44*	42	35	4,23	4,89	4,56
10	1	46	45*	48	2	46	47*	42	4,50	4,70	4,60
11	2	50*	50	54	1	54*	51	43	4,55	4,91	4,72
12	1	58	52*	58	2	56	56*	50	4,33	4,66	4,49
13	2	62	57*	64	2	58	61*	57	4,38	4,70	4,54
14	2	66	62*	70	2	60	66*	64	4,43	4,71	4,56
15	2	70	67*	76	2	62	71	71*	4,47	4,73	4,60
16	3	71*	74	79	1	70	75*	72	4,44	4,69	4,56
17	2	75*	79	85	1	78	79*	73	4,41	4,65	4,53
18	2	79*	84	91	1	86*	83	74	4,39	4,78	4,58
…	…	…	…	…	…	…	…	…	…	…	…

Далее идет номер j стратегии, выбранной противником, и, соответственно, накопленный выигрыш за n игр при стратегиях А₁, А₂, А₃; из этих значений отмечено максимальное. Отмеченные значения определяют выбор ответной стратегии другого игрока. В следующих графах последовательно приведены: минимальный средний выигрыш V', равный минимальному накопленному выигрышу, деленному на число игр n; максимальный средний выигрыш V'', равный максимальному накопленному выигрышу, деленному на n, и их среднее арифметическое V* = (V' + V'')/2. При увеличении n все три величины V', V'' и V* будут приближаться к цене игры n, но величина V*, естественно, будет приближаться к ней сравнительно быстрее.

Преимущество итерационного метода решения игр в том, что объем и сложность вычислений сравнительно слабо возрастают по мере увеличения числа стратегий n и m.

Примеры решения конечных игр

В смешанных стратегиях

Пример 3.1. Найдем решение игры 2´2, рассмотренной ранее в примере 2.2 раздела 2 (выкладывание монет) с матрицей

В А	В₁	В₂	a_i
А₁	1	-1	-1
А₄	-1	1	-1
b_j	1	1

Проверим наличие седловой точки a=max (-1; -1)=-1

b =min (1; 1)=1

Игpa не имеет седловой точки и, следовательно, решение должно лежать в области смешанных стратегий:

А₁ А₂ В₁ В₂

S*_A = S*_B =

p₁ p₂ q₁ q₂

Нужно найти р₁, р₂, q₁, q₂.

Для определения р₁ и p₂ имеем уравнения :

1·р₁ + (-1)·p₂ = n;

(-1)·р₁ + 1·р₂ = n;

p₁ + p₂ = 1

т.е. p₁ - (1-p₁) = -p₁ + (1-p₁) или 4·p₁ = 2

откуда р₁ = 1/2; р₂ = 1/2; n = 0.

Аналогично найдем: q₁ = 1/2; q₂ = 1/2.

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

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

Пример 3.2. Найти геометрическим и аналитическим методами в смешанных стратегиях решение конечной игры, заданной следующей матрицей:

В А	В₁	В₂	В₃	В₄	В₅
А₁	2	-1	0	1	3
А₂	-3	4	2	2	-1

Решение. Прежде всего, исключим “лишние” стратегии игрока В.

Как видно из матрицы, дублирующих стратегий у игрока В нет, стратегия В₄ уступает стратегии В₃, стратегия В₅ уступает стратегии В1. То есть, можем исключить стратегии В₄ и В₅. Получили игру 2´3. Теперь убедимся в том, что в игровой матрице нет седловых точек. Для этого вычислим нижнюю и верхнюю цены игры a= max (-1, -3) = -1,

b = min (2, 4, 2) = 2

и приходим к выводу a¹b.

Следовательно, решение игры необходимо искать в области смешанных -стратегий.

B₂

B₃

B₄

B₁

B₅

-1 0,2 0,4 0,6 0,8

-2

-3

Рис. 3.9

Рассмотрим стратегию В₁: она дает на осях I-I и II-II две точки с ординатами а₁₁=2 и а₂₁=-3 (рис. 3.9). Соединим эти точки прямой B₁. Стратегия В₂ дает точки с ординатами а₁₂=-1, а₂₂ = 4. Соединим прямой В₂. Аналогично, строим графики стратегий В₃, В₄, В₅. Нижняя граница выигрыша - минимальный выигрыш - ломаная МNP. Точка N, в которой этот минимальный выигрыш достигает максимума, определяет решение и цену игры.