Антагонистические матричные игры

Рассмотрим конечную парную игру с нулевой суммой. Обозначим через a выигрыш игрока A, а через b – выигрыш игрока B. Так как a = – b, то при анализе такой игры нет необходимости рассматривать оба этих числа – достаточно рассматривать выигрыш одного из игроков. Пусть это будет, например, A. В дальнейшем для удобства изложения сторону A будем условно именовать " мы ", а сторону B – " противник ".

Пусть у нас имеется m возможных стратегий A ₁, A ₂, …, A_m, а у противника n возможных стратегий B ₁, B ₂, …, B_n (такая игра называется игрой m×n). Предположим, что каждая сторона выбрала определенную стратегию: мы выбрали A_i, противник B_j. Если игра состоит только из личных ходов, то выбор стратегий A_i и B_j однозначно определяет исход игры – наш выигрыш (положительный или отрицательный). Обозначим этот выигрыш через a_ij (выигрыш при выборе нами стратегии A_i, а противником – стратегии B_j).

Если игра содержит кроме личных случайные ходы, то выигрыш при паре стратегий A_i, B_j есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша. Для удобства будем обозначать через a_ij как сам выигрыш (в игре без случайных ходов), так и его математическое ожидание (в игре со случайными ходами).

Предположим, что нам известны значения a_ij при каждой паре стратегий. Эти значения можно записать в виде матрицы, строки которой соответствуют нашим стратегиями (A_i), а столбцы – стратегиям противника (B_j):

Такая матрица называется платежной матрицей игры или просто матрицей игры.

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

Рассмотрим пример 1 антагонистической игры 4×5. В нашем распоряжении есть четыре стратегии, у противника – пять стратегий. Матрица игры следующая:

Какой стратегией нам (т.е. игроку A) воспользоваться? Какую бы мы ни выбрали стратегию, разумный противник ответит на нее той стратегией, для которой наш выигрыш будет минимальным. Например, если мы выберем стратегию A ₃ (соблазнившись выигрышем 10), противник в ответ выберет стратегию B ₁, и наш выигрыш будет всего лишь 1. Очевидно, исходя из принципа осторожности (а он – основной принцип теории игр), надо выбирать ту стратегию, при которой наш минимальный выигрыш максимален.

Обозначим через α_i минимальное значение выигрыша для стратегии A_i:

и добавим к матрице игры столбец, содержащий эти значения:

Выбирая стратегию, мы должны предпочесть ту, для которой значение α_i максимально. Обозначим это максимальное значение через α:

Величина α называется нижней ценой игры или максимином (максимум минимального выигрыша). Стратегия игрока A, соответствующая максимину α, называется максиминной стратегией.

В данном примере максимин α равен 3 (соответствующая клетка в таблице выделена серым цветом), а максиминная стратегия – A ₄. Выбрав эту стратегию, можем быть уверены, что при любом поведении противника выиграем не меньше, чем 3 (а может быть и больше при "неразумном" поведении противника"). Эта величина – наш гарантированный минимум, который мы можем себе обеспечить, придерживаясь наиболее осторожной ("перестраховочной") стратегии.

Теперь проведем аналогичные рассуждения за противника B. Он заинтересован в том, чтобы обратить наш выигрыш в минимум, то есть отдать нам поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Например, если он выберет стратегию B ₁, то мы ответим ему стратегией A ₃, и он отдаст нам 10. Если выберет B ₂ – мы ему ответим A ₂, и он отдаст 8 и т. д. Очевидно, осторожный противник должен выбрать ту стратегию, при которой наш максимальный выигрыш будет минимален.

Обозначим через β_j максимальные значения в столбцах платежной матрицы (максимальный выигрыш игрока A, или, что то же самое, максимальный проигрыш игрока B) для стратегии A_i:

и добавим к матрице игры строку, содержащую эти значения:

Выбирая стратегию, противник предпочтет ту, для которой значение β_j минимально. Обозначим его через β:

7.ЧТО НАЗЫВАЕТСЯ ВЕРХНЕЙ ЦЕННОЙ ИГРЫТеперь проведем аналогичные рассуждения за противника B. Он заинтересован в том, чтобы обратить наш выигрыш в минимум, то есть отдать нам поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Например, если он выберет стратегию B ₁, то мы ответим ему стратегией A ₃, и он отдаст нам 10. Если выберет B ₂ – мы ему ответим A ₂, и он отдаст 8 и т. д. Очевидно, осторожный противник должен выбрать ту стратегию, при которой наш максимальный выигрыш будет минимален.

Обозначим через β_j максимальные значения в столбцах платежной матрицы (максимальный выигрыш игрока A, или, что то же самое, максимальный проигрыш игрока B) для стратегии A_i:

и добавим к матрице игры строку, содержащую эти значения:

Выбирая стратегию, противник предпочтет ту, для которой значение β_j минимально. Обозначим его через β:

Величина β называется верхней ценой игры или минимаксом (минимум максимального выигрыша). Соответствующая минимаксу стратегия противника (игрока B), называется минимаксной стратегией.

Минимакс – это значение выигрыша, больше которого заведомо не отдаст нам разумный противник (иначе говоря, разумный противник проиграет не больше, чем β). В данном примере минимакс β равен 5 (соответствующая клетка в таблице выделена серым цветом) и достигается он при стратегии противника B ₃.

Итак, исходя из принципа осторожности («всегда рассчитывай на худшее!»), мы должны выбрать стратегию A ₄, а противник – стратегию B ₃. Принцип осторожности является в теории игр основным и называется принципом минимакса.

Рассмотрим пример 2. Пусть игроки A и В одновременно и независимо друг от друга записывают одно из трех чисел: либо «1», либо «2», либо «3». Если сумма записанных чисел оказывается четной, то игрок B платит игроку A эту сумму. Если сумма нечетная, то эту сумму выплачивает игрок A игроку В.

Запишем платежную матрицу игры, и найдем нижнюю и верхнюю цены игры (номер стратегии соответствует записанному числу):

Игрок A должен придерживаться максиминной стратегии A ₁, чтобы выиграть не меньше –3 (то есть чтобы проиграть не больше 3). Минимаксная стратегия игрока B – любая из стратегий B ₁ и B ₂, гарантирующая, что он отдаст не более 4.

Тот же самый результат мы получим, если будем записывать платежную матрицу с точки зрения игрока В. Фактически, эта матрица получается путем транспонирования матрицы, построенной с точки зрения игрока A, и изменения знаков элементов на противоположный (так как выигрыш игрока A – это проигрыш игрока В):

Исходя из этой матрицы следует, что игрок B должен придерживаться любой из стратегий B ₁ и B ₂ (и тогда он проиграет не более 4), а игрок A – стратегии A ₁ (и тогда он проиграет не более 3). Как видно, результат в точности совпадает с полученным выше, поэтому при анализе не важно, с точки зрения какого игрока мы его проводим.

8 ЧТО НАЗЫВАЕТСЯ ЦЕННОВОЙ ИГРОЙ.

9.В ЧЕМ СОСТОЙТ ПРИНЦЕП МИНИМАКСА. 2. Нижняя и верхняя цена игры. Принцип минимакса

Рассмотрим матричную игру типа с платежной матрицей

.

Если игрок А выберет стратегию А_i, то все его возможные выигрыши будут элементами i -й строки матрицы С. В наихудшем для игрока А случае, когда игрок В применяет стратегию, соответствующую минимальному элементу этой строки, выигрыш игрока А будет равен числу .

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

· Число

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

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

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

Если игрок В выберет стратегию В_j, то все возможные выигрыши игрока А будут элементами j -го столбца платежной матрицы С. В наихудшем для игрока В случае, когда игрок А применяет стратегию, соответствующую максимальному элементу этого столбца, выигрыш игрока В будет равен числу .

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

· Число

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

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

· Принцип осторожности, заставляющий игроков придерживаться максиминной и минимаксной стратегий соответственно, называют «Принципом минимакса», а минимаксную стратегию называют общим термином «Минимаксные стратегии».

Пример 2.1. Найти нижнюю и верхнюю цены игры с платежной матрицей

.

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

.

Нижняя цена игры

.

Верхняя цена игры

.