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

Рассмотрим конечную парную игру с нулевой суммой. Игрок I имеет m стратегий (А1, А2, ..., Аm), а игрок II — n стратегий (В1, В2, ..., Вn). Такая игра называется игрой размерностью m ´ n. Пусть каждая сторона определилась с выбором стратегии: игрок I — Ai (i = 1, 2, ..., m), игрок II — Bj (j = 1, 2, ..., n). Выигрыши игрока I — (Ai, Bj) и игрока II — (Ai, Bj) удовлетворяют соотношению (Ai, Bj) + (Ai, Bj) = 0.

Если игра состоит только из личных ходов, то выбор стратегии (Ai, Bj) однозначно определяет исход игры , т. е. выигрыш игрока I. Если игра содержит также случайные ходы, то выигрыш при паре стратегий (Ai, Bj) есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае ожидаемый выигрыш — это среднее значение (математическое ожидание). Предположим, что значения aij известны для каждой пары стратегий (Ai, Bj). Построим таблицу, строки которой соответствуют стратегиям игрока I, а столбцы — стратегиям игрока II, т. е. платежную матрицу. Каждый элемент (aij > 0) матрицы определяет величину выигрыша игрока I и проигрыш игрока II. Цель игрока I — максимизировать свой выигрыш, а игрока II — минимизировать свой проигрыш. Платежная матрица имеет следующий вид:

I \ II B1 B2 ... Bj... Bn

A1 a11 a12 ... a1j... a1n a1

A2 a21 a22 ... a2j... a2n a2

... ... ... ... ... ... ... ...

Ai ai1 ai2 ... aij... ain ai

... ... ... ... ... ... ... ...

Am am1 am2 ... amj... amn am

Βj b1 b2 ... bj... bn

Задача состоит в определении:

1) наилучшей (оптимальной) стратегии игрока I из стратегий A1, A2, ..., Am;

2) наилучшей (оптимальной) стратегии игрока II из стратегий B1, B2, ..., Bm.

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

Проанализируем последовательно каждую стратегию игрока I. Если игрок I выбирает стратегию А1, то игрок II может выбрать такую стратегию Bj, при которой выигрыш игрока I будет равен наименьшему из чисел a1j:

.

Выбирая стратегию Ai, игрок I должен рассчитывать на то, что в результате разумных действий игрока II он не выиграет больше, чем ai. Поэтому игрок I должен выбрать ту стратегию, для которой ai максимально:

.

Величина a — гарантированный выигрыш, который может обеспечить себе игрок I при любом поведении игрока II. Величина a называется Нижней ценой игры или Максимином, а стратегия Аi игрока I, обеспечивающая получение нижней цены игры, называется максиминной чистой стратегией. При этом игрок I при любом поведении игрока II обеспечивает себе выигрыш, не меньше a: ai ³ a (i = 1, 2, ..., m).

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

.

И среди этих значений выбрать наименьшее: .

Величина b называется Верхней ценой игры или Минимаксом. Стратегия игрока II, обеспечивающая получение верхней цены игры, называется минимаксной чистой стратегией. Применяя ее, игрок II проиграет не больше b при любых действиях игрока I:

Bj £ b (j = 1, 2, ..., n), причем всегда справедливо неравенство a £ b.

Таким образом, придерживаясь максиминной стратегии Ai, игрок I желает получить выигрыш не менее a не зависимо от действий игрока II, а игрок II, придерживаясь минимаксной стратегии Bj, гарантирует себе проигрыш не больше b.

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

Пример 1. Дана платежная матрица. Найти решение игры: определить нижнюю и верхнюю цены игры и минимаксные стратегии:

I \ II B1 B2 B3 B4 a

A1 5 3 8 2 2

A2 1 6 4 3 1

A3 9 5 4 7 4

Βj 9 6 8 7

Таким образом, нижней цене игры (a = 4) соответствует стратегия A3 игрока I. Выбирая эту стратегию, игрок I достигнет выигрыша не меньше 4 при любом поведении игрока II. Верхней цене игры (b = 6) соответствует стратегия игрока II — В2. Эти стратегии являются минимаксными. Если обе стороны будут придерживаться этих стратегий, выигрыш будет равен А33 = 4.

Существуют матричные игры, для которых нижняя цена игры равна верхней, т. е. a = b. Такие игры называются играми с седловой точкой.

В этом случае g = a = b называется чистой ценой игры, а стратегии игроков и , позволяющие получить это значение — оптимальными. Пара называется седловой точкой матрицы, так как элемент Одновременно является минимальным в i-й строке и максимальным в j-м столбце. Оптимальные стратегии и и чистая цена являются решением игры в чистых стратегиях, т. е. без привлечения механизма случайного выбора.

Пример 2. пусть задана платежная матрица. Найти нижнюю и верхнюю цены игры.

I II B1 B2 B3 a

A1 5 1 2 1

A2 2 6 2 2

A3 3 4 3 3

B 5 6 3

Следовательно a = b = g = 3.

Седловой точкой является пара альтернатив (А3, В3).

< Предыдущая		Следующая >