Смешанные стратегии. Основная теорема теории игр

Целесообразность случайного выбора стратегии в игре без седловой точки

 

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

 


 

Вернемся к примеру 2:

 

Bj Ai B1 B2 B3 минимум в строках αi  
A1 –3 –3 максимин
A2 –3 –5 –5  
A3 –5 –5  
максимум в столбцах βj    
  минимакс      

 

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

 

Однако выше было показано, что при наличии информации о том, какую стратегию выберет противник В (например, мы видим, что противник все время выбирает одну и ту же минимаксную стратегию), мы можем отклониться от нашей максиминной стратегии и получить больший выигрыш. Иначе говоря, в отличие от игр с седловой точкой, в данной игре отклоняться от оптимальной чистой стратегии может быть выгодно.

 

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

 

 

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

 

Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, как поведет себя противник в данной партии. Такая тактика (правда, обычно безо всяких математических обоснований) часто применяется в карточных играх. Заметим при этом, что лучший способ скрыть от противника свое поведение – это придать ему случайный характер и, значит, самому не знать заранее, как ты поступишь.

 

Введем обозначения для смешанных стратегий. Пусть у нас (игрока A) имеется m возможных стратегий A1, A2, …, Am, а у противника (игрока B) – n возможных стратегий B1, B2, …, Bn. Будем обозначать

 

 

 

нашу смешанную стратегию, в которой стратегии A1, A2, …, Am применяются с вероятностями p1, p2, …, pm, причем p1 + p2 + … + pm = 1.

Аналогичное обозначение для смешанной стратегии противника будет

 

 

 

где q1 + q2 + … + qn = 1.

 

Очевидно, что чистая стратегия – это частный случай смешанной стратегии, при которой все стратегии, кроме данной, имеют вероятности, равные нулю, а данная стратегия – единице.

 

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

 

Пара оптимальных стратегий образует в игре некое положение равновесия: мы хотим обратить наш выигрыш в максимум, противник – в минимум, каждый тянет в свою сторону и, при разумном поведении обоих, устанавливается равновесие и устойчивый выигрыш ν. Если ν > 0, то игра выгодна для нас, если ν < 0 – для противника; при ν = 0 игра «справедливая», одинаково выгодная для обоих участников.

 

Выигрыш, соответствующий решению, называется ценой игрыν (обозначаетсякак раньше обозначали чистую цену игры). Цена игры всегда ν лежит между нижней α и верхней β ценой игры:

 

α ≤ ν ≤ β.

 

Игры с седловой точкой также подчиняются основной теореме теории игр и являются ее частным случаем. Поэтому можно сформулировать общее правило:

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

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

 

Решение игры с седловой точкой в чистых стратегиях находится очень просто – по матрице игры с использованием принципа минимакса.

 

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