Платежная матрица антагонистической игры,

Принцип минимакса

Будем считать, что у игрока A всего m стратегий, а у игрока B – n стратегий.

1 2 n

1 2 m

B B ...........B

A A ..........A

Таблица 41

B1 B2 . Bn

. . .

Аm am1 11 a .amn

Если игрок А применяет свою

стратегию Аi, а В применяет Bj, то

выигрыш в игре составляет aij. А

старается увеличивать выигрыш, а

В – уменьшить эту величину. Ве-

личины aij образуют матрицу, ко-

торая называется платежной мат-

рицей .

Рассмотрим пример простейшей игры «Поиск».

Игрок А прячется в двух местах I

и II. Игрок В ищет игрока А в местах I

и II. Если В находит А, то А платит

ему 1 рубль, если не находит, то В

платит 1 рубль игроку А.

Платежная матрица – Таблица 42.

Таблица 42

B1 B2

А1-1 1

А21 -1 Основой для анализа игр является анализ платежной матрицы. Поэтому

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

матричными играми.

Для игр с полной информацией, т. е. когда один игрок знает, как посту-

пил второй, всегда можно построить платёжную матрицу.

Основным принципом, которым необходимо пользоваться для объектив-

ной оценки игровой ситуации, является следующий подход: противник на-

столько же разумен, как и мы, и делает все, чтобы использовать свои воз-

можности против нас, т. е. активно противодействует в выборе оптимального

решения. Задачей теории игр является обоснование оптимальных стратегий

обоих игроков.

Если игрок А будет применять любое сколь угодно сложное правило че-

редования мест I и II, то В все равно разгадает этот закон чередования и бу-

дет выигрывать. Ниже мы обоснуем оптимальные стратегии игроков А и В.

Рассмотрим другие простые примеры игр.

Игра «Три пальца».

Таблица 43

B1 B2 B3

А12 -3 4

А2-3 4 -5

А34 -5 6

Игрок А и игрок В одновре-

менно показывают один, два или

три пальца. Выигрыш равен сум-

ме, причём выигрывает А, если

сумма очков четная, и _______В, если

сумма нечетная. Построим пла-

тёжную матрицу.

Игра «Конкуренты».

Таблица 44

B1 B2 B3

А1-2 -2 1

А21 0 2

А30 -1 1

Фирма А может поставить на

рынок три товара A1, A2, A3, а

фирма В три своих конкурирую-

щих товара B1, B2, B3. Если фирма

А поставит товар Ai, а фирма В -

товар Bj, то в результате выигрыш

в доходах фирм определяется при-

веденной платежной матрицей.

Возникает вопрос – как на основе анализа матрицы найти оптимальное

решение игры, и что понимать под оптимальным решением игры?

Рассмотрим так называемый принцип минимакса при решении игры.

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

необходимо, чтобы мы больше всего реагировали на опасные для нас ходы

со стороны противника. По отношению к игроку А рассуждаем так, что если

он применит стратегию A1, то можно зафиксировать самый плохой для него

выигрыш: a1 = min aij. Для стратегии A2: a2 = min a2j., и так далее.

Для Am: am = min amj.

Тогда естественно, что игрок А выберет ту стратегию, для которой вели-

чина ai будет максимальной (по строкам в платежной матрице).

Величина maxmin i j ij

a = a называется нижней ценой игры. Она показыва-

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

подходе к игре. Аналогично рассуждая относительно игрока В, получаем ве-

личины:

max j ij b = a - максимальные величины в столбцах, и затем

maxmin i j ij

b = a - верхняя цена игры.

Эта величина показывает, больше какой величины не может быть выиг-

рыш в игре.

Получим значения a и b для вышеприведенных игр.

Для игры «Поиск» a = -1; b =1.

Для игры «Три пальца» a = -3; b =4.

Для игры «Конкуренты» a = b =0.

Эта игра обладает седловой точкой, так как в ней максимин совпадает с

минимаксом. Принятие стратегий, соответствующих седловой точке, взаи-

моприемлемо для обоих игроков, поэтому их можно принять за оптимальное

решение игры. Таким образом, пара стратегий (A2, B2) является оптималь-

ным решением игры «Конкуренты». Оптимальный выигрыш в этой игре на-

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

Если игра имеет седловую точку, то говорят, что игра решается в чистых

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

устойчивости: если один игрок примет оптимальную стратегию, то другому

невыгодно отклоняться от своей оптимальной стратегии. (Проверьте это,

рассмотрев строку A2 и столбец B2). Такое свойство устойчивости положено

в основу понятия оптимального решения любой игры.