Платежная матрица. Нижняя и верхняя цена игры. Принцип минимакса
Найдем наилучшую стратегию игрока A
, для чего проанализируем последовательно все его стратегии. Выбирая стратегию A i
, мы должны рассчитывать, что игрок B
ответит на нее такой стратегией B j
,
для которой выигрыш A
будет минимальным. Поэтому среди чисел первой строки выбираем минимальное, обозначим его , запишем его в добавочный столбец. Аналогично для каждой стратегии A i
выбираем , т.е.
α i
– минимальный выигрыш при применении стратегии A i
.
В примере 1:
α 1
= min {0, –1, –2} = –2;
α 2
= min {1, 0, –1} = –1;
α 3
= min {0, –1, –2} = 0.
Эти числа запишем в добавочном столбце. Какую же стратегию должен выбрать игрок A
? Конечно же, ту стратегию, для которой α i
максимально. Обозначим . Это гарантированный выигрыш, который может обеспечить себе игрок A
, т.е.
; этот выигрыш называется нижней ценой игры
или максимином
. Стратегия
A i
, обеспечивающая получение нижней цены игры, называется максиминной
(перестраховочной). Если игрок A
будет придерживаться этой стратегии, то ему гарантирован выигрыш ≥α
при любом поведении игрока B
.
В примере 1 . Это означает, что если A
будет писать «3», то он хотя бы не проиграет. Игрок B
заинтересован уменьшить выигрыш A
.
Выбирая стратегию B 1
, он из соображений осторожности учитывает максимально возможный при этом выигрыш A
. Обозначим . Аналогично при выборе стратегии B j
максимально возможный выигрыш A–
; запишем эти числа в добавочной строке.
Чтобы уменьшить выигрыш A
, надо из чисел β j выбрать наименьшее . Число называется верхней ценой игры
или минимаксом
. Это гарантированный проигрыш игрока B
(т. е. он проиграет не больше, чем β).
Стратегия игрока B
, обеспечивающая выигрыш ≥ - β, называется его минимаксной
стратегией.
В примере 1:
;
;
;
.
Это означает, что оптимальная стратегия B
– писать «3», тогда он хотя бы не проиграет.
| B A | B 1 | B 2 | B 3 | |
| A 1 | 0 | – 1 | –2 | –2 |
| A 2 | 1 | 0 | –1 | –1 |
| A 3 | 2 | 1 | 0 | 0 |
| 2 | 1 | 0 | 0 0 |
Можно доказать, что , т. е. .
В примере 1 α = β. Если , т.е. минимакс совпадает с максимином, то такая игра называется игрой с седловой точкой . Седловая точка – это пара оптимальных стратегий ( A i , B j ). В примере 1 игра имеет седловую точку (А 3 , B 3 ). В этом случае число α = β называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце. В примере 1 это элемент 0. Цена игры равна 0.
Оптимальные стратегии в любой игре обладают важным свойством, а именно – устойчивостью . Это означает, что каждый из игроков не заинтересован в отходе от своей оптимальной стратегии, т. к. это ему невыгодно. Отклонение от оптимальной стратегии игрока А приводит к уменьшению его выигрыша, а одностороннее отклонение игрока В – к увеличению проигрыша. Говорят, что седловая точка дает положение равновесия .
Пример 2. Первая сторона (игрок А ) выбирает один из трех типов вооружения – А 1 , А 2 , А 3 , а противник (игрок В ) – один из трех видов самолетов: В 1 , В 2 , В 3 . Цель В – прорыв фронта обороны, цель А – поражение самолета. Вероятность поражения самолета В 1 вооружением А 1 равна 0,5, самолета В 2 вооружением А 1 равна 0,6, самолета В 3 вооружением А 1 равна 0,8 и т.д., т.е. элемент a ij платежной матрицы – вероятность поражения самолета В j вооружением А i . Платежная матрица имеет вид: Решить игру, т.е. найти нижнюю и верхнюю цену игры и оптимальные стратегии.
Решение. В каждой строке находим минимальный элемент и записываем его в добавочном столбце. В каждом столбце находим максимальный элемент и записываем его в добавочной строке.
| В А | В 1 | В 2 | В 3 | α i |
| А 1 | 0,5 | 0,6 | 0,8 | 0,5 |
| А 2 | 0,9 | 0,7 | 0,8 | 0,7 |
| А 3 | 0,7 | 0,5 | 0,6 | 0,5 |
| β j | 0,9 | 0,7 | 0,8 | 0,7 0,7 |
В добавочном столбце находим максимальный элемент = 0,7, в добавочной строке находим минимальный элемент = 0,7.
Ответ: = 0,7. Оптимальные стратегии – А 2
и В 2
.
Пример 3
. Игра в орлянку. Каждый игрок при своем ходе может выбирать одну из двух стратегий: орел или решка. При совпадении выбранных стратегий А
получает выигрыш +1, при несовпадении B
получает выигрыш 1 (т. е. А
получает выигрыш –1). Платежная матрица:
Найти нижнюю и верхнюю цену игры. Имеет ли игра седловую точку?
Решение.
| В А | В 1 | В 2 | |
| А 1 | 1 | -1 | -1 |
| А 2 | -1 | 1 | 1 |
| 1 | 1 | -1 1 |
α = -1, β = 1, т. е. А проиграет не больше 1, и B проиграет не больше 1. Так как α ≠ β, игра не имеет седловой точки. Положения равновесия в этой игре не существует, и оптимального решения в чистых стратегиях найти нельзя.
Пример . Найдите нижнюю цену игру, верхнюю цену игры, определите седловые точки, оптимальные чистые стратегии и цену игры (если они существуют).
Рассмотрим парную конечную игру. Пусть игрок А располагает т личными стратегиями, которые обозначим
Пусть у игрока В имеется п личных стратегий, обозначим их. Говорят, что игра имеет размерность т х п.
В результате выбора игроками любой пары стратегий однозначно определяется исход игры, т.е. выигрыш а ;. игрока А (положительный или отрицательный) и проигрыш (-ау) игрока В. Предположим, что значения а.. известны для любой пары стратегий (А:, В ;.). Матрица Р = (a..), i = = 1, 2, ..., m j = 1, 2, ..., п, элементами которой являются выигрыши, соответствующие стратегиям А. и Bj, называется платежной матрицей, или матрицей игры. Общий вид такой матрицы представлен в табл. 12.1. Строки этой таблицы соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В.
Таблица 12.1
Составим платежную матрицу для следующей игры.
12.1. Игра "поиск".
Игрок А может спрятаться в одном из двух убежищ (I и II); игрок В ищет игрока А, и если найдет, то получает штраф 1 ден. ед. от А, в противном случае платит игроку А 1 ден. ед. Необходимо построить платежную матрицу игры.
Р е ш е н и с. Для составления платежной матрицы следует проанализировать поведение каждого из игроков. Игрок А может спрятаться в убежище I – обозначим эту стратегию через A v либо в убежище II – стратегия А. г Игрок В может искать первого игрока в убежище I – стратегия В { либо в убежище II – стратегия В.,. Если игрок А находится в убежище I и там его обнаруживает игрок В, т.е. осуществляется пара стратегий (Α ν В {), то игрок А платит штраф, т.е. а п = -1. Аналогично получаем а. п = -1 (А 2, В.,). Очевидно, что стратегии (А, В.,) и (Л2, /1,) дают игроку А выигрыш 1, поэтому а п = а. п = I. Таким образом, для игры "поиск" размера 2x2 получаем платежную матрицу:
Рассмотрим игру т х п с матрицей Р =a j}, i = 1,2, ..., τη; j = 1, 2, ..., и и определим наилучшую среди стратегий А у A v ..., А т. Выбирая стратегию A jy игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий В., для которой выигрыш для игрока А минимален (игрок В стремится "навредить" игроку А).
Обозначим через а; наименьший выигрыш игрока А при выборе им стратегии Л; для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы), т.е.
Среди всех чисел а (г = 1,2,..., т) выберем наибольшее: . Назовем а нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,
(12.2)
Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию В., он учитывает максимально возможный при этом выигрыш для А. Обозначим
Среди всех чисел β. выберем наименьшее,
и назовем β верхней ценой игры , или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следовательно,
(12.4)
Стратегия, соответствующая минимаксу, называется минимаксной стратегией.
Принцип, диктующий игрокам выбор наиболее "осторожных" минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника. Определим нижнюю и верхнюю цены игры и соответствующие стратегии в задаче 12.1. Рассмотрим платежную матрицу
из задачи 12.1. При выборе стратегии Л, (первая строка матрицы) минимальный выигрыш равен a, =min(-l; 1) = -1 и соответствует стратегии β1 игрока В. При выборе стратегии Л 2 (вторая строка матрицы) минимальный выигрыш равен а 2 = min(l; -1) = -1, он достигается при стратегии В.,.
Гарантируя себе максимальный выигрыш при любой стратегии игрока В , т.е. нижнюю цену игры а = тах(а, а2) = = max(-l; -1) = -1, игрок А может выбирать любую стратегию: Aj или А 2, т.е. любая его стратегия является максиминнои.
Выбирая стратегию В, (столбец 1), игрок В понимает, что игрок А ответит стратегией А 2, чтобы максимизировать свой выигрыш (проигрыш В). Следовательно, максимальный проигрыш игрока В при выборе им стратегии В, равен β, = шах(-1; 1) = 1.
Аналогично максимальный проигрыш игрока В (выигрыш А ) при выборе им стратегии В2 (столбец 2) равен β2 = max(l; -1) = 1.
Таким образом, при любой стратегии игрока А гарантированный минимальный проигрыш игрока В равен β = = πιίη(β1, β2) = min(l; 1) = 1- верхней цене игры.
Любая стратегия игрока В является минимаксной. Дополнив табл. 12.1 строкой β; и столбцом а;, получим табл. 12.2. На пересечении дополнительных строки и столбца будем записывать верхнюю и нижнюю цены игр.
Таблица 12.2
В задаче 12.1, рассмотренной выше, верхняя и нижняя цены игры различны: а Ф β.
Если верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены игры α = β = υ называется чистой ценой игры, или ценой игры. Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность – оптимальным решением, или решением игры. В этом случае игрок А получает максимальный гарантированный (не зависящий от поведения игрока В) выигрыш υ, а игрок В добивается минимального гарантированного (вне зависимости от поведения игрока Л) проигрыша υ. Говорят, что решение игры обладает устойчивостью, т.е. если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии.
Пара чистых стратегий А. и В.дает оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент гг является одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация, если она существует, называется седловой точкой (по аналогии с поверхностью седла, которая искривляется вверх в одном направлении и вниз – в другом).
Обозначим А* и В* – пару чистых стратегий, на которых достигается решение игры в задаче с седловой точкой. Введем функцию выигрыша первого игрока на каждой паре стратегий: Р(А :, В -) = а у . Тогда из условия оптимальности в седловой точке выполняется двойное неравенство: P(Aj, В*)<Р(А*, В*)<Р(А", В ), которое справедливо для всех i = 1, 2, ..., m;j = 1, 2, ..., п. Действительно, выбор стратегии А * первым игроком при оптимальной стратегии В" второго игрока максимизирует минимальный возможный выигрыш: Р(А *, B ")> Р(А Г В"), а выбор стратегии B" вторым игроком при оптимальной стратегии первого минимизирует максимальный проигрыш: Р(Д , В*)<Р(А", В).
12.2. Определить нижнюю и верхнюю цену игры, заданной платежной матрицей
Имеет ли игра седловую точку?
Таблица 12. 3
Решение.
Все расчеты удобно проводить в таблице, в которую, кроме матрицы Р,
введены столбец а; и строка }