Рассмотрим конечную парную игру с нулевой суммой. Обозначим через a выигрыш игрока A , а через b – выигрыш игрока B . Так как a = –b , то при анализе такой игры нет необходимости рассматривать оба этих числа – достаточно рассматривать выигрыш одного из игроков. Пусть это будет, например, A . В дальнейшем для удобства изложения сторону A будем условно именовать "мы ", а сторону B – "противник ".
Пусть у нас имеется m возможных стратегийA 1 , A 2 , …, A m , а у противника n возможных стратегий B 1 , B 2 , …, 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 ):
| B j A i | B 1 | B 2 | … | B n |
| A 1 | a 11 | a 12 | … | a 1n |
| A 2 | a 21 | a 22 | … | a 2n |
| … | … | … | … | … |
| A m | a m 1 | a m 2 | … | a mn |
Такая матрица называется платежной матрицей игры или просто матрицей игры .
Заметим, что построение платежной матрицы для игр с большим количеством стратегий может представлять непростую задачу. Например, для шахматной игры число возможных стратегий так велико, что построение платежной матрицы является практически неосуществимым. Однако, в принципе любая конечная игра может быть приведена к матричной форме.
Рассмотрим пример 1 антагонистической игры 4×5. В нашем распоряжении есть четыре стратегии, у противника – пять стратегий. Матрица игры следующая:
| B j A i | B 1 | B 2 | B 3 | B 4 | B 5 |
| A 1 | |||||
| A 2 | |||||
| A 3 | |||||
| A 4 |
Какой стратегией нам (т.е. игроку A ) воспользоваться? Какую бы мы ни выбрали стратегию, разумный противник ответит на нее той стратегией, для которой наш выигрыш будет минимальным. Например, если мы выберем стратегию A 3 (соблазнившись выигрышем 10), противник в ответ выберет стратегию B 1 , и наш выигрыш будет всего лишь 1. Очевидно, исходя из принципа осторожности (а он – основной принцип теории игр), надо выбирать ту стратегию, при которой наш минимальный выигрыш максимален .
Обозначим через α i минимальное значение выигрыша для стратегии A i :
и добавим к матрице игры столбец, содержащий эти значения:
| B j A i | B 1 | B 2 | B 3 | B 4 | B 5 | минимум в строках α i | |
| A 1 | |||||||
| A 2 | |||||||
| A 3 | |||||||
| A 4 | максимин |
Выбирая стратегию, мы должны предпочесть ту, для которой значение α i максимально. Обозначим это максимальное значение через α :
Величина α называется нижней ценой игры или максимином (максимум минимального выигрыша). Стратегия игрока A , соответствующая максимину α , называется максиминной стратегией .
В данном примере максимин α равен 3 (соответствующая клетка в таблице выделена серым цветом), а максиминная стратегия –A 4 . Выбрав эту стратегию, можем быть уверены, что при любом поведении противника выиграем не меньше, чем 3 (а может быть и больше при "неразумном" поведении противника"). Эта величина – наш гарантированный минимум, который мы можем себе обеспечить, придерживаясь наиболее осторожной ("перестраховочной") стратегии.
Теперь проведем аналогичные рассуждения за противника B B A B 2 – мы ему ответим A .
Обозначим через β j A B ) для стратегии A i :
β j β :
7.ЧТО НАЗЫВАЕТСЯ ВЕРХНЕЙ ЦЕННОЙ ИГРЫТеперь проведем аналогичные рассуждения за противника B . Он заинтересован в том, чтобы обратить наш выигрыш в минимум, то есть отдать нам поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Например, если он выберет стратегию B 1 , то мы ответим ему стратегией A 3 , и он отдаст нам 10. Если выберет B 2 – мы ему ответим A 2 , и он отдаст 8 и т. д. Очевидно, осторожный противник должен выбрать ту стратегию, при которой наш максимальный выигрыш будет минимален .
Обозначим через β j максимальные значения в столбцах платежной матрицы (максимальный выигрыш игрока A , или, что то же самое, максимальный проигрыш игрока B ) для стратегии A i :
и добавим к матрице игры строку, содержащую эти значения:
Выбирая стратегию, противник предпочтет ту, для которой значение β j минимально. Обозначим его через β :
Величина β называется верхней ценой игры или минимаксом (минимум максимального выигрыша). Соответствующая минимаксу стратегия противника (игрока B ), называется минимаксной стратегией .
Минимакс – это значение выигрыша, больше которого заведомо не отдаст нам разумный противник (иначе говоря, разумный противник проиграет не больше, чем β ). В данном примере минимакс β равен 5 (соответствующая клетка в таблице выделена серым цветом) и достигается он при стратегии противника B 3 .
Итак, исходя из принципа осторожности («всегда рассчитывай на худшее!»), мы должны выбрать стратегию A 4 , а противник – стратегию B 3 . Принцип осторожности является в теории игр основным и называется принципом минимакса .
Рассмотрим пример 2 . Пусть игроки A и В одновременно и независимо друг от друга записывают одно из трех чисел: либо «1», либо «2», либо «3». Если сумма записанных чисел оказывается четной, то игрок B платит игроку A эту сумму. Если сумма нечетная, то эту сумму выплачивает игрок A игроку В .
Запишем платежную матрицу игры, и найдем нижнюю и верхнюю цены игры (номер стратегии соответствует записанному числу):
Игрок A должен придерживаться максиминной стратегии A 1 , чтобы выиграть не меньше –3 (то есть чтобы проиграть не больше 3). Минимаксная стратегия игрока B – любая из стратегий B 1 и B 2 , гарантирующая, что он отдаст не более 4.
Тот же самый результат мы получим, если будем записывать платежную матрицу с точки зрения игрока В . Фактически, эта матрица получается путем транспонирования матрицы, построенной с точки зрения игрока A , и изменения знаков элементов на противоположный (так как выигрыш игрока A – это проигрыш игрока В ):
Исходя из этой матрицы следует, что игрок B должен придерживаться любой из стратегий B 1 и B 2 (и тогда он проиграет не более 4), а игрок A – стратегии A 1 (и тогда он проиграет не более 3). Как видно, результат в точности совпадает с полученным выше, поэтому при анализе не важно, с точки зрения какого игрока мы его проводим.
8 ЧТО НАЗЫВАЕТСЯ ЦЕННОВОЙ ИГРОЙ.
9.В ЧЕМ СОСТОЙТ ПРИНЦЕП МИНИМАКСА.2. Нижняя и верхняя цена игры. Принцип минимакса
Рассмотрим матричную игру типа с платежной матрицей
Если игрок А выберет стратегию А i , то все его возможные выигрыши будут элементами i -й строки матрицы С . В наихудшем для игрока А случае, когда игрокВ применяет стратегию, соответствующую минимальному элементу этой строки, выигрыш игрока А будет равен числу .
Следовательно, для получения наибольшего выигрыша, игроку А нужно выбирать ту из стратегий, для которой число максимально .
Задача принятия решения, рассматриваемая в рамках системного подхода, содержит три основные компоненты: в ней выделены система, управляющая подсистема и среда. Теперь мы переходим к изучению задач принятия решения, в которых на систему воздействует не одна, а несколько управляющих подсистем, каждая из которых имеет свои цели и возможности действий. Такой подход к принятию решений называется теоретико-игровым, а математические модели соответствующих взаимодействий называются играми . Ввиду различия целей управляющих подсистем, а также определенных ограничений на возможности обмена информацией между ними, указанные взаимодействия носят конфликтный характер. Поэтому всякая игра представляет собой математическую модель конфликта. Ограничимся случаем, когда управляющих подсистем две. Если цели систем противоположны, конфликт называется антагонистическим, а математическая модель такого конфликта называется антагонистической игрой ..
В теоретико-игровой терминологии 1-я управляющая подсистема называется игроком 1 , 2-я управляющая подсистема - игроком 2 , множества
их альтернативных действий называются множествами стратегий этих игроков. Пусть Х - множество стратегий игрока 1, Y - множество стратегий
игрока 2. Состояние системы однозначно определяется выбором управляющих воздействий подсистемами 1 и 2, то есть выбором стратегий
x ∈X и y ∈Y . Пусть F (x ,y )- оценка полезности для игрока 1 того состояния
системы, в которое она переходит при выборе игроком 1 стратегии х и
игроком 2 стратегии у . Число F (x ,y ) называется выигрышем игрока 1 в ситуации (x ,y ), а функция F - функцией выигрыша игрока 1 . Выигрыш игрока
1 одновременно является проигрышем игрока 2 , то есть величиной, которую первый игрок стремится увеличить, а второй – уменьшить. Это и есть
проявление антагонистического характера конфликта: интересы игроков полностью противоположны (то, что выигрывает один, проигрывает другой).
Антагонистическую игру естественно задать системой Г= (Х, Y, F ).
Заметим, что формально антагонистическая игра задается фактически так же, как и задача принятия решения в условиях неопределенности - если
отождествить управляющую подсистему 2 со средой. Содержательное различие между управляющей подсистемой и средой состоит в том, что
поведение первой носит целенаправленный характер. Если при составлении математической модели реального конфликта у нас есть основание (или намерение) рассматривать среду как противника, цель которого - принести
нам максимальный вред, то такую ситуацию можно представить в виде антагонистической игры. Другими словами, антагонистическую игру можно трактовать как крайний случай ЗПР в условиях неопределенности,
характеризуемый тем, что среда рассматривается как противник, имеющий цель. При этом мы должны ограничить виды гипотез о поведении среды.
Наиболее обоснованной здесь является гипотеза крайней осторожности, когда, принимая решение, мы рассчитываем на самый худший для нас возможный вариант действий среды.
Определение. Если Х и Y конечны, то антагонистическая игра называется матричной. В матричной игре можно считать, что X ={1,…,n },
Y ={1,…,m } и положить aij=F (i,j ). Таким образом, матричная игра полностью определяется матрицей A= (aij ), i =1,…,n, j =1,…,m .
Пример 3.1. Игра с двумя пальцами.
Два человека одновременно показывают один или два пальца и называют число 1 или 2, означающее, по мнению говорящего, количество
пальцев, показанное другим. После того, как пальцы показаны и числа названы, происходит распределение выигрыша по следующим правилам:
если оба угадали или оба не угадали, сколько пальцев показал их соперник, выигрыш каждого равен нулю; если угадал только один, то противник платит угадавшему сумму денег, пропорциональную общему числу показанных
Это антагонистическая матричная игра. Каждый игрок имеет четыре стратегии: 1- показать 1 палец и назвать 1, 2- показать 1 палец и назвать 2, 3-
показать 2 пальца и назвать 1, 4 - показать 2 пальца и назвать 2. Тогда матрица выигрышей A=(aij), i= 1,…, 4, j= 1,…, 4 определяется следующим образом:
a12= 2, a21 = – 2, a13=a42= –3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 в остальных случаях.
Пример 3.2. Дискретная игра типа дуэли.
Задачами дуэльного типа описывается, например, борьба двух игроков,
каждый из которых желает совершить некое единовременное действие (выброс на рынок партии товара, заявка о покупке на аукционе) и выбирает для этого время. Пусть игроки продвигаются навстречу друг другу на n шагов. После каждого сделанного шага игрок может выстрелить или не выстрелить в противника. Выстрел может быть у каждого только один. Считается, что вероятность попасть в противника, если продвинуться на k n =5 имеет вид
Подход к решению матричных игр может быть обобщен на случай антагонистических игр, в которых платеж игроков задается в виде непрерывной функции (бесконечная антагонистическая игра).
Такая игра представляется как игра двух игроков, в которой игрок 1 выбирает число х из множества X, игрок 2 выбирает число у из множества 7, и после этого игроки 1 и 2 получают соответственно выигрыши U (х, у) и -U(x, у). Выбор определенного числа игроком означает применение его чистой стратегии, соответствующей этому числу.
По аналогии с матричными играми чистой нижней ценой игры можно назвать v { = max min U(x, у), а чистой верхней ценой игры -v 2 =
min max U{x, у). Тогда по аналогии можно считать, что если для какой-
у *
либо бесконечной антагонистической игры величины V и v 2 существуют и равны между собой («i =v 2 =v), то такая игра имеет решение в чистых стратегиях, т.е. оптимальной стратегией игрока 1 является выбор числа х° е X, а игрока 2 - числа у 0 е 7, при которых Щх { у 0) -v.
В этом случае v называется чистой ценой игры, а (х°, у 0) - седловой точкой бесконечной антагонистической игры.
Для матричных игр величины v x и v 2 всегда существуют, но в бесконечных антагонистических играх они могут и не существовать, т.е. бесконечная антагонистическая игра не всегда разрешима.
При формализации реальной ситуации в виде бесконечной антагонистической игры обычно выбирается единичный стратегический интервал - единичный промежуток, из которого игроки могут сделать выбор (х - число (стратегия), выбираемое игроком 1; -
число (стратегия), выбираемое игроком 2). Технически это упрощает решение, так как простым преобразованием любой интервал можно перевести в единичный и наоборот. Такая игра называется антагонистической игрой на единичном квадрате.
Для примера допустим, что игрок 1 выбирает число х из множества Х= , игрок 2 выбирает число у из множества Y= . После этого игрок 2 платит игроку 1 сумму Щх, у) -2х 2 -у 2 . Поскольку игрок 2 стремится минимизировать платеж игрока 1, то он определяет min (2х 2 - у 2) = 2х 2 - 1, т.е. при этому= 1. Игрок 1 стремится мак- тег
симизировать свой платеж, поэтому определяет maxi min Щх, у)1 =
xGX у ег
- max (2х 2 - 1) = 2- 1 = 1, который достигается при х = 1.
Таким образом, нижняя чистая цена игры v x - 1. Верхняя чистая
цена игры v 2 = min - min (2 - у 2) = 2 - 1 = 1, т.е. в этой
>ег хех у еу
игре v l =v 2 =l. Поэтому чистая цена игры v = 1, а седловая точка (х° = 1; у°=1).
Предположим теперь, что Хи Y- открытые интервалы, т.е. игрок 1 выбираетxeA"=(0; 1), игрок 2 выбирает уе 7= (0; 1). В этом случае, выбирая х, достаточно близкое к 1, игрок 1 будет уверен, что он получит выигрыш не меньше, чем число, близкое к»=1; выбирая у, близкое к 1, игрок 2 не допустит, чтобы выигрыш игрока 1 значительно превышал чистую цену игры v= 1.
Степень близости к цене игры может характеризоваться числом?>0. Поэтому в описываемой игре можно говорить об оптимальности чистых стратегий х° = 1, у 0 = 1 соответственно игроков 1 и 2 с точностью до произвольного числа?>0. Точка (х„ , у Е), где х е е X, у (. eY, в бесконечной антагонистической игре называется точкой z-равновесия (с.-седловой точкой) , если для любых стратегий хеТигрока 1,уе Тигро- ка 2 имеет место неравенство Щх, у.) - ? Щ x r , у (.) U(x t ., у) + ?. В этом случае стратегии х к. и у. называются с,-оптимальными стратегиями . Эти стратегии являются оптимальными с точностью до? в том смысле, что если отклонение от оптимальной стратегии никакой пользы игроку принести не может, то его отклонение от с-оптимальной стратегии может увеличить его выигрыш не более чем на е.
Если игра не имеет седловой точки (с-седловой точки), т.е. решения в чистых стратегиях, то оптимальные стратегии можно искать среди смешанных стратегий, в качестве которых используются функции распределения вероятностей применения игроками чистых стратегий.
Пусть F(x) - функция распределения вероятностей применения чистых стратегий игроком 1. Если число Е, - чистая стратегия игрока 1, то F(x) = P(q где P(q - Х) - вероятность того, что случайно выбранная чистая стратегия Е, не будет превосходить х. Аналогично рассматривается функция распределения вероятностей применения чистых стратегий г| игроком 2: Q(y) = Р(г .
Функции F(x) и Q(y) называются смешанными стратегиями соответственно игроков 1 и 2. Если Fx) и Q(y) дифференцируемы, то существуют их производные, обозначаемые соответственно через f{x) и q(y) (функции плотности распределения).
В общем случае дифференциал функции распределения dF{x ) выражает вероятность того, что стратегия с, находится в промежутке х Е, Аналогично для игрока 2: dQ(y) означает вероятность того, что его стратегия р находится в интервале у г| у+dy. Тогда платеж игрока 1 составит Щх, у) dF(x), а платеж игрока 2 равен Щх, у) dQ(y).
Средний платеж игрока 1 при условии, что игрок 2 применяет свою чистую стратегию у, можно получить, проинтегрировав платежи по всем возможным значениям х, т.е. на единичном интервале:
Средний платеж игрока 1 при условии, что оба игрока применяют свои смешанные стратегии F{x) и Q(y), будет равен
По аналогии с матричными играми определяются оптимальные смешанные стратегии игроков и цена игры: если пара смешанных стратегий F*(x ) и Q*(y) соответственно для игроков 1 и 2 являются оптимальными, то для любых смешанных стратегий F(x) и Q(y) справедливы соотношения:
Если игрок 1 отступает от своей стратегии F*(x), то его средний выигрыш не может увеличиться, но может уменьшиться из-за рациональных действий игрока 2. Если игрок 2 отступит от своей смешанной стратегии Q*(y), то средний выигрыш игрока 1 может увеличиться, но не уменьшиться, за счет более разумных действий игрока 1. Средний выигрыш E(F*, Q*), получаемый игроком 1 при применении игроками оптимальных смешанных стратегий, соответствует цене игры.
Тогда нижняя цена бесконечной антагонистической игры, решаемой в смешанных стратегиях, может быть определена как v x = шах
min Е (FQ), а верхняя цена игры как v 2 = min max Е(F, Q).
Q Q f
Если существуют такие смешанные стратегии F* (х) и Q* (у) соответственно для игроков 1 и 2, при которых нижняя и верхняя цены игры совпадают, то F*(x) и Q*(y) естественно назвать оптимальными смешанными стратегиями соответствующих игроков, a v=v x = v 2 - ценой игры.
В отличие от матричных игр решение бесконечной антагонистической игры существует не для всякой функции Щх, у). Но доказана теорема о том, что всякая бесконечная антагонистическая игра с непрерывной платежной функцией Щх, у) на единичном квадрате имеет решение (игроки имеют оптимальные смешанные стратегии), хотя общих методов для решения бесконечных антагонистических игр, в том числе непрерывных игр, не существует. Однако достаточно просто решаются антагонистические бесконечные игры с выпуклыми и вогнутыми непрерывными платежными функциями (они называются соответственно выпуклыми и вогнутыми играми).
Рассмотрим решение игр с выпуклой платежной функцией. Решение игр с вогнутой функцией выигрыша симметрично.
Выпуклой функцией/переменной х на интервале (а ; Ь) называется такая функция, для которой выполняется неравенство
где Хх и х 2 - любые две точки из интервала (а; b );
Х.1, А.2 > 0, причем +Х.2= 1.
Если для / ч * 0 Д 2 * 0, всегда имеет место строгое неравенство
то функция/называется строго выпуклой на (а; Ь).
Геометрически выпуклая функция изображает дугу, график которой расположен ниже стягивающей ее хорды. Аналитически выпуклость дважды дифференцируемой функции соответствует неотрицательности (а в случае строгой выпуклости - положительности) ее второй производной.
Для вогнутых функций свойства противоположны, для них должно выполняться неравенство/(/4X1 +А.2Х2) > Kf (xi) +)-if (х 2) (> при строгой вогнутости), а вторая производная/"(х)
Доказано , что непрерывная и строго выпуклая функция на замкнутом интервале принимает минимальное значение только в одной точке интервала. Если Щх, у) - непрерывная функция выигрышей игрока 1 на единичном квадрате и строго выпуклая по у для любого х, то имеется единственная оптимальная чистая стратегия у=у° е для игрока 2, цена игры определяется по формуле
а значение у 0 определяется как решение следующего уравнения:
Если функция Щх, у) не строго выпуклая по у, то у игрока 2 оптимальная чистая стратегия не будет единственной.
Симметричное свойство выполняется и для строго вогнутых функций. Если функция Щх, у) непрерывна по обоим аргументам и строго вогнута по х при любом у, то игрок 1 имеет единственную оптимальную стратегию.
Цена игры определяется по формуле
а чистая оптимальная стратегия х 0 игрока 1 определяется из уравнения
На основании этих свойств бесконечных антагонистических игр с выпуклой или вогнутой функциями выигрыша построена общая схема решения таких игр на единичном квадрате (х е , у е ). Приведем эту схему лишь для выпуклых игр , поскольку для вогнутых игр она симметрична.
1. Проверить функцию Щх, у) на выпуклость по у (вторая частная производная должна быть больше либо равна 0).
2. Определить у 0 из соотношения v- min max Щх, у) как значение
у, на котором достигается минимакс.
3. Найти решение уравнения v = U(x, у 0) и составить пары его решений Х и х 2 , для которых
4. Найти параметр а из уравнения
Параметр а определяет оптимальную стратегию игрока 1 и имеет смысл вероятности выбора им его чистой стратегии х х. Величина 1 - а имеет смысл вероятности выбора игроком 1 его чистой стратегии х 2 .
Покажем на примере использование этой схемы для решения игры такого вида. Пусть функция выигрыша в бесконечной антагонистической игре задана на единичном квадрате и равна Щх, у) = = (х - у) 2 =х 2 - 2ху ч-у 2 .
1. Эта функция непрерывна по х
и у,
и поэтому эта игра имеет решение. Функция Щх, у)
строго выпукла по у,
так как
Следовательно, игрок 2 имеет единственную чистую оптимальную стратегию у 0 .
2. Имеем v = min max (х - у) 2 . Для определения max (х 2 - 2ху Ч-у 2)
последовательно найдем первую и вторую частные производные пла- тежной функции по х:
Таким образом, функция U имеет минимум для любого у при х=у. Это значит, что при ху - возрастает, а ее максимум должен достигаться в одной из крайних точек х=0 или х= 1. Определим значения функции U в этих точках:
Тогда шах (х - у) 2 = тах {у 2 ; 1 - 2у+у 2 }. Сравнивая «внутренние»
максимумы, стоящие в фигурных скобках, легко заметить, что у 2 > 1 - - 2у+у 2 , если у > */ 2 и у 2 1 - 2у+у 2 , если у "/ 2 . Более наглядно это представляется графиком (рис. 2.5).
Рис. 2.5. Внутренние максимумы платежной функции U(х, у) = (х- у ) 2
Поэтому выражение (х - у) 2 достигает своего максимума при х=0, если у > 7 2 , и при х= 1, если у У 2:
Следовательно, v= min { min у 2 ; min (1 - у) 2 }. Каждый из вну-
тренних минимумов достигается при у= */ 2 и принимает значение У 4 . Таким образом, цена игры г = У 4 , а оптимальная стратегия игрока 2:
3. Определим оптимальную стратегию игрока 1 из уравнения U(x, у 0)=v, т.е. для данной игры (х - У 2) 2 =У 4 . Решением этого уравнения ЯВЛЯЮТСЯ Х| =0, х 2 = 1.
Для них выполняются условия
4. Определим параметр а, т.е. вероятность применения игроком 1 его чистой стратегии Х] = 0. Составим уравнение а-1 + (1 - а) (-1)=0, откуда а = У 2 . Таким образом, оптимальная стратегия игрока 1 состоит в выборе им своих чистых стратегий 0 и 1 с вероятностью 1 / 2 каждая. Задача решена.
Самым простым случаем, подробно разработанным в теории игр, является конечная парная игра с нулевой суммой (антагонистическая игра двух лиц или двух коалиций). Рассмотрим такую игру G, в которой участвуют два игрока А и В, имеющие противоположные интересы: выигрыш одного равен проигрышу другого. Так как выигрыш игрока А равен выигрышу игрока В с обратным знаком, мы можем интересоваться только выигрышем а игрока . Естественно, А хочет максимизировать, а В - минимизировать а.
Для простоты отождествим себя мысленно с одним из игроков (пусть это будет А) и будем его называть «мы», а игрока В - «противник» (разумеется, никаких реальных преимуществ для А из этого не вытекает). Пусть у нас имеется возможных стратегий а у противника - возможных стратегий (такая игра называется игрой ). Обозначим наш выигрыш в случае, если мы пользуемся стратегией а противник - стратегией
Таблица 26.1
Предположим, что для каждой пары стратегий выигрыш (или средний выигрыш) a нам известен. Тогда в принципе можно составить прямоугольную таблицу (матрицу), в которой перечислены стратегии игроков и соответствующие выигрыши (см. таблицу 26.1).
Если такая таблица составлена, то говорят, что игра G приведена к матричной форме (само по себе приведение игры к такой форме уже может составить трудную задачу, а иногда и практически невыполнимую, из-за необозримого множества стратегий). Заметим, что если игра приведена к матричной форме, то многоходовая игра фактически сведена к одноходовой - от игрока требуется сделать только один ход: выбрать стратегию. Будем кратко обозначать матрицу игры
Рассмотрим пример игры G (4X5) в матричной форме. В нашем распоряжении (на выбор) четыре стратегии, у противника - пять стратегий. Матрица игры дана в таблице 26.2
Давайте, поразмышляем о том, какой стратегией нам (игроку А) воспользоваться? В матрице 26.2 есть соблазнительный выигрыш «10»; нас так и тянет выбрать стратегию при которой этот «лакомый кусок» нам достанется.
Но постойте: противник тоже не дурак! Если мы выберем стратегию он, назло нам, выберет стратегию , и мы получим какой-то жалкий выигрыш «1». Нет, выбирать стратегию нельзя! Как же быть? Очевидно, исходя из принципа осторожности (а он - основной принцип теории игр), надо выбрать ту стратегию, при которой наш минимальный выигрыш максимален.
Таблица 26.2
Это - так называемый «принцип мини-макса»: поступай так, чтобы при наихудшем для тебя поведении противника получить максимальный выигрыш.
Перепишем таблицу 26.2 и в правом добавочном столбце запишем минимальное значение выигрыша в каждой строке (минимум строки); обозначим его для строки а (см. таблицу 26.3).
Таблица 26.3
Из всех значений (правый столбец) выделено наибольшее (3). Ему соответствует стратегия . Выбрав эту стратегию, мы во всяком случав можем быть уверены, что (при любом поведении противника) выиграем не меньше, чем 3. Эта величина - наш гарантированный выигрыш; ведя себя осторожно, меньше этого мы получить не можем может быть, получим и больше).
Этот выигрыш называется нижней ценой игры (или «максимином» - максимальный из минимальных выигрышей). Будем обозначать его а. В нашем случае
Теперь станем на точку зрения противника и порассуждаем за него. Он ведь не пешка какая-нибудь, а тоже разумен! Выбирая стратегию, он хотел бы отдать поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Если он выберет стратегию мы ему ответим и он отдаст 10; если выберет - мы ему ответим и он отдаст и т. д. Припишем к таблице 26.3 добавочную нижнюю строку и в ней запишем максимумы столбцов Очевидно, осторожный противник должен выбрать ту стратегию, при которой эта величина минимальна (соответствующее значение 5 выделено в таблице 26.3). Эта величина Р - то значение выигрыша, больше которого заведомо не отдаст нам разумный противник. Она называется верхней ценой игры (или «ми-нимаксом» - минимальный из максимальных выигрышей). В нашем примере и достигается при стратегии противника
Итак, исходя из принципа осторожности (перестраховочного правила «всегда рассчитывай на худшее!»), мы должны выбрать стратегию А а противник - стратегию Такие стратегии называются «минимаксными» (вытекающими из принципа минимакса). До тех пор, пока обе стороны в нашем примере будут придерживаться своих минимаксных стратегий, выигрыш будет равен
Теперь представим себе на минуту, что мы узнали о том, что противник придерживается стратегии . А ну-ка, накажем его за это и выберем стратегию мы получим 5, а это не так уж плохо. Но ведь противник - тоже не промах; пусть он узнал, что наша стратегия , он тоже поторопится выбрать , сведя наш выигрыш к 2, и т. д. (партнеры «заметались по стратегиям»). Одним словом, минимаксные стратегии в нашем примере, неустойчивы по отношению к информации о поведении другой стороны; эти стратегии не обладают свойством равновесия.
Всегда ли это так? Нет, не всегда. Рассмотрим пример с матрицей, данной в таблице 26.4.
В этом примере нижняя цена игры равна верхней: . Что из этого вытекает? Минимаксные стратегии игроков А и В будут устойчивыми. Пока оба игрока их придерживаются, выигрыш равен 6. Посмотрим, что будет, если мы (А) узнаем, что противник (В) держится стратегии В?
Таблица 26.4
А ровно ничего не изменится, Потому что любое отступление от стратегии может только ухудшить наше положение. Равным образом, информация, полученная противником, не заставит его отступить от своей стратегии Пара стратегий обладает свойством равновесия (уравновешенная пара стратегий), а выигрыш (в нашем случае 6), достигаемый при этой паре стратегий, называется «седловой точкой матрицы». Признак наличия седловой точки и уравновешенной пары стратегий - это равенство нижней и верхней цены игры; общее значение называется ценой игры. Мы будем обозначать его
Стратегии (в данном случае ), при которых этот выигрыш достигается, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях. Обеим сторонам А и В можно указать их оптимальные стратегии, при которых их положение - наилучшее из возможных. А что игрок А при этом выигрывает 6, а игрок В - проигрывает что же, таковы условия игры: они выгодны для А и невыгодны для В.
У читателя может возникнуть вопрос: а почему оптимальные стратегии называются «чистыми»? Несколько забегая вперед, ответим на этот вопрос: бывают стратегии «смешанные», состоящие в том, что игрок применяет не одну какую-то стратегию, а несколько, перемежая их случайным образом. Так вот, если допустить кроме чистых еще и смешанные стратегии, всякая конечная игра имеет решение - точку равновесия. Но об этом речь еще впереди.
Наличие седловой точки в игре - это далеко не правило, скорее - исключение. Большинство игр не имеет седловой точки. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это - так называемые «игры с полной информацией». Игрой с полной информацией называется такая игра, в которой каждый игрок при каждом личном ходе знает всю предысторию ее развития, т. е. результаты всех предыдущих ходов, как личных, так и случайных. Примерами игр с полной информацией могут служить: шашки, шахматы, «крестики и нолики» и т. п.
В теории игр доказывается, что каждая игра с полной информацией имеет седловую точку, и значит, решается в чистых стратегиях. В каждой игре с полной информацией существует пара оптимальных стратегий, дающая устойчивый выигрыш, равный цене игры и. Если такая игра состоит только из личных ходов, то при применении каждым игроком своей оптимальной стратегии она должна кончаться вполне определенным образом - выигрышем, равным цене игры. А значит, если решение игры известно, самая игра теряет смысл!
Возьмем элементарный пример игры с полной информацией: два игрока попеременно кладут пятаки на круглый стол, выбирая произвольно положение центра монеты (взаимное перекрытие монет не разрешается). Выигрывает тот, кто положит последний пятак (когда места для других уже не останется). Легко убедиться, что исход этой игры, в сущности, предрешен. Есть определенная стратегия, обеспечивающая выигрыш тому из игроков, кто кладет монету первым.
А именно, он должен первый раз положить пятак в центре стола, а затем на каждый ход противника отвечать симметричным ходом. Очевидно, как бы ни вел себя противник, ему не избежать проигрыша. Точно так же обстоит дело и с шахматами и вообще играми с полной информацией: любая из них, записанная в матричной форме, имеет седловую точку, и значит, решение в чистых стратегиях, а следовательно, имеет смысл только до тех пор, пока это решение не найдено. Скажем, шахматная игра либо всегда кончается выигрышем белых, либо всегда - выигрышем черных, либо всегда - ничьей, только чем именно - мы пока не знаем (к счастью для любителей шахмат). Прибавим еще: вряд ли будем знать и в обозримом будущем, ибо число стратегий так огромно, что крайне трудно (если не невозможно) привести игру к матричной форме и найти в ней седловую точку.
А теперь спросим себя, как быть, если игра не имеет седловой точки: Ну что же, если каждый игрок вынужден выбрать одну-единственную чистую стратегию, то делать нечего: надо руководствоваться принципом минимакса. Другое дело, если можно свои стратегии «смешивать», чередовать случайным образом с какими-то вероятностями. Применение смешанных стратегий мыслится таким образом: игра повторяется много раз; перед каждой партией игры, когда игроку предоставляется личный ход, он «передоверяет» свой выбор случайности, «бросает жребий», и берет ту стратегию, которая выпала (как организовать жребий, мы уже знаем из предыдущей главы).
Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, как поведет себя противник в данной партии. Такая тактика (правда, обычно безо всяких математических обоснований) часто применяется в карточных играх. Заметим при этом, что лучший способ скрыть от противника свое поведение - это придать ему случайный характер и, значит, самому не знать заранее, как ты поступишь.
Итак, поговорим о смешанных стратегиях. Будем обозначать смешанные стратегии игроков А и В соответственно где (образующие в сумме единицу) - вероятности применения игроком А стратегий - вероятности применения игроком В стратегий
В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.
Существует основная теорема теории игр: любая конечная игра двух лиц с нулевой суммой имеет по крайней мере одно решение - пару оптимальных стратегий, в общем случае смешанных и соответствующую цену
Пара оптимальных стратегий образующих решение игры, обладает следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Эта пара стратегий образует в игре некое положение равновесия: один игрок хочет обратить выигрыш в максимум, другой - в минймум, каждый тянет в свою сторону и, при разумном поведении обоих, устанавливается равновесие и устойчивый выигрыш v. Если то игра выгодна для нас, если - для противника; при игра «справедливая», одинаково выгодная для обоих участников.
Рассмотрим пример игры без седловой точки и приведем (без доказательства) ее решение. Игра состоит в следующем: два игрока А я В одновременно и не сговариваясь показывают один, два или три пальца. Выигрыш решает общее количество пальцев: если оно четное, выигрывает А и получает у В сумму, равную этому числу; если нечетное, то, наоборот, А платит В сумму, равную этому числу. Как поступать игрокам?
Составим матрицу игры. В одной партии у каждого игрока три стратегии: показать один, два или три пальца. Матрица 3х3 дана в таблице 26.5; в дополнительном правом столбце приведены минимумы строк, а в дополнительной нижней строке - максимумы столбцов.
Нижняя цена игры и соответствует стратегии Это значит, что при разумном, осторожном поведении, мы гарантируем, что не проиграем больше, чем 3. Слабое утешение, но все же лучше, чем, скажем, выигрыш - 5, встречающийся в некоторых клетках матрицы. Плохо нам, игроку Л... Но утешимся: положение противника, кажется, еще хуже: нижняя цена игры при. разумном поведении он отдаст нам минимум 4.