Главная / Основы оптимизационных методов / Методы решения конечных игр

Методы решения конечных игр

Перед тем, как решать игру M×N, нужно, прежде всего, попытаться ее упростить, избавившись от лишних стратегий. Это делается подобно тому, как мы когда-то отбрасывали заведомо невыгодные решения в § 6. Введем понятие «доминирования». Стратегия AI Игрока А называется доминирующей над стратегией АK, если в строке AI стоят выигрыши не меньшие, чем в соответствующих клетках строки AK, и из них по крайней мере один действительно больше, чем в соответствующей клетке строки АK. Если все выигрыши строки Ai, равны соответствующим выигрышам строки Ak, то стратегия АI называется дублирующей стратегию Ak. Аналогично определяются доминирование и дублирование для стратегий игрока В: доминирующей называется та его стратегия, при которой везде стоят выигрыши не большие, чем в соответствующих клетках другой, и по крайней мере один из них действительно меньше; дублирование означает полное повторение одного столбца другим. Естественно, что если для какой-то стратегии есть доминирующая, то эту стратегию можно отбросить; также отбрасываются и дублирующие стратегии.

Поясним сказанное примером. Пусть игра 5×5 задана матрицей таблицы 27.1.

Таблица 27.1

Bj

Ai

B1

B2

B3

B4

B5

A1

A2

A3

A4

A5

4

3

4

3

3

7

5

4

6

5

2

6

2

1

6

3

8

2

2

8

4

9

8

4

9

Прежде всего заметим, что в ней стратегия A5 дублирует стратегию А2, поэтому любую из них можно отбросить. Отбрасывая A5, замечаем, что в строке А1 Все выигрыши больше (или равны) соответствующим выигрышам строки А4 значит А1 доминирует над A4. Отбросим A4 и получим матрицу 3×5 (таблица 27.2).

Но это еще не все! Приглядевшись к таблице 27.2, замечаем, что в ней некоторые стратегии игрока В доминируют над другими: например, B3 над B4, и В5, a B1Над стратегией В2 (не забудьте, что В стремится отдать поменьше!).

Таблица 27.2

Bj

Ai

B1

B2

B3

B4

B5

A1

A2

A3

4

3

4

7

5

4

2

6

2

3

8

2

4

9

8

Отбрасывая столбцы B2, В4, В5, получаем игру 3×2 (таблица 27.3).

Наконец, в таблице 27.3 строка А3 дублирует А1, Поэтому ее можно отбросить. Окончательно получим игру 2×2 (таблица 27.4).

Таблица 27.3

Bj

Ai

B1

B3

A1

A2

A3

4

3

4

2

6

2

Таблица 27.4

Bj

Ai

B1

B3

A1

A2

4

3

2

6

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

В руководствах по теории игр обычно останавливаются на решении простейших игр 2×2, 2×П И т×2, которое допускает геометрическую интерпретацию, но мы этого делать не будем — сразу возьмем «быка за рога» и покажем, как можно решить любую игру Т×п.

Пусть имеется игра Т×п без седловой точки с матрицей (АIj) (см. таблицу 27.5).

Таблица 27.5

Ai

Bj

B1

B2

Bn

A1

A2

Am

A11

A21

Am1

A12

A22

Am2

A1n

A2n

Amn

Допустим, что все выигрыши АIj положительны (этого всегда можно добиться, прибавляя ко всем членам матрицы достаточно большое число М; от этого цена игры увеличится на М, а решение не изменится). Если все Aij Положительны, то конечно, и цена игры, т. е. средний выигрыш при оптимальной стратегии, тоже положителен: V > 0.

Мы хотим найти решение игры, т. е. две оптимальные смешанные стратегии

(27.1)

Дающие каждой стороне максимально возможный для нее средний выигрыш (минимальный проигрыш).

Найдем сначала Мы знаем, что если один из игроков (в данном случае это А) применяет свою оптимальную стратегию, то другой (В) не может улучшить свое положение, отступая от своей. Заставим противника (В) отступать от своей оптимальной стратегии, пользуясь чистыми стратегиями В1, B2, …, ВN (а мы тем временем упорно держимся стратегии ). В любом случае наш выигрыш будет не меньше, чем V:

(27.2)

Разделим неравенства (27.2) на положительную величину V и введем обозначения:

(27.3)

Тогда условия (27.2) примут вид

(27.4)

Где X1, X2,..., XmНеотрицательные переменные. В силу (27.3) и того, что P1 + р2 + ... + РM = 1, переменные X1, X2,…, хM удовлетворяют условию

Х1, + х2, + … + Xm = . (27.5)

Но V есть не что иное, как наш гарантированный выигрыш, естественно, мы хотим сделать его максимальным, а значит, величину — минимальной.

Таким образом, задача решения игры свелась к математической задаче: найти неотрицательные значения переменных Х1, х2, …, Xm такие, чтобы они удовлетворяли линейным ограничениям-неравенствам (27.4) и обращали в минимум линейную функцию этих переменных:

L = Х1, + х2, + … + Xm => min. (27.6)

«Ба! — скажет читатель, — что-то знакомое!» И точно — перед нами не что иное, как Задача линейного программирования. Таким образом, задача решения игры Т×П свелась к задаче линейного программирования с N ограничениями-неравенствами и Т переменными. Зная X1, X2, …, Xm, можно по формулам (27.3) найти P1, р2, …, рM и, значит, оптимальную стратегию и цену игры V.

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

Таким образом, решение игры M×П эквивалентно решению задачи линейного программирования. Нужно заметить, что и наоборот, — для любой задачи линейного программирования может быть построена эквивалентная ей задача теории игр (на том, как это делается, мы останавливаться не будем). Эта связь задач теории игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения игр, которые в некоторых случаях (при большой размерности задачи) оказываются проще, чем «классические» методы линейного программирования.

Опишем один из самых простых численных методов решения игр — так называемый метод итераций (иначе — метод Брауна — Робинсон). Идея его в следующем. Разыгрывается «мысленный эксперимент», в котором стороны А и В поочередно применяют друг против друга свои стратегии, стремясь выиграть побольше (проиграть поменьше). Эксперимент состоит из ряда «партий» игры. Начинается он с того, что один из игроков (скажем, А) выбирает произвольно одну из своих стратегий Ai. Противник (В) отвечает ему той из своих стратегий Bj которая хуже всего для А, т. е. обращает его выигрыш при стратегии 4, в минимум. Дальше снова очередь А —Он отвечает В той своей стратегией АK, которая дает максимальный выигрыш при стратегии ВJ Противника. Дальше — снова очередь противника. Он отвечает нам той своей стратегией, которая является наихудшей не для последней, примененной нами, стратегии АK, а для смешанной стратегии, в которой до сих пор примененные стратегии Ai, Ak встречаются с равными вероятностями. И так далее: на каждом шаге итерационного процесса каждый игрок отвечает на очередной ход другого Той своей стратегией, которая является оптимальной для него относительно смешанной стратегии другого, в которую все примененные до сих пор стратегии входят пропорционально частотам их применения. Вместо того чтобы вычислять каждый раз средний выигрыш, можно пользоваться просто «накопленным» за предыдущие ходы выигрышем и выбирать ту свою стратегию, при которой этот накопленный выигрыш максимален (минимален). Доказано, что такой метод сходится: при увеличении числа «партий» средний выигрыш на одну партию будет стремиться к цене игры, а частоты применения стратегий — к их вероятностям в оптимальных смешанных стратегиях игроков.

Впрочем, лучше всего можно понять итерационный метод на конкретном примере. Продемонстрируем его на примере игры 3×3 предыдущего параграфа (таблица 26.5). Чтобы не иметь дела с отрицательными числами, прибавим к элементам матрицы таблицы 26.5 число 5 (см. таблицу 27.6); при этом цена игры увеличится на 5, а решение не изменится.

Начнем с произвольно выбранной стратегии игрока А, — например, со стратегии А3. В таблице 27.7 приведены первые 15 шагов итерационного процесса по методу Брауна — Робинсон (читатель может самостоятельно продолжить расчеты).

Таблица 27.6

Bj

Ai

B1

B2

B3

A1

A2

A3

7

2

9

2

9

0

9

0

11

В первом столбце дан номер партии (пары выборов) K, во втором — номер I выбранной в данной партии стратегии игрока А. В последующих трех столбцах — «накопленный выигрыш» за первые K Партий при тех стратегиях, которые применяли игроки в предыдущих партиях и при стратегиях В1, В2, B3 игрока В в данной партии (получается прибавлением элементов соответствующей строки к тому, что было строкой выше). Из этих накопленных

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

Таблица 27.7

K

I

B1

B2

B3

J

A1

A2

A3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

3

2

2

2

1

3

1

2

2

1

3

2

2

1

3

9

11

13

15

22

31

38

40

42

49

58

60

62

69

78

0

9

18

27

29

29

31

40

49

51

51

60

69

71

71

11

11

11

11

20

31

40

40

40

49

60

60

60

69

80

2

2

3

3

3

2

2

2

3

1

2

2

3

1

2

2

4

13

22

31

33

35

37

46

53

55

57

66

73

75

9

18

18

18

18

27

36

45

45

47

56

65

65

67

76

0

0

11

2

33

33

33

33

44

53

53

53

64

73

73

0

4,5

3,67

2,75

4,00

4,84

4,43

5,00

4,45

4,90

4,64

5,00

4,61

4,93

4,74

9

9

6

5,50

6,60

5,50

5,14

5,61

5,11

5,30

5,09

5,41

5,07

5,21

5,06

4,5

6,75

4,84

4,13

5,30

5,17

4,79

5,30

4,78

5,10

4,87

5,20

4,84

5,07

4,90

Трех столбцах дается накопленный выигрыш за K партий соответственно при стратегиях А1, А2, А3 игрока А (получается прибавлением элементов столбца ВJ к тому, что было строкой выше). Из этих значений в таблице 27.7 «надчеркнуто» максимальное; оно определяет выбор стратегии игрока А в следующей партии (строкой ниже). В последних трех столбцах таблицы 27.7 даны:

нижняя оценка цены игры, равная минимальному накопленному выигрышу, деленному на числа партий K;

* верхняя оценка цены игры, равная максимальному накопленному выигрышу, деленному на K;

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

Как видно, величина V* незначительно колеблется около цены игры V = 5 (цена исходной игры была 0, но мы прибавили к элементам матрицы по 5). Подсчитаем по таблице 27.7 частоты стратегий игроков. Получим:

Что не так уж сильно отличается от вероятностей P1, P2, P3, Q1, Q2, Q3, равных, как мы указывали раньше, для первой, второй и третьей стратегий соответственно 1/4 = 0,25, 1/2 = 0,50, 1/4 = 0,25. Такие сравнительно хорошие приближения мы получили уже при 15 итерациях — это обнадеживает! К сожалению, дальше процесс приближений будет идти не так резво. Сходимость метода Брауна — Робинсон, как показывает опыт, очень медленная, Существуют способы, позволяющие как бы «подхлестнуть» еле плетущийся процесс, но мы на них останавливаться не будем.

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